In einer eMail vom 02.03.2010 13:19:47 Westeuropäische Normalzeit schreibt

Hello  Heiner,

Here are some data bits from the compact routing  view:

Shortest path routing is incompressible (lower = upper bound):  Omega(n
log n).

There are a set of compact routing universal algorithms  that
"compresses" routing table to O(n^1/2) (upper bound) with the cost  of
increasing the worst case stretch to 3 [1,2] . 
Yuk. I am in favor of inflating (rather than  compressing) the (TARA-) 
routing tables (with multiple spares) so that next  hop lookup can be done by 
either one or three table offsets.
Wrt  stretch: This term makes only sense, if your solution has to live  
with stretch 3  and might be happy by avoiding stretch 17.  But  we should 
definitely shoot for stretch 1, i.e. have  a lot of  shortest paths and ,yes, 
also a plenty of detours. 

Universal in this context
means that nothing is assumed about  the graph topology. If you can
assume, such as power law distribution for  the Internet there are a
scheme offering routing table scaling of O[(log  n)^2][3]. (here log is
log base 2).

All of them reduce the routing  table size as you can see.
See above. I can afford to inflate them.

Now, would these schemes be applied to the core BGP to  reduce the table
size. I do not think so. That's because the BGP works, and  fixing
something that works is not practical at least cost wise. But  these
schemes could be used for to limit the growth in the routing system  that
routes based on the end point identities. Please see my proposal on  that
part, if you care.

It is not only TARA, but with TARA and with quite a few more routing  
algorithms, routing technology can soar to a new level of  perfection. A  whole 
generation of young students could spin the wheel of progress for  some 
decades just as "we" did, based on the current but awfully  bad  paradigms, for 
quite a while.

By the  way, I would be very much interested to read the TARA
specification that  you have been referring several years already.

Best regards

[1]      Krioukov D., kc claffy, K. Fall, and A. Brady. On compact
for  the Internet. ACM SIGCOMM Computer Communication
Review (CCR), 37(3),  2007.

[2] I. Abraham, C. Gavoille, A. Goldberg, D. Malkhi. "Routing  in
Networks with Low Doubling Dimensions", Proceedings of the 26th  IEEE
International Conference on Distributed Computing Systems, p.75,  July
04-07, 2006  

[3] S. Carmi, R. Cohen, and D. Dolev.  "Searching complex networks
efficiently with minimal information".  Europhysics Letters, 74(6), 2006.

>-----Original  Message-----
>From: []  On 
>Behalf Of ext Brian E Carpenter
>Sent: Tuesday, March 02,  2010 02:06
>Subject: Re: [rrg]  draft-narten-radir-problem-statement-05.txt
>On 2010-03-02  12:36, wrote:
>> Statement:   Neither LISP nor any of all the other submitted  
>> do reduce the number of routes
>> - not even by the  number 1.
>IMHO the issue is not to reduce the number of routes  but to 
>limit their growth. At the moment they seem to be limited  
>loosely like the square root of the size of the Internet, and  
>our goal is presumably to limit them more strongly than that  
>-- log(N) would be lovely.
>There is a lot of  speculation in this, but since the pressure 
>towards route  de-aggregation seems to come mainly from PI 
>addressing and the demand  for multihoming, a solution that 
>enables PA aggregation seems certain  to limit growth, compared 
>to doing nothing. There are a number of  solutions in the list 
>that appear to do this.
>    Brian
>rrg  mailing  list

rrg mailing list

Reply via email to