In Cisco IOS packets are forwarded through the router (or Layer 3 switch) by Cisco Express Forwarding (CEF). A data structure called the CEF table contains a list of known IP prefixes and the outgoing interface that packets should be put on in order to get them onwards to their destination. That's well and good. But how do the IP prefixes make it into the CEF table? To answer that question you have to work backwards and understand the order of operations that IOS goes through in order for a prefix to make it into the CEF table.

The answer to the question of what makes it into the CEF table confused me a bit, particularly when working with complex redistribution schemes. I would end up concentrating so much on admin distance (AD) that I would overlook the other, more important elements that went into determining what went into the CEF table. In order to improve my understanding I came up with this order of operations which helps me not only with redistribution, but in pretty much any situation where I'm trying to do traffic engineering.

You will not find this order of operations on cisco.com or in any Cisco Press book. It's my own creation. It's meant to help conceptualize what IOS is doing and is not necessarily an accurate depiction of the IOS routing subsystem.

IGP/BGP Best-Path Decision Process — Every routing protocol (OSPF, EIGRP, IS-IS, BGP, even good old RIP) has its own unique process for determining which of the routes they've learned will be considered the best and passed down to the RIB. OSPF has the Dijkstra algorithm, EIGRP has DUAL, BGP has a multi-step process, and RIP pretty much just looks for the lowest metric. Each protocol only looks at its own routes. OSPF doesn't look at what EIGRP has in its database. OSPF only looks at its own routes and decides, "of the routes I've learned myself, which of these is the best?" If a particular route was only learned via 1 neighbor, then as long as that route is determined to be valid by the protocol it's automatically passed to the RIB (classic example: a BGP route with a NEXT_HOP that is unreachable is invalid and is not passed to the RIB even if it's technically the best route). If a particular route is learned via more than 1 neighbor, then the protocol has to decide which one is the best based on its own best-path process.

Every routing protocol running on the box, static and "connected" included, pass their best routes down to the RIB. They're at the Big Show now where they compete with routes from all the other protocols in a contest for which will be installed in the CEF table.

Longest Prefix Match — IOS always tries to find and use the most precise route to a destination. As an example, if IOS has two routes, 192.168.0.0/16 and 192.168.1.0/24 and a packet comes in destined to 192.168.1.100, IOS is going to match on the /24 and forward the packet based on the information associated with that route. This rule is true even if the /16 has an AD of 1 and a metric of 1 (making it the best of the best); longest prefix match always wins. If you can inject a route with a longer prefix into the routing table, then it doesn't matter what the route's AD or metric is because longest prefix match short-circuits those checks.

Lowest Admin Distance — The AD is used to decide which routing protocol is trusted more in the case where the same route (with the same prefix length, of course) is learned via more than one protocol and they all pass that route to the RIB. The RIB needs to decide which source for this route is most preferred. Take note that most collateral refers to the AD being a property of the protocol, and indeed, that's where the AD is configured, under the routing protocol, however every route is actually tagged with an AD. And to that end, it's possible to modify the AD for specific routes and not others or for routes learned via a particular neighbor. At any rate, the route that is passed to the RIB tagged with the lowest AD will be preferred.

Discard with AD == 255 — The AD of 255 has a special meaning. It basically means "don't use this route". If a route with an AD of 255 makes it this far in the decision process, it's actually tossed aside and not sent to the CEF table. As a result, there is no entry in the CEF table for that prefix.

At this point all of the decision criteria has been evaluated and, all things being equal, the prefixes now exist in the CEF table and traffic can be forwarded through the router/switch.

By looking at this order of operations, you can see that an element such as AD does play a part in the decision process, but it's not the most important factor. By visualizing the order of operations as a flowchart, it makes it easier to see the relationship between the different decision points and also aids in understanding why a particular route is installed in the CEF table, or maybe more importantly, why a particular route is not installed in the CEF table and some other route is installed instead.

Disclaimer: The opinions and information expressed in this blog article are my own and not necessarily those of Cisco Systems.