[rrg] BGP scaling limit?

[HeinerHummel at aol.com]

In einer eMail vom 02.01.2009 01:34:12 Westeuropäische Normalzeit schreibt  
tony.li at tony.li:

ICBW,  but I think you're describing what's been called the "Memory 
|wall" by  Wulf & McKee:
|
|   http://www.cs.virginia.edu/papers/Hitting_Memory_Wall-wulf94.pdf
|
|and  see also:
|
|   http://www.csl.cornell.edu/~sam/papers/cf04.pdf


Thank you for the  excellent references, I think they're exactly on point.
Routing is simply  one of the applications that is going to hit the  memory
wall.



Thanks for these very interesting documents.It tells me: after the ignoring  
phase and now the rejection phase TARA will still get -within a decade- its  
chance. Not because of eliminating the update churn or the table size problem  
but for eliminating the need to cache at any  transit-router.
 
Ignoring phase:
I am still waiting for the promised detailed response by Lixia, or for  
Bill's explanation why a link-state protocol cannot express the same policy as a  
DV protocol, and -wrt to the above - I only got collective silence when I said  
in spite of 300 000 stored routes DV does only enable one third of them, ie 
that  twice the number cannot be provided.Very very rougly. Let me eloborate 
more  on this factor by the following example:
 
Imagine destination node d surrounded by a tightly meshed network such that  
each node has 6 neighbor nodes whereby 2 are closer, 2 are equidistant and 2 
are  more remote wrt to d. Now assume a source node s being 10 hops away from d 
and  let us consider the number of different paths (differing at least by one 
 hop):
Dijkstra provides 1 path. ECMP provides 2^10 paths (at least this is what I  
accredit to/expect from ECMP). My own algorithm provides 6^10 paths. This is 
not  just twice but 3^10 times  what can ECMP (and DV ?)provide. These are such 
 extremely big numbers that you don't want to store a single route of them,  
instead look for a more intelligent mechanism.Keep in mind the average path  
length is said to be 20, not 10.
 
Heiner
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.irtf.org/pipermail/rrg/attachments/20090102/d685e5a6/attachment.htm>