Subject: Re: Equal-cost path

From: "Naidu, Venkata" <[email-masked]>
Date: Wed, 13 Apr 2005 15:40:06 -0400

-> >  If we assuming all nodes in an area have same
-> >  capabilities (like, line rate forwarding etc), fewer number
-> >  node path performs better in the average case.
-> >
-> 
-> I do not believe that you can make this claim, except in a 
-> simulation, which has little to do with reality.

 I don't think so...[please read on]
 
-> In real networks, with reasonably fast routers and links, the 
-> performance of the routers and per-link serialization are greatly 
-> overwhelmed by other issues (such as the speed of light and queue 
-> lengths.)

 That is why I said, "in the average case", where the assumption
 is all the routers in an area have equal capabilities. In such a
 a case, simple queuing theory would suffice to prove that 
 shorter paths minimizes delay (if link costs are all same).

 Practically, any service provider buying bunch of routers, never
 going mix routers from different providers in an IGP area. Simply,
 can't justify for non-technical reasons. The assumption that
 an IGP area has equal capable routers is a valid assumption.
 If not, why don't we have a router metric in Router LSA ?

-> One could just as plausibly posit that, on average, a random 
-> assignment 
-> in the case of equal path costs could improve performance by 
-> spreading 
-> the load more effectively across the infrastructure, but it totally 
-> depends on the particulars of equipment, topology, and traffic.
 
 Most of the cases, a deterministic algorithm performs better than
 non-deterministic algorithm. Randomized selections of equal-cost
 paths can bring instability. 
 
 Take this for example: If IGP is flapping between equal-cost paths 
 in a non-deterministic manner would increase out-of-order IP packets. 
 This makes overhead for higher layers waiting for all IP datagrams
 to make out a transport packet. It is always better to send all IP
 datagrams of an application packet on a single deterministic path.
 
 That said, non-determinism and randomized algorithms are good for 
 proving theorems like probabilistic checkable proofs etc.
 
Venkat.

---

From: Dave Katz <[email-masked]>
Date: Wed, 13 Apr 2005 14:05:36 -0700

>  shorter paths minimizes delay (if link costs are all same).

There is no "average case" in reality.  It's totally nonpredictive.  
Real networks and routers don't follow simple queuing theory either;  
their behaviors are dominated by the particulars of implementation.  I 
don't build theoretical, average equipment;  I build real equipment 
that runs in real networks.

>  can't justify for non-technical reasons.

Another nice theory with absolutely no grounding in reality.  This is 
demonstrably not true in very many networks, and likely is not true in 
almost all large ISPs (or my current employer would have never gotten 
off the ground, and the world would have been even more dominated by my 
previous employer.)  Multivendor networks are extremely common.

>  The assumption that

It's not a valid assumption;  I think you'll find very few networks in 
which all routers are identical.  Even single-vendor networks have 
multiple models of routers with different capabilities.

There's no metric in the router LSA because it was deemed unimportant 
even in 1988, and is arguably even less important now due to the 
negligible impact of the routers relative to the links, though trying 
to claim *anything* based on design decisions made by committee during 
the Reagan administration is silly.

>  datagrams of an application packet on a single deterministic path.

I did not make myself sufficiently clear.  I was not suggesting 
choosing random paths per packet, but rather per-route (or even 
per-flow.)  Even with multiple next hops, most routers default to a 
behavior in which subsets of the traffic (based on flow, if possible) 
are bound to particular, single next hops.  The traffic for a single 
flow follows a particular single path, and the flows are spread across 
the multiple paths.  This simultaneously avoids packet reordering while 
providing predictable paths and good resource utilization.

--Dave