Algorithm/steps to find Longest Prefix search in Patricia Trie

ip lookup patricia-trie
vyom picture vyom · May 26, 2009 · Viewed 9.9k times · Source

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) ?

Answer

Corwin Joy picture Corwin Joy · Dec 18, 2009

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

Related questions

Reverse DNS lookup in perl

How do I perform a reverse DNS lookup, that is how do I resolve an IP address to its DNS hostname in Perl?

Read More
How to get the Country according to a certain IP?

Does anyone know any simple way to retrieve the country from a given IP Address, preferably in ISO_3166-1 format?

Read More
How to get a list of all valid IP addresses in a local network?

Is there a way to get a list of all valid IP addresses in a local network? I mean all IP addresses that each user is using in the network.

Read More