Longest Prefix Match

When a router gets a packet, it has to pick a route from its routing table to decide how to forward it. The routing table can hold many routes, sometimes dozens or even hundreds. Each route stands for a different network.

Sometimes, a router discovers multiple routes that match the same destination IP address but with different subnet masks. This is when the Longest Prefix Match (LPM) rule is important. This rule helps the router choose the best path for the destination network. It picks the most accurate route instead of a broader, less specific option.

Example scenario

Let’s look at an example together.
A packet with the destination IP address 192.168.1.130 arrives at router R1.

Figure 1 – Router with multiple matching routes

When we check the routing table, the router finds three possible matches for this destination:

• 192.168.0.0/16

• 192.168.1.0/24

• 192.168.1.128/25

At first glance, all three entries seem valid because they all include the destination IP address 192.168.1.130. However, the router must select the most specific route according to the Longest Prefix Match (LPM) principle.

The router picks the route with the longest prefix. This means it chooses the network that has the most bits in common with the destination address. This method ensures that traffic is always forwarded through the most precise and efficient path available.

Let’s explore the LPM process step by step in the next section.

The concept of the Longest Prefix Match (LPM) is simple. Each route in the routing table has a prefix length that tells the router how much of the IP address identifies the network part.

To visualize this, let’s take the same routing table and look at the range of addresses covered by each prefix:

• 192.168.0.0/16 → 192.168.0.0 – 192.168.255.255

• 192.168.1.0/24 → 192.168.1.0 – 192.168.1.255

• 192.168.1.128/25 → 192.168.1.128 – 192.168.1.255

Figure 2 – Routing table with different prefix lengths for the Longest Prefix Match

A shorter prefix covers a larger network, while a longer prefix is more specific.
When a router forwards a packet, it checks the destination IP address. It compares it to all prefixes in its table. The router selects the prefix with the most matching bits. This is known as the Longest Prefix Match rule.

Finding the best route

Let’s see how it works using the destination 192.168.1.130.
By converting the networks into binary, we can see which prefix matches the destination for the longest bit sequence:

Table 1 - Longest Prefix Match Process

As shown above, the /25 prefix shares the longest sequence of identical bits with the destination address. Therefore, the router selects 192.168.1.128/25 as the best route to forward the packet.