Algorithm/steps to find Longest Prefix search in Patricia Trie

Question

I am implementing Patricia tries for IP prefix lookup, I could get the code working for complete key match, but facing problems with prefix search, when there are keys which are prefixes of other keys, like:

1.2.3.0
1.2.0.0

Can anyone help me with the algorithm for prefix searches in the above case Should I consider these as keys of separate length (i.e, /24 and 16) ?

Bayard

Answer 1

Take a look at Net-Patricia. This is an implementation of a Patricia trie to look up IP addresses. The interface is perl, but the underlying code is in C. Here is a link, but many CPAN archives should have it:

http://cpansearch.perl.org/src/PHILIPP/Net-Patricia-1.15_07/libpatricia/patricia.c

Moneyer

Answer 2

If you use this trie for storing IP numbers as elements of the fixed length then it is definitely not the right way. The point here is that PT is especially useful for storing variable length data.

If you store parts of IP numbers, as prefixes of variable length then PT is a good choice.
In this case yes your keys should be of different length.
Let's say you are storing prefix "192.168" in binary 0xC0 0xA8, you add this as first key.
Then, when searching for IP like 192.168.1.1 you can get information that your trie contains 192.168 which is a prefix of what you look for.

All you have to do is to store the "common part" while traversing the trie.
This is a minor addition to the this implementation. Just make sure that while going down the trie you store the common part somewhere in the parameters of the recursive function.
For good understanding of Patricia trie I would suggest reading Robert Sedgewick's Algorithms book which is a great source of knowledge.

EDIT: There is one problem when storing C strings in PT. This trie is designed to store binary data, but you are interested only in getting the whole bytes. Make sure you are storing common part of the prefix only if its size in bits is multiple of 8. For a wrong example: you have key in your tree: 0xC0 0xA5 and you are looking fro 0xC0 0xA6. Your traversal will stop when the common part "0xC0 0xA", but you are interested in taking only "0xC0". So make sure to store common bytes, not bits.

Avouch

Answer 3

There's a fairly-readable C implementation in the test code for LLVM: https://llvm.org/svn/llvm-project/test-suite/trunk/MultiSource/Benchmarks/MiBench/network-patricia/

Vandavandal