Subject: IPv6 Packet Forwarding Algorithms

From: Dheeraj Singh <[email-masked]>
Date: Thu, 16 Feb 2006 22:34:45 -0800 (PST)

Hi,
  
  I am wondering, whether there is any algorithm for performing the IPv6 Lookup and forwarding table.
  Is there any work going on over this in any of the forum!!
  
  -Dheeraj

---------------------------------
 Yahoo! Mail
 Use Photomail to share photos without annoying attachments.

--------------------------------------------------------------------
IETF IPv6 working group mailing list
[email-masked]
Administrative Requests: https://www1.ietf.org/mailman/listinfo/ipv6
--------------------------------------------------------------------

---

From: Fred Baker <[email-masked]>
Date: Fri, 17 Feb 2006 13:24:14 -0800

> Is there any work going on over this in any of the forum!!

There are a bunch of papers on this in SIGCOMM and IEEE over the past  
15 years or so. One could use a patricia tree, or a radix tree built  
off the lengths of the prefixes one has received in routing  
advertisements, or an m-trie, for example.

To figure out the radix model, you basically observe the prefix  
lengths in your own configuration and being advertised to you. From  
http://www.ripe.net/ripe/docs/ipv6policy.html#initial_allocation, I  
observe that you are likely to receive advertisements of:

	/32 prefixes for remote ISPs
	/48 (and /56?) prefixes for customers of your own ISP
	/64 prefixes for some customers of your ISP and LANs in your own  
network
	/128 prefixes of some individual systems

One might also note that /23s are allocated to RIRs, and input that  
to the program as a given. One might also understand /10 prefixes as  
address types, as some (multicast) have to be understood differently  
than unicast addresses. Observing this in the data you receive, you  
might then go on to build what amounts to a B-Tree, identifying for  
example

	the first 10 bits as an address type
	the next 13 bits as an RIR key
	the next 9 bits as an ISP identifier within the RIR
	the next 16 bits as a customer identifier within an ISP
	the next 8 bits as customer-or-group-of-LANs
	the next 8 bits as customer-or-LAN
	the remaining 64 bits if appropriate.

Note of course that there is nothing hard and fast here; one could  
readily imagine an ISP numbering its POPs with /44s and its customers  
with /56s, for example, in which case routing would advertise /44s  
and /56s to you. I could also imagine that if you are in the vicinity  
of the Indian Ocean, you might aggregate (or have someone aggregate  
to you) all RIPE and ARIN-assigned addresses as "to Europe" and "to  
North America", and as a result actually have /23s in routing rather  
than thinking of the fact as a precondition.

In fact, I could think of a lot of things. Which is why you don't  
want to build the magic numbers in as compile options or hardware  
offsets, but rather learn them from the route database actually  
advertised to you.

http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Tree/PATRICIA/
http://www.cs.princeton.edu/software/lcc/doc/mrst.pdf
http://ieeexplore.ieee.org/iel5/9494/30133/01382613.pdf? 
tp=&arnumber=1382613&isnumber=30133
http://www-inst.eecs.berkeley.edu/~cs268/sp03/notes/Lecture13.pdf
http://netlab.cs.tsinghua.edu.cn/~xuke/papers_on_iplookup.htm

---

From: Joe Abley <[email-masked]>
Date: Sun, 19 Feb 2006 22:56:39 -0500

> 	/48 (and /56?) prefixes for customers of your own ISP

... and also /48s advertised by ASes who qualify for long-prefix PI  
assignments from the various RIRs (e.g. under critical infrastructure  
policies; F-Root is numbered within 2001:500::/48.)

> 	/128 prefixes of some individual systems

[...]

> offsets, but rather learn them from the route database actually  

I think also it's good advice not to assume that what you see on the  
v6 Internet today is any indication of what you might see in (say) 5  
years time. RIR assignment policies change; as/if substantial  
commercial/production traffic moves to v6, that will cause additional  
pressures.

Joe