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).

A “source” can be a routing protocol or a static route.

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:

Destination IP address Binary
192.168.2.82 11000000.10101000.00000010.01010010

The router has the following prefixes in its routing table:

Prefix Binary
192.168.2.80/29 11000000.10101000.00000010.01010000
192.168.2.64/27 11000000.10101000.00000010.01000000
192.168.2.0/24 11000000.10101000.00000010.00000000

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:

Destination IP address Binary
10.4.1.62 00001010.00000100.00000001.00111110

The router has the following prefixes in its routing table:

Prefix Binary
10.4.1.32/27 00001010.00000100.00000001.00100000
10.4.1.0/24 00001010.00000100.00000001.00000000
10.0.0.0/8 00001010.00000000.00000000.00000000

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:

Four Routers With Switch Middle

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.

Configurations

Want to take a look for yourself? Here you will find the startup configuration of each device.

R1

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

R2

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

R3

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

R4

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.

These static routes point to the IP addresses of R2, R3, and R4. These networks don’t exist but that doesn’t matter for this example. I only need these static routes so that we have something to look at in the routing table.

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.


Forum Replies

  1. Hello Robert

    The order is indeed AD, Metric, and then prefix length. A router uses the AD and the metric to determine which route ends up being installed in the routing table. The prefix length is then used to determine which of the already installed routes in the routing table will be used to route a particular packet. AD and metric necessarily come before the prefix length. Consider this:

    Administrative Distance - When a router learns about a specific route from two or more different sources, it must choose which source to use. This is done by looking at

    ... Continue reading in our forum

Ask a question or join the discussion by visiting our Community Forum