Subject: Re: [rrg] draft-narten-radir-problem-statement-05.txt

From: [email-masked]
Date: Mon, 1 Mar 2010 18:36:28 EST

In einer eMail vom 25.02.2010 22:23:17 Westeuropäische Normalzeit schreibt  
[email-masked]:

My  conclusion is that we can hope for 1 million routes but
should have a  solution for 10 million. I don't think there is
anything in the data or  technology that tells us we will
need a solution for 100 million or  more.

Statement:  Neither LISP nor any of all the other submitted  solutions do 
reduce the number of routes
- not even by the number 1.
 
I would appreciate either being confirmed or being taught that this is not  
correct.
 
Heiner

---

From: Brian E Carpenter <[email-masked]>
Date: Tue, 02 Mar 2010 13:05:47 +1300

On 2010-03-02 12:36, [email-masked] wrote:
...
> - 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

---

From: "Flinck, Hannu (NSN - FI/Espoo)" <[email-masked]>
Date: Tue, 2 Mar 2010 14:19:38 +0200

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] . 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.

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.

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

Best regards
Hannu

[1] 	Krioukov D., kc claffy, K. Fall, and A. Brady. On compact
routing
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: [email-masked] [mailto:[email-masked]] On 
>Behalf Of ext Brian E Carpenter
>Sent: Tuesday, March 02, 2010 02:06
>To: [email-masked]
>Cc: [email-masked]; [email-masked]
>Subject: Re: [rrg] draft-narten-radir-problem-statement-05.txt
>
>> Statement:  Neither LISP nor any of all the other submitted  
>solutions 
>> do reduce the number of routes
>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
>[email-masked]
>http://www.irtf.org/mailman/listinfo/rrg
>