1.1.b Network Theory – Cisco Express Forwarding

The following key concepts will be explained here:

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

Cisco Express Forwarding (CEF) is a cisco proprietary technology which allows for more efficient  and faster layer 3 switching.  It is a type of interrupt context switching as opposed to process switching.  It offloads much of the processing involved in layer 3 switching to the hardware; unlike the more cumbersome software-laden computing and associated latency with conventional routing.  It out-competes fast switching route caching, by performance, scalability, and resilience.    FIB and Adjacency table are the two main components making up CEF operations.

In Central CEF mode both the FIB and adjacency table reside on the Route Processor (RP) and the express forwarding is done on it .  Distributed CEF mode is the other type of the two which CEF can be enabled as; in it line cards keep a synchronized local copy of the FIB and adjacency tables from the RIB through a mechanism called Inter Process Communication (IPC) and offloads the processing from the RP by performing the express forwarding between port interfaces itself.

Routing Information Base (RIB) aka the routing table contains all the routes received from manual static entries and routing peers by layer-3 protocols.

Forwarding Information Base (FIB); it contains the forwarding information of the RIB,  the singular unique paths for any particular subnet (/0 -/32 for example in IPv4).  FIB gets updated  when the forwarding information of the RIB is updated when there is routing update due to routing or topology change.  Precisely because of that, it eliminates the requirement for route caching as found in other interrupt context switching; and it is a more resilient type of switching as it avoids the need for process switching (using RIB) due to invalid routing entries in the route caches.

Adjacency table contains the layer 2 next-hop mapping for all FIB entries in CEF.   It also prepends the layer-2 addressing information.  It points to the next-hop interface (host-route adjacencies).  Adjacency table is built using adjacency discovery which computes and stores the data link-layer header information for the adjacent node during an ARP (along with adding the adjacency entry during that process).  Additionally to expedite layer 3 switching when an exception condition is met; there are other adjacency types for exception processing;

1. Null adjacency – packets are dropped destined to null interface,.
2. Glean adjacency – for example in a BMA network where a router is directly connected to several hosts; FIB has subnet prefix instead of individual host prefixes; adjacency table is gleaned for the specific host-prefix.
3. Punt adjacency – unsupported features by CEF, which require special processing, are forwarded to conventional route switching.
4. Discard adjacency – packets are dropped.
5. Drop adjacency – prefix is checked and packets are dropped.

Load balancing hash function or hash ID in CEF takes the source and destination IP addresses and randomizes the session to path assignment across the end-to-end path.  There is one to one assignment of a session to an active path.  Session is defined as a unidirectional flow.  There are 16 has buckets an active path can be assigned to, of those enabled (path to bucket assignment), the hash function selects one bucket per path; each active path carries the same number of sessions.

CEF polarization is when there are unused redundant paths by resulting in suboptimal use of bandwidth and path availability for a particular destination subnet.  This is a suboptimal result of the computation of he XOR algorithm on the low-order bits of the Source IP and Destination IP; which results in a single path being used per Source IP and Destination IP (i.e. single ECMP *Equal-Cost Multi-Path).  Avoidance of CEF polarization can be done in the following three ways:

1. Alternate between default (SIP and DIP) and full hashing (SIP, DIP, and L4 port numbers) inputs configuration across each layer of the hierarchical network model of the network

router(config)#mls ip cef load-sharing full 
router(config)#mls ip cef load-sharing ?

2. Alternate between an even and odd number of ECMP links across each layer of the hierarchical network model of the network. (impractical)

3. Add Anti-polarization weight.

router(config)#mls ip cef load-sharing full simple

4. Uses a universal algorithm which uses a concept called unique-ID/universal-ID

router(config)#ip cef load-sharing algorithm universal <id>

Label Forwarding Information Base is used by MPLS enabled routers on MPLS networks to forward labelled packets between LSRs (Labelled Switch Routers).  LFIB is used instead of FIB for label lookups.  CEF is the only switching mode for which Labels can be used.  CEF adjacency table determines the outgoing data link encapsulation for the LFIB entry.

References:
http://www.cisco.com/c/en/us/td/docs/ios/12_2/switch/configuration/guide/fswtch_c/xcfcef.html
http://www.cisco.com/c/en/us/support/docs/routers/12000-series-routers/47321-ciscoef.html
http://www.cisco.com/c/en/us/td/docs/ios/12_2/switch/configuration/guide/fswtch_c/xcfcefc.html
http://www.cisco.com/en/US/products/hw/modules/ps2033/prod_technical_reference09186a00800afeb7.html
http://www.cisco.com/c/en/us/support/docs/ip/express-forwarding-cef/116376-technote-cef-00.html
http://www.cisco.com/c/en/us/support/docs/ip/express-forwarding-cef/18285-loadbal-cef.html ***
http://www.cisco.com/c/en/us/tech/ip/express-forwarding-cef/index.html
http://www.ciscopress.com/articles/article.asp?p=68082
https://tools.ietf.org/html/rfc3222