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

From: Robin Whittle <[email-masked]>
Date: Thu, 19 Jul 2007 22:21:43 +1000

If someone can help me with a few questions, I would really
appreciate it.  One concerns IPv6 BGP practice and the other how
Tree-Bitmap FIBs work with long prefixes.

When I look at the table "Root Prefix Length Distributions":

  http://bgp.potaroo.net/v6/as1221/

(not the first table which precedes it "Prefix Length
Distributions") I see a bunch of prefix lengths which I assume are
those advertised globally:

  /19     2
  ...
  /32	617
  /33	  4 	
  /34	  1 	
  /35	 18 	
  /48	 60 	

Is there some formal or informal agreement not to accept
advertisements for prefixes longer than /48?  I know
there is such a rule for IPv4 (/24) but am not sure if it is
formalised anywhere.

If so, then when an end-user gets a /48 of PI space, as per ARIN
or AfriNIC policies:

  http://www.arin.net/policy/nrpm.html#six58
  http://www.afrinic.net/Registration/afsup-ipv6pi-assignments.htm

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

I also want to confirm or improve my understanding of how
ASIC-based FIBs (rather than those which use TCAM) actually cope
with classifying packets which match really long rules.

I understand that the CRS-1 uses the Tree Bitmap algorithm:

  http://www.firstpr.com.au/ip/sram-ip-forwarding/#Vargese_CRS_1

I have the final 2004 paper if anyone wants a copy.  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).

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.

For a /48 rule, it seems that with a 6 bit stride, the number of
memory accesses goes up to 7 or so.   This is a really ugly amount
of DRAM cycles to classify each packet passing through a transit
router.  Maybe on-chip caches could help, but I can't imagine how.

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.

  - Robin

_______________________________________________
RAM mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/ram

---

From: Jeroen Massar <[email-masked]>
Date: Thu, 19 Jul 2007 13:49:43 +0100

Robin Whittle wrote:
[..]
> there is such a rule for IPv4 (/24) but am not sure if it is

Yes there is. In general a /48 is seen as 'the smallest chunk of
globally routeable address space'.

Most ISP's and transits follow Gert Doerings filter recommendations:
http://www.space.net/~gert/RIPE/ipv6-filters.html

