Job Scheduling Algorithms In Linux Virtual Server Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

The virtual service is assigned a scheduling algorithm that is used to allocate incoming connections to the real servers. In LVS the schedulers are implemented as separate kernel modules. Thus new schedulers can be implemented without modifying the core LVS code.

There are many different scheduling algorithms available to suit a variety of needs. The simplest are round robin and least connected scheduling algorithms. These work using a simple strategy of allocating connections to each real server in turn and allocating connections to the real server with the least number of connections respectively. Weighted variants of these schedulers allow connections to be allocated proportional to the weighting of the real server, more powerful real servers can be set with a higher weight and thus, will be allocated more connections.

More complex scheduling algorithms have been designed for specialised purposes. For instance to ensure that requests for the same IP address are sent to the same real server.

4.1 Job Scheduling Algorithms in Linux Virtual Server (LVS)

Job scheduling algorithms implemented in Linux Virtual Server are

Round-Robin Scheduling

Weighted Round-Robin Scheduling

Least-Connection Scheduling

Weighted Least-Connection Scheduling

Destination Hashing Scheduling

Source Hashing Scheduling

Never Queue Scheduling

4.1.1 Round-Robin Scheduling

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 servers.

4.1.2 Weighted Round-Robin Scheduling

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. Servers with higher weights receive new connections first than those with less weights, and servers with higher weights get more connections than those with less weights and servers with equal weights get equal connections. 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 . 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 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.

Actually, the round-robin scheduling is a special instance of the weighted round-robin scheduling, in which all the weights are equal.

4.1.3 Least-Connection Scheduling

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.

With the least-connection scheduling method, when a new request for a service running on one of the cluster nodes arrives at the Director, the Director looks at the number of active and inactive connections to determine which cluster node should get the request. The mathematical calculation performed by the Director to make this decision is as follows: For each node in the cluster, the Director multiplies the number of active connections the cluster node is currently servicing by 256, and then it adds the number of inactive connections (recently used connections) to arrive at an overhead value for each node. The node with the lowest overhead value wins and is assigned the new incoming request for service. If the mathematical calculation results in the same overhead value for all of the cluster nodes, the first node found in the IPVS table of cluster nodes is selected.

4.1.4 Weighted Least-Connection Scheduling

The weighted least-connection scheduling method combines the least connection method and a specified weight or ranking for each server to select the cluster node. (This is the default selection method if you do not specify one.) This method was intended for use in clusters with nodes that have differing processing capabilities. The Director determines which cluster node to assign to a new inbound request for a cluster service by first calculating the overhead value (as described earlier in the discussion of the LC scheduling method) for each cluster node and then dividing this value by the weight you have assigned to the cluster node to arrive at a WLC value for each cluster node. The cluster node with the lowest WLC value wins, and the incoming request is assigned to that node. If the WLC value for all of the nodes is the same, the first node found in the list of cluster nodes is selected. The WLC scheduling method is a good choice for a Linux Cluster because it does a good job of balancing the workload of a typical enterprise.

4.1.5 Destination Hashing Scheduling

The destination hashing scheduling algorithm assigns network connections to the servers through looking up a statically assigned hash table by their destination IP addresses.

4.1.6 Source Hashing Scheduling

The source hashing scheduling algorithm assigns network connections to the servers through looking up a statically assigned hash table by their source IP addresses.

This method can be used when the Director needs to be sure the reply packets are sent back to the same router or firewall that the requests came from. This scheduling method is normally only used when the Director has more than one physical network connection, so that the Director knows which firewall or router to send the reply packet back through to reach the proper client computer.

4.1.7 Never Queue Scheduling

The never queue scheduling algorithm adopts a two-speed model. When there is an idle server available, the job will be sent to the idle server, instead of waiting for a fast one. When there is no idle server available, the job will be sent to the servers that minimize its expected delay (The Shortest Expected Delay scheduling algorithm).