recursive lookup ?

kaustubhchavan · ‎01-23-2009

wht is recursive look up how router does tht ?

could explain briefly........

Giuseppe Larosa · ‎01-24-2009

Hello Kaustubh,

a recursive lookup happens when a second search in the routing table has to be done.

A typical example is given by BGP that provides a BGP next hop.

The BGP next hop is reported in the routing table but it is not always the real next hop for the local router.

Let's make an example:

We have two routers with iBGP in AS 65000 that use their loopbacks 0 to setup an iBGP session

int loop0

ip address 10.254.254.1 255.255.255.255

router ospf 10

network 10.254.254.1 0.0.0.0 area 0

network 10.10.10.0 0.0.0.255 area 0

router bgp 65000

neigh 10.254.254.2 remote-as 65000

neigh 10.254.254.2 update-source loopback0

Now let's suppose R2 advertise in BGP net 172.16.24.0/24

the BGP information and the routing will say

172.16.24.0/24 B [200/0] via 10.254.254.2

actually the meaning of above is :

packets for net 172.16.24.0/24 follow the same path as ip address 10.254.254.2

the router to be able to forward packets need to do a second lookup (a recursion) to find out how to forward packets:

a sh ip route 10.254.254.2 in this case tells

O [110/2] via 10.10.10.2

and 10.10.10.2 is the ip address of R2 on the LAN segment between them

an entry for 10.10.10.2 exists in the ARP table that points to R2 f0/0 MAC address.

So R1 can build a forwarding table for prefix 172.16.24.0/24 that says :

rewrite packet putting it in an ethernet frame with source MAC R1 f0/0 and Dest= R2 f/0 MAC address.

if instead the prefix 172.16.24.0/24 was advertised in OSPF the routing table would have been:

O [110/2] via 10.10.10.2

in this case a second lookup in routing table is not needed because 10.10.10.2 is already the real next-hop.

This BGP mechanism is actually a great advantage:

on this capability of telling a BGP next hop are based for the example the forwarding of MPLS L3 VPN packets:

for devices in the middle the packets are treated as destinated to the loopback or a remote PE. (MPLS employs a two labels stack for this)

Hope to help

Giuseppe

sarahr202 · ‎01-25-2009

Hi Kaustubh!

"recursive lookup - Method of consulting the routing table to locate the actual physical next hop for a route when the supplied next hop is not directly connected."

let take an example to understand it

let say we have router with following routing table:

s 199.199.199.0/24[1/0]via 199.199.198.1

c 199.199.198.0/24 is directly connected s0

Suppose the router receives a packet destined to 199.199.199.12

Now router look at the destination (199.199.199.12) in the Ip header.

It checks its routing table and find the following entry:

s 199.199.199.0/24 [1/0] via 199.199.198.1

Router determines that in order to forward this packet to its destination 199.199.199.12, it must find out out how to reach next hop 199.199.198.1

Router again consults the routing table ,this time to find the match for 199.199.198.1

Router finds an entry" 199.199.198.0/24 directly connected s0"

Now the router will forward the packet , having found how to reach next hop (199.199.198.1)

This is called recursive look up

If you still need help, just ask