On Feb 16, 2006, at 10:34 PM, Dheeraj Singh wrote:
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!!
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
--------------------------------------------------------------------
IETF IPv6 working group mailing list
ipv6@ietf.org
Administrative Requests: https://www1.ietf.org/mailman/listinfo/ipv6
--------------------------------------------------------------------
