Difference between revisions of "Round-Robin Scheduling"
| Line 1: | Line 1: | ||
| − | The round-robin scheduling algorithm assigns jobs to all participants in round-robin manner. For example, there are three servers (server A, B and C) in round-robin scheduling, the first request would go to server A, the second request would go to server B, the third request would go to server C, and the fourth request would go to server A, then repeat in round-robin manner. The formal procedure of round-robin scheduling is as follows: | + | The round-robin scheduling algorithm assigns jobs to all participants in round-robin manner. For example, there are three servers (server A, B and C) in round-robin scheduling, the first request would go to server A, the second request would go to server B, the third request would go to server C, and the fourth request would go to server A, then repeat in round-robin manner. In mathematical form, it selects server by '''''i = (i + 1) mod n''''' every time, where n is the number of servers. |
| + | |||
| + | In the [[IPVS]] implementation, an extra condition was introduced in the round-robin scheduling to check if a server is available or not, because a server may be taken out of service for either masking server failure or system maintenance. The formal procedure of round-robin scheduling is as follows: | ||
Supposing that there are n servers in the set S = {S''0'', S1, ..., Sn-1}, where n > 0; | Supposing that there are n servers in the set S = {S''0'', S1, ..., Sn-1}, where n > 0; | ||
i indicates the server selected last time, and i is initialized with -1; | i indicates the server selected last time, and i is initialized with -1; | ||
Revision as of 14:55, 19 July 2005
The round-robin scheduling algorithm assigns jobs to all participants in round-robin manner. For example, there are three servers (server A, B and C) in round-robin scheduling, the first request would go to server A, the second request would go to server B, the third request would go to server C, and the fourth request would go to server A, then repeat in round-robin manner. In mathematical form, it selects server by i = (i + 1) mod n every time, where n is the number of servers.
In the IPVS implementation, an extra condition was introduced in the round-robin scheduling to check if a server is available or not, because a server may be taken out of service for either masking server failure or system maintenance. The formal procedure of round-robin scheduling is as follows:
Supposing that there are n servers in the set S = {S0, S1, ..., Sn-1}, where n > 0;
i indicates the server selected last time, and i is initialized with -1;
j = i;
do {
j = (j + 1) mod n;
if (Available(Sj)) {
i = j;
return Si;
}
} while (j != i);
return NULL;
It treats all real servers as equals regardless of the number of incoming connections or response time each server is experiencing. It doesn't need to record the status of each server, thus it can be called a stateless scheduling algorithm.
IP Virtual Server of round-robin scheduling provides a few advantages over traditional round-robin DNS. Round-robin DNS resolves a single domain to the different IP addresses, the scheduling granularity is host-based, and the caching of DNS queries hinders the basic algorithm, these factors lead to significant dynamic load imbalances among the real servers. The scheduling granularity of IPVS is per network connection, and it is much superior to round-robin DNS due to the fine scheduling granularity.
The round-robin scheduling algorithm has the great advantage of the fact that it is easy to implement in software. It is a simple and classic scheduling algorithm, it's widely used in modern computer systems.
