The Need for CEF(peed) – Part 1

Before I even get started – yes, I know that is probably the worst effort you’ve ever seen someone put into doctoring a graphic.  And maybe into a play-on-words as well.  But trust that what it lacks in artistic prowess and ingenuity, it makes up for in relevance, because CEF is all about one thing – speed!  Plus, it’s far more family-friendly than my alternative theme: “Let’s talk about CEF, Baby”

As far as the exam objectives go, here’s what we’re covering:

1.1.b   Identify Cisco express forwarding concepts
1.1.b (i)   RIB, FIB, LFIB, Adjacency table

CEF is one of those topics that, in the past, I’ve learned just enough about to know that I should know more.  I knew that it offered performance enhancements when it is turned on, and that it keeps some extra tables that are in addition to the standard routing table and CAM or MAC table, but that’s honestly about it.  I’m glad to have had the chance to dig in deeper now though, as it’s a fascinating topic.  The need for CEF comes from the fact that these two tables (routing table and CAM table), while we live and die by them for troubleshooting, they are by themselves terribly inefficient without the help of CEF.

The Need for CEF

Think about the routing process without CEF – say a router receives a packet destined to 192.168.1.1.  What does the router do?  The router first looks in its routing table, then calculates the best match for the address, and notes the next hop address for that routing table entry.  The router then checks its MAC table to see if it knows the MAC address for that next hop address.  If it doesn’t, it ARPs for it, and then stores the MAC for that next hop in its MAC table.  Then, the router creates a brand new ethernet frame in which to encapsulate the packet.  Thankfullly, the router caches the MAC address that it learned from the ARP process because it would be TERRIBLY inefficient to have to ARP for the MAC associated with that IP every single time it receives a packet destined for that address.  We accept the need to cache MAC addresses without second thought because it’s a concept we’ve been comfortable with since the days when we first started logging into routers and switches.

But what about the first and last steps in that process, the parts where the router is consulting its own routing table, and then creating ethernet frames for the next hop?  The problem comes into play when you think about what a router is doing with that packet destined for 192.168.1.1: it’s looking up its egress interface so that it can just hand the packet off, completely ignoring the fact that there could potentially be millions, billions, trillions of packets coming right after it, destined for the exact same next hop host address.  As many packets as the router receives, it must perform THAT MANY lookups of the routing table to see if it has a route to the destination, and then create THAT MANY brand new ethernet frames.  That’s insanely processor intensive.  Forcing the router’s CPU to look up the routing table every single time it receives a packet makes the whole process of routing packets painfully slow.  It is these processor-intensive lookups that earned this process the name “process switching.”  This architecture seriously limited the ability of routers to keep up with growing interface speeds and traffic demands, and was the main reason that routing traffic was, for many years, considered far slower than switching traffic.

That’s when fast switching entered the picture.  If someone asks you “What is 521 multiplied by 347?”, what do you do?  Assuming you don’t have a computer or calculator in front of you, you probably get out some paper and do some quick calculations until you (hopefully) come up with 180787.  But what if, immediately after answering the question, that person asks you again… and again, and again for the value of 521 multiplied by 347.  Sure, you calculated it the first time, but every successive time after it, you just recalled it from memory, because it doesn’t make sense to waste time calculating it over and over.  That’s exactly what what fast switching does for you.  It caches those lookups and the parts of the layer-2 frame header that will remain static for each successive packet.

CEF is the next evolution of the process.  Fast switching was a big improvement over process switching, but still had some drawbacks.  First, cached entries were per destination IP address.  This led to massive caches that had to be flushed out often.  Second, the first packet to each destination IP still had to be process switched so that the entry could be cached.  This still created a burden for the CPU of the router, especially when there was a lot of traffic destined for unique host addresses.  These are the issues that CEF is able to address!

CEF Operations

