Mastering Dynamic Feedback Load Balancing in Linux IPVS: Algorithms & Implementation

Table of Contents

Preface

Previously we discussed three IP load‑balancing techniques implemented in an LVS cluster, which address system scalability and transparency by using a load scheduler to efficiently distribute requests across multiple servers, making the cluster appear as a single high‑performance virtual server to client applications.

Next we will focus on load‑scheduling strategies and algorithms within the load scheduler, describing how request flows are dispatched to servers to maintain load balance.

Describe the various connection scheduling algorithms implemented by the IPVS load‑balancing software in the kernel.

Describe a dynamic‑feedback load‑balancing algorithm that combines kernel weighted connection scheduling with real‑time load feedback to further avoid server imbalance.

In the following description, we refer to the communication between a client socket and a server socket as a connection, regardless of whether TCP or UDP is used. For UDP packets, IPVS creates a scheduling record with a timeout (e.g., 5 minutes); packets from the same source address and port are dispatched to the same server.

IPVS performs load‑balancing at the connection granularity. In non‑persistent HTTP, each object requires a new TCP connection, so fine‑grained scheduling can mitigate sudden load spikes from individual users.

1. Connection Scheduling Algorithms in the Kernel

IPVS implements the following ten scheduling algorithms:

Round‑Robin Scheduling

Weighted Round‑Robin Scheduling

Least‑Connection Scheduling

Weighted Least‑Connection Scheduling

Locality‑Based Least Connections Scheduling

Locality‑Based Least Connections with Replication Scheduling

Destination Hashing Scheduling

Source Hashing Scheduling

Shortest Expected Delay Scheduling

Never Queue Scheduling

2. Dynamic Feedback Load Balancing Algorithm

The Dynamic‑feedback Load Balancing Algorithm considers real‑time server load and response, continuously adjusting request distribution to prevent overloaded servers from receiving excessive traffic, thereby improving overall throughput. A Monitor Daemon runs on the load scheduler, collecting server load metrics, computing an aggregate load, and adjusting server weights in the kernel’s IPVS scheduler when the weight change exceeds a threshold.

2.1 Connection Scheduling

When clients access services via TCP, the required processing time and resources vary widely, depending on factors such as service type, network bandwidth, and server resource utilization. Heavy requests may involve intensive computation, database access, or large data streams, while light requests may only fetch an HTML page or perform simple calculations.

These differences can cause server utilization skew, where some servers become overloaded while others remain idle, leading to long client wait times and perceived poor service quality.

Simple Connection Scheduling

Simple scheduling can exacerbate server skew. For example, with round‑robin across four servers, a large file request (e.g., image D) may consistently hit the same server, reducing overall resource utilization.

Characteristics of Real TCP/IP Traffic

Network traffic exhibits bursty, wave‑like patterns, with periods of high flow followed by low flow. Both WAN and LAN traffic, as well as web access patterns, show self‑similarity, necessitating a dynamic feedback mechanism that adapts to these characteristics.

2.3 Dynamic Feedback Load Balancing Mechanism

TCP/IP traffic consists of many short transactions and a few long ones that dominate workload. We need a load‑balancing algorithm that distributes bursty traffic more evenly across servers.

We propose a dynamic‑feedback mechanism that controls new connection assignment to balance server load. In the IPVS kernel, weighted round‑robin scheduling is used for new connections, while a user‑space Monitor Daemon periodically gathers server load metrics, computes a composite load, and derives new weights. If the weight change exceeds a threshold, the daemon updates the kernel’s IPVS scheduler. This periodic adjustment forms a negative‑feedback loop that maintains good server utilization.

When a server’s weight is set to zero, existing connections continue to be served, but new connections are not assigned, allowing administrators to gracefully drain and maintain the server without disrupting active sessions.

2.4 Aggregate Load

Aggregate load combines two categories of metrics: input metrics collected by the scheduler and server metrics collected from each server. Input metrics reflect the ratio of new connections to average connections over a time interval. Server metrics include CPU load (LOADi), disk usage (Di), memory usage (Mi), and process count (Pi). These metrics can be obtained via SNMP or a custom agent reporting to the Monitor Daemon.

If a server does not respond within the configured interval, its weight is set to zero. All metric values are normalized to the range [0, ∞), where 1 indicates ideal load, >1 indicates overload, and <1 indicates under‑load.

We introduce adjustable coefficients Ri (∑Ri = 1) to weight each metric’s importance. The aggregate load is calculated as:

For example, in a web server cluster we might use coefficients {0.1, 0.3, 0.1, 0.1, 0.1, 0.3}, giving higher importance to CPU load and response time.

The monitoring interval balances accuracy and overhead; we recommend 5–20 seconds.

2.5 Weight Calculation

Each server starts with an initial weight DEFAULT_WEIGHTi. To prevent weights from growing excessively, they are constrained to [DEFAULT_WEIGHTi, SCALE × DEFAULT_WEIGHTi] with a default SCALE of 10.

The Monitor Daemon periodically computes the aggregate load AGGREGATE_LOADi and updates the weight using the formula:

Here 0.95 is the target utilization, and A (default 5) is an adjustable coefficient. When aggregate load equals 0.95, the weight remains unchanged; higher load reduces the weight, lower load increases it. If the new weight exceeds SCALE × DEFAULT_WEIGHTi, it is capped. Weight changes exceeding the threshold are applied to the kernel; otherwise, no adjustment is made to avoid unnecessary overhead.

If all servers’ weights fall below DEFAULT_WEIGHT, the cluster is overloaded and additional nodes should be added. Conversely, if weights approach SCALE × DEFAULT_WEIGHT, the system is underutilized.