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

[Steven Blake <slblake@petri-meat.com>]

On Sun, 2008-09-21 at 15:52 +1200, Brian E Carpenter wrote:

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

It wouldn't hurt if the vast majority of those prefixes were the same
length (say /48).  There are max-two memory access schemes for fixed
length keys.


Regards,

// Steve


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