I suggest that in addition to the above excellent site, take a peek at
http://www.sixxs.net/tools/grh/ as that has a somewhat more complete
view of the IPv6 DFZ getting quite a few feeds from global providers. It
also has a few other tools that give you different abilities. Oh and not
to forget of course that RIPE has the great RIS system
(http://ris.ripe.net) which gives yet another view on all of this.
Depending on what you are looking for, one of those 3 tools can provide
you with the angle you need.

GRH shows that there are even /64's being announced successfully, though
they don't reach to all ISP's.

> providers.

They indeed can't as it will be filtered. The whole idea of IPv6 is
aggregation after all.

This is indeed unfortunate as when one wants to do anycast, as for a few
hosts one ends up abusing a /48.

The other problem is indeed when you have a couple of offices or if you
have a number of hosting sites, each needs it's own /48.

> This would mean the end-user needs a separate /48 for

Separately physical offices are in effect sites, so that is not an issue
at least RIR wise, but one will have to justify that to the RIR. The
issue though are the RIR policies and the force that is applied to it.

Traffic Engineering, BGP and IPv6 in one sentence with a 'small DFZ'
doesn't work unfortunately and this is currently also one of the
deployment problems for IPv6. All the policies are made for ISP's, even
the ARIN PI ones. They expect 1 prefix to be put into a routing slot in
the DFZ, but in effect if you have a /32 you will want to break that up
and not get all the traffic to your main site and then have to reroute
it to another site. With a /32 or up you can break it into /48s most of
the time though and with a /20 you can add a lot of /32's with ease as
those will never be filtered. The RIR game thus seems to be to get a
huge prefix as then you can split it, or go RIR shopping and get one or
multiple prefixes from every RIR (See GRH's DFP pages on that and you
will soon spot who is doing that :).

For Traffic Engineering and other purposes we really will either have to:
 - simply accept that there will be lot of /48's and /64's in the DFZ
or:
 - really quickly come up with an ID/LOC solution that is deployed
   globally.

Greets,
 Jeroen

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Thu, 19 Jul 2007 18:11:48 +0200

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

> 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

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

> offices in different cities or countries which use different

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

> each physical office in a different city or country.  Can someone

As opposed to which situation?

> In this

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.

> RAM table for the next 11 bits and then the last 18 bits as a 3 *

Just 6 bits?

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

---

From: Robin Whittle <[email-masked]>
Date: Fri, 20 Jul 2007 12:20:07 +1000

Thanks Jeroen and Iljitsch for your helpful responses regarding
IPv6 prefix lengths.

I got rather lost in the Ghost Route Hunter pages, but I didn't
have time to try to fully understand them.

Thanks for answering my questions about /48s and for pointing me
to the guidelines which some or many people follow - Gert
Doering's page:

As noted in that page, the rules there are not fully updated to
recent developments, such as:

 ipv6 prefix-list ipv6-ebgp-strict permit 2620::/23 ge 24 le 32

 route-filter 2620::/23 prefix-length-range /24-/32;

which should end in "48" to reflect the fact that this prefix is
where ARIN is assigning /48s to AS-end-users.  A few of these are
listed in the May 2007 report (page 19):

 http://www.space.net/~gert/RIPE/R54-v6-table.pdf

There are a regular series of such reports in that directory.

I wrote to Gert Doering about this initially, not realising he was
in fact the person who maintains these guidelines.

I often wondered whether there was a formal arrangement for the
way most networks (or at least sufficient networks to affect
global reachability) filter BGP advertisements based on their
length.  Gert's guidelines above are the closest it comes to a
recognised agreement - which is not very formal.  The length limit
varies according to which part of the address space it is for.
For instance, in areas where /32s are assigned, the rules reject
advertisements for prefixes longer than /32.

Gert also told me there is no formal agreement about the widely
accepted practice of refusing to accept advertisements for IPv4
prefixes longer than /24:  He wrote:

> For IPv4, there are a number of large providers that do not
> accept prefixes longer than /24, and thus, have made it a
> de-facto rule - but it's not written into any sort of "Internet
> book of rules" anywhere that this must be so.

He also wrote:

> For IPv6, people still very much disagree on what they want to
> see in the global BGP table - some just announce /64s, others
> filter everything that is more specific than a /32, except for
> well-known exceptions like the ARIN PI range, where it's known
> that the allocation is done in /48 chunks.

He said that /48s shouldn't be split and that there should be a
/48 for each "site".  However, from the point of view of keeping
the global IPv6 BGP routing table small, ideally these sites would
just get one or more /48s of PA space from their local provider.
(But this doesn't provide portability or traditional network-wide
multihoming.)

Iljitsch, you wrote, in part:

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

OK - but I think that a simple array for the first "stride" of 24
bits wouldn't fit into on-chip RAM of any ASIC such as Cisco's
SPP, unless there was on-chip code to do a second lookup for that
smaller subset of the address range, which sounds feasible.

>> /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 was going by the suggested hardware implementation from the 2004
paper - but I guess in high-powered implementations such as
Cisco's SPP in the CRS-1, they may have enough RAM to do more bits
per stride.  I don't fully understand Tree-Bitmap, but perhaps
there is some problem with larger strides than 6, something to do
with the memory system not being wide enough to read in a single
clock cycle all the data they need for the various things which
could happen next.

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

Yes.  Although the train is just pushing off from the station, the
seeds of it tumbling into the ravine at full speed five or ten
years from now are clearly apparent.

I suggested in a now largely defunct I-D:

  http://www.firstpr.com.au/ip/sram-ip-forwarding/

that before the train moves any more from the station, that there
be an agreement to assign PI address space in a particular area,
such as a /10, in a way that this could be easily handled by a
single memory access FIB system.  (Section 6.3 in the above I-D,
although I explain it there in terms of specific fast SRAM chips,
rather than what I would write now: as an array in the DRAM of an
existing ASIC-based FIB system.)

Then, for instance, 32 million /35s could be mapped into that
area.  The idea is that future routers (by the time the IPv6
global routing table starts to become painfully large) will be
equipped to do single external memory cycle classification of all
packets in this /10, on the assumption that there is no rule with
a longer prefix than /35.

This gives rise to a completely different approach to assigning
this address space to end-users.  Give each end-user one or more
(on some reasonable basis - they need to justify it) /35s,
starting at the bottom of this /10.  Just fill it up from one end
to the other.  That is 32 million end-user prefixes, with each
able to be advertised in any provider network, because we don't
care about route aggregation - because we have a RAM-lookup FIB.

By the time this process reaches the end of the /10, routers will
have more RAM and allocation will continue on the next /10 above
the first one.

The trouble with this idea is that it solves the FIB problem
beautifully, in a way which only makes sense if the BGP control
plane could handle millions of routes.

Maybe some scheme such as this should be kept in mind, for a
future situation where BGP or some new system can cope with such a
large number of routes.

 - Robin

---

From: Per Heldal <[email-masked]>
Date: Fri, 20 Jul 2007 10:21:21 +0200

>   http://www.space.net/~gert/RIPE/ipv6-filters.html

In the absence of scalable IDR and route-certificates you'll also find
people using more strict filters in an attempt to achieve operational
stability. Such filters aim to keep the maximum numbers of prefixes
within the capacity of available hardware. Thus, if a registry allocates
blocks out of e.g. a /23 only a small fraction of that /23 may initially
be accepted, especially if it is used for PI /48s. The current v6
routing-table may be small, but I'm sure attitudes will change as more
people realise the potential impact on their infrastructure as it
becomes increasingly common to operate dual-stack networks.

A practical approach to the process of building v6 filters would be:

1. Look at IANA's assignments to RIRs

2. Examine policies for each block to check if they are sub-divided into
smaller blocks with individual allocation policies.

3. Obtain prefix-length-recommendations from the RIRs' routing policies
for each address-block.

4. Examine (download&process) the records of the RIR's allocations to
LIRs and end-users to determine the last allocation (highest number) in
each block.  

This, combined with a wish to allow some extra prefix-bits for shorter
AS-paths (traffic-engineering) defines a "baseline" for prefix-filters.
Note: It's not unusual to use a similar approach for ipv4 -- either for
operational filters or in tools used to analyse various aspects of the
DFZ. 

(The task would of course be much simpler if this information was
available in a consistent/unified/standardised format from all parties
involved ;))

//per

---

From: Brian E Carpenter <[email-masked]>
Date: Sun, 22 Jul 2007 18:19:58 +0200

> becomes increasingly common to operate dual-stack networks.

Exactly, and a DFZ with ten million /48s seems to be an unlikely
end-point, which is why we are here, I thought.

    Brian