Abstract:
Grid computing holds the great promise to effectively share geographically distributed heterogeneous resources to solve large-scale complex scientific problems. Scheduling large scale computationally intensive applications in the Grid environment is challenging issue because target resources are heterogeneous and their load and availability may very with time. Further, as resources are geographically distributed in large-scale Grid environments and communication latency is significantly large due to Wide Area Network (WAN) through which resources are connected, job migration cost becomes an imperative factor for load balancing decision. Thus, performance of the Grid system depends greatly on the effective task scheduling and load balancing algorithm.
We address this problem by proposing load balancing algorithms, which are MELISA (Modified ELISA), R-MELISA (Receiver-initiated MELISA) and LBA (Load Balancing on Arrival). The algorithms differ in the way load balancing is carried out and is shown to be efficient in minimizing the response time on large and small scale Grid environments. MELISA and R-MELISA, applicable to large scale systems, is a modified version of ELISA[1] in which we consider job migration cost, resource heterogeneity and network heterogeneity when taking load balancing decision. LBA algorithm, applicable for small scale Grid systems, performs load balancing by estimating expected finish time of a job on buddy processors. One of the unique characteristics of our algorithms is system parameter estimation. Our algorithms estimate system parameters such as job arrival rate, CPU processing rate, load at processor and balance the load by migrating jobs to buddy processors taking into account all affecting factors for load balancing decision.
We quantify the performance of our algorithms using several influencing parameters such as, job size, data transfer rate, status exchange period, migration limit, and we discuss the implications of the performance and choice of our approaches. These load balancing algorithms are simulated in C++ language using Dev C++ software tool.
