Locality-Based Least-Connection Scheduling

The locality-based least-connection scheduling algorithm is for destination IP load balancing. This algorithm usually directs packet destined for an IP address to its server if the server is alive and under load. If the server is overloaded (its active connection numbers is larger than its weight) and there is a server in its half load, then allocate the weighted least-connection server to this IP address.

The pseudo code of locality-based least-connection scheduling algorithm is as follows:

Supposing there is a server set S = {S0, S1, ..., Sn-1},
W(Si) is the weight of server Si;
C(Si) is the current connection number of server Si;
ServerNode[dest_ip] is a map from destination IP address to server;
WLC(S) is the server of weighted least connection in the server set S;
Now is the current system time.

if (ServerNode[dest_ip] is NULL) then {
    n = WLC(S);
    if (n is NULL) then return NULL;
    ServerNode[dest_ip].server = n;
} else {
    n = ServerNode[dest_ip].server;
    if ((n is dead) OR
        (C(n) > W(n) AND
         there is a node m with C(m) < W(m)/2))) then {
        n = WLC(S);
        if (n is NULL) then return NULL;
        ServerNode[dest_ip].server = n;
    }
}
ServerNode[dest_ip].lastuse = Now;
return n;

The locality-based least-connection scheduling algorithm is usually used in cache cluster, because the destination IP address of request packet varies in transparent proxy cache cluster. The goal of this algorithm is that when load of all the servers are almost balanced, sending the requests for the same IP address to the same server will fully take advantage of access locality and improve cache hit rate at server, and it helps improve the throughput of the whole cluster system.