A NOVEL LOAD BALANCING ALGORITHM FOR COMPUTATIONAL GRID

Saravanakumar E.¹*, Gomathy Prathima²*
¹Department of CSE, Adhiyamaan College of Engineering, Hosur, India
²Department 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