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
Here is a description of how the hashing algorithm works:
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 SIP and DIP. The XOR operation of the same SIP and DIP 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)
How CEF load balancing works
CEF is an advanced Layer 3 switching technology inside a router. Usually a router uses a route cache to speed up packet forwarding. The route cache is filled on demand when the first packet for a specific destination needs to be forwarded. If the destination is on a remote network reachable via a next hop router, the entry in the route cache is consisting of the destination network. If parallel paths exist this does not provide load balancing, as only one path would be used. Therefor the entry in the route cache now relates to a specific destination address, or host. If multiple hosts on the destination network are receiving traffic a route cache entry for each individual host is made, balancing the hosts over the available paths. This provides per destination load balancing. The problem that arises is that for a backbone router carrying traffic for several thousands of destination hosts a respective number of cache entries is needed. This consumes memory and makes cache maintenance a demanding task. In addition the decision about which path to use is done at the time the route-cache is filled, and it is based on the utilization of the individual links at that point in time. However the amount of traffic on individual connections can change over time, possibly leading to a situation where some links carry mostly idle connections and others are congested. CEF takes a different approach as it calculates all information necessary for the forwarding task in advance and decouples the forwarding information from the next hop adjacency, which allows for effective load balancing.
The two main components of CEF operation are the
•
Forwarding Information Base
•
Adjacency Tables
Forwarding Information Base
CEF uses a Forwarding Information Base (FIB) to make IP destination prefix-based switching decisions. The FIB is conceptually similar to a routing table or information base. It maintains a mirror image of the forwarding information contained in the IP routing table. When routing or topology changes occur in the network, the IP routing table is updated, and those changes are reflected in the FIB. The FIB maintains next-hop address information based on the information in the IP routing table. Because there is a one-to-one correlation between FIB entries and routing table entries, the FIB contains all known routes and eliminates the need for route cache maintenance that is associated with earlier switching paths such as fast switching and optimum switching.
Adjacency Tables
Network nodes in the network are said to be adjacent if they can reach each other with a single hop across a link layer. In addition to the FIB, CEF uses adjacency tables to prepend Layer 2 addressing information. The adjacency table maintains Layer 2 next-hop addresses for all FIB entries.
The adjacency table is populated as adjacencies are discovered. Each time an adjacency entry is created (such as through the ARP protocol), a link-layer header for that adjacent node is precomputed and stored in the adjacency table. Once a route is determined, it points to a next hop and corresponding adjacency entry. It is subsequently used for encapsulation during CEF switching of packets. A route might have several paths to a destination prefix, such as when a router is configured for simultaneous load balancing and redundancy. For each resolved path a pointer is added for the adjacency corresponding to the next-hop interface for that path. This mechanism is used for load balancing across several paths. For per destination load balancing a hash is computed out of the source and destination IP address. This hash points to exactly one of the adjacency entries in the adjacency table, providing that the same path is used for all packets with this source/destination address pair. If per packet load balancing is used the packets are distributed round robin over the available paths. In either case the information in the FIB and adjacency tables provide all the necessary forwarding information, just like for non-load balancing operation. The additional task for load balancing is to select one of the multiple adjacency entries for each forwarded packet.
