Re: [RAM] IPv6 /32 to /48 prefixes and Tree-Bitmap FIB speed

[Iljitsch van Beijnum <iljitsch at muada.com>]

On 19-jul-2007, at 14:21, Robin Whittle wrote:

> If someone can help me with a few questions, I would really
> Is there some formal or informal agreement not to accept
> advertisements for prefixes longer than /48?

There are currently 8 prefixes between /35 and /48 given out (not  
inclusive), 215 /48 and 6 /64. So I'd say that /48 is the new /24.  
However, don't forget that you need to carry more specifics  
internally, which could easily be very large numbers of customer / 
56s. I'm assuming internal aggregation will keep the number of /64s  
in check.

> I know
> there is such a rule for IPv4 (/24) but am not sure if it is
> formalised anywhere.

It isn't, and in IPv6 things are still up in the air to a large degree.

> I guess this means they can't split this prefix, for instance for
> load balancing in a multihomed situation or for using with two
> offices in different cities or countries which use different
> providers.

They'll try, but there's a good chance it won't work well enough to  
depend on it.

> This would mean the end-user needs a separate /48 for
> each physical office in a different city or country.  Can someone
> confirm this?

As opposed to which situation?

> In this
> paper, the hardware reference design deals with the most
> significant 8 bits of address in an on-chip RAM lookup table
> (actually a 12 bit index).  Then the rest of the address bits are
> processed 6 at a time (stride of 6, in Figure 12).

In IPv4 there is a good distribution over the first 8 bits but in  
IPv6 there isn't, lots of stuff is still in 2001::/16. I think you  
need to look at the first 24 bits or so if you want to do the same here.

> I recognise that the actual CRS-1 algorithm may differ somewhat
> from this, but still, it seems that to match a packet against a
> /32 rule will probably take 4 external memory reads.  For instance
> ignore the first 3 bits which are always 001, then use an internal
> RAM table for the next 11 bits and then the last 18 bits as a 3 *
> 6 bit stride.

Just 6 bits?

> I find it impossible to think happily of such cumbersome
> techniques, but as far as I know, strides beyond 6 bits have
> various problems.  Even if the stride was 12 bits, it would still
> be 3 or 4 memory accesses per packet.

> Is the future really this grim?  TCAMs are fast but power-hungry
> and a can of worms in other respects, such as worst-case update
> time.  The fact that Juniper and Cisco use trie-based techniques
> indicates that TCAMs can't do the job - but these trie-based
> approaches seem to be so slow.

You can shuffle the bits a bit first so you start looking at the  
important ones and not the ones that are the same for all addresses  
first. Or do a hash-based system.

It would also help to optimize the address assignment policies. For  
instance, leaving 7 /48s unused between two ones that are used so  
there is room for growth is really suboptimal here. Being able to see  
whether an address will match /32 or shorter or whether it will have  
to match a /48 could also be helpful.

_______________________________________________
RAM mailing list
RAM at iab.org
https://www1.ietf.org/mailman/listinfo/ram