Scheduling in Distributed Computing Environment Using Dynamic Load Balancing

Text sample:

Chapter 3.1 PREAMBLE:

As we have seen in previous chapter, DLB is one of the distributed scheduling techniques, used extensively to improve scalability and overall system throughput in the rapidly growing resource intensive distributed applications. It is responsible for task scheduling as well as monitoring load variation in the system. In such distributed applications, uneven process arrival may cause load imbalance, where some nodes are overloaded while some other nodes are idle. DLB technique distributes processing workload as evenly as possible among the nodes in a cluster. This helps in improving response time by minimizing job's execution time, minimizing communication overheads and maximizing resource utilization. It also tries to preserve fairness in individual job execution so that a low priority process should not be overtaken by an arbitrary number of higher priority processes [Kanungo,2002). DLB is realized through process migration. DLB allows cluster of nodes to be used as a cost effective alternative to mainframe computing as well as parallel computing [Amiri,2000]. Dynamic load balancing is also used to balance load in a cluster of web servers deployed by websites for processing clients' requests [Abdelzaher,2000]. In present chapter, we have investigated some important issues like measurement of processing workload for taking process transfer decisions and measurement of performance of load balancing algorithms [Petri,1995].
DLB approach can create additional overhead in collecting system state, analyzing the data, making load balancing decisions and transferring the processes from one node to another [Wilson,1998]. Performance of load balancing is closely related to the process information made available to the load balancer, accuracy of the load measurement and the efficiency with which such information is used. Load balancing yields greater performance improvement when workload is heavy and unbalanced. The index used to measure the load in the system strongly affects the performance of load balancing algorithm. It may not be possible to include all load indices in calculating the load, as this requires collecting and exchanging huge amount of information. This may lead to excessive communication cost. Moreover, a poor load index may cause some process migrations which do not contribute to balancing the load in the system, thereby making the situation worse [Dessel,2004].
Therefore, basic problem associated with DLB algorithms is to identify the parameters, which are to be used for estimation of the load on various processors and making load management decisions dynamically. This load will define the current state of the system. Effective load index measures will minimize the communication cost in the system and will allow the load balancer to take quick decisions about load distribution, thereby improving the effectiveness of the algorithm. In a heterogeneous environment, load indices must be adjusted to make them comparable. For example, to compare nodes with different processing powers, their processor utilizations may be divided by respective processing capabilities. Multiple load indices may also be used for making placement decisions. The load index should be easily computable and correlated to those parameters which are to be optimized e.g. response time [Dalhin,2000].
Thus, even though it is established that load balancing facility is necessary for improving the performance of a distributed system, the important issues like load index selection, performance measurement parameters and quality of algorithm needs to be investigated further and are being considered in this chapter.
3.2 LOAD INFORMATON MANAGEMENT:

Transfer of processes from overloaded nodes to underloaded nodes requires load balancer to collect load information from the nodes continuously. This helps in identifying overloaded nodes, underloaded nodes and the processes to be transferred. Load information management is therefore a critical issue in DLB. The load balancer must have a global knowledge of load on the nodes in the system at any instant. Although entire state of a node may be transferred, typically only selective information is exchanged to minimize the communication cost. In fact, just a little information may lead to substantial and sometimes, even dramatic performance improvement over no load balancing and perform nearly as well as more complex policies that use large amount of information [Milojicic,2000].
Almost all the load balancing policies require some sort of load indices to measure the workload. Most fundamental issue is the selection of load index to be used in measurement of the load. The choice of load index greatly affects the performance of DLB. We are considering following load indices:

3.2.1 Parameters for Static Load Balancing:

In static algorithms, load balancing is performed at the compile time before the start of execution of processes. The following parameter may be used in static load balancing:

(a) Processor parameters including number of processors, speed of processors and ratio of speed of ith processor with respect to a base processor.
(b) The program parameters including data size, number of loop iterations, work per iteration, data communication per iteration and execution time of each iteration on a base processor.
(c) Network parameters including network latency, network bandwidth and network topology.
On the other hand, DLB algorithms collect load information at run time. This information is based on some load index or combination of load indices. Parameters used for load measurement in DLB are being discussed in the following sections.