irp demo
Request Noction IRP Demo

Request a personalized demo/review session of our Intelligent Routing Platform

irp trial
Start Noction IRP Trial

Evaluate Noction IRP, and see how it meets your network optimization challenges

nfa demo
Noction Flow Analyzer Demo

Schedule a one-on-one demonstration of our network traffic analysis product

nfa trial
Free Noction Flow Analyzer Trial

Test drive NFA today with your own fully featured 30-day free trial

Recursive Lookup in BGP

Recursive Lookup BGPThe 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.

def factorial(n):
 if n == 1:
  return 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.

Recursion example technology nested virtualization

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.Routing Table

Picture 2: Routing Table

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

Packet to is CEF-Switched

Picture 3: Packet to 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.

 Network Topology with iBGP Peers

Picture 4: Network Topology with iBGP Peers

The BGP route 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 contains a reference to that next-hop address (Picture 5).

Network in BGP Routing Table of R2

Picture 5: Network 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 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.

The next-hop IP Address is Reachable Over OSPF Learned Route

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

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

Packet to is CEF Switched

Picture 7: Packet to 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 [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.

Boost BGP Performance

Automate BGP Routing optimization with Noction IRP

bgp demo


You May Also Like

ACK and NACK in Networking

ACK and NACK in Networking

In networking, communication between devices relies on the efficient exchange of data packets. Among the essential...

BGP and asymmetric routing

BGP and asymmetric routing

What is asymmetric routing? Asymmetric routing is a network communication scenario where the forward and reverse paths...