North American Network Operators Group Date Prev | Date Next | Date Index | Thread Index | Author Index | Historical RE: Traffic engineering tools
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:[email protected]] Sent: Friday, October 22, 1999 2:01 PM To: [email protected] Subject: RE: Traffic engineering tools > Date: Thu, 21 Oct 1999 20:49:07 -0700 > From: Bora Akyol <[email protected]> > 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...
|