We are going back to networking basics with this post. In few lines below you will find most important theory that makes network gear do its job.
The main router job is to making routing decisions to be able to route packets toward their destination. Sometimes that includes recursive lookup of routing table if the next-hop value is not available via connected interface.
Routing decision on end devices
Lets have a look at routing decision that happens if we presume that we have a PC connected on our Ethernet network.
If one device wants to send a packet to another device, it first needs to find an answer to these questions:
- Is maybe the destination IP address chunk of local subnet IP range?
- If that is true, packet will be forwarded to the neighbour device using Layer 2 in the ARP example below.
- If that is not the case, does the device network card configuration include a router address through which that destination can be reached? (default gateway)
- Device then looks at his local ARP table. Does it include a MAC address associated with the destination IP address?
- If the destination is not part of the local subnet, does the local ARP table contain the MAC address of the nearest router? (MAC address to IP address mapping of default gateway router)
Routing decision on a router
Contrary to user end device like iPhone or Notebook which usually have only one way out of local network using broadband home router as Internet access default gateway, routers across the network usually have multiple network subnets each connected to one of their interfaces. That makes them able to route traffic out on different interfaces forwarding that traffic across different paths. If router receives the packet that is destined to some destination IP address it goes through similar list of questions like the end host in the example above, but it can became more complicated. Router receives the packet, opens the IP header and reads the destination IP address. After that the questions for him to solve are these:
- Is maybe the destination IP address chunk of one of the local subnets that this router has on one of his interfaces?
- If that is true, packet will be forwarded using the Layer 2 described in the question No2 below.
- If that is not the case, Router needs to make a route lookup on his routing table in order to find the longest match for this IP address subnet. Each routing table entry has the destination subnet defined together with next-hop IP address which needs to be used in order to forward the packet to that destination network. Router makes that routing table lookup in order to decide out on which interface (towards which next-hop address) he will need to forward the packet so that IP destination can be reached.
- Device then looks at his local ARP table.
- Does it include a MAC address associated with the destination IP address?
- If there is no ARP table entry for that IP address it will need to broadcast an ARP request to get this destination IP host response with his MAC address.
Route recursion
Routing recursion is a recursive search process of routers routing table where the next-hop IP address is wanted to route packed towards its destination but when found it is not part of any directly connected network.
Usually, Router checks the destination address inside packets IP header and makes the decision based of few steps described in the routing example above.
When router finds longest match route for wanted destination, the next-hop value for this prefix is read and checked. If that longest match next-hop IP address value is a connected route then outgoing interface is known and layer 2 address is found which enables the frame to be built and transition of the packet can be done towards the destination.
If the next-hop that IP does not exist on any of the ends of connected interfaces, additional routing lookups must be done for an outgoing interface to be found. This additional routing table lookups are known as recursive lookups.
Example
Here is an example that will show the recursive lookup within a simple topology and routing table from R1:
R1(config)#do sh ip route 10.0.0.0/8 is variably subnetted, 2 subnets, 2 masks C 10.10.1.0/24 is directly connected, FastEthernet0/0 L 10.10.1.1/32 is directly connected, FastEthernet0/0 S 192.168.1.0/24 [1/0] via 10.10.1.2 S 192.168.2.0/24 [1/0] via 10.10.1.2
When packet arrives with destination IP 192.168.2.111, router R1 will make a routing table lookup and it will find that a route for that packet is static route 192.168.2.0/24 with the next hop 10.10.1.2
That next hop IP 10.10.1.2 is then found as a part of directly connected subnet 10.10.1.0/24 through exit interface FastEthernet0/0.
Process used by router R1 in the example above is called recursive lookup because router needed to go across the routing table twice in order to find the out interface.
When a route table entry shows next-hop IP address and not a directly connected exit interface, recursive lookup is needed. Therefore another lookup has to be made. There can be more lookups, until the route with exit interface specified is found.
Please comment if you have any info regarding this case.
Unintentional was the part with “This additional routing table lookup process is known as recursive lookup”. It is true, Recursive means keep looking until you find next-hop and outgoing interface or drop the packet, so it is correct to say: “This additional routing table lookups are known as recursive lookups.” taking into account more of them if more of them are needed not only the first additional lookup.
Also, giving the example at the beginning about Routing decision on end devices did not state clearly that is an example for a device connected to Ethernet network. I made that clear now.
Outdated part was my last tip at the end of the article saying that “It is always better in order to get the best routing performance that every route table entry is defined with outgoing Interface and not next-hop address”. I’m silly, we have route-cache mechanisms like Cisco CEF in our network devices which enable us to skip routing table lookup every time same destination is needed. This TIP is about network devices older than me. I removed that last paragraph. The reasons why it does not matter is explained in this one: How can router decide so fast?
Thanks Dmitry
Thanks for the article, but there several things that are not exactly true.
“Device then looks at his local ARP table.
Does it include a MAC address associated with the destination IP address?
If there is no ARP table entry for that IP address it will need to broadcast an ARP request to get this destination IP host response with his MAC address.
”
It is assumed that the media between two routers is always Ethernet what in many cases is not true.
“This additional routing table lookup process is known as recursive lookup”
No, it’s always called recursive lookup. Recursive means keep looking until you find next-hop and outgoing interface or drop the packet.
“It is always better in order to get the best routing performance that every route table entry is defined with outgoing Interface and not next-hop address. The best thing to do is to make sure that next-hop IP address is always directly connected and we will be sure that routing works nicely.”
No. It does not add any routing performance. CEF will recalculate outgoing interface/next-hop anyways.
“We can probably state that recursive routing when it happens, is basically a mistake in our routing table.”
No, the first example that comes to my mind is BGP.
Dmitry,
Just wanted to let you know that I corrected the article after you drew my attention to some errors inside.
Thanks again,