IPv6-Lookup-Datenstruktur

Question

Eine patricia trie ist die wohlbekannte, empfohlene Daten Struktur für Zuweisungen / Zuweisungen IPv4 Speichern und Ausführen Lookup.

Ist das wahr für zu IPv6 adddresses? Nur ein tiefer / höher trie die zusätzlichen 96 Bits aufzunehmen? Ist die Trie noch patricia, oder eine andere 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.