nanog mailing list archives
RE: Traffic engineering tools
From: Vadim Antonov <avg () kotovnik com>
Date: Fri, 22 Oct 1999 16:23:41 -0700
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.
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 real-time 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 real-life 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 load-sharing trick allow traffic to be treated exactly like liquid flow - thus making the traffic engineering problem trivial. The one-router-per-POP ideology also allows to satisfy acyclicity criteria for load-shared destination-address forwarding, making label switching and associated complexity simply unnecessary. --vadim (who believes in KISS principle)
Current thread:
- Traffic engineering tools Sean Donelan (Oct 20)
- <Possible follow-ups>
- RE: Traffic engineering tools Bora Akyol (Oct 21)
- Re: Traffic engineering tools Sean Donelan (Oct 21)
- RE: Traffic engineering tools Bora Akyol (Oct 21)
- RE: Traffic engineering tools Patrick Greenwell (Oct 21)
- Re: Traffic engineering tools Prabhu Kavi (Oct 22)
- RE: Traffic engineering tools Patrick Greenwell (Oct 21)
- RE: Traffic engineering tools Andrew Bender (Oct 22)
- RE: Traffic engineering tools Bora Akyol (Oct 22)
- RE: Traffic engineering tools Vadim Antonov (Oct 22)
- RE: Traffic engineering tools Alex P. Rudnev (Oct 25)
- Re: Traffic engineering tools Tony Li (Oct 25)
- RE: Traffic engineering tools Alex P. Rudnev (Oct 25)
- Re: Traffic engineering tools Andrew Bender (Oct 26)
- Re: Traffic engineering tools Jerry Scharf (Oct 26)
- Re: Traffic engineering tools Jeremy Porter (Oct 26)
- Re: Traffic engineering tools Jerry Scharf (Oct 26)
- Re: Traffic engineering tools Vadim Antonov (Oct 26)
- Re: Traffic engineering tools John Patteson (Oct 27)
- Re: Traffic engineering tools Vadim Antonov (Oct 26)
- Re: Traffic engineering tools Prabhu Kavi (Oct 28)
- Re: Traffic engineering tools Alex P. Rudnev (Oct 28)
- Re: Traffic engineering tools Prabhu Kavi (Oct 28)
(Thread continues...)