[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [RRG] Re: Fast and sparse mapping?
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
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 ?
> 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
>>>> 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
>> are multihomed, or care in the least if they get a new IP address
>> each time they connect.
>> to unsubscribe send a message to firstname.lastname@example.org 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 email@example.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