IPv6 lookup data structure

Question

A patricia trie is the well-know, recommended data structure for storing IPv4 allocations/assignments and performing lookup.

Is this true for IPv6 adddresses too? Just a deeper/taller trie to accommodate the extra 96 bits? Is the trie still patricia, or a different radix trie?

Answer 1

You can still use Patricia tries with a bigger depth, but the problem is the performance degrades linearly with the trie depth. Designing specialized data structures for IPv6 lookup is an active field. Recent publications include:

• A Dynamic Binary Hash Scheme for IPv6 Lookup (PDF)
• IPv6 Lookups using Distributed and Load Balanced Bloom Filters for 100Gbps Core Router Line Cards (PDF)
• FlashTrie: Hash-based Prefix-Compressed Trie for IP Route Lookup Beyond 100Gbps (PDF)

I don't know of any available (open source) implementations of these data structures.