About Longest Prefix Match document

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

About Longest Prefix Match document

Cesar Olvera
Hi,

Somebody knows the document that specifies the Longest Prefix Match
(LPM) Algorithm?

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
[hidden email]
https://www1.ietf.org/mailman/listinfo/routing-discussion
Reply | Threaded
Open this post in threaded view
|

Re: About Longest Prefix Match document

Alexandru Petrescu-2
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
> [hidden email]
> https://www1.ietf.org/mailman/listinfo/routing-discussion
>


_______________________________________________
routing-discussion mailing list
[hidden email]
https://www1.ietf.org/mailman/listinfo/routing-discussion
Reply | Threaded
Open this post in threaded view
|

Re: About Longest Prefix Match document

fonesurj
In reply to this post by Cesar Olvera
Check out RFC 1812.

This RFC defines what "longest match" means (under "5.2.4.3 Next Hop Address").

There is a number of references to the longest match method in the RFC.  This RFC more-or-less specifies that internet gateways (routers) should use this method when operating in a classless fashion, as most routers do these days.

Derick Winkworth
CCIE#15672


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