On the Design of Adaptive and Decentralized Load Balancing Algorithms with Load Estimation for Computational Grid Environments

In this paper, we address several issues that are imperative to grid environments such as handling resource heterogeneity and sharing, communication latency, job migration from one site to other, and load balancing. We address these issues by proposing two job migration algorithms, which are MELISA...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on parallel and distributed systems 2007-12, Vol.18 (12), p.1675-1686
Main Authors: Shah, R., Veeravalli, B., Misra, M.
Format: Article
Language:English
Subjects:
Algorithm design and analysis
Algorithms
Arrivals
average response time
communication delays
Costs
Delay
Distributed computing
ELISA
Grid computing
Grid systems
Heterogeneity
Heuristic algorithms
Load balancing
Load balancing (computing)
Load management
Migration
Processor scheduling
Processors
Product introduction
Resource management
Scheduling algorithm
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, we address several issues that are imperative to grid environments such as handling resource heterogeneity and sharing, communication latency, job migration from one site to other, and load balancing. We address these issues by proposing two job migration algorithms, which are MELISA (modified ELISA) 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 heterogeneous grid environments, respectively. MELISA, which is applicable to large-scale systems (that is, interGrid), is a modified version of ELISA in which we consider the job migration cost, resource heterogeneity, and network heterogeneity when load balancing is considered. The LBA algorithm, which is applicable to small-scale systems (that is, intraGrid), performs load balancing by estimating the expected finish time of a job on buddy processors on each job arrival. Both algorithms estimate system parameters such as the job arrival rate, CPU processing rate, and load on the processor and balance the load by migrating jobs to buddy processors by taking into account the job transfer cost, resource heterogeneity, and network heterogeneity. We quantify the performance of our algorithms using several influencing parameters such as the job size, data transfer rate, status exchange period, and migration limit, and we discuss the implications of the performance and choice of our approaches.
ISSN:1045-9219
1558-2183
DOI:10.1109/TPDS.2007.1115