Load Balancing Hash Algorithms
What Is Load Balancing?
During network deployment, load balancing is often deployed when multiple forwarding paths are available. With load balancing, packets can be forwarded based on their input location (inbound interface), service type (protocol), packet content, flow table, and timestamp; alternatively, random or round-robin per-packet load balancing can be performed to fully utilize links and improve the forwarding efficiency.
Timestamp-based, random, or round-robin per-packet load balancing is seldom deployed. This is because it may cause the destination server to receive out-of-order packets or multiple copies of the same packets if these packets that belong to the same user are transmitted along different paths. Generally, packets are load balanced based on the service type or packet content, typically 5-tuple information (source IP address, destination IP address, protocol number, source port, and destination port).
The typical load balancing process includes input (traffic and valid fields), processing (calculation using the hash algorithm), and output (outbound interface for forwarding traffic out). The hash result directly affects the load balancing effect. Therefore, how to use the hash algorithm for calculation is particularly important in load balancing deployment.
The commands and configuration examples used in this document may be supported only by some switch models. For details about the support capability, see the product documentation.
How Do I Use Hash Algorithms to Implement Load Balancing?
A hash algorithm converts fixed-length or variable-length input into fixed-length output. The output is a hash value. This conversion is a compression mapping. Generally, the hash value space is far less than the input space. Different inputs may be converted into the same output, and a hash value cannot be used to uniquely identify an input value. Simply put, the hash algorithm compresses a message of a certain length into a fixed-length message digest.
As shown in Figure 1-1, the hash calculation process is as follows:
- The device obtains packet header information. In case of common IP packets, the fields of source MAC address, destination MAC address, source IP address, destination IP address, VLAN ID, and Layer 4 port number need to be obtained. In case of tunnel packets, the preceding fields in the inner and outer packet headers need to be obtained. Based on the configured hash model, the information is used as the reference values of hash factors. The reference values can be set using commands.
- The chip calculates hash factors using the hash algorithm and seed to generate a hash key.
A chip provides fixed types of hash algorithms. The calculation results of different hash algorithms vary according to the traffic models. The hash algorithm to be used can be specified using commands.
Seed is a value used for hash calculation. If hash factors are the same, the seed value affects the calculated hash key. The seed value can be set using commands.
- The chip offsets 0 to 15 bits from the hash key. This enables the same hash factor to change more frequently and flexibly to adapt to different hash scenarios. The number of bits to be offset from the hash key can be set using commands.
- The chip converts the hash key into an offset value, and performs the remainder operation between the offset value and the number of outbound interfaces to determine the outbound interface of packets.
Load Balancing Modes
ECMP Load Balancing
Equal-Cost Multi-Path (ECMP) implements load balancing and backup among multiple paths. It applies to a network where multiple links to the same destination are available. ECMP is classified into per-flow load balancing and per-packet load balancing. Per-flow load balancing can ensure the packet sequence and ensure that the same data flow is forwarded according to the routing entry with the same next hop and different data flows are forwarded according to routing entries with different next hops. Per-packet load balancing improves ECMP bandwidth utilization and evenly load balances traffic among equal-cost routes, but it cannot prevent out-of-order packet delivery. To resolve this issue, the device or terminal that receives traffic must support reassembly of out-of-order packets.
- Random mode: A route is randomly selected among multiple equal-cost routes to forward packets. When the IP address and MAC address of known unicast packets remain unchanged, configure random per-packet load balancing.
- Round-robin mode: Each equal-cost route is used to forward packets in turn. When known unicast packets have a similar length, configure round-robin per-packet load balancing.
Table 1-1 describes the per-flow load balancing modes for different types of packets.
Packets (Inbound Direction) |
Default Load Balancing Mode |
Configurable Load Balancing Mode |
|---|---|---|
IPv4 packets |
src-ip, dst-ip, l4-src-port, and l4-dst-port |
src-ip, dst-ip, l4-src-port, l4-dst-port, protocol, vlan, src-interface, and dscp |
IPv6 packets |
src-ipv6, dst-ipv6, l4-src-port, and l4-dst-port |
flow-label |
GRE packets |
|
inner-src-ip, inner-dst-ip, inner-l4-dport, and inner-l4-sport |
Eth-Trunk Load Balancing
Ethernet link aggregation, also known as Eth-Trunk, bundles multiple physical links into a logical link to increase link bandwidth. The bundled links back up each other, increasing reliability.
- Per-packet load balancing improves Eth-Trunk bandwidth utilization, but it cannot prevent out-of-order packet delivery. To resolve this issue, the device or terminal that receives traffic must support reassembly of out-of-order packets. The following per-packet load balancing modes are supported:
- Random mode: The outbound interface of packets is selected randomly based on the time when packets reach the Eth-Trunk. When the IP address and MAC address of known unicast packets remain unchanged, configure random per-packet load balancing.
- Round-robin mode: Each member interface of an Eth-Trunk forwards traffic in turn. When known unicast packets have a similar length, configure round-robin per-packet load balancing.
- Per-flow load balancing ensures the packet sequence and ensures that the same data flow is forwarded through the same physical link and different data flows are forwarded through different physical links. Table 1-2 describes the per-flow load balancing modes for different types of packets.Table 1-2 Load balancing modes for different types of packets
Packets (Inbound Direction)
Default Load Balancing Mode
Configurable Load Balancing Mode
Description
IPv4 packets
src-ip, dst-ip, l4-src-port, and l4-dst-port
src-ip, dst-ip, l4-src-port, l4-dst-port, and protocol
The load balancing mode is related to the packet type, but not the packet forwarding process.
The system identifies the type of Ethernet frames based on the inner packet header. For example, if packets are identified as IPv4 packets and the system provides only Layer 2 forwarding for them, these packets are load balanced according to the load balancing mode for IPv4 packets. When the system cannot identify packets as IPv4 or IPv6 packets, the system load balances the packets using the mode for Layer 2 packets (src-mac, dst-mac, src-interface, and eth-type).
IPv6 packets
src-ip, dst-ip, l4-src-port, and l4-dst-port
src-ip, dst-ip, protocol, l4-src-port, and l4-dst-port
Other Layer 2 packets
src-mac and dst-mac
src-mac, dst-mac, src-interface, and eth-type
How Do I Solve the Hash Polarization Problem?
Hash polarization, also known as hash imbalance, indicates that traffic is unevenly load balanced after being hashed twice or more. This situation is common when hash operations are performed across devices multiple times. For example, a device performs ECMP hashing and forwards traffic to two or more connected devices, which then perform ECMP or Eth-Trunk hashing again. Hash polarization may also occur if the outbound interfaces of ECMP routes are multiple Eth-Trunk interfaces on the same device.
Symptom
In Figure 1-2, there are four types of flows on the inbound interfaces of Switch A and four equal-cost links in the outbound direction. According to hash calculation, flows 3 and 4 are transmitted to Switch B through upper two links, and flows 1 and 2 are transmitted to Switch C through lower two links. Switch B also has four equal-cost links in the outbound direction. If Switch B uses the same or similar hash algorithm as Switch A, flows 3 and 4 will be transmitted through upper two links of Switch B according to the hash result. As a result, no flow is transmitted through lower two links of Switch B. A similar situation will occur on Switch C. This causes extremely serious load imbalance between ECMP routes or Eth-Trunk member interfaces, which is referred to as hash polarization.
The implementation of the hash function on switches heavily depends on chips. Therefore, hash polarization may occur if switches using the same type of chips are located at adjacent network layers. If both Eth-Trunk hashing and ECMP hashing exist on the same device, hash polarization may also occur.
Therefore, if ECMP or Eth-Trunk hashing is deployed on a multi-layer network, consider the risk of hash polarization.
Suggestions
If load imbalance or hash polarization occurs during traffic forwarding, you can adjust the hash algorithm on the device to resolve the problem. For example, for an inter-device hash polarization scenario similar to that shown in Figure 1-2, the hash algorithm on Switch A can be adjusted to resolve this problem.
The following factors affect the hash calculation result:
- Hash factor: can be configured based on the traffic model.
Examples of configuration commands:
ip [ src-ip | dst-ip | l4-src-port | l4-dst-port | protocol ] *
ipv6 [ src-ip | dst-ip | protocol | l4-src-port | l4-dst-port ] *
l2 [ src-mac | dst-mac | vlan | eth-type ] *
- Hash algorithm: is configured by specifying the hash-mode hash-mode-id parameter.
- Seed value: is configured by specifying the seed seed-data parameter. If devices from multiple vendors exist on the network, you are advised to configure the same seed value for these devices.
- Offset: is configured by specifying the universal-id universal-id parameter. Typically, one hash algorithm corresponds to one offset. When devices from multiple vendors exist on the network, you are advised to configure the same offset for these devices.
- Offset algorithm: is fixed on chips and cannot be changed on CE series switches.
Switch vendors can select and combine hash algorithms and offset values only based on the preceding hash calculation parameters supported by chips. The hash load balancing effect is closely related to the traffic model. For flow-based hashing, theoretically, there is no fixed combination of hash parameter settings applicable to all service scenarios.
If hash polarization or load imbalance occurs, adjust the hash calculation parameters on devices at different network layers to implement differentiated hash calculation.