longest prefix match algorithm

Best Route, Routing Table Terms, and Lookup Process

Best Route, Routing Table Terms, and Lookup Process

/ /

The best route is the longest match route to the destination IP address. The route lookup process matches the destination IP address with the route available in the routing table and chooses the longest to match route as the forwarding route.

To match the destination IPv4 address of a packet with the routes in the routing table, the minimum number of far-left bits must match the IPv4 address of the packet and the route in the routing table.

The router found the best route in the routing table for the packet using the subnet mask. The data packet never contains the subnet mask in the packet header.

The best route is the longest match or the most significant number of equivalent far-left bits. The figure below illustrates the maximum bits match, which is the best route for the packet.

best route

If the router receives a packet destined for 172.16.2.100, the router has three possible routes for the packet: 172.16.0.0/16, 172.16.1.0/24, and 172.16.2.0/24. Look at the table above in the figure to understand the most prolonged match routing process.

172.16.2.0/24 has the longest match, so the router has selected this route as the best route and forwards the packet to Ethernet 1/1. For any of these routes to be considered a match, there must be at least the number of matching bits indicated by the route’s subnet mask.

Routing Table Terms

The Cisco IP routing table is a hierarchical structure that speeds up the lookup process when locating routes and forwarding packets. Within this structure, the hierarchy includes:

  • Ultimate route
  • Level1 route
  • Level1 parent route
  • Level2 child routes

Ultimate Route

This route contains either a next-hop IPv4 address or an exit interface. Directly connected, dynamically learned, and local routes are also ultimate routes. The figure below illustrates the ultimate routes.

Level 1 Route

The route that is equal to a subnet mask or less than the classful mask of the network address. The source of the level 1 route can be a directly connected network, a static route, and a dynamic routing protocol. Therefore, a level 1 route is also the ultimate route. The type of level 1 route included:

  • Network route– A route with a subnet mask equal to the classful network is called a network route.
  • Default route– This is a static route for the packet whose destination is unknown to the router. The address of the default static route is 0.0.0.0/0.
  • Supernet route– This route has a network address with a maskless than the classful mask.

Level 1 Parent Route

The Level 1 parent route is a Level 1 network route that is subnetted. A parent route can never be an ultimate route. The figure below illustrates the level 1 parent route highlighted.

The level 1 parent route is the heading for the specific subnets. Each entry displays the classful network address, the number of subnets, and the number of different subnet masks.

Level 2 Child Route

This is a subnet of a classful network address. As illustrated in Figure 1, a level 1 parent route is a level 1 network route that is subnetted. A Level 1 parent route contains Level 2 child routes, as shown in the Figure below.

There are two level 2 child routes for level 1 parent route 10.0.0.0 and three level 2 child routes for level 1 parent route 172.16.0.0. The source of a level 2 route can be a directly connected network, a static route, or a dynamically learned route. Level 2 child routes are also ultimate routes.

Route Lookup Process

When a router receives a packet on an interface, the router examines the packet’s header, identifies the destination IPv4 address, and proceeds through the router lookup process.

Step-1

  1. The router examines level 1 routes, network routes, and supernet routes for the best match with the destination address of the IP packet.
  2. If the best match is a level 1, ultimate, or supernet route, the packet is forwarded to the destination using the best match route.
  3. If the best match is a level 1 parent route, continue to the next step.

Step-2

  1. The router examines level 2 child routes of the level 1 parent route for the best match.
  2. If a match with a level 2 child route is found, the router forwards the packet to the destination using this route.
  3. Continue to the next step if no match is found with any level 2 child routes.

Step-3

  1. The router starts looking up the best match in level 1 supernet routes in the routing table, including the default route.
  2. If there is now a minor match with a level 1 supernet or default route, the router uses that route to forward the packet.
  3. The router drops the packet if a match to the destination is not found with any route in the routing table.