DHC Load Balancing Algorithm
Extracted elements (25)
Pearson's hash was chosen because it is computationally inexpensive, requiring only an array lookup and XOR operation for each key byte, while yielding a fairly even bucket distribution for both random STIDs and patterned STID sequences.
The algorithm requires no information exchange beyond initial configuration, enabling cooperating servers to independently decide which one should service a client without negotiation. This avoids the need for any runtime coordination protocol.
The algorithm was originally devised for the DHCP Failover Protocol but the authors realized it could also optimize cooperating DHCP servers and BOOTP relay agents, making it more broadly applicable.
The approach is probabilistic: for short periods the actual percentage of clients served by a given server may deviate from the desired percentage, but as the number of requests grows the actual load distribution approximates the configured percentage.
The Delayed Service parameter was introduced to handle the case where the server supposed to respond is unavailable or out of addresses, allowing a secondary server to step in after a configured timeout rather than leaving the client unserved.
A forwarding agent may be configured to forward a given packet to more than one server, for example to split load between primary-backup server pairs each running the DHCP Failover Protocol.
All interoperable implementations must use exactly the same Pearson's hash function with the identical 256-entry mixing table; any deviation will cause different servers to compute different hash assignments for the same client, breaking load balancing.
Some DHCP clients may not correctly implement the secs field, so servers MAY track the elapsed time between repeated requests from the same client as an alternative to relying on the secs field value.
A DHCP server MAY use the elapsed time between first and subsequent client request instead of the secs field if the secs field in the second packet is zero and the transaction ID matches a previously recorded request.
A DHCP server providing delayed service capability SHOULD use the value in the secs field of the client request if its value is not zero.
All interoperable implementations MUST use the specified Pearson's hash function with the exact mixing table values given in section 6. No alternative hash functions are permitted.
DHCP server implementations providing delayed service capability SHOULD set the DS (Delayed Service) configuration parameter to the number of seconds to wait after the client's first request before responding to a client whose hash would not normally permit service.
DHCP servers MUST use the Client Identifier option as the STID if it is present. If no Client Identifier option is present, the hlen field MUST be used as the length of the data to be hashed, and the contents of the chaddr MUST be the data to be hashed.
HBA transmissions MAY be encapsulated in messages of some other protocol, e.g., email or DHCP Failover Protocol option.
If a bit is set in the HBA bitmap, the recipient server MUST service each client request where the STID yields the corresponding hash value.
When configuring a forwarding agent (e.g., BOOTP relay), HBAs consisting of pairs of Server-ID / Hash Bucket values MAY be used.
When configuring one specific server, an HBA in the form of a simple bitmap of 32 octet values SHOULD be used.
Hash Bucket Assignments (HBA) are configuration directives that assign a set of hash bucket values (0-255) to a server participating in the load-balancing scheme, determining which client requests that server will service.
Server ID (SID) is an identifier (e.g., IP address or DNS name) used to designate one of the participating servers; used by forwarding agents to route client requests to the appropriate server.
Service Delay (SD) is a load balancing parameter allowing delayed service of a client by a server participating in the load-balancing scheme, instead of ignoring the client entirely when the hash does not assign that client to this server.
The Service Transaction ID (STID) is the attribute of individual client requests used for load balancing. It is derived from the Client Identifier option if present, or from the chaddr field (up to 16 bytes) of the DHCP packet.
The algorithm itself provides no security and does not impact existing security. If HBA contents are transmitted over the network during server configuration, that message MUST be secured against tampering, since a modified HBA could result in denial of service for some or all clients.
At most the first 16 bytes of the Client Identifier option or chaddr field are used as the key for hashing. The hash function is initialized with the key length and iterates over key bytes using a 256-entry mixing table via XOR.
The hash function output is an 8-bit value (0-255). The HBA index is computed as (hash >> 3) & 31 to select the octet, and bitmask as 1 << (hash & 7) to select the bit within that octet.
The HBA for a single server is a 32-octet bitmap. The first octet represents hash values 0-7, the next 8-15, and so on; within each octet the least significant bit represents the smallest hash value. Each bit set to 1 means the server must service requests hashing to that value.