Process Switching, Fast Switching, and Cisco Express Forwarding

With fast switching, the first packet to a specific destination IP address is process switched. The router adds the results of this daunting lookup to the fast-switching cache, sometimes called the route cache which contains the destination IP address, the next-hop information, and the data-link header information that needs to be added to the packet before forwarding. Future packets to the same destination address match the cache entry, so it takes the router less time to process and forward the packet. Significant drawbacks - the cache entries are timed out relatively quickly, because otherwise the cache could  get overly large as it has an entry per each destination address, not per destination subnet/prefix. If the routing table or Layer 3–to–Layer 2 tables change, parts of the route cache must be invalidated rather than updated, causing packets for affected destinations to become process switched again. Support for unicast fast switching has therefore been discontinued and removed from IOS Releases 12.2(25)S and 12.4(20)T onward.  

CEF. The crucial part of routing a packet through a router is finding out how to construct the Layer 2 frame header to allow the packet to be properly encapsulated toward its next hop, and forward the packet out the correct interface.
All destinations reachable through a particular next hop are using the same Layer 2 rewrite information.
Preconstruct the Layer 2 frame headers and egress interface information for each neighbor, and keep them ready in an adjacency table stored in the router’s memory. This table can be constructed immediately as the routing table is populated, using IP addresses of next hops in the routing table and utilizing ARP. A packet that is to be routed through a particular next hop will then simply use the preconstructed Layer 2 frame header for that next hop, without needing to visit the ARP or similar tables.

The routing table contains lots of information crucial to its construction but not that important for routing lookups, such as origin and administrative distances of routes, their metrics, age, and so on. Entries in the routing table can require recursive lookups.

The destination prefixes alone from the routing table can be stored in a separate data structure called the Forwarding Information Base, or FIB, optimized for rapid lookups. Each entry in the FIB that represents a destination prefix can instead contain a pointer toward the particular entry in the adjacency table that stores the appropriate rewrite information: Layer 2 frame header and egress interface indication. Any necessary recursion in the routing table is resolved while creating the FIB entries and setting up the pointers toward appropriate adjacency table entries.

After the FIB and adjacency table are created, the routing table is not used anymore to route packets for which all forwarding information is found in the FIB/adjacency table. With FIB-based routers, the routing table can be used for packets that require more complex processing not available through straightforward Layer 2 rewrite; The routing table therefore becomes more of a source of routing data to build the FIB and adjacency table contents but is not necessarily used to route packets anymore.

If the next hop for a destination changes, only the pointer in the respective FIB entry needs to be updated to point toward the new adjacency table entry.
Both FIB and adjacency tables are maintained in router’s memory, and lookups in these structures are done by the CPU as part of interrupt handler executed when a packet is received.

Adjacency table - preconstruct layer2 frame headers(include next hop info using ARP or other mapping) and egress interface info for each neighbor

FIB - stores destination prefixes alone from routing table, contains pointers toward the particular entry in the adjacency table that store appropriate rewrite info(layer2 frame header and egress interface)

To run IPv6 CEF, IPv4 CEF must be active. The  no ip route-cache cef  interface subcommand can then be used to selectively disable CEF on an interface

show ip cef

show adjacency //note separate entries are created for IPv4 and IPv6 adjacencies as the Protocol or EtherType field value in pre-constructed frame headers is different for IPv4 and IPv6

show adjacency  s0/0/0 detail 

Load Sharing with CEF and Related Issues  

One of major advantages of CEF is its native support for different load-sharing mechanisms, allowing the use of multiple paths toward a destination network if present in the FIB. Two modes of load sharing: per-packet and per-destination. With the per-destination mode, the CEF actually takes the source and destination IP address and optionally other data to produce a hash value that identifies the particular path to carry the packet. The per-destination load-sharing mode is the default. It is preferred because it avoids packet reordering within a single conversation.

Per-destination load sharing in CEF is technically achieved by placing a so-called load-share table between the FIB and the adjacency table. This loadshare table contains up to 16 pointers to entries in the adjacency table. 

When a packet arrives, the router performs a hashing operation over the packet’s source and destination address fields, and uses the hash result value as an index into the loadshare table to select one of the possible paths toward the destination. With the hashing performed over fixed packet and/or segment address fields, a single hash function produces the same result for all packets in a flow.

CEF polarization - R1 computes hash for the traffic, split and sends to R2 and R3.When R2 compute the hash on the received traffic, it'll be the same result/hash for all traffic/flows, hence not load balance anymore.

Each router chooses a random 4B-long number called a Universal ID whichi is used as a seed in the hashing function used by CEF. It produce different hashing results for a particular packet flow.

To verify the current load-sharing mechanism and Universal ID value, the output of show cef state, show ip cef summary , or show ip cef detail.