Longest Prefix Match Routing

Introduction

The longest prefix match (also known as Maximum prefix length match) is an algorithm that routers use in Internet Protocol (IP) networking to select a routing table entry. Because each forwarding table entry can specify a sub-network, a single destination address can match more than one forwarding table entry. Routers look at the destination address's IP prefix is explained further, search for a match in the forwarding table, and then forward the packet to the corresponding next hop in the forwarding table.

Representation of IP Prefix

The IP prefix is an IP address prefix. IP addresses are the unique addresses that represent a device's location on the Internet. On a single network, every computer has the same IP prefix. An IP prefix is used to represent a range of IP addresses available for use. As a result, it begins with an IP address and ends with the length of the prefix. The prefix length represents the number of fixed bits that cannot be changed. Consider the following IP prefix: 192.168.64.0/18. The binary representation of IP address 192.168.64.0 is:

According to prefix length, which is 18 bits, We can not change the values of the first 18 bits. We are only allowed to change the values of the last 14 bits to represent 214 different IP addresses. 192.168.127.255 is the last IP address represented by the IP prefix 192.168.64.0/18. The binary representation of IP address 192.168.127.255 is:

In the above binary representation, all last 14 bits are set to 1 to represent the given network's last IP address.

Packet Forwarding

Packets are routed from one router to another based on their destination IP addresses. In computer networking, this is referred to as packet forwarding.

A data packet contains a destination IP address for a router. As a result, each router must decide which router node the data packet should be sent to next in the network, and this decision is based on a forwarding table. For packet forwarding, routers check the destination address's IP prefix, search for a match in the forwarding table, and then forward the packet to the corresponding next hop in the forwarding table.

Let's move on to the forwarding table. It is distinct from the routing table. The forwarding table contains multiple entries containing an IP prefix or range and router node information. Furthermore, a specific IP prefix or range packet will be routed to the appropriate router node.

Let us take an example for a better understanding of packet forwarding.

If a packet's destination IP address belongs to Address_Range1 in the above forwarding table, the packet is sent along the hop A. If it belongs to Address_Range2, the packet is sent along hop B.

Longest Prefix Matching

The main issue with packet forwarding is the possibility of overlapping entries in the forwarding table. Because of this, a new entry in the table may match an entry already present in the forwarding table.  In case of overlapping entries, different prefixes or subnet masks could be a viable option for an IP address belonging to both table entries. As a result, we must pick an IP prefix that is more specific and has a longer prefix that matches the destination address.

For instance, suppose Rohit wants to send a letter to a specific address. There are two choices. The first choice is  Rohit can hand over his letter to Person X, who works in a post office in the city where the letter is to be delivered. Another choice is to give the letter to Person Y, who works in a particular area of that city. As a result, giving the letter to person Y is more efficient because he handles more localized regions.

Similarly, we use the longest prefix matching to select a route with more specific information. As a result, when the number of possible IP options in a route is limited, the packet is more likely to arrive at its destination quickly. The forwarding table uses the longest prefix matching with a unique destination address of the packet to assign the next router so that the packet reaches the destination efficiently. Refer to Example1 and Example2 to understand how the longest prefix matching is used to find the next hop.

Example 1

Consider the following example, where the destination IP address of a packet is 192.17.21.26, and a node has a forwarding table:

In addition, the IP prefix 192.17.0.0/18 can have destination addresses ranging from 192.17.0.0 to 192.17.63.255. In the same way, the IP prefix 192.17.20.0/22 can have destination addresses ranging from 192.17.20.0 to 192.17.23.255.

If we look at the binary value of 192.17.21.26, we can see that the prefixes 192.17.0.0/18 and 192.17.20.0/22 are valid for the IP address 192.17.21.26. However, the main question is which route the router will take. From the above-Converted IP Addresses table, we can see that the IP address 192.17.21.26 has the longest prefix matching with 192.17.20.0/22, so we select B as the next hop for the data packet.

We offer a default node route as a fallback mechanism that ensures that a packet reaches its next destination even if the forwarding table does not contain a matching prefix for a certain destination address. A typical data structure called Trie can quickly identify the longest prefix corresponding to a given destination IP address.

Example 2

Let's consider an example where the router receives a packet with the destination IP address 192.168.1.33. The following matches are possible in the routing table:

To identify the longest match, convert the IP addresses into binary and compare them.

From the above-converted IP Addresses table, we can see that the IP address 192.168.1.33 has the longest prefix matching with 192.168.1.32/28, so we select A as the next router for the data packet.