This page describes some scheduling algorithms implemented on Linux virtual server.
Round-robin scheduling algorithm, in its word meaning, directs the network connections to the different server in a round-robin manner. It treats all real servers as equals regardless of number of connections or response time. Although the round-robin DNS works in this way, there are quite different. The round-robin DNS resolves the single domain to the different IP addresses, the scheduling granularity is host-based, and the caching of DNS hinder the algorithm take effect, these will lead to significant dynamic load imbalance among the real servers. The scheduling granularity of virtual server is network connection-based, and it is much superior to the round-robin DNS due to the fine scheduling granularity.
The weighted round-robin scheduling can treat the real servers of different processing capacities. Each server can be assigned a weight, an integer value that indicates the processing capacity. The default weight is 1. For example, the real servers, A, B and C, have the weights, 4, 3, 2 respectively, a good scheduling sequence will be ABCABCABA in a scheduling period (mod sum(Wi)). In the implementation of the weighted round-robin scheduling, a scheduling sequence will be generated according to the server weights after the rules of virtual server are modified. The network connections are directed to the different real servers based on the scheduling sequence in a round-robin manner.
The weighted round-robin scheduling doesn't need to count the network connections for each real server, and the overhead of scheduling is smaller than dynamic scheduling algorithms, it can have more real servers. However, it may lead to dynamic load imbalance among the real servers if the load of requests vary highly. In short, there is possible that most of long requests may be directed to a real server.
The round-robin scheduling is a special instance of the weighted round-robin scheduling, in which all the weights are equal. The overhead of generating the scheduling sequence after modifying the virtual server rules is trivial, and it doesn't add any overhead in real scheduling. So, there is unnecessary to implement the round-robin scheduling alone.
The least-connection scheduling algorithm directs network connections to the server with the least number of established connections. This is one of dynamic scheduling algorithms; because it needs to count live connections for each server dynamically. At a virtual server where there is a collection of servers with similar performance, the least-connection scheduling is good to smooth distribution when the load of requests vary a lot, because all long requests won't have chance to be directed to a server.
At a first look, the least-connection scheduling can also perform well even when there are servers of various processing capacities, because the faster server will get more network connections. In fact, it cannot perform very well because of the TCP's TIME_WAIT state. The TCP's TIME_WAIT is usually 2 minutes, between this 2 minutes a busy web site often get thousands of connections, for example, the server A is twice as powerful as the server B, the server A has processing thousands of requests and kept them in the TCP's TIME_WAIT state, but the server B is crawling to get its thousands of connections finished. So, the least-connection scheduling cannot get load well balanced among servers with various processing capacities.
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.
The weighted least-connections scheduling works as follows:
Supposing there is n real servers, each server i has weight Wi (i=1,..,n), and alive 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
(Cj/ALL_CONNECTIONS)/Wj = min { (Ci/ALL_CONNECTIONS)/Wi } (i=1,..,n)
Since the ALL_CONNECTIONS is a constant in this lookup, there is no need to divide Ci by ALL_CONNECTIONS, it can be optimized as
Cj/Wj = min { Ci/Wi } (i=1,..,n)
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.
Last updated: 1998/11/20
Created on: 1998/11/20