Recursive Lookup in BGP

def factorial(n):
 if n == 1:
  return 1
 else:
  return n * factorial(n-1)

print(factorial(5))

120

In virtualization technology, the nested virtualization represents another recursion example where a virtual machine is running inside of another virtual machine of the same type. Another funny example of a recursion can be found in the architecture of a Matryoshka doll, also known as a Russian nesting doll. It is a set of wooden dolls of decreasing size placed one inside another.

Picture 1: Russian Doll

Recursive Route Lookup

The Recursive Route Lookup follows the same logic of dividing a task into subtasks of the same type. The device performs its routing table lookup again and again until it finds the ongoing interface to reach a certain network. The routing table containing recursive chained entries is depicted in Picture 2.

Picture 2: Routing Table

Picture 3 illustrates the list of recursive entries for the 192.168.1.0/24 network. In order to forward a packet to the destination IP address of 192.168.1.100, the router performs a lookup of the routing table. The route 192.168.1.0/24 is the best-match with the next-hop IP address 192.168.2.254. Now, the routing table is looked up again for 192.168.2.254 and the route 192.168.2.0/24 is matched with the next-hop IP address 192.168.3.254. Again, the routing table is browsed to find the  best match for the next-hop IP 192.168.3.254. The route 192.168.3.0/24 is matched with the next-hop IP 10.0.0.2/24. Finally, the route 10.0.0.0/30 is matched and the packet is forwarded over the egress interface Gi0/0 towards the destination.

Picture 3: Packet to 192.168.1.1 is CEF-Switched

Recursive Lookup in BGP

So far, we have explained the concept of recursion and the recursive route lookup.

But how is the recursive lookup applied in BGP and why do we need it?

The main issue with BGP is that neighbors do not have to be directly connected and they might by located several hops away. Without the recursive lookups, BGP could not work as the entire BGP is built on top of recursive routing. iBGP does not modify the next hop, leaving it at its original value. Therefore when the router performs a route recursion / lookup it can fail if there is no IGP route to the next-hop address which is advertised with the BGP prefix.

Let’s have a look at a simple network topology depicted in Picture 4. The routers R2 and R3 are iBGP peers in AS 64500.

Picture 4: Network Topology with iBGP Peers

The BGP route 33.33.33.33/32 is installed into the routing table of the router R2 only if the IP address of the next-hop attribute is reachable based on the information already stored in the routing table. The installed BGP route 33.33.33.33/32 contains a reference to that next-hop address 3.3.3.3 (Picture 5).

Picture 5: Network 33.33.33.33/32 in BGP Routing Table of R2

The network 33.33.33/32 is reachable via an IP-address, which is not directly connected. The physical interface is not located so the BGP route is installed in the IP routing table without any information of the outgoing interface. But how does the R2 find out the outgoing interface? The router makes a recursive lookup to find the BGP next-hop in the routing table. A BGP next-hop IP address must be reachable in order to use a BGP route. Reachability information is usually provided by IGP. The BGP next-hop 3.3.3.3 is found in the routing table of R2, known via OSPF and the outgoing interface is GigabitEthernet0/0 (Picture 6). The first route lookup checks whether the destination prefix is in the routing table and if so, then a recursive lookup is performed for its next-hop IP address since the next hop address is not a directly connected interface. Therefore, the BGP recursion process is – BGP route – IGP Route – Connected interface.

Picture 6: The next-hop IP Address 3.3.3.3 is Reachable Over OSPF Learned Route

Picture 7 confirms that the route 33.33.33.33/32 is recursive via 3.3.3.3 with the next-hop IP address 10.0.0.1 and the outgoing interface GigabitEthernet0/0.

Picture 7: Packet to 33.33.33.33 is CEF Switched

Conclusion:

Recursion in  computer science is a method of solving a problem where a solution depends on solutions to smaller instances of the same problem [2]. BGP recursive route lookup allows to use the next-hop attribute to find a path to a network that the IGP is aware of. Without the recursive lookup the Border Gateway Protocol would not work, because BGP is built on top of recursive routing.