Routing Decision Longest Match Explained

Routers connect different networks. To connect different networks, they learn all network routes and store them in their routing tables. They use a separate entry for each route. A routing table entry contains the network address and the route to reach it.

When a router receives a data packet, it reads its destination address and compares it against the routing table's entries. It may find no matching entry, one matching entry, or multiple matching entries.

• If it finds no matching entry, it discards the data packet.
• If it finds only one matching entry, it forwards the data packet along the route defined in that entry.
• If it finds multiple matching entries, it selects the entry that matches the maximum bits with the destination address and forwards the data packet along the route defined by that 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, routing is the process by which a router determines the path to forward data packets to a particular destination.

How routers make routing decisions

The following image shows the routing table entries for router R1 and the network in which R1 is located.

Suppose R1 receives five data packets. The table below 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 to different classless networks.

A classful network can be divided into smaller classless networks. 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.

If the destination address of a data packet matches only one route in the routing table, the router uses that route to forward the packet. However, if the destination address of a data packet matches multiple routes in the routing table, the router selects the best route to forward it. To select the best route, the router compares the network bits of the destination address with the route's network mask. The route that matches the maximum number of network bits is considered the best route. If there is a tie, the router uses the route that belongs to the same subnet.

In this 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. Although the second route (via 40.0.0.0.2) and the third route (via 50.0.0.2) both have 90 in the first octet and match the destination network (90.0.0.10/8), 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 and third routes 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 and second routes match 8 network bits.

The following image shows how the router makes routing decisions 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: subnetting math and the 'show ip route' command.

To use subnetting math, follow these steps.

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

Example

The following table lists five routes, their subnet prefixes, and the addresses they match.

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

Determine the route the router will take for the following addresses:

10.0.0.1, 10.1.0.36, 10.1.1.25, 10.1.1.1, and 20.0.0.1.

The first address (10.0.0.1) is within 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). A 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 you exclude the default route, only the first route is left 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), the second route (10.1.0.0 – 10.1.255.255), and the last route (0.0.0.0 – 255.255.255.255). If you exclude the default route, the first and second routes are left 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 within the address range of the first route (10.0.0.0 – 10.255.255.255), the second route (10.1.0.0 – 10.1.255.255), the 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, second, and third routes remain for the third address. The subnet prefixes for these routes are /8, /16, and /24, respectively. Since the router uses the longest prefix to select the best route, it will use the route with the/24 prefix for the third address.

The fourth address (10.1.1.1) is available in all routes' address ranges. 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

The 'show ip route [address]' command shows the route the router will use for the given address. For example, to identify the route for the address 10.0.0.1, use the following command.

#show ip route 10.0.0.1

The following image shows a few moe examples of this command for other addresses.

Conclusion

Routers make routing decisions by comparing the destination address of incoming data packets against entries in their routing tables. If multiple matching routes exist, the router selects the one with the longest prefix match. The host route (/32) and the default route (/0) are special cases. Routers have special rules for these routes. If a host route matches a packet’s destination address, the router always uses it. If a default route is available, the router uses it to forward a packet only when no other route matches its destination address.