CEF builds its tables based on prefixes, rather than destination IP addresses, and does not wait for matching traffic before building these tables.  As soon as a prefix appears in the routing table, matching entries are built in the corresponding CEF tables.  In fact, the first of these tables that CEF uses is called the Routing Information Base, or RIB.  The RIB is the entity that we are used to calling “the routing table.”  In CEF nomenclature, it makes more sense to call it a routing information base because it is not the final authority on forwarding decisions, but rather is being used as the base table from which to gather relevant routing information.  From the RIB, the Forwarding Information Base, or FIB, is built.  The FIB is the table that holds route prefixes and next-hop IP addresses.  At first hearing of that description, that might sound like the same job that the routing table is already taking care of, and you could hardly be blamed for thinking so.  The fact is though, that the routing table (RIB) is quite inefficient for routing lookups for a few reasons.  First, it can have multiple matching entries for a destination.  Second, the information is not ordered in an easily searchable manner.  Third, there’s a ton of other information in the routing table, like metric information, where the route was learned from, whether it is interacting with routing protocols, etc.  A router that is using process switching must filter through all of that information in order to find the relevant forwarding information that it needs.  Fourth, entries can be recursive, meaning that an entry references another entry in the table, which requires multiple lookups.  The FIB is built from the routing table, but only contains the information that is actually relevant to the packet-forwarding process.  It contains the one, single “winning” entry for the next hop of each prefix.    Along with the FIB, an adjacency table is also populated.  The adjacency table is where each entry in the FIB is matched up with an egress interface and pre-populated layer 2 frame header information.

As far as general configuration of CEF, there’s just one command to enable CEF, and it’s turned on by default: it’s the global configuration ip cef command.  For IPv6, you can also enable CEF with the global ipv6 cef command.  Interestingly, running CEF for IPv6 requires that the IPv4 command ip cef be turned on.  The inverse is not true (IPv4 CEF does not require IPv6 CEF to be running).  Once CEF is running, it can be disabled per-interface with the no ip route-cache cef command.

CEF Troubleshooting And Verification

First, let’s check out each of the tables that we just discussed, starting with the RIB.  As we explained before, the RIB is nothing more than the routing table that we’re all used to seeing, so good ole’ show ip route is our winner here.  Notably, when you simply use this command with no extra keywords, you are given a very specific subset of the information for each route.  It might be easy to think that there’s not a whole lot of extra information in this table because of that.  Try looking for information about a specific route though, and you’ll see that there’s a lot more information than just the stuff we’re used to seeing when we query the routing table in general, and a lot of that information is unneeded for a simple forwarding operation.

Router#show ip route 10.1.0.0
Routing entry for 10.1.0.0/16
  Known via “static”, distance 1, metric 0
  Routing Descriptor Blocks:
  * 192.168.1.2
      Route metric is 0, traffic share count is 1

That’s where the FIB comes into play.  The FIB takes the prefixes from the RIB and creates a pointer to the adjacency table, which is the table that holds the layer-2 addresses and pre-calculated frame header information.  We can view what’s in the FIB with the show ip cef command.

Router#show ip cef
Prefix               Next Hop             Interface
0.0.0.0/0            1.2.3.4               FastEthernet0/1
  1.2.3.4/29     attached             FastEthernet0/1

Notice that this information is very simple – we just see a prefix, next hop and egress interface.

Finally, the adjacency table can be viewed with the show adjacency command.  Further, you can see the pre-calculated ethernet frame information for a destination with the show adjacency detail command.

Router#show adjacency 192.168.1.1 detail
Protocol Interface                 Address
IP       FastEthernet0/0           192.168.1.1(9)
                                   1 packets, 76 bytes
                                   epoch 0
                                   sourced in sev-epoch 0
                                   Encap length 14
                                   58BFEAB764E8001FCA958A140800
                                   ARP

The adjacency table holds some special adjacency types.  The first of these is the null adjacency.  This is a record that is kept for packets that are to be forwarded to the null interface.  Next is the glean adjacency.  Since the FIB only maintains prefix information, the router needs a way of tracking hosts that can be reached via a directly connected interface, as obviously, those packets should not all be forwarded to the same layer-2 address.  So while the FIB still only keeps a single entry for the subnet, the FIB points to the glean adjacency database, which informs the router that it will need to ARP for the correct next-hop address.  Once the MAC is cached, the adjacency table creates an adjacency entry for this host.  Next up is the punt adjacency.  I’ll start by saying that as a Michigan Football fan, I sometimes call this one the “Well, at least they didn’t throw another pick” adjacency.  And then I get sad… but I digress.  The punt adjacency is used for packets that need special handling, such as packets that are destined for the router itself (like OSPF or telnet session traffic), traffic handled by Policy-based routing, packets that need to be fragmented, packets that require an ICMP response, packets that need to be encapsulated for IPsec or GRE tunnels… basically anything that cannot simply be forwarded out an interface.  Finally, there are the discard adjacency, and the drop adjacency.  Unfortunately, information on the difference between these two is scarce.

That’s it for part one of our CEF discussion.  Our next post will cover CEF load-sharing, and the concept of CEF polarization and how to avoid it.  Stay tuned!

Leave a Comment

Your email address will not be published. Required fields are marked *