Curtis,
Thanks for your comment on our paper "IP traffic engineering without full
mesh overlaying".
I could not respond sooner because I was not on the mailing list and was not
aware of the
discussion until a colleague of mine forwarded me your email.
Our work is basically a theoretical result with an attemp to find some
practical applications.
I agree that it is too early to say how ready or how ususful it can be for
real world networks.
I am aware of some of its limitations. One of them is that it sometimes
needs to split traffic
unequally between two or more equal weight shortest paths in order to
achieve the optimal
traffic engineering which is doable by MPLS (uneqal split between two LSPs
between the same
source-destination) but for some reason difficult to do by OSPF at present
time. Another is that
we may be able to set appropriate link weights to optimize the long term
network performance in the
statistical sense, but we don't want to change link weights dynamically
reacting to traffic
fluctuations in real time. I welcome critics or sugegstions to make it more
practical.
But unfortunately I do want to clarify that your specific comments in the
included message
are not valid due to a misunderstanding of a definition used in the paper
called "loopy routig".
First, loopy is a property of routing, not topology. Actually it is a
property collectively
formed by a set of routes. Therefore it is different from the conventional
routing loops which
talks about a single route. Second, link bandwidth constraint is well taken
care of. In the
definition given in the paper, a set of routes P is said loopy if there
exists a better set of
routes Q which consumes less bandwidth than P not only overall, but also
uses less or equal
bandwidth than P on EVERY link. As a result, if P satisfies link capacity
constraint, Q must
satisfy as well since Q uses no more capacity than P on every link. And Q
can be reproduced
as shortest path routing. Intuitively speaking, loopy routing is something
stupid (with obvious
deficiencies) which can be improved on every account.
For your specific example, the traffic split between B-D and B-C-D due to
limited capacity
of B-D is not a "loopy routing" at all. It is a reasonable thing to do, and
it can well
be reproduced as shortest path routing. As a matter of fact, if we simply
set weight of 2 for
link B-D and weight of 1 for both link B-C and link C-D, then both B-D and
B-C-D are always
on the shortest paths regardless of weights of other links and traffic. At
point B the traffic
destined to D,E,F will be split in proportion to the capacities of B-D and
B-C-D. In other words,
if B-D and B-C-D have equal capacity, then traffic will be split 50%-50%. If
the capacity ratio
is 1 to 3, the traffic will be split according to the ratio of 1 to 3 as
well.
I encourage you to send me any more specific traffic engineering examples
which you suspect
IGP metric setting method cannot handle as well as MPLS LSPs and I will find
the link weights
for you. What we have proved mathematically is that the shortest path
routing can match any
MPLS traffic engineering design, exactly.
Yufei
-----Original Message-----
From: Xipeng Xiao [mailto:xiaoxipe@cse.msu.edu]
Sent: Monday, May 07, 2001 5:48 PM
To: ywang@photuris.com
Cc: Xipeng Xiao; Xipeng
Subject: Re: interesting Infocom paper on traffic engineering via
routing metrics
YuFei,
I assume you are aware of this discussion. What's your comments
on Curtis's comments?
Thanks,
XiPeng
> -----Original Message-----
> From: Curtis Villamizar [mailto:curtis@workhorse.fictitious.org]
> Sent: Monday, March 26, 2001 1:49 PM
> To: Van Jacobson
> Cc: irtf-rr@puck.nether.net
> Subject: Re: interesting Infocom paper on traffic engineering via
> routing metrics
>
>
>
> 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