<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<title>Virtual Server Scheduling Algorithms</title>
</head>
<body text="#000000" bgcolor="#FFFFFF" link="#0000FF" vlink="#FF0000">
<h1>Virtual Server Scheduling Algorithms</h1>
<p>This page describes some scheduling algorithms implemented on
Linux virtual server.</p>
<h2>Round-Robin Scheduling</h2>
<p>The round-robin scheduling algorithm sends each incoming request to
the next server in it's list. Thus in a three server cluster (servers
A, B and C) request 1 would go to server A, request 2 would go to
server B, request 3 would go to server C, and request 4 would go to
server A, thus completing the cycling or 'round-robin' of servers. It
treats all real servers as equals regardless of the number of incoming
connections or response time each server is experiencing. Virtual
Server 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 Virtual Server is network connection-based,
and it is much superior to round-robin DNS due to the fine scheduling
granularity.</p>
<h2>Weighted Round-Robin Scheduling</h2>
<p>The weighted round-robin scheduling is designed to better handle
servers with 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 AABABCABC 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.</p>
<p>The weighted round-robin scheduling is better than the round-robin
scheduling, when the processing capacity of real servers are
different. However, it may lead to dynamic load imbalance among the
real servers if the load of the requests vary highly. In short, there
is the possibility that a majority of requests requiring large
responses may be directed to the same real server.</p>
<p>Actually, the round-robin scheduling is a special instance of the
weighted round-robin scheduling, in which all the weights are
equal.</p>
<h2>Least-Connection Scheduling</h2>
<p>The least-connection scheduling algorithm directs network
connections to the server with the least number of established
connections. This is one of the dynamic scheduling algorithms;
because it needs to count live connections for each server
dynamically. For a Virtual Server that is managing a collection of
servers with similar performance, least-connection scheduling
is good to smooth distribution when the load of requests vary a
lot. Virtual Server will direct requests to the real server
with the fewest active connections.</p>
<p>At a first glance it might seem that 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,
during this 2 minutes a busy web site often receives thousands of
connections, for example, the server A is twice as powerful as
the server B, the server A is processing thousands of requests
and keeping them in the TCP's TIME_WAIT state, but 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.</p>
<h2>Weighted Least-Connection Scheduling</h2>
<p>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.</p>
<p>The weighted least-connections scheduling works as follows:</p>
<blockquote>
<p>Supposing there is n real servers, each server i has
weight W<sub>i</sub> (i=1,..,n), and alive connections C<sub>i</sub>
(i=1,..,n), ALL_CONNECTIONS is the sum of C<sub>i</sub>
(i=1,..,n), the next network connection will be directed to
the server j, in which</p>
<blockquote>
<p>(C<sub>j</sub>/ALL_CONNECTIONS)/W<sub>j</sub> = min {
(C<sub>i</sub>/ALL_CONNECTIONS)/W<sub>i</sub> }
(i=1,..,n)</p>
</blockquote>
<p>Since the ALL_CONNECTIONS is a constant in this lookup,
there is no need to divide C<sub>i</sub> by ALL_CONNECTIONS,
it can be optimized as</p>
<blockquote>
<p>C<sub>j</sub>/W<sub>j</sub> = min { C<sub>i</sub>/W<sub>i</sub>
} (i=1,..,n)</p>
</blockquote>
</blockquote>
<p>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.</p>
<h2>Locality-Based Least-Connection Scheduling</h2>
<p>The locality-based least-connection scheduling algorithm is for
destination IP load balancing. It is usually used in cache cluster.
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.
<h2>Locality-Based Least-Connection with Replication scheduling</h2>
<p>The locality-based least-connection with replication scheduling
algorithm is also for destination IP load balancing. It is
usually used in cache cluster. It differs from the 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.
<h2>Destination Hashing Scheduling</h2>
<p>The destination hashing scheduling algorithm assigns network
connections to the servers through looking up a statically assigned
hash table by their destination IP addresses.
<h2>Source Hashing Scheduling</h2>
<p>The source hashing scheduling algorithm assigns network
connections to the servers through looking up a statically assigned
hash table by their source IP addresses.
<hr>
<p align="center">
<font size="-1">
$Id: scheduling.html,v 1.2 2001/06/07 20:09:39 copeland Exp $
<br>Created on: 1998/11/20</p>
</body>
</html>
