Review/Perspective: CEF Concepts

1.1.b Identify Cisco express forwarding concepts

  • 1.1.b [i] RIB, FIB, LFIB, Adjacency table
  • 1.1.b [ii] Load balancing Hash
  • 1.1.b [iii] Polarization concept and avoidance

Adjacency table – contains the layer two header encapsulation information to forward frames to each respective next hop specific to the link type on said interface.

You can view the adjacency table by typing in: show adjacency

FIB – The Forwarding Information Base is a cached copy of routing and next hop information so when a packet comes into the router it doesn’t have to perform a routing lookup and figure out next hop encapsulation…instead it refers to the FIB which already has this information and uses that information to more quickly forward the packet instead of reprocessing the decision each and every time it receives a packet.  FIB table is also referred to as the CEF table.

You can view the FIB table using: show ip cef
sh ip cef.PNG

The routing table is referred to as the RIB, the reason for this is once a routers adjacency and FIB table has been filled with next hop layer 2 encapsulation information. via the IPv4 routing table, the router no longer relies on the IPv4 routing table to make routing decisions, instead it relies on the FIB, at which point the routing table is simply a database of routing information otherwise called a RIB used to populate the FIB.

You can view the Routing Table/RIB using: show ip route

LFIB – The Label Forwarding Information Base is used in MPLS network configurations.  This table contains cached routing and next hop information just like the FIB, however it also includes Label information so for the same reason, a label decision doesn’t have to be made on every ingress packet to the router, the router simply refers to this LFIB table on core MPLS routing lookups and forwards the packet based on the cached information, instead of re-determining the label path on each packet.

You can view the LFIB by using: show mpls forwarding-table

Load Balancing Hash – When there are equal cost multiple routes to the same destination CEF will use an algorithm primarily based on L4 information (ie: Source IP, Dest. IP, Source Port, Dest Port) to create a hash that determines the route CEF will choose to take in order to load balance traffic to that destination.  This has is deterministic in that it will decide which specific interface that specific flow of traffic will traverse to get to the destination.

You can view hashing information using: show ip cef internal
sh ip cef x internal.PNG
You’ll notice in this image that starting at Hash 1 it will attempt to forward the packet out Gig0/1.2, then Tunnel2, then Tunnel1 in a round robin fashion to effectively load balance traffic.  You can configure unequal cost load distribution so it doesn’t do round robin as well.

CEF Polarization occurs when a hash algorithm chooses a particular path, and redundant paths remain completely unused in the scenario described above.  When there are only two paths, the switch/router performs an exclusive-OR (XOR) operation on the lower-order bits (one bit when either of two links need to be selected, two bits for 3-4 links, and so on) of the Source IP and Destination IP. The XOR operation of the same Source IP and Destination IP always results in the packet use of the same link.

The packet then passes onto the distribution layer, where the same hashing algorithm is used along with the same hash input, and picks a single link for all flows, which leaves the other link underutilized. This process is called CEF polarization (use of the same hash algorithm and same hash input which results in the use of a single Equal-Cost Multi-Path (ECMP) link for ALL flows)

A way to avoid polarization is to use the universal CEF algorithm, Cisco IOS introduced a concept called unique-ID/universal-ID which helps avoid CEF polarization. This algorithm, called the universal algorithm (the default in current Cisco IOS versions), adds a 32-bit router-specific value to the hash function (called the universal ID – this is a randomly generated value at the time of the switch boot up that can can be manually controlled). This seeds the hash function on each router with a unique ID, which ensures that the same source/destination pair hash into a different value on different routers along the path. This process provides a better network-wide load-sharing and circumvents the polarization issue. This unique -ID concept does not work for an even number of equal-cost paths due to a hardware limitation, but it works perfectly for an odd number of equal-cost paths. In order to overcome this problem, Cisco IOS adds one link to the hardware adjacency table when there is an even number of equal-cost paths in order to make the system believe that there is an odd number of equal-cost links.

You can configure the universal CEF algorithm to avoid polarization in EXEC mode with:
ip cef load-sharing algorithm universal
conf ip cef load-sharing algorithm.PNG


Leave a Reply

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

You are commenting using your 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