Longest prefix match
Encyclopedia
Longest prefix match refers to an algorithm
used by routers in Internet Protocol
(IP) networking to select an entry from a routing table
.
Because each entry in a routing table
may specify a network, one destination address may match more than one routing table entry. The most specific table entry — the one with the highest subnet mask — is called the longest prefix match. It is called this because it is also the entry where the largest number of leading address bits in the table entry match those of the destination address.
For example, consider this IPv4
routing table (CIDR notation
is used):
192.168.20.16/28
192.168.0.0/16
When the address 192.168.20.19 needs to be looked up, both entries in the routing table "match". That is, both entries contain the looked up address. In this case, the longest prefix of the candidate routes is 192.168.20.16/28, since its subnet mask (/28) is higher than the other entry's mask (/16), making the route more specific.
Routing 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.
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
used by routers in Internet Protocol
Internet Protocol
The Internet Protocol is the principal communications protocol used for relaying datagrams across an internetwork using the Internet Protocol Suite...
(IP) networking to select an entry from a routing table
.
Because each entry in a routing table
Routing table
In computer networking a routing table, or Routing Information Base , is a data table stored in a router or a networked computer that lists the routes to particular network destinations, and in some cases, metrics associated with those routes. The routing table contains information about the...
may specify a network, one destination address may match more than one routing table entry. The most specific table entry — the one with the highest subnet mask — is called the longest prefix match. It is called this because it is also the entry where the largest number of leading address bits in the table entry match those of the destination address.
For example, consider this IPv4
IPv4
Internet Protocol version 4 is the fourth revision in the development of the Internet Protocol and the first version of the protocol to be widely deployed. Together with IPv6, it is at the core of standards-based internetworking methods of the Internet...
routing table (CIDR notation
CIDR notation
CIDR notation is a compact specification of an Internet Protocol address and its associated routing prefix. Classless Inter-Domain Routing is an Internet Protocol address allocation and route aggregation methodology used within the Internet addressing architecture that replaced the IPv4 classful...
is used):
192.168.20.16/28
192.168.0.0/16
When the address 192.168.20.19 needs to be looked up, both entries in the routing table "match". That is, both entries contain the looked up address. In this case, the longest prefix of the candidate routes is 192.168.20.16/28, since its subnet mask (/28) is higher than the other entry's mask (/16), making the route more specific.
Routing tables often contain a default route
Default route
A default route, also known as the gateway of last resort, is the network route used by a router when no other known route exists for a given IP packet's destination address. All the packets for destinations not known by the router's routing table are sent to the 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 EngineNetwork Search EngineComputer networks are connected together to form larger networks such as campus networks, corporate networks, or the Internet. Routers are network devices that may be used to connect these networks...
: hardware accelerator used in routers for LPM lookups. - TrieTrieIn computer science, a trie, or prefix tree, is an ordered tree data structure that is used to store an associative array where the keys are usually strings. Unlike a binary search tree, no node in the tree stores the key associated with that node; instead, its position in the tree defines the...
: prefix tree