Re: [RRG] Re: Fast and sparse mapping?

[Brian E Carpenter <brian.e.carpenter@gmail.com>]

Hi Marshall,

Well, if there is some number like 2^23 or 2^27 of prefixes active
in a 64-bit prefix space, and they don't aggregate, that seems sparse
in exactly the sense of a sparse matrix. I'm not suggesting this is
fundamentally different (except in scale) from today's BGP4 situation
of something like 2^18 prefixes active in a 32-bit space.

I'm not aware of any solutions other than TCAMs or Patricia tries
for fast lookups in such a space, whether it's for mapping or
for forwarding.

   Brian

On 2008-09-21 14:54, Marshall Eubanks wrote:
> Dear Brian;
> 
> When I hear "sparse" I think of sparse matrix techniques (which I don't
> think could apply here)
> or sparse message passing techniques (see, e.g.,
> http://www.cs.umass.edu/~culotta/pubs/culotta07sparse.pdf ),
> which might.
> 
> Are you implying that such methods might be useful in routing in a
> "flat" internet ?
> 
> Regards
> Marshall
> 
> 
> On Sep 20, 2008, at 10:08 PM, Brian E Carpenter wrote:
> 
>> On 2008-09-20 04:53, Scott Brim wrote:
>>> On 9/18/08 5:33 PM, Brian E Carpenter allegedly wrote:
>>>>> Do you really mean that?  Are you really suggesting that we
>>>>> engineer routing
>>>>> for 2^48 prefixes?
>>>> No. I still believe that the natural limit is somewhere around 10
>>>> million
>>>> PI prefixes, or just conceivably 100 million, so my target range is
>>>> 2^23 to 2^27.
>>>
>>> How is this a 'natural limit'?  Could you review how you got there?  My
>>> totally casual estimate is that 2^27 is reasonable but that we had
>>> better engineer for 2^30.
>>
>> 10 million is my rough estimate for the number of medium-sized and larger
>> businesses that would exist in a fully developed world of 10 billion
>> people (i.e. one such business per thousand people). 100 million
>> is an upper limit - one multihomed network per hundred people - at
>> that level even the dentist's offices are multihomed.
>>
>> I don't think we need to design for a world where most domestic
>> subscribers
>> are multihomed, or care in the least if they get a new IP address
>> each time they connect.
>>
>>    Brian
>>
>> -- 
>> to unsubscribe send a message to rrg-request@psg.com with the
>> word 'unsubscribe' in a single line as the message text body.
>> archive: <http://psg.com/lists/rrg/> & ftp://psg.com/pub/lists/rrg
> 
> 

--
to unsubscribe send a message to rrg-request@psg.com with the
word 'unsubscribe' in a single line as the message text body.
archive: <http://psg.com/lists/rrg/> & ftp://psg.com/pub/lists/rrg