Longest Prefix Match
Longest Prefix Match is a simple method from the network field . This is about how a router can find the maximum possible match between the destination address and a stored IP address from its internal routing table as efficiently as possible . The route algorithm is used when the routing table contains several address ranges that potentially match the destination address of a packet and, after the replacement of network classes by addresses and freely selectable network masks ( CIDR ), is part of the standard procedure.
In general, the following applies: A router internally maintains a routing table with network addresses and network masks and an associated interface in order to be able to forward a received packet. If the destination address is in several available subnets, the entry with the longest match is selected.
The method is used for both IPv4 and IPv6 .
example
In the following, a router contains a routing table with three IP address templates and the interfaces assigned to them. A packet with the destination address is 198.51.100.78
received, so the best possible selection must be made for forwarding the packet. Although it 198.51.100.0/24
fits the network (interface 1), the packet is only forwarded via the interface that has a maximum match with the destination address, in this case interface 2. The packet does not match the address of interface 3, so the Netmask of this entry is irrelevant.
Simplified IPv4 routing table for a router
# | Network address | Subnet mask (prefix length) |
interface |
---|---|---|---|
1 | 198.51.100.0 | 255.255.255.0 / 24 | Interface 1 |
2 | 198.51.100.64 | 255.255.255.192 / 26 | Interface 2 |
3 | 198.51.100.128 | 255.255.255.192 / 26 | Interface 3 |
Received packet with the IPv4 address 198.51.100.78
Adresse/Netz (CIDR) Binärdarstellung Übereinstimmung 198.51.100.78/32 11000110.00110011.01100100.01001110 198.51.100.0/24 11000110.00110011.01100100.00000000 24 Bit 198.51.100.64/26 11000110.00110011.01100100.01000000 26 Bit 198.51.100.128/26 11000110.00110011.01100100.10000000 -
Entry # 2 has the longest match with the respective complete fixed address part, namely 26 bits. Forwarding of the package accordingly via interface 2.
literature
- Douglas Comer: Computer Networks and Internet , 5th edition 2009, ISBN 978-0-13-606127-4 , p. 369.