Editing Longest prefix match

{{Short description|String-searching algorithm used in IP routing}}
{{More citations needed|date=October 2007}}
'''Longest prefix match''' (also called '''Maximum prefix length match''') refers to an [[algorithm]] used by [[Router (computing)|router]]s in [[Internet Protocol]] (IP) networking to select an entry from a routing table.<ref>
{{cite book|
first   = Douglas|
last    = Comer|
title   = Computer Networks and Internets|
year    = 2008|
pages   = 368|
publisher = Pearson/Prentice Hall|
isbn    = 978-0-13-606698-9|
edition = 5th}}
</ref>

Because each entry in a [[forwarding table]] may specify a sub-network, one destination address may match more than one forwarding table entry. The most specific of the matching table entries &mdash; the one with the longest subnet mask &mdash; is called the longest prefix match. It is called this because it is also the entry where the largest number of leading address bits of the destination address match those in the table entry.
<ref>
{{cite book|
first   = Robert|
last    = Wright|
title   = IP Routing Primer|
year    = 1998|
pages   = 352|
publisher = Cisco Press|
isbn    =  978-1578701087}}
</ref>

For example, consider this [[IPv4]] forwarding table ([[CIDR notation]] is used):

 192.168.20.16/28
 192.168.0.0/16

When the address <code>192.168.20.19</code> needs to be looked up, both entries in the forwarding table "match". That is, both entries contain the looked up address. In this case, the longest prefix of the candidate routes is <code>192.168.20.16/28</code>, since its [[subnet mask]] (/28) is longer than the other entry's mask (/16), making the route more specific.

Forwarding tables often contain a [[default route]], which has the shortest possible prefix match, to fall back on in case matches with all other entries fail.

==See also==
* [[Network Search Engine]]: hardware accelerator used in routers for LPM lookups.
* [[Trie]]: prefix tree

== References ==
<references/>

[[Category:Routing protocols]]
[[Category:Internet architecture]]