tags:

views:

31

answers:

1
Q: 

IPv6 lookup data structure

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?

A: 

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:

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

schot  2010-10-19 14:21:35

related questions

Fundamental Data Structures in C#
What are you currently using for data access?
What are good alternative data formats to XML?
One or Two Primary Keys in Many-to-Many Table?
What are some alternatives to a bit array?
How do you build a ratings implementation?
How do I efficiently keep track of the smallest element in a collection?
What is a good open source B-tree implementation in C?
What are models for storing tree structures and what are their characteristics?
Does PHP have built-in data structures?
How to maintain a recursive invariant in a MySQL database?
Aging Data Structure in C#
Is there a "Set" data structure in .Net?
Removing elements with Array.map in JavaScript
[C#] Best implementation for Key Value Pair Data Structure?
Graph visualization code in javascript?
Best way to abstract season/show/episode data
What is the best way to create a sparse array in C++
What problems can be solved, or tackled more easily, using graphs and trees?
Reading a C/C++ data structure in C# from a byte array
Good STL-like library for C.
Best self-balancing BST for quick insertion of a large number of nodes
Binary file layout reference
Mapping Stream data to data structures in C#
What is the most efficient graph data structure in Python?