Recursive Lookup?

[sagar.painuly1]

Hi All ,

Could you all let me know what is Recursive Lookup.

I just want to know it without any regards to any protocol.

As per my understanding :

Routing table for R2:

C - 10.0.0.0/24 -> S3

C - 10.0.1.0/24 -> S2

C - 10.0.2.0/24 -> S0

C - 10.0.3.0/24 -> S0

S - 20.0.0.0/24 -> 10.0.0.2

Now if a packet comes to R2 destined for 10.0.2.1 n/w, recursive lookup will be done something like :

10.0.2.1 >> whole 32 bits on if no match then

10.0.2.0 >> whole 24 bits on if no match then

10.0.0.0 >> whole 16 bits on.Match found.

Packet forwarded to S3 interface.

Please correct me if i am wrong. I just need to know if this is right and if yes how does this happen.

Thanks in advance

Sam               

[fb_webuser]

The recursive lookup, will always be the longest match, /32; then /31; /30, etc.

But you can check this by using the CEF.

Try to use the CEF like this:

show ip cef 10.0.2.1

the CEF entry for this route is the interface that the router decided to send the packets.

Don´t forget that you can have packets forwarded without using the Routing table.

If you use PBR, policy based-routing, you can overide the routing table.

in you example, if you have a

 route-map

saying that the packets to 10.0.2.1 should use the

 next-hop 10.0.3.0/24 

S0, but the recursive lookup on the routing table that Jan mencionet will be wrong.

So the best way to check the forwarding plane is using CEF.

Best Regards

Pedro Avila

---

Posted by WebUser Pedro Seabra Ávila from Cisco Support Community App

[paolo bevilacqua]

You should avoid recursive routing, that is essentially a mistake when it happens.

Make sure next-hope is always directly connected, and things will work always nice and easy.

[Peter Paluch]

Hello Paolo,

You should avoid recursive routing, that is essentially a mistake when it happens.

I respectfully beg to differ here. Recursive routing has a connotation of causing added complexity and decreasing the router's performance, and in naive routing code implementations, that may indeed be so - but again, that is not always the case, and also, the existence of recursive routing entries is not an indication of a mistake per se. Think of BGP - without recursive lookups, it could not work at all. The entire BGP is built on top of recursive routing - the iBGP does not modify the next hop, leaving it at its original value; MPLS L3 VPNs resolve next hops of VRF customer routes to PE identifiers in the global routing table; 6PE and 6VPE resolve IPv6 prefixes to IPv4 nexthops, etc.

It is true that when explaining process-based switching, it can be easily seen why recursive lookups slow down the router - instead of making a single lookup in a routing table and immediately identifying the egress interface, the router has to browse the routing table again (and possibly again and again) until it finds the exit interface. However, when using CEF, the recursion is resolved in the backround during the FIB tree build. So even if a route needs a recursive lookup in the routing table, it most certainly already has all the necessary recursion resolved in the CEF FIB (the only exception to this is, to my best knowledge, BGP PIC). The lookup in the FIB is not recursive even if the underlying routing table contains recursively chained entries.

Make sure next-hope is always directly connected, and things will work always nice and easy.

For static routes, I absolutely agree. Usually, if dynamic routing protocols install recursively chained routes, they know why they do that and they also know how to use them appropriately.

Best regards,

Peter

[paolo bevilacqua]

I respectfully beg to differ here. Recursive routing has a connotation of causing added complexity and decreasing the router's performance, and in naive routing code implementations, that may indeed be so - but again, that is not always the case, and also, the existence of recursive routing entries is not an indication of a mistake per se. Think of BGP - without recursive lookups, it could not work at all. The entire BGP is built on top of recursive routing - the iBGP does not modify the next hop, leaving it at its original value; MPLS L3 VPNs resolve next hops of VRF customer routes to PE identifiers in the global routing table; 6PE and 6VPE resolve IPv6 prefixes to IPv4 nexthops, etc.

Correct, but these are strictly SP type applications, much beyond the scope of normal training for beginners.

Beside, many BGP network also use an IGP to carry peer's connected routes, that resolves the next hop and is a good practice in my opinion.

So I think the correct approach is that when an engineer has reached a CCIE level of knowledge and skill, can be introduced to recursive routing and other advanced features, not before.

[Peter Paluch]

Hi Paolo,

Thank you for your insight!

So I think the correct approach is that when an engineer has reached a  CCIE level of knowledge and skill, can be introduced to recursive  routing and other advanced features, not before.

I guess this depends. I can attest as a teacher that I have students - beginners basically on CCNA level - that are nonetheless capable of grasping the intricacies of recursive routing. It's about their prior knowledge in data structures and algorithms, without doubt. The "CCIE" is too far-fetched, in my opinion - I do not recall learning significantly more about recursive routing as I progressed from CCNP via CCIP to CCIE. But yes, I agree, it is not a topic usually cut out for beginners.

Best regards,

Peter

[sagar.painuly1]

Hi all,

Many thanks for a detailed explanation. It was a concept which my tutor introduced to me in CCNP - Route. I had some confusion in it, hence thought of posting it here.

Thanks again,

Regards

Sam

[Jan Hrnko · Accepted solution]

Hi Sam,

Well I suppose that the term recursive lookup stands for something different. Let me explain it on an example.

Here we got a very simple routing table:

172.16.0.0/24 is subnetted, 2 subnets

C 172.16.1.0 [1/0] via 172.16.2.2

C 172.16.2.0 is directly connected, Serial0/0/0

S 192.168.2.0/24 [1/0]  via 172.16.2.2

S 192.168.3.0/24 [1/0]  via 172.16.2.2

Now, when a packet arrives with destination IP let's say 192.168.2.69, router will find out that a suitable route for such packet is static route 192.168.2.0/24 with the next hop IP address 172.16.2.2

This next hop IP address 172.16.2.2 is then found as directly connected through exit interface Serial0/0/0.

As stated in cisco curriculum:

Every route that references only a next-hop IP address and does not reference an exit interface must have the next-hop IP address resolved using another route in the routing table that has an exit interface. 

So this process is called recursive lookup - when a route table entry references to another IP address and not to a directly connected exit interface. Therefore another lookup has to be made. There can be more lookups, until the route with exit interface specified is found - so that's why it's called recursive.

In your scenario:

Routing table for R2:

C - 10.0.0.0/24 -> S3

C - 10.0.1.0/24 -> S2

C - 10.0.2.0/24 -> S0

C - 10.0.3.0/24 -> S0

S - 20.0.0.0/24 -> 10.0.0.2

When packet arrives destined for 20.0.0.1 recursive lookup will be done like this :

looks up entry for 20.0.0.1

20.0.0.1 >> via 10.0.0.2

looks up entry for 10.0.0.2

10.0.0.2 

send packet through directly connected interface S0

end

Maybe you want to know more about routing table lookup and not the recursive lookup. It just seems to me from the scenario you have provided.

Hope that helps a little bit.

Best regards,

Jan

[Beacon Bits]

Simply, Recursive Lookup is self explanatory 

"Lookup and again lookup in the same routing table and then send to the directly connected or to the next hop of the second lookup that could be a connected interface or next-hop IP address"

Regards,

Shaiq