longest prefix match in the router

longest prefix match in the router

The longest prefix match means that out of all routes in a routing table, the router should choose the one that has the longest prefix and at the same time this prefix matches the prefix of the destination IP address of the received packet and via that ip addresses interface packet will be forwarded 

The length of the prefix is determined by a network mask, and the longer the prefix is, the higher the netmask is. Therefore, a router keeps its routing table sorted so that all known networks with the prefix length of /32 (255.255.255.255) are at the top of the routing table. Below them, the router puts all known networks with the prefix length of /31 (255.255.255.254), then all known networks with the prefix length of /30 (255.255.255.252), and so on, until it comes to all known networks with the prefix length of /1 (128.0.0.0) and finally all known networks with the prefix length of /0 (0.0.0.0; this is actually a default route). Assuming your router knows about networks 10.0.0.0/8, 10.0.0.0/16, and 10.0.0.0/24, the routing table would be sorted as follows:

Row 1: Network 10.0.0.0 / 255.255.255.0
Row 2: Network 10.0.0.0 / 255.255.0.0
Row 3: Network 10.0.0.0 / 255.0.0.0

Then, when a packet comes in, destined to, say, 10.10.10.10, the router will start at the top of the routing table, performing a bitwise AND between the destination IP and the netmask of the route in that table row. This operation will "extract" the prefix of a certain length determined by the netmask from the destination IP address, and fill the rest with binary zeros. Then, the router compares the resulting address to the network address in that table row, and if they match, the router has found the best matching routing table entry. If they do not match, the router goes to the next row in the table and repeats the whole process. Because the table is sorted according to the prefix lengths, most specific networks being at the top, the first found match is the longest match.

So with our destination IP address of 10.10.10.10 and the routing table shown above, the process would be:

Row 1: 10.10.10.10 & 255.255.255.0 = 10.10.10.0, differs from 10.0.0.0
Row 2: 10.10.10.10 & 255.255.0.0 = 10.10.0.0, differs from 10.0.0.0
Row 3: 10.10.10.10 & 255.0.0.0 = 10.0.0.0, matches 10.0.0.0 :)

Please note that the show ip route output is not sorted according to network masks. However, the router still keeps the routing table sorted internally so than when doing a lookup, it goes from the most specific network to the least specific network as shown above.

Feel welcome to ask further!

Refer: https://supportforums.cisco.com/discussion/12932911/please-explain-how-longest-prefix-matching-works

What is Forwarding?
Forwarding is moving incoming packets to appropriate interface. Routers use forwarding table to decide which incoming packet should be forwarded to which next hop.

What is IP prefix?
IP prefix is a prefix of IP address. All computers on one network have same IP prefix. For example, in 192.24.0.0/18, 18 is length of prefix and prefix is first 18 bits of the address.

How does forwarding work?
Routers basically look at destination address’s IP prefix, searches the forwarding table for a match and forwards the packet to corresponding next hop in forwarding table.

What happens if the prefixes overlap?
Since prefixes might overlap (this is possible as classless addressing is used everywhere), an incoming IP’s prefix may match multiple IP entries in table.
For example, consider the below forwarding table

In above table, addresses from 192.24.12.0 to 192.24.15.255 overlap, i.e., match with both entries of the table.
To handle above situation, routers use Longest Prefix Matching rule. The rule is to find the entry in table which has the longest prefix matching with incoming packet’s destination IP, and forward the packet to corresponding next hope.

Ref: http://www.geeksforgeeks.org/computer-networks-longest-prefix-matching-in-routers/