The aim of this article is to discuss the importance of Recursive Lookup in BGP. First of all we need to understand the purpose of the recursion method and find some evidence of its use in everyday life.
Recursion is based on self-reference and can be found in many disciplines. For instance, in linguistics, a recursive acronym is an acronym that refers to itself. The notorious example is the GNU acronym that is explained as GNU’s Not Unix. In computer programming the recursion function calls itself. For instance, in the Python script below, the function factorial is placed within its own definition, calling itself with a modified argument that is decreased by one. The if condition n equals 1 represents a base case here. Its purpose is to stop the recursion, otherwise we would end up with a RecursionError: the maximum recursion depth being exceeded or even worse, exhausting resources. The benefit of using the recursion approach is in dividing a single task (factorial computing) into sub-tasks of the same type
if n == 1:
return n * factorial(n-1)
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
|Note: The recursive routing table lookup described above is only valid for the switching process when a CPU is involved with every routing decision. In this case, browsing the routing table again and again until the exit interface is found slows down the router. The modern switching method such as Cisco Express Forwarding (CEF) builds the Forwarding Information Base (FIB) that contains pre-computed reverse lookups (IP address, Next-hop IP address, Next-hop Mac address and the egress port). Therefore, the lookup in the FIB is not recursive even if the underlying routing table contains recursively chained entries.
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 18.104.22.168/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 22.214.171.124/32 contains a reference to that next-hop address 126.96.36.199 (Picture 5).
Picture 5: Network 188.8.131.52/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 184.108.40.206 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 220.127.116.11 is Reachable Over OSPF Learned Route
Picture 7 confirms that the route 18.104.22.168/32 is recursive via 22.214.171.124 with the next-hop IP address 10.0.0.1 and the outgoing interface GigabitEthernet0/0.
Picture 7: Packet to 126.96.36.199 is CEF Switched
Recursion in computer science is a method of solving a problem where a solution depends on solutions to smaller instances of the same problem . 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.