Merit Network
Can't find what you're looking for? Search the Mail Archives.
  About Merit   Services   Network   Resources & Support   Network Research   News   Events   Home

Discussion Communities: Merit Network Email List Archives

North American Network Operators Group

Date Prev | Date Next | Date Index | Thread Index | Author Index | Historical

RE: Traffic engineering tools

  • From: Bora Akyol
  • Date: Fri Oct 22 18:04:47 1999


First of all, a multicommodity flow problem is not NP-complete
provided that the individual flows are an order of magnitude or so
smaller than the link capacities so that you can use a fluid approximation.
Moreover, you can come up with a heuristic that works pretty well. I believe
you
must have heard of greedy algorithms.


It is **so** easy to label a problem NP complete these days.

Bora

-----Original Message-----
From: Andrew Bender [mailto:abender@tns-inc.com]
Sent: Friday, October 22, 1999 2:01 PM
To: nanog@merit.edu
Subject: RE: Traffic engineering tools



> Date: Thu, 21 Oct 1999 20:49:07 -0700
> From: Bora Akyol <akyol@pluris.com>
> Subject: RE: Traffic engineering tools
> 
> If you don't want a GUI and the fancy what if scenarios, it is not
difficult
> to write
> a Perl/Script that does constraint-based routing or Multi-commodity flow
> problems.
> 
> I would guess 2-3 weeks if one is familiar with basic linear programming.
> 
> Bora

Release note:
NPcomplete.pl may also require 2-3 weeks to converge when
sub{optimum_backup_paths} is used. This may be due to a suspected
"suboptimality" in PDL::Opt::Simplex...

Application note:
"basic" as the term is used in the context of the phrase "basic linear
programming" seen in the marketing literature should be taken to mean "graph
or
subgraph of degree 1"

Regards,
Andrew Bender
Total Network Solutions, Inc.

P.S. Advance apologies for the (ostensibly excusable?) off topic cynicism...





Discussion Communities


About Merit | Services | Network | Resources & Support | Network Research
News | Events | Contact | Site Map | Merit Network Home


Merit Network, Inc.