Locality-Based Least-Connection with Replication Scheduling

The locality-based least-connection with replication (LBLCR) scheduling algorithm is also for destination IP load balancing. It only differs from the locality-based least-connection (LBLC) scheduling as follows: the load balancer maintains mappings from a target to a set of server nodes that can serve the target. Requests for a target are assigned to the least-connection node in the target's server set. If all the node in the server set are over loaded, it picks up a least-connection node in the cluster and adds it in the sever set for the target. If the server set has not been modified for the specified time, the most loaded node is removed from the server set, in order to avoid high degree of replication.

The pseudo code of locality-based least-connection with replication 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;
ServerSet[dest_ip] is a map from destination IP address to server set;
WLC(S) is the server of weighted least connection in the server set S;
WGC(S) is the server of weighted greatest connections in the server set S;
Now is the current system time;
ServerSet[dest_ip].lastmod is the last modified time of server set for destination IP;
T is the specified time for adjust server set.

if (ServerSet[dest_ip] is NULL) then {
    n = WLC(S);
    if (n is NULL) then return NULL;
    add n into ServerSet[dest_ip];
} else {
    n = WLC(ServerSet[dest_ip]);
    if ((n is NULL) OR
        (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;
        add n into ServerSet[dest_ip];
    } else
    if (|ServerSet[dest_ip]| > 1 AND
        Now - ServerSet[dest_ip].lastmod > T) then {
        m = WGC(ServerSet[dest_ip]);
        remove m from ServerSet[dest_ip];
    }
}
ServerSet[dest_ip].lastuse = Now;
if (ServerSet[dest_ip] changed) then
    ServerSet[dest_ip].lastmod = Now;
return n;

The locality-based least-connection with replication (LBLCR) scheduling algorithm is usually used in cache cluster.