What is route recursion

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:

  1. 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.
  2. 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:

Route recursion

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.

REFERENCE and UPDATE NOTICE:
For further reading on routing table topics I have one article particularly related to this one. Is an older article here which describes the difference between static route defined with next-hop address and one defined with out interface:  Difference between defining static routes with next-hop address or exit interface

Please comment if you have any info regarding this case.

UPDATE on 22 Dec 2015:
Thanks to Dmitry I took some time and corrected several unintentional errors and outdated parts of the articles that were not relevant in network devices today.

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

2 Comments

  1. Dmitry Figol December 22, 2015
    • Valter Popeskic December 22, 2015

Leave a Reply