Load balancing with CEF for IP
In IOS software 11.1CC a new forwarding mechanism for IP packets was
introduced: Cisco Express Forwarding (CEF). The design of Cisco Express
Forwarding includes enhancements that allow to use load balancing
without sacrificing forwarding performance even when using per packet
load balancing. Previously per packet load balancing required disabling
of route-caching mechanisms like fast switching or optimum switching . CEF is available in IOS software version 11.1CC
for Cisco 7200 and 7500 series routers only. CEF currently supports the
following encapsulations: ATM/AAL5snap, ATM/AAL5mux, ATM/AAL5nlpid,
Frame Relay, Ethernet, FDDI, PPP, HDLC, and tunnels.
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.
