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.

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 :slight_smile:

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)

As for me, I hardly believe to the pre-computed pathes; it seems to be
more easy to build some kind of self-loaded system, which can adapt
dynamically to the existing data flows. Such system should take a time to
establish the optimal data flows, and always have a chance to began some
kind of oscillations, but I don't think it's a hard problem - many years
such analog systems was used for the different purposes...

I mean some kind of (dynamically increase the cost of the loaded links,
decrease the cost of non-loaded pathes, re-calculate the balancing,
etc)... No one can predict the data pathes in the really big ISP, and it
was not proven the advantage of the statically calculated data pathes to
the dynamically established. The whole nature (including the homo
sapience) are build of the dynamically-balances systems, and it works
pretty well.

That's why the ideas of the statically calculated pathes don't seems to be
an excellent; it has it's own scope of useness, but we should not restrict
the solutions by such systems only.

Alex.

> 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 :slight_smile:

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)

Aleksei Roudnev, Network Operations Center, Relcom, Moscow
(+7 095) 194-19-95 (Network Operations Center Hot Line),(+7 095) 230-41-41, N 13729 (pager)
(+7 095) 196-72-12 (Support), (+7 095) 194-33-28 (Fax)

Alex,

You are absolutely correct. A critically damped, dynamic traffic engineering system would
provide benefits above and beyond that which can be derived in a static system.

However, the dynamic system is non-trivial to construct. As has been shown with routing
protocols that react to dynamic changes, it is very easy to underdamp the system, with
catastrophic results.

I certainly believe that such dynamic systems are possible, and certainly folks with enough
background in control theory could contribute wonderfully here. However, the state of the art
isn't quite there yet. Sigh.

                            "And that's the way it is..."
                                                    - Walter Cronkite

Tony

"Alex P. Rudnev" wrote: