Today, I will be discussing some basic stuff about CEF (Cisco Express Forwarding) load balancing mechanisms and understanding how different algorithms are working. But, lets first start with defining what is load balancing. Load balancing is basically the ability to share the trafic to the destination IP prefix over all the active paths. CEF supports two methods of load balancing:
1. Per-packet load balancing
2. Per-destination load balancing
We will now be discussing them one by one.
Per-packet load balancing:
Per-packet load-balancing works by using the available active paths for given destination prefix in a round-robin manner. CEF maintains a record of which path was used last for each destination prefix. This allows the round-robin code to calculate which path to use next. Unequal load balancing is supported by per-packet. What happens in unequal load balancing is that the round-robin code keeps sending packets on a path that is weighted to be used multiple times, before moving to the next path in the active set. Per-packet load balancing will give a near perfect split of traffic across the available paths, but has the disadvantage of causing packets in the same session to follow different routes through the network. This can cause packet reordering and non-predictive latency for that session.
Per-destination load balancing:
Per-destination load balancing addresses the disadvantage of per-packet while attempting to provide the same accurate split of traffic across the available paths. Per-destination is perhaps a misnomer; it should be called per-session load balancing. Per-destination load balancing works by assigning each session (i.e packets with the same source and destination ) ti ab active path., such that for all sessions being forwarded by the router, each active path will carry the same number of sessions. This has the advantage of keeping the packets in a session in the same order and following the same route across the network, which helps in maintaining the latency for each packet. Unequal load balancing is also supported by per-destination load balancing. Paths that are weighted to be used more than others will get more sessions assigned to them.
The session to path assignment is done using a hash function that takes the source and destination IP addresses. The set of active paths are assigned to 16 hash buckets (which may not all be enabled), and the result of the hash function is used to pick one of the enabled buckets and hence decide which path to use for the session. The 16 hash buckets are setup depending on the type of load balancing and the number of active paths. The simple case is for equal load balancing. The 16 buckets are evenly filled with the active paths. If 16 isn't divisible by the number of active paths, the last few buckets that represent the remainder are disabled.
Prior to the bug CSCdm87756, Cisco IOS CEF per-destination load balancing suffered from this polarisation effect. CSCdm87756 implements, by default, a scheme where the hash function is different in all routers in a given network, thereby cancelling out the polarisation effect of a hash function. The ability to vary the hash function in a router is accomplished using a new concept, the unique id. This is a 32-bit number assigned automatically to each router in the network which is used to modify the hash function in such a way as to eliminate the polarisation effect. The unique id is derived algorithmically from a router’s
base IP address. It is possible that two routers end up with the same unique id (or two unique ids that, while different, modify the hash function in such a manner as to re-introduce the polarisation effect). To correct this, CEF allows the unique id to be set directly from the router’s configuration, either by generating the next unique id in a sequence seeded by the base IP address, or by explicitly setting the 32-bit value in the configuration. One final topic for discussion, per-destination load balancing with a small number of sessions. Per-destination load balancing assigns sessions to paths independently of other sessions. This means that for a small number of sessions, statistically the paths may not be used evenly. Only when the number of sessions is large, will traffic share be assigned to each path as required by the routing protocols.
This is important when considering IP tunnel environment, which by their nature, run traffic over a small number of session (even traffic within a tunnel may represent many more sessions). Per-destination load balancing may not give the desired traffic sharing in such an environment (but see the tunnel algorithm description below). CEF’s implementation of per-destination load balancing algorithm has a number of options that allow some of these exceptions to be overcome. Specifically the hashing algorithm can be modified on a per-router basis. The following three sections describe the configurable algorithms.
The universal algorithm, with an automatically calculate unique id, is the default mode for CEF. It implements the scheme described by the previous section. The unique id can be fixed using the configuration command:
ip cef load-sharing algorithm universal [<id>]
Entering this command without specifying the <id> will generate a new unique id, using the current id and base IP address as seeds. The universal algorithm is supported by all platforms that employ a software forwarding path, in addition to all GSR linecards using the PSA forwarding ASIC.
The tunnel algorithm implements a different hash function from the universal algorithm, that has been tuned to work better in a tunnel environment, and overcome some of the unequal traffic sharing that might be observed. The tunnel algorithm also implements a polarisation fix, using the same unique id concept as the universal algorithm, The algorithm can be enabled using the configuration command:
ip cef load-sharing algorithm tunnel [<id>]
Entering this command without specifying the <id> will generate a new unique id, using the current id and base IP address as seeds. The tunnel algorithm is only supported on platforms that employ a software forwarding path. Attempting to enable it on a GSR with linecards using the PSA forwarding ASIC will generate an error message.
To maintain backward compatibility, the original pre-CSCdm87756 CEF per-destination load balancing algorithm can be re-enabled using the command:
ip cef load-sharing algorithm original
A unique id is not calculated, nor can one be specified with this algorithm. It will therefore exhibit traffic polarisation as described previously. This algorithm is supported by all platforms that employ a software forwarding path, in addition to all GSR linecards using the PSA forwarding ASIC.
I will be discussing how to monitor how the load distribution is happening in another post.