[erlang-questions] Longest prefix match

[jm]

I've implemented this a number of times in different languages for 
ip_address/bitmask, eg 192.168.1.0/24. 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} ->
          Val
    end.

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
  1999

"Analysis of Random LCTries"
Luc Devroye
2001

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

"Generalizing Generalized Tries"
Ralf Hinze
1999


Hope that helps,

Jeff.


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