Notes: CEF Polarization

Introduction

• CEF polarization can cause suboptimal use of redundant paths to a destination network.
• CEF polarization is in effect when a hash algorithm chooses a particular path and the redundant paths remain completely unused.

Background

Consider the following topology.

• Assume that to reach host 10.1.1.1 from [Top Left] router, there are two equal-cost paths (L1, L2).
• The decision of the chosen link is made by a hashing algorithm using the source and destination IP addresses (SIP and DIP).
• When there are only two paths, the router performs an exclusive OR (XOR) operation on the lower-order bits of the SIP and DIP (one bit, two bits for 3-4 links, and so on).
• The XOR of the same SIP and DIP always results in the same hash, and hence, the use of the same link.
• At the next layer, the same hashing algorithm is used along with the same hash input, and a single link is picked for all flows, leaving the other link underutilized.
• CEF polarization = use of the same hash algorithm and same hash input, which results in the use of a single ECMP link for ALL flows.

In more detail:

1. Traffic sourced from 10.240.18.1 and destined to 10.240.20.1 arrives at Router A, and the information goes through a hashing algorithm. The path toward Router C is chosen. From there the packets travel to Router F, and on to their final destination.

2. Router A performs the hashing function on traffic sourced from 10.240.18.2 and destined to 10.240.20.1, and sends the packets to Router B. The same happens to traffic from 10.240.18.3.

3. Router B produces the same results that the hash algorithm on Router A produced. Therefore, both streams of packets pass along one path towards Router E. The link toward Router D is never used.

4. The packets are forwarded to their final destination through Router F.

Avoiding CEF Polarization

1. Alternate between default (SIP and DIP) and full (SIP + DIP + Layer 4 ports) hashing inputs configuration at each layer of the network.

The Catalyst 6500 provides a few choices for the hashing algorithm:

• Default - Use the source and destination IP address, with unequal weights given to each link to prevent polarization.
• Simple - Use the source and destination IP address, with equal weight given to each link.
• Full - Use source and destination IP address and Layer 4 port number, with unequal weights.
• Full Simple - Use the source and destination IP address and Layer 4 port number, with equal weights given to each link.

• No commands (except show run) exist to check the load-sharing algorithm in use.
• The Catalyst 6500 does not support per-packet load sharing.
• The Full option does NOT include a universal ID in hash.

2. Alternate between an even and odd number of ECMP links at each layer of the network.
CEF load balancing is independent of the route source. OPSF routes exhibit the same behavior EIGRP.

The hash algorithm load-balances this way by default:

1: 1
2: 7-8
3: 1-1-1
4: 1-1-1-2
5: 1-1-1-1-1
6: 1-2-2-2-2-2
7: 1-1-1-1-1-1-1
8: 1-1-1-2-2-2-2-2

This means that:

• For two equal cost paths, load-sharing is 46.666%-53.333%, not 50%-50%.
• For three equal cost paths, load-sharing is 33.33%-33.33%-33.33% (as expected).
• For four equal cost paths, load-sharing is 20%-20%-20%-40% and not 25%-25%-25%-25%.

• Evidently, when there is an even number of ECMP links, the traffic is NOT load balanced!
• Anti-polarization weight was introduced in Version 12.2(17d)SXB: mls ip cef load-sharing full simple
• Use this command if there are two equal-cost paths, and both need to be used equally.

3. A concept called unique-ID/universal-ID helps with CEF polarization.

• The universal ID is a randomly generated value at router bootup that can be controlled manually.
• A universal algorithm (the default in current IOS versions) adds a 32-bit value to the hash function.
• This seeds the hash function on each router with a unique ID, which ensures that the same source/destination pair hash into a different value on different routers along the path.
• Result: better load sharing and lowered polarization.
• The unique-ID concept does not work for an even number of equal-cost paths due to hardware limitation.
• To overcome this problem, Cisco IOS adds one link to the hardware adjacency table when there is an even number of equal-cost paths in order to make the system believe that there is an odd number of equal-cost links.
• Customize the universal ID with ip cef load-sharing algorithm universal <id>.

References

CEF Polarization