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)