Longest Prefix Match

The destination IP address in a packet is searched in the subnet ranges available in the route table during the forwarding of a packet to an interface.

Let’s assume the route table has the entries displayed in the table below:

Sample Route Table

Destination Subnet

Interface

0.0.0.0/0

eth1

10.1.240.0/21

eth0

10.1.248.0/21

eth2

10.1.248.0/26

eth3

10.1.248.64/26

eth4

10.1.248.128/26

eth5

10.1.248.192/26

eth6

Let’s see how a matching subnet range can be found for the destination IP address, 10.1.248.137. Each entry in the table is tested to find what IP address range has this destination IP address:

0.0.0.0/0           0.0.0.0 – 255.255.255.255           match
10.1.240.0/21       10.1.240.0 – 10.1.247.255           no match
10.1.248.0/21       10.1.248.0 – 10.1.255.255           match
10.1.248.0/26       10.1.248.0 – 10.1.248.63            no match
10.1.248.64/26      10.1.248.64 – 10.1.248.127          no match
10.1.248.128/26     10.1.248.128 – 10.1.248.191         match
10.1.248.192/26     10.1.248.192 – 10.1.248.255         no match

Which route is the best option then?

Here are the options to pick from (as indicated in the route table, each of these subnets are on a different interface):

0.0.0.0/0         0.0.0.0 – 255.255.255.255
10.1.248.0/21     10.1.248.0 – 10.1.255.255
10.1.248.128/26   10.1.248.128 – 10.1.248.191

Among the possible options, the subnet range that matches the given IP address with the longest prefix of the address is picked. Tracing the matching portions of the subnets in this list: first subnet matches all since the prefix in 0.0.0.0 is itself. In the second range, the destination IP address, 10.1.248.137 matches the subnet range up to its last octet, that is, the portion with the first three octets: 10.1.248. The last subnet range has the largest matching portion of this destination address with its 10.1.248.128 starting point.

This method is realized by visualizing the route table in a tree. IP address ranges are connected according to the common address ranges that are shared from one branch to the next. For example, the matching exercise above can visualize the existing route table in the tree shown here.

_images/prefixtree1.png

This is a tree representation of the IP address ranges that go from the least specific to more specific as we trace the IP addresses down the tree.

Tracing the tree down until there is no match between the packet’s destination IP address and the destination subnet ranges in the route table is the method utilized in this search.

_images/prefixtree2.png

Tracing the tree down until the destination IP address is matched as shown.

Here is another example in the same route table. Let’s assume the destination IP address 10.1.249.30 is being matched to the subnet ranges in the tree. Matching routes are:

0.0.0.0/0         0.0.0.0 – 255.255.255.255
10.1.248.0/21     10.1.248.0 – 10.1.255.255
_images/prefixtree3.png

The trace this time stops at the second level branches since there is no more matching subnets in the next branch level for this tree.

Here is another example IP address where this time the search stops at the root level: 13.1.24.233.

_images/prefixtree4.png

The trace this time stops at the first level, namely, at the root, since there are no branches that has a matching range for this destination IP address.