Saravanakumar E.1*, Gomathy Prathima2*
1Department of CSE, Adhiyamaan College of Engineering, Hosur, India
2Department of CSE, Adhiyamaan College of Engineering, Hosur, India
* Corresponding Author : gomathy.prathima@gmail.com
Received : - Accepted : - Published : 15-06-2010
Volume : 1 Issue : 1 Pages : 20 - 26
Int J Comput Intell Tech 1.1 (2010):20-26
Keywords : Grid systems, load balancing, average response time, migration
Conflict of Interest : None declared
The Grid computing environment is a cooperation of distributed computer systems where user jobs can be executed on either local or remote computer. Many problems exist in grid environment. Not only the computational nodes are heterogeneous but also the underlying networks connecting them are heterogeneous. The network bandwidth varies and the network topology among resources is also not fixed. Thus with this multitude of heterogeneous resources, a proper scheduling and efficient load balancing across the Grid is required for improving performance of the system. The load balancing is done by migrating jobs to the buddy processors, a set of processors to which a processor is directly connected. An algorithm, Load Balancing on Arrival (LBA) is proposed for small-scale (intraGrid) systems. It is efficient in minimizing the response time for small-scale grid environment. When a job arrives LBA computes system parameters and expected finish time on buddy processors and the job is migrated immediately. This algorithm estimates system parameters such as job arrival rate, CPU processing rate and load on each processor to make migration decision. This algorithm also considers job transfer cost, resource heterogeneity and network heterogeneity while making migration decision.
[1] Ruchir Shah, Bhardwaj Veeravalli and
Manoj Mishra “On the Design of
Adaptive and Decentralized Load-
Balancing Algorithms with Load
Estimation for Computational
Environments”, IEEE Trans. Parallel
and Distributed Systems, vol 18, no
12, December 2007
» CrossRef » Google Scholar » PubMed » DOAJ » CAS » Scopus
[2] L. Anand, D. Ghose, and V. Mani,
“ELISA: An Estimated Load
Information Scheduling Algorithm for
Distributed Computing Systems,”
Int’l J. Computers and Math. with
Applications, vol. 37, no. 8, pp. 57-
85, Apr. 1999
» CrossRef » Google Scholar » PubMed » DOAJ » CAS » Scopus
[3] M. Arora, S.K. Das, and R. Biswas, “A
De-Centralized Scheduling and
Load Balancing Algorithm for
Heterogeneous Grid Environments,”
Proc. Int’l Conf. Parallel Processing
Workshops (ICPPW ’02), pp. 499-
505, 2002.
» CrossRef » Google Scholar » PubMed » DOAJ » CAS » Scopus
[4] Y. Feng, D. Li, H. Wu, and Y. Zhang, “A
Dynamic Load Balancing Algorithm
Based on Distributed Database
System,” Proc. Fourth Int’l Conf.
High-Performance Computing in the
Asia-Pacific Region, pp. 949-952,
May 2000
» CrossRef » Google Scholar » PubMed » DOAJ » CAS » Scopus
[5] Ian Foster, Carl Kesselman, Steven
Tuecke “The Anatomy of the Grid
Enabling Scalable Virtual
Organizations” Int’l J. High
Performance Computing
Applications, vol. 15, no. 3, pp. 200-
222, 2001. [6] I. Foster and C.
Kesselman, “The Grid: Blueprint for
a Future Computing Infrastructure,”
Morgan Kaufmann, 1999.
» CrossRef » Google Scholar » PubMed » DOAJ » CAS » Scopus
[6] H. Lin and C. Raghavendra, “A
Dynamic Load-Balancing Policy with
a Central Job Dispatcher (LBC),”
IEEE Trans. Software Eng., vol. 18,
no. 2, pp. 148-158, Feb. 1992.
» CrossRef » Google Scholar » PubMed » DOAJ » CAS » Scopus
[7] G. Manimaran and C. Siva Ram
Murthy, “An Efficient Dynamic
Scheduling Algorithm for
Multiprocessor Real¬Time
Systems,” IEEE Trans. Parallel and
Distributed Systems, vol. 9, no. 3,
pp. 312-319, Mar. 1998
» CrossRef » Google Scholar » PubMed » DOAJ » CAS » Scopus
[8] Y. Murata, H. Takizawa, T. Inaba, and
H. Kobayashi, “A Distributed and
Cooperative Load Balancing
Mechanism for Large-Scale P2P
Systems,” Proc. Int’l Symp.
Applications and Internet (SAINT
’06) Workshops, pp. 126-129, Jan.
2006
» CrossRef » Google Scholar » PubMed » DOAJ » CAS » Scopus
[9] L. Oliker, R. Biswas, H. Shan, and W.
Smith, “Job Scheduling in
Heterogeneous Grid Environment,”
Technical Report LBNL-54906,
Lawrence Berkeley Nat’l Laboratory,
2004
» CrossRef » Google Scholar » PubMed » DOAJ » CAS » Scopus
[10] H. Shan, L. Oliker, and R. Biswas, “Job
Superscheduler Architecture
and Performance in
Computational Grid Environments,”
Proc. ACM/IEEE Conf.
Supercomputing, Nov. 2003.
» CrossRef » Google Scholar » PubMed » DOAJ » CAS » Scopus
[11] N. Shivaratri, P. Krueger, and M.
Singhal, “Load Distributing for
Locally Distributed Systems,”
Computer, vol. 25, no. 12, pp. 33-
44, Dec. 1992
» CrossRef » Google Scholar » PubMed » DOAJ » CAS » Scopus
[12] L. Smarr and C.E. Catlett,
“Metacomputing,” Comm. ACM, vol.
35, no. 6, pp. 44-52, June 1992
» CrossRef » Google Scholar » PubMed » DOAJ » CAS » Scopus
[13] J. Watts and S. Taylor, “A Practical
Approach to Dynamic Load
Balancing,” IEEE Trans. Parallel
and Distributed Systems, vol. 9, no.
3, pp. 235-248, Mar. 1998
» CrossRef » Google Scholar » PubMed » DOAJ » CAS » Scopus
[14] M. Willebeek-LeMair and A. Reeves,
“Strategies for Dynamic Load
Balancing on Highly Parallel
Computers,” IEEE Trans. Parallel
and Distributed Systems, vol. 9, no.
4, pp. 979-993, Sept.1993
» CrossRef » Google Scholar » PubMed » DOAJ » CAS » Scopus
[15] M.J. Zaki and W.L.S. Parthasarathy,
“Customized Dynamic Load
Balancing for a Network of
Workstations,” J. Parallel and
Distributed Computing, vol. 43, no.
2, pp.156-162, June 1997.
» CrossRef » Google Scholar » PubMed » DOAJ » CAS » Scopus