Is the default route looked at first or last?

[ChuckHaynes]

Does a device look at the default route first and then look to see if a more specific route is listed that will trump it... or does a device look through only specific routes and then look at the default route last? I understand that in the end, it may not technically matter, as the traffic will go to the default route anyway (if it doesn't see anything else more specific), but I was just trying to understand the correct operation a device performs. I notice that 0.0.0.0 0.0.0.0 x.x.x.x is always listed first in the config, but I assume that's because the config lists the routes in numerical order (thus 0.0.0.0 would be first). However, when I have done a "sh ip route", I have seen 0.0.0.0 0.0.0.0 x.x.x.x at the top on some devices, at the bottom on some devices, and in the middle on some devices?

[Farooq Muhammad]

The most specific route is matched first in terms of the longest match , then follows the Administrative distance and finally if no route is found for a particular destination in the routing table the last resort is default route which is the least possible specific route for all ipv4 address space i-e 0.0.0.0/0.

H.T.H

[Jon Marshall]

Just a slight correction to what you said.

AD is used as a factor in deciding which routes to install the IP routing table. It is used when you have multiple routes for the same prefix and mask and they come from different sources eg. statics, different dynamic routing protocols.

It does not come before the default route because the default route is still a prefix with a mask.

In terms of which route is used in the IP routing table to forward packets AD doesn't come into it all because it has already been decided which are the best routes.

So it is simply a question of finding the most specific match which may or may not be the default route.

Jon

[ChuckHaynes]

I appreciate the replys, but I'm not sure they answer my exact question. I am questioning whether the device is made aware of the default route before or after it is made aware of any specific routes. For example: Does a router look at the config and see 0.0.0.0/0 listed before any other routes (because technically it is numerically listed first in the config). I understand in the end it will see all the routes anyway, and then send it to the best match - but I am trying to determine if the router "knows" the default route BEFORE it looks through the rest of the routes?  Also, does anyone have any idea about why some devices list 0.0.0.0/0 at the top of the routing table, while others list it in the middle or the bottom? Thanks.

[Jon Marshall]

I don't really understand your question in terms of the device being aware ?

The router doesn't look at the configuration at all when doing a route lookup, it looks at the IP routing table.

That is all that matters when it comes a routing decision.

Can you clarify exactly what you mean ?

Jon

[ChuckHaynes]

I guess what I'm asking is specifically how the router looks at the routing table when a route lookup is requested. Does it do it line by line starting at the top or not? For example: A router sees the request for 172.16.13.1. Does it start at the top and say "Well, my default route is 10.10.10.3. If I don't see anything more specific, then I will send it out that way." Then it continues on down the table and says "Oh wait, I do see a more specific route for 172.16.13.1, so I will send it out that way instead." ----- Or does the router ignore the default route (initially) and start with the specific routes. Then after it exhausts the entire specific routing table and doesn't find a route, it says "Well, I couldn't find a specific route for the lookup, I will now go look at the default route and send it out that way."

0.0.0.0 0.0.0.0 10.10.10.3

192.168.1.0 255.255.255.0 10.10.10.1

172.16.13.1 255.255.255.255 10.10.10.2

[Jon Marshall]

You are basically asking whether it goes through the routing table from top to bottom or in a different order.

The short answer is I don't really know but that it makes no difference, it will still end up with most specific match however it does it.

Jon

[ChuckHaynes]

Ok, thank you. We were having this debate in CCENT class last week, and no one really knew the answer either. But you are correct, it doesn't really matter in the end - as it will take the most specific route. I was just trying to determine exactly how it went about the lookup, but that may be a moot point.

Do you have any idea why different devices might list the 0.0.0.0 line at different places in the routing table when you do a 'sh ip route'? Again, I'm not sure that it really matters. It's just something that I noticed.

[Jon Marshall · Accepted solution]

I just did a few quick searches and found this thread on CLN (Cisco Learning Network) which discusses a similar thing.

There is no definitive answer which is not unsurprising considering IOS is proprietary but there are references to hash tables for both the order of routes and for the lookups -

https://learningnetwork.cisco.com/thread/15433

Jon

[ChuckHaynes]

Thanks for the information and the link. I believe this is the best answer that I'm going to find.

[Jon Marshall]

Bear in mind that routers and L3 switches use CEF for actually forward the traffic so it doesn't use the IP routing to do route lookups unless there is no CEF entry.

I do understand your question, it's just that it's not something I have every really thought about too much.

It could be something along the lines of finding the first route that matches and then if a more specific one was found using that one etc. until it got through the routing table.

Although I suspect they use more efficient algorithms than that.

Jon

[Peter Paluch · Accepted solution]

Jon and Chuck,

You may be interested in knowing that the order of routes in which the routing table is displayed has changed between IOS versions 12.4T and 15.x.

In 12.4T, the order would be similar to this:

R1(config-if)#do show ip route
Codes: C - connected, S - static, R - RIP, M - mobile, B - BGP
       D - EIGRP, EX - EIGRP external, O - OSPF, IA - OSPF inter area
       N1 - OSPF NSSA external type 1, N2 - OSPF NSSA external type 2
       E1 - OSPF external type 1, E2 - OSPF external type 2
       i - IS-IS, su - IS-IS summary, L1 - IS-IS level-1, L2 - IS-IS level-2
       ia - IS-IS inter area, * - candidate default, U - per-user static route
       o - ODR, P - periodic downloaded static route

Gateway of last resort is not set

     1.0.0.0/24 is subnetted, 8 subnets
C       1.0.1.0 is directly connected, Loopback0
C       1.0.0.0 is directly connected, Loopback0
C       1.0.3.0 is directly connected, Loopback0
C       1.0.2.0 is directly connected, Loopback0
C       1.0.5.0 is directly connected, Loopback0
C       1.0.4.0 is directly connected, Loopback0
C       1.0.7.0 is directly connected, Loopback0
C       1.0.6.0 is directly connected, Loopback0

The ordering indeed corresponds to the order in which the individual networks were stored in the hash table. The hashing function itself is very simple: the XOR of the octets in the network prefix part:

1 ^ 0 ^ 1 = 0
1 ^ 0 ^ 0 = 1
1 ^ 0 ^ 3 = 2
1 ^ 0 ^ 2 = 3
1 ^ 0 ^ 5 = 4
1 ^ 0 ^ 4 = 5
1 ^ 0 ^ 7 = 6
1 ^ 0 ^ 6 = 7

The basic idea behind this roots back in the classful routing. Whenever a packet came in, the router first determined the class of the destination IP address (A, B, or C). Therefore, the router first looked up the entry for the classful (major) network itself. In my output, it is the sole network described as "1.0.0.0/24" which really says: "I am the first-level network entry for 1.0.0.0, obviously class A, and all known subnets of this range have their netmask set to /24". This first-level table entry for 1.0.0.0 then pointed to second-level hash table that was sorted by XORing the first /24 bits of each known subnet of the 1.0.0.0 major network. That is the computation I've performed above. Notice that the output of the show ip route follows this ordering. If I had a slightly more complex routing table, the order would be:

R1(config-if)#do sh ip route
Codes: C - connected, S - static, R - RIP, M - mobile, B - BGP
       D - EIGRP, EX - EIGRP external, O - OSPF, IA - OSPF inter area
       N1 - OSPF NSSA external type 1, N2 - OSPF NSSA external type 2
       E1 - OSPF external type 1, E2 - OSPF external type 2
       i - IS-IS, su - IS-IS summary, L1 - IS-IS level-1, L2 - IS-IS level-2
       ia - IS-IS inter area, * - candidate default, U - per-user static route
       o - ODR, P - periodic downloaded static route

Gateway of last resort is not set

     1.0.0.0/24 is subnetted, 8 subnets
C       1.0.1.0 is directly connected, Loopback0
C       1.0.0.0 is directly connected, Loopback0
C       1.0.3.0 is directly connected, Loopback0
C       1.0.2.0 is directly connected, Loopback0
C       1.0.5.0 is directly connected, Loopback0
C       1.0.4.0 is directly connected, Loopback0
C       1.0.7.0 is directly connected, Loopback0
C       1.0.6.0 is directly connected, Loopback0
     172.19.0.0/24 is subnetted, 4 subnets
C       172.19.3.0 is directly connected, Loopback0
C       172.19.2.0 is directly connected, Loopback0
C       172.19.1.0 is directly connected, Loopback0
C       172.19.0.0 is directly connected, Loopback0
     172.20.0.0/24 is subnetted, 4 subnets
C       172.20.0.0 is directly connected, Loopback0
C       172.20.1.0 is directly connected, Loopback0
C       172.20.2.0 is directly connected, Loopback0
C       172.20.3.0 is directly connected, Loopback0
     192.168.0.0/25 is subnetted, 2 subnets
C       192.168.0.0 is directly connected, Loopback0
C       192.168.0.128 is directly connected, Loopback0

Here, the major networks are sorted in increasing order but the subnets of each major network follow the order given by the hashing function. Sometimes, the hashing function preserves their apparent increasing order, in other cases, it causes the networks to be displayed in a seemingly haphazard order.

In IOS 15.x, probably also related to the removal of the route cache (fast switching), the routing table is automatically displayed in the increasing order of all network entries:

Router(config-if)#do show ip route | ex ^L
Codes: L - local, C - connected, S - static, R - RIP, M - mobile, B - BGP
       D - EIGRP, EX - EIGRP external, O - OSPF, IA - OSPF inter area
       N1 - OSPF NSSA external type 1, N2 - OSPF NSSA external type 2
       E1 - OSPF external type 1, E2 - OSPF external type 2
       i - IS-IS, su - IS-IS summary, L1 - IS-IS level-1, L2 - IS-IS level-2
       ia - IS-IS inter area, * - candidate default, U - per-user static route
       o - ODR, P - periodic downloaded static route, H - NHRP, l - LISP
       a - application route
       + - replicated route, % - next hop override

Gateway of last resort is not set

      1.0.0.0/8 is variably subnetted, 16 subnets, 2 masks
C        1.0.0.0/24 is directly connected, Loopback0
C        1.0.1.0/24 is directly connected, Loopback0
C        1.0.2.0/24 is directly connected, Loopback0
C        1.0.3.0/24 is directly connected, Loopback0
C        1.0.4.0/24 is directly connected, Loopback0
C        1.0.5.0/24 is directly connected, Loopback0
C        1.0.6.0/24 is directly connected, Loopback0
C        1.0.7.0/24 is directly connected, Loopback0
      172.19.0.0/16 is variably subnetted, 8 subnets, 2 masks
C        172.19.0.0/24 is directly connected, Loopback0
C        172.19.1.0/24 is directly connected, Loopback0
C        172.19.2.0/24 is directly connected, Loopback0
C        172.19.3.0/24 is directly connected, Loopback0
      172.20.0.0/16 is variably subnetted, 8 subnets, 2 masks
C        172.20.0.0/24 is directly connected, Loopback0
C        172.20.1.0/24 is directly connected, Loopback0
C        172.20.2.0/24 is directly connected, Loopback0
C        172.20.3.0/24 is directly connected, Loopback0
      192.168.0.0/24 is variably subnetted, 4 subnets, 2 masks
C        192.168.0.0/25 is directly connected, Loopback0
C        192.168.0.128/25 is directly connected, Loopback0

Whatever the order of displayed routes is, however, this has absolutely no bearing on what order the routing table is searched in. For routing table lookups, the only rule that matters is the obligatory longest-prefix-match. Whether you keep the routing table internally sorted according to the netmasks (all /32 networks, then all /31, /30, ..., /2, /1, /0) and then start on the top and take the first match that will obviously be the longest available, or whether you transcribe it to a tree-like structure and perform prefix lookups in this tree (which is exactly what CEF/FIB does), the results must be the same. Keep in mind that displaying the contents of a routing table is different from performing lookups in it. For tree-like structures, there even isn't a single way of displaying the contents, as there are multiple algorithms to list the contents of a tree (depth-first, breadth-first, pre-order, in-order, post-order)...

In any case, the default route, no matter where it shines in the show ip route output, is always tried as the very last routing table entry. There can be no exception to this rule, regardless of which vendor is involved. Otherwise, we'd be out of the basic paradigm of IP routing.

Best regards,
Peter

[Jon Marshall]

Quoting Chuck  "I believe this is the best answer that I'm going to find"

Apparently not :-)

Great answer as usual Peter.

Jon

[ChuckHaynes]

hehe :)