Network: Longest Prefix Matching

1. Overview

In this tutorial, we’ll discuss the basic concept of IP prefix and longest prefix matching in networking with an example.

2. Representation of IP Prefix

An IP address is a unique address used to represent the location of a device on the Internet. Moreover, there’re two variations of IP address: IPv4 and IPv6. The first version of the IP address, IPv4, contains 32-bit addresses. In order to fulfill the growing demand for IP addresses, IPv6 uses a 128-bit address scheme. Other differences can be found in the article: Networking: IPv4 vs. IPv6 Addresses.

We use an IP prefix to represent a range of IP addresses. Therefore, it contains an IP address followed by the length of the IP address. Moreover, the IP address in an IP prefix represents the first IP address in a given range. Finally, the size of the prefix denotes the number of fixed bits that we can’t change.

Let’s consider an example of IP prefix: . Here, the IP address can be represented in binary:

Here, we highlight the prefix of the first bits. Additionally, we add the remaining zeroes to represent the first IP address in the range. Moreover, these binary digits can change values to represent different IP addresses represented by the IP prefix 192.168.64.0/18. Finally, the last IP address in this range will be .

Let’s look at the representation of the last IP address in binary format:

The key takeaway here is that the first bits highlighted won’t change across all the IP addresses in the given range.

3. Packet Forwarding

Packets are forwarded from one router to another based on their destination IP addresses. This process is known as packet forwarding in computer networking. Therefore, the longest prefix matching technique is used in networks to handle the overlapping problem of packet forwarding.

Moreover, a data packet comes with a destination IP address to a router. Therefore, each router has to decide the router node to which the data packet should be sent next. Finally, this decision is taken based on a forwarding table.

Now, let’s talk about the forwarding table. It’s different from the routing table. The forwarding table contains multiple entries, with each entry being an IP prefix or range along with the router node information. Moreover, a packet belonging to a particular IP prefix or range will be forwarded to the specific router node.

4. Longest Prefix Matching

The main problem in the packet forwarding process is that there could be overlapping entries in the forwarding table. Therefore, a new entry in the table can match an existing entry in the forwarding table.

In such a case, different prefixes or subnet masks could be a valid option for an IP address belonging to both the table entries. Therefore, we need to choose a more specific IP prefix with a longer prefix matching the destination address.

For an analogy, consider that Sam wants to send a letter to a particular destination. There’re two options. Firstly, Sam can give his latter to Person A, who works in a postal service in the city where the letter needs to be sent. Another option is to give it to Person B, who works in a particular locality in that city. Hence, it’s more efficient to give the letter to person B as he handles more localized regions.

Similarly, we choose a route with more specific information using the longest prefix matching. Hence, when the number of possible IP options is less in a route, the packet is more likely to be sent to the destination quickly.

By using the longest prefix matching, the forwarding table ensures that the next destination is provided with more granularity and ensures all the packets with different destination addresses have a next node to shift.

5. An Example

Let’s consider an example where the destination IP address of a packet is , and a node has a forwarding table:

Furthermore, the IP prefix can have destination addresses in the range to :

Similarly, the IP prefix can have destination addresses in the range to .

Clearly, if we see the value of in binary (), both the prefixes and are valid for the IP address . Although, the main question is which route would the router choose?

As has the longest prefix or longest subnet mask matching in the forwarding table, we select C as the next hop for the data packet:

If there’s no matching prefix in the forwarding table to a particular destination address, we provide a default node route as a fallback mechanism. Additionally, it ensures that a packet finds its next destination even if there’s no prefix match in the table.

Trie is a common data structure that can quickly find the longest prefix that matches a given destination IP address. Moreover, Trie is a tree-like data structure in which we can start from the root node and keep checking its children until we find the longest common prefix.

6. Conclusion

In this tutorial, we discussed the IP prefix concept in computer networking. We also explained the need for longest prefix matching in forwarding the packets with an example.