Routing Decision Longest Match Explained

This tutorial explains how routers make a routing decision. Learn what a routing decision is and how a router takes the routing decision.

Routers connect different networks. To connect different networks, routers learn all the routes of the network and store them in the routing table. Routers store each route in a separate entry. A routing table entry contains the network address and the route to reach the network address.

When a router receives a data packet, the router reads the destination address of the data packet and compares the destination address to the routing table's entries. The router may find no matching entry, one matching entry, or multiple matching entries.

If the router finds no matching entry, the router discards the data packet. If the router finds only one matching entry, the router forwards the data packet from the route defined in the entry. If the router finds multiple matching entries, the router selects the entry that matches the maximum of the destination address and forwards the data packet from the route defined in the selected entry.

The process of comparing a destination address to the routing table entries and selecting the matching entry is known as a routing decision. In other words, a routing decision is a process in which the router decides the route to forward data packets to a particular destination.

Let's take an example to understand how a router makes a routing decision. The following image shows the routing table of router R1 in a sample network.

Now suppose, R1 receives five data packets. The following table lists the destination address of each data packet.

The destination address of the first packet is 192.168.1.1/24. The network address in this address is 192.168.1.0/24. Since there is no route for the network 192.168.1.0/24, the router discards the first data packet.

The destination address of the second data packet is 20.0.0.10/8. The network address in this address is 20.0.0.0/8. There is one route for the network address 20.0.0.0/8. This route is available on the local interface (C- Directly connected). The router forwards the second data packet to the connected local network from the interface mentioned in the route.

The destination address of the third data packet is 90.0.0.10/8. The network address in this address is 90.0.0.0/8. The router has three routes for the network 90.0.0.0/8. These routes are 90.0.0.0/8, 90.1.0.0/16, and 90.2.0.0/24. These routes belong to the same classful network 90.0.0.0/8 but different classless networks.

You can break a classful network into small classless networks. The process of breaking a large classful network into small classless networks is called subnetting. You can check the following tutorial to learn more about subnetting.

Subnetting Tutorial - Subnetting Explained with Examples

When you break a large classful network into small classless networks, each classless network works independently. A router treats each classless network as a separate network. It does not use the route of a classless network for another classless network even if both classless networks are created from the same classful network.

A router lists all routes for classless networks created from the same classful network under the classful network. It also shows how many routes it knows for classless networks created from the same classful network.

Routing decision and the longest prefix match

If the destination address of a data packet matches only one route of the routing table, the router uses the matched route to forward the data packet. But if the destination address of a data packet matches more than one route of the routing table, the router uses the best route to forward the data packet. To select the best route, the router matches the network bits of the destination address and the address defined in the route. The route which matches the maximum number of network bits is considered the best route. If there is a tie, the router uses the route which belongs to the same subnet.

In our example, the router uses the first route for the third data packet. The first route (via – 30.0.0.0/8) matches the network address 90.0.0.0/8. However, the second route (via 40.0.0.0.2) and the third route (via - 50.0.0.2) also have 90 in the first octet and also match the network address of the destination address (90.0.0.10/8), yet the router does not use them to forward the data packet as they belong to other classless networks.

For the fourth data packet, the router uses the second route. The second route (via – 40.0.0.2) matches 16 network bits. The first route and the third route match 8 network bits.

For the fifth data packet, the router uses the third route. The third route (via – 50.0.0.2) matches 24 network bits. The first route and the second route match 8 network bits.

The following image shows how the router takes the routing decision for the third, fourth, and fifth data packets.

Identifying the route with the longest prefix length mask

There are two ways to identify the route the router will use to forward the packet. These ways are using subnetting math and using the 'show ip route address' command.

To use the subnetting math, use the following steps.

• Identify the routes that match the address.
• If multiple routes match the address, use the route that matches the longest prefix.
• If there is a tie, use the route that belongs to the same subnet or exactly matches the address.

Let's take an example to understand this process.

The following table lists five routes with their subnet prefix and the address they match.

The/32 and /0 are two special subnet prefixes. The /32 matches only one address. The /0 matches all addresses. If /32 prefix matches, the router always uses this route. A route with /32 prefix is known as the host route. The router uses /0 as the last route. A route with /0 prefix is known as the default route. The router uses the default route only when no other route matches.

Now, can you guess the route for the following addresses?

Let's start with the first address.

The first address (10.0.0.1) is available in the address range of the first route (10.0.0.0 – 10.255.255.255) and the last route or the default route (0.0.0.0 – 255.255.255.255). As mentioned earlier, the router uses the default route only when no other route is available. Since a route is available, the router will not use the default route. If we exclude the default route, only the first route will be available for the first address. Thus, the router will use the first route for the first address.

The second address (10.1.0.36) is available in the address range of the first route (10.0.0.0 – 10.255.255.255), second route (10.1.0.0 – 10.1.255.255), and the last route (0.0.0.0 – 255.255.255.255). If we exclude the default route, the first route and the second route remain for the second address. The subnet prefix of the first route is /8. The subnet prefix of the second route is /16. Since /16 is more than /8, the router will use the second route for the second address.

The third address (10.1.1.25) is available in the address range of the first route (10.0.0.0 – 10.255.255.255), second route (10.1.0.0 – 10.1.255.255), third route (10.1.1.0 – 10.1.1.255), and the last route (0.0.0.0 – 255.255.255.255). After excluding the default route, the first route, second route, and third route remain for the third address. Subnet prefixes of these routes are /8, /16, and /24, respectively. Since the router uses the longest prefix to select the best route, the router will use the route with /24 prefix for the third address.

The fourth address (10.1.1.1) is available in the address range of all routes. The fourth route (10.1.1.1/32) with the /32 prefix exactly matches the address. The router will use the fourth route for this address.

The fifth address (20.0.0.1) is available only in the address range of the last or the default route. The router will use this route for the fifth address.

The 'show ip route address' command

If you don't want to do the subnetting math, you can use the 'show ip route address' command. This command prints the route the router will use for the given address. For example, if you want to know which route the router will use for the address 10.0.0.1, you can use the following command.

#show ip route 10.0.0.1

The following image shows some examples of the 'show ip route address' command.

That's all for this tutorial. In this tutorial, we learned how routers take a routing decision.