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 [EMAIL PROTECTED] 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 PROTECTED] 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
