[erlang-questions] Longest prefix match

jm jeffm@REDACTED
Fri Nov 30 02:52:47 CET 2007

I've implemented this a number of times in different languages for 
ip_address/bitmask, eg What I say here may be a little 
IP centric. I should warn you I am by no means an expert either. Now the 
disclaimers are out of the way on with the show...

Thing you can check out:
  patricia Tries
  Level Compression Tries (LC-Tries)
  List of Hashes

This last one is the fastest I've found in software and easiest to 
implement in a high level language or at least a language which already 
provides hash algorithms and lists for you. It is memory hungry in 
comparisan with other method, but I found out later someone had 
investigated this or a similar algorithm and found it to be one of the 
fastest methods in software. In short,

Imagine a list of tuples {dicts, maskbits}

* mask the address
    MaskedAddress = Address band Mask
    or possibly MaskedAddress = << Address:Maskbits/integer-big>>

* walk a list of {dicts, maskbits} to find the Maskbits entry. The first 
entry in the list will be for Maskbits = 32, the second for Maskbits = 
31, etc assuming IPv4

* store MaskedAddress implies value in hash.
  eg, NewLevelDict = dict:store(MaskedAddress, Value, LevelDict)

* To find the stored values you then search the hashes/dictionaries from 
the longest prefix to the shortest.

  search([{HeadDict, Maskbits}| Tail], Address) ->
    MaskedAddress = Address band Maskbits,
    case dict:find(MaskedAddress, HeadDict) of
       error ->
          search(Tail, Address);
       {value, Val} ->

There's most likely errors in the foregoing, but it should be enough to 
give you the idea.

Papers that may be of interest.
     search for paper with these titles/author I've lost the original 
links for these.

  "CS209 HOW-TO Series How to build Patricia Tries"

"Data Structures For One-Dimensional Packet Classification Using 
Most-Specific-Rule Matching"
Sartaj Sahni Kun Suk Kim Haibin Lu
  {sahni, kskim, halu} @cise.ufl.edu
  Department of Computer and Information Science and Engineering
  University of Florida, Gainesville, FL 32611

  "IP-Address Lookup Using LC-Tries"
  Stefan Nilsson, Gunnar Karlsson
  IEEE Journal on Selected Areas in Communications

"Analysis of Random LCTries"
Luc Devroye

"Survey & Taxonomy of Packet Classification Techniques"
David E. Taylor
May 10, 2004

"Generalizing Generalized Tries"
Ralf Hinze

Hope that helps,


Dragan Zubac wrote:
> Hello
> A couple of questions regarding 'lpm' algorithm if anyone has any 
> experience with this.
> What would be the most elegant and efficient way for LPM ? For 
> example,we have some list of numbers:
> - 889123456
> - 44712345678
> - 5550123456789
> - 32112345
> - 5501
> and the desired number for example:
> 550123555666
> I guess the most efficient way would be to use some sort of 'tree' and 
> traverse each number from the beginning of destination number and check 
> it in number's list and if we can't match N position to claim it to be 
> the longest prefix match ? 
> Second question is the same as question one,but implies that to have 
> some additional data with prefix (route,price,user_id,etc.),what would 
> be algorithm looks like in this situation ? For example:
> - 889123456,100
> - 44712345678,100
> - 5550123456789,101
> - 32112345,101
> - 5501,100
> - 5550123456789,100
> number is 550123555666,100 ,the problem would be to find LPM for 
> specific price (100),in this case there's no unique prefix,but there's 
> unique prefix+price 'object'.
> Anybody had any experience with this issues ?
> Sincerely
> Dragan Zubac
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://www.erlang.org/mailman/listinfo/erlang-questions

More information about the erlang-questions mailing list