North American Network Operators Group
Date Prev  Date Next 
Date Index 
Thread Index 
Author Index 
Historical
RE: Traffic engineering tools
 From: Vadim Antonov
 Date: Fri Oct 22 19:25:41 1999
> First of all, a multicommodity flow problem is not NPcomplete
> 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.
My friend prof. Plotkin says greedy algorithms were shown to produce
horrible results in pretty trivial topologies.
(He is the authority in MCF problems, btw).
In any case, doing MCF computations in realtime is out of question even
with simplistic approaches. Do it at a rate of 500 times a second 
that's what you need to deal with reallife bursts of routing updates.
> It is **so** easy to label a problem NP complete these days.
It is so easy to miss pretty trivial solutions to problems deemed
complicated. The goal of a scientist is to find an interesting problem,
and live off it for a while. The goal of an engineer is to evade
interesting problems :)
In fact, Pluris boxes by the virtue of doing the loadsharing trick allow
traffic to be treated exactly like liquid flow  thus making the traffic
engineering problem trivial. The onerouterperPOP ideology also allows
to satisfy acyclicity criteria for loadshared destinationaddress forwarding,
making label switching and associated complexity simply unnecessary.
vadim
(who believes in KISS principle)
