In message <3ABAB306.4E38D7BD@packetdesign.com>, Van Jacobson writes:
> There's a paper in this year's Infocom that manages to prove MPLS is
> unnecessary for traffic engineering. It shows that for *any* set of
> LSPs, it is possible to compute a set of routing link metrics that
> result in exactly the same traffic flow. This is slightly surprising
> since for N nodes there are typically O(N^2) LSPs but only O(N) links so
> there's a huge difference in information content between the two
> approaches. But their development shows that the problem is so
> conditioned by flow balance contraints (ie., all the flow that enters a
> node must leave it) that O(N) parameters (the link metrics) are
> sufficient to completely specify the solution.
>
> If anyone's interested, the paper is available at:
> http://infocom.ucsd.edu/papers/744-2798113708.pdf
>
> - Van
Van,
Before you get too excited about this technique you should give it
some sanity checking.
Many simple topologies cannot be optimized by setting IGP metrics but
can easily be optimized using MPLS. For example:
C E
/ \ /
A---B---D--F
The largest traffic contributors are A-E and A-F. The bottlenecks are
B-C or B-D where the available capacity of B-C and B-D are unequal and
the flows A-E and A-F are unequal. It is easy to pick values that
where neither ECMP or putting all of the flows on one leg would do as
well as a traffic engineered solution.
The above example of large flow (B->D) that is unevenly divisible as a
result of having multiple endpoints (A->B->D->{E,F}) and having
multiple paths (B-C-D or B-D) often occurs as a subset of the topology
within a provider.
The big caveat in the paper is (in the authors terminology but
paraphrased), the approach doesn't work for loopy topologies for some
values of "work".
On the other hand, since f P^k : k K_g is loopy, there exists an
improved set of routes f Q^k : k K_g which uses no more bandwidth
than f P^k : k K_g ...
I think the key is that the cirteria is that if all the traffic A-E
and A-F went by way of B-D, it would use no more bandwidth than if
some traffic took B-C-D and some took B-D. The fact that B-D may not
have enough bandwidth to support this flow is not considered as a
constraint. Some people would consider that a failure to produce a
usable result but that type of constraint is not considered.
If you accept my notion of an algorithm that "works" (meets
constraints imposed by the topology without moving capacity to other
links) and toss out the math in pages 5-7 they say little more than
sometimes it works (shortest-path-reproducible) and sometimes it
doesn't (non-shortest-path-reproducible).
If you have plenty of capacity everywhere you fail the Vijay Gill
criteria "You must have traffic to need traffic engineering" which
could have been said with a lot less math.
Curtis
This archive was generated by hypermail 2b29 : Mon Aug 04 2003 - 04:10:03 EDT