Subject: Re: About Longest Prefix Match document

From: Alexandru Petrescu <[email-masked]>
Date: Mon, 27 Mar 2006 16:26:12 +0200

Cesar Olvera wrote:
> Hi,
> 
> Somebody knows the document that specifies the Longest Prefix Match
> (LPM) Algorithm?

I'm afraid it's not specified in any RFC nor I-D.  The algorithm looks 
like this: given an IP address and a table of prefix-gw pairs, identify 
the pair whose first n bits of the prefix match the first n bits of the 
address, for a maximum n.  A trivial implementation is straightforward 
and can be written very shortly by a good programmer.

One may look at the FreeBSD kernel routing code and/or gated source code.

"Practical Algorithm To Retrieve Information Coded In Alphanumeric." 
http://portal.acm.org/citation.cfm?id=321481

A relatively more recent method is in paper "Adaptive Data Structures 
for IP Lookups" 2005
http://www.comsoc.org/confs/ieee-infocom/2003/papers/02_04.PDF
whose References section lists a number of alternative methods for 
routing lookup.

Alex

> 
> Thanks in advance,
> 
> César Olvera
> Consulintel
> 
> 
> 
> 
> **********************************************
> The IPv6 Portal: http://www.ipv6tf.org
> 
> Barcelona 2005 Global IPv6 Summit
> Slides available at:
> http://www.ipv6-es.com
> 
> This electronic message contains information which may be privileged or 
> confidential. The information is intended to be for the use of the 
> individual(s) named above. If you are not the intended recipient be 
> aware that any disclosure, copying, distribution or use of the contents 
> of this information, including attached files, is prohibited.
> 
> 
> 
> 
> _______________________________________________
> routing-discussion mailing list
> [email-masked]
> https://www1.ietf.org/mailman/listinfo/routing-discussion
> 

_______________________________________________
routing-discussion mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/routing-discussion