IP Forwarding: CEF

Cisco Express Forwarding is the most efficient method of switching packets to date, to understand how it works you must first understand the most crucial part of routing a packet through a router is defining how to construct the layer 2 frame header to allow the packet to be properly encapsulated toward its next hop, and then forwarding that frame out the correct interface.

This crucial part is referred to as the layer 2 frame rewrite.  Something to consider is that the routing table itself can hold thousands of prefix entries, but any specific router will only ever have a handful of neighbors (next hop to any particular destination).  All destinations through a specific next hop will use the same layer 2 rewrite information and must be encapsulated with the same header before it’s transmitted to that next hop to reach those destinations.  CEF makes this layer 2 rewrite step more efficient by pre-constructing the layer 2 headers and saving them to memory in an adjacency table.

The adjacency table is uses the routing tables IP address and next hops as well as the ARP tables Layer 3 to Layer 2 mapping tables to create and cache the layer 2 headers for each neighbor (adjacency)

Once this is completed and packets are destined to those neighbors, the router will simply use the pre-constructed next hop layer 2 frame to forward packets to that next without needing to visit the ARP table or the Routing table to make a forwarding decision.

Something else to consider is that the routing table itself is not optimized for rapid lookups.  It contains important information needed to build the routing table such as Administrative Distance, or route metrics, age, etc…  Routing table entries may require recursive lookups, once a destination network entry is matched in a routing table, the next hop information might contain only the IP address of the next hop but NOT the egress interface.  So at that point the next hops IP address must be looked up in the routing table, these recursive lookups can theoretically go on forever.  Even when it finds the final routing entry that contains an egress next hop interface, the routing table doesn’t have any information needed to rewrite the layer 2 headers to forward the packet.  This last hop address with an interface must have an ARP entry for the egress interface to know how to rewrite the layer 2 frame header.

CEF improves upon this lookup by storing the destination prefixes in a separate data structure called the Forward Information Base (FIB).  The FIB is cached in router memory and contains pointers toward the appropriate adjacency entry that contains the prepared layer 2 header and egress information toward the next hop.

Once the FIB and adjacency tables are created, the routing table is not used anymore to route packets.  With FIB routers the routing table can be used for packets that require more complex processing, however for plain packet forwarding only the FIB and adjacency tables are used.  The routing table becomes a source of routing data to build the FIB and adjacency table contents but no longer used to route packets.  At this point the routing table is referred to as the Routing Information Base (RIB) it is the master copy of routing information from which the FIB and other tables are populated.

Other protocols have their own internal routing tables called RIBs but these are separate from the routers routing table and should not be confused with the RIB in a FIB router.

Multi-layer switches and high end router platforms go further and store the FIB and adjacency in the Ternary Content Addressable Memory (TCAM) to perform even faster lookups.






Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s