Difference between revisions of "Weighted Least-Connection Scheduling"

From LVSKB
Jump to: navigation, search
 
m (Introduction)
 
(4 intermediate revisions by the same user not shown)
Line 1: Line 1:
The weighted least-connection scheduling is a superset of the least-connection scheduling, in which you can assign a performance weight to each real server. The servers with a higher weight value will receive a larger percentage of live connections at any one time. The Virtual Server Administrator can assign a weight to each real server, and network connections are scheduled to each server in which the percentage of the current number of live connections for each server is a ratio to its weight. The default weight is one.
+
== Introduction ==
  
The weighted least-connections scheduling works as follows:
+
The weighted least-connection scheduling is a superset of the [[Least-Connection Scheduling|least-connection scheduling]], in which you can assign a performance weight to each real server. The servers with a higher weight value will receive a larger percentage of active connections at any one time. The default server weight is one, and the [[IPVS]] Administrator or monitoring program can assign any weight to real server. In the weighted least-connections scheduling, new network connection is assigned to a server which has the least ratio of the current active connection number to its weight.
  
  Supposing there is n real servers, each server i has weight Wi (i=1,..,n), and alive
+
== Algorithm ==
  connections Ci (i=1,..,n), ALL_CONNECTIONS is the sum of Ci (i=1,..,n), the next network
+
 
connection will be directed to the server j, in which
+
The weighted least-connection scheduling works 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;
 +
CSUM = ΣC(Si) (i=0, 1, .. , n-1) is the sum of current connection numbers;
 
   
 
   
  (Cj/ALL_CONNECTIONS)/Wj = min { (Ci/ALL_CONNECTIONS)/Wi } (i=1,..,n)
+
  The new connection is assigned to the server j, in which
 +
  (C(Sm) / CSUM)/ W(Sm) = min { (C(Si) / CSUM) / W(Si)} (i=0, 1, . , n-1),
 +
  where W(Si) isn't zero
 +
Since the CSUM is a constant in this lookup, there is no need to divide by CSUM,
 +
the condition can be optimized as
 +
  C(Sm) / W(Sm) = min { C(Si) / W(Si)}  (i=0, 1, . , n-1), where W(Si) isn't zero
 
   
 
   
  Since the ALL_CONNECTIONS is a constant in this lookup, there is no need to divide Ci by
+
  Since division operation eats much more CPU cycles than multiply operation, and Linux
  ALL_CONNECTIONS, it can be optimized as
+
  does not allow float mode inside the kernel, the condition C(Sm)/W(Sm) > C(Si)/W(Si)
 +
can be optimized as C(Sm)*W(Si) > C(Si)*W(Sm). The scheduling should guarantee
 +
that a server will not be scheduled when its weight is zero. Therefore, the pseudo
 +
code of weighted least-connection scheduling algorithm is
 
   
 
   
  Cj/Wj = min { Ci/Wi } (i=1,..,n)
+
  for (m = 0; m < n; m++) {
 +
    if (W(Sm) > 0) {
 +
        for (i = m+1; i < n; i++) {
 +
            if (C(Sm)*W(Si) > C(Si)*W(Sm))
 +
                m = i;
 +
        }
 +
        return Sm;
 +
    }
 +
}
 +
return NULL;
 +
 
 +
The weighted least-connection scheduling algorithm requires additional division than the [[Least-Connection Scheduling|least-connection scheduling]]. In a hope to minimize the overhead of scheduling when servers have the same processing capacity, both the [[Least-Connection Scheduling|least-connection scheduling]] and the weighted least-connection scheduling algorithms are implemented.
  
The weighted least-connection scheduling algorithm requires additional division than the least-connection. In a hope to minimize the overhead of scheduling when servers have the same processing capacity, both the least-connection scheduling and the weighted least-connection scheduling algorithms are implemented.
+
== Usage ==
  
 
[[Category:Job Scheduling Algorithms]]
 
[[Category:Job Scheduling Algorithms]]

Latest revision as of 04:48, 17 December 2006

Introduction

The weighted least-connection scheduling is a superset of the least-connection scheduling, in which you can assign a performance weight to each real server. The servers with a higher weight value will receive a larger percentage of active connections at any one time. The default server weight is one, and the IPVS Administrator or monitoring program can assign any weight to real server. In the weighted least-connections scheduling, new network connection is assigned to a server which has the least ratio of the current active connection number to its weight.

Algorithm

The weighted least-connection scheduling works 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;
CSUM = ΣC(Si) (i=0, 1, .. , n-1) is the sum of current connection numbers;

The new connection is assigned to the server j, in which
  (C(Sm) / CSUM)/ W(Sm) = min { (C(Si) / CSUM) / W(Si)}  (i=0, 1, . , n-1),
  where W(Si) isn't zero
Since the CSUM is a constant in this lookup, there is no need to divide by CSUM,
the condition can be optimized as
  C(Sm) / W(Sm) = min { C(Si) / W(Si)}  (i=0, 1, . , n-1), where W(Si) isn't zero

Since division operation eats much more CPU cycles than multiply operation, and Linux
does not allow float mode inside the kernel, the condition C(Sm)/W(Sm) > C(Si)/W(Si)
can be optimized as C(Sm)*W(Si) > C(Si)*W(Sm). The scheduling should guarantee
that a server will not be scheduled when its weight is zero. Therefore, the pseudo
code of weighted least-connection scheduling algorithm is

for (m = 0; m < n; m++) {
    if (W(Sm) > 0) {
        for (i = m+1; i < n; i++) {
            if (C(Sm)*W(Si) > C(Si)*W(Sm))
                m = i;
        }
        return Sm;
    }
}
return NULL;

The weighted least-connection scheduling algorithm requires additional division than the least-connection scheduling. In a hope to minimize the overhead of scheduling when servers have the same processing capacity, both the least-connection scheduling and the weighted least-connection scheduling algorithms are implemented.

Usage