Longest Prefix Match Routing

When a router receives an IP packet, it has to decide from which interface and (optionally) to which next-hop it has to forward the packet.

It looks in the routing table to find a match and uses these items to make a decision:

1. Administrative distance
2. Metric
3. Prefix length

The administrative distance is the “trustworthiness” of a route. When a router learns the same prefix through multiple sources, it must choose one route. That’s what the administrative distance is for (explained in detail in this lesson).

Routing protocols use a metric to calculate the best path to the destination. Each routing protocol has a different metric and a different way of calculating the metric.

Last but not least is the prefix length. That’s what this lesson is about.

Longest prefix match routing is an algorithm where the router prefers the longest prefix in the routing table. In other words, the most specific prefix. 

When a router receives the IP packet, it compares the destination IP address bit-by-bit with prefixes in the routing table. The prefix with the most matching bits is the prefix that the router will use. Let me help you visualize this.

Example 1

Imagine the router receives an IP packet with destination 192.168.2.82. In binary, the IP address looks like this:

The router has the following prefixes in its routing table:

All of the prefixes above match our destination IP address. If you look closely at the bits above, you can see that 192.168.2.80/29 matches the most bits with IP address 192.168.2.82. This is our “longest prefix” for this destination.

Example 2

Let’s look at one more example. The router receives an IP packet with destination 10.4.1.62. In binary, the IP address looks like this:

The router has the following prefixes in its routing table:

In the example above, you can see that 10.4.1.32/27 is the closest match.

Verification

We can verify longest prefix match routing on a router by looking at the routing table. Let’s see what this looks like in action. I’ll use the following topology:

We have four routers connected to a switch. There are six static routes on R1 that point to R2, R3, and R4 so we have some routes to look at.

hostname R1
!
ip cef
!
interface GigabitEthernet0/0
 ip address 192.168.1.1 255.255.255.0
!
ip route 10.0.0.0 255.0.0.0 192.168.1.4
ip route 10.4.1.0 255.255.255.0 192.168.1.2
ip route 10.4.1.32 255.255.255.224 192.168.1.3
ip route 192.168.2.0 255.255.255.0 192.168.1.4
ip route 192.168.2.64 255.255.255.224 192.168.1.3
ip route 192.168.2.80 255.255.255.248 192.168.1.2
!
end

hostname R2
!
ip cef
!
interface GigabitEthernet0/0
 ip address 192.168.1.2 255.255.255.0
!
end

hostname R3
!
ip cef
!
interface GigabitEthernet0/0
 ip address 192.168.1.3 255.255.255.0
!
end

hostname R4
!
ip cef
!
interface GigabitEthernet0/0
 ip address 192.168.1.4 255.255.255.0
!
end

Here are the static routes in the routing table:

R1#show ip route static

      10.0.0.0/8 is variably subnetted, 3 subnets, 3 masks
S        10.0.0.0/8 [1/0] via 192.168.1.4
S        10.4.1.0/24 [1/0] via 192.168.1.2
S        10.4.1.32/27 [1/0] via 192.168.1.3
      192.168.2.0/24 is variably subnetted, 3 subnets, 3 masks
S        192.168.2.0/24 [1/0] via 192.168.1.4
S        192.168.2.64/27 [1/0] via 192.168.1.3
S        192.168.2.80/29 [1/0] via 192.168.1.2

In the output above, you can see that the router sorts the prefixes from short to long.

Example 1

Let’s look at the destination in our first example: 192.168.2.82. Here are all the prefixes R1 knows about that match this destination:

R1#show ip route 192.168.2.0
Routing entry for 192.168.2.0/24, 3 known subnets
  Variably subnetted with 3 masks
S        192.168.2.0/24 [1/0] via 192.168.1.4
S        192.168.2.64/27 [1/0] via 192.168.1.3
S        192.168.2.80/29 [1/0] via 192.168.1.2

How can I tell which route the router will use? You can use the show ip route command and specify the destination IP address you want to check:

R1#show ip route 192.168.2.82
Routing entry for 192.168.2.80/29
  Known via "static", distance 1, metric 0
  Routing Descriptor Blocks:
  * 192.168.1.2
      Route metric is 0, traffic share count is 1

By using show ip route and specifying the destination IP address, R1 tells us that it will use the route with prefix 192.168.2.80/29. That’s the longest prefix that matches this destination.

Example 2

Let’s try the destination IP address from our second example: 10.4.1.62. Here are all the prefixes that match this destination:

R1#show ip route 10.0.0.0
Routing entry for 10.0.0.0/8, 3 known subnets
  Variably subnetted with 3 masks
S        10.0.0.0/8 [1/0] via 192.168.1.4
S        10.4.1.0/24 [1/0] via 192.168.1.2
S        10.4.1.32/27 [1/0] via 192.168.1.3

Which route will the router use? Let’s find out:

R1#show ip route 10.4.1.62
Routing entry for 10.4.1.32/27
  Known via "static", distance 1, metric 0
  Routing Descriptor Blocks:
  * 192.168.1.3
      Route metric is 0, traffic share count is 1

The route with prefix 10.4.1.32/27 is the longest prefix that matches this destination.

Conclusion

• Routers check the routing table and use the following items as a tie-breaker to select the best path:
  • Administrative distance
  • Metric
  • Prefix length
• Routers prefer the longest prefix in the routing table.
• You can check which route the router will use with the show ip route command.

I hope you enjoyed this lesson. If you have any questions please leave a comment.