IPv6 Search Data Structure

Question

A patricia trie is a well-known recommended data structure for storing IPv4 allocations / assignments and performing searches.

Is this also true for additional IPv6 addresses? Only a deeper / higher three to accommodate an additional 96 bits? Is trie still patricia, or another radix trie?

Answer 1

You can still use Patricia's attempts with greater depth, but the problem is that performance degrades linearly with trie depth. Designing specialized data structures for IPv6 search is an active field. Recent publications include:

• Dynamic Binary Hashing Pattern for IPv6 Search (PDF)
• IPv6 Search Using Distributed and Downloadable Balanced Filters for 100 Gbps Linear Router Cards (PDF)
• FlashTrie: Trash pre-compression for hashing to find IP routes beyond 100 Gbps (PDF)

I do not know of any available (open source) implementations of these data structures.