Dynamic Load Balancing Strategy for Grid Computing

Authors: Belabbas Yagoubi, Yahya Slimani

Abstract:

Workload and resource management are two essential functions provided at the service level of the grid software infrastructure. To improve the global throughput of these software environments, workloads have to be evenly scheduled among the available resources. To realize this goal several load balancing strategies and algorithms have been proposed. Most strategies were developed in mind, assuming homogeneous set of sites linked with homogeneous and fast networks. However for computational grids we must address main new issues, namely: heterogeneity, scalability and adaptability. In this paper, we propose a layered algorithm which achieve dynamic load balancing in grid computing. Based on a tree model, our algorithm presents the following main features: (i) it is layered; (ii) it supports heterogeneity and scalability; and, (iii) it is totally independent from any physical architecture of a grid.

Keywords: Grid computing, load balancing, workload, tree based model.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1058309

References:

[1] E. Deelman A.Chervenak and al. High performance remote access to climate simulation data: a challenge problem for data grid technologies. In Proceeding. of 22th parallel computing, volume 29(10), pages 13-35, 1997.
[2] E. Badidi. Architecture and services for load balancing in object distributed systems. PhD thesis, Faculty of High Studies, University of Montreal, Mai 2000.
[3] F. Berman, G. Fox, and Y. Hey. Grid Computing: Making the Global Infrastructure a Reality. Wiley Series in Communications Networking & Distributed Systems, 2003.
[4] T.L. Casavant and J.G. Kuhl. A taxonomy of scheduling in general purpose distributed computing systems. IEEE Transactions on Software Engineering, 14(2):141-153, 1994.
[5] D.L. Eager, E.D. Lazowska, and J. Zahorjan. Adaptive load sharing in homogeneous distributed systems. In IEEE Trans. on Soft. Eng., volume 12(5), pages 662-675, 1986.
[6] I. Foster and C. Kesselman. Globus: a metacomputing infrastructure toolkit. Int. Jour. of Super-Computer and High Performance Computing Applications, 11(2):115-128, 1997.
[7] I. Foster and C. Kesselman. The Grid: Blueprint for a New Computing Infrastructure. Morgan Kaufmann, 1998.
[8] GridSim. A grid simulation toolkit for resource modelling and application scheduling for parallel and distributed computing. www.buyya.com/gridsim/.
[9] M. Houle, A. Symnovis, and D. Wood. Dimension-exchange algorithms for load balancing on trees. In Proc. of 9th Int. Colloquium on Structural Information and Communication Complexity, pages 181-196, Andros, Greece, June 2002.
[10] H.D. Karatza. Job scheduling in heterogeneous distributed systems. Journal. of Systems and Software, 56:203-212, 1994.
[11] W. Leinberger, G. Karypis, V. Kumar, and R. Biswas. Load balancing across near-homogeneous multi-resource servers. In 9th Heterogeneous Computing Workshop, pages 60-71, 2000.
[12] XtremWeb. A global computing experimental platform. http://www.lri.fr/fedak/XtremWeb/introduction.php3.
[13] C.Z. Xu and F.C.M. Lau. Load Balancing in Parallel Computers: Theory and Practice. Kluwer, Boston, MA, 1997.
[14] B. Yagoubi. Dynamic load balancing for beowulf clusters. In Proceeding of the 2005 International Arab Conference On information Technology, pages 394-401, Israa University, Jordan, December 6th 8th 2005.
[15] M.J. Zaki, W. Li, and S. Parthasarathy. Customized dynamic load balancing for a network of workstations. In Proc. of the 5th IEEE Int. Symp. HDPC, pages 282-291, 1996.