A Fitted Random Sampling Scheme for Load Distribution in Grid Networks

Authors: O. A. Rahmeh, P. Johnson, S. Lehmann

Abstract:

Grid networks provide the ability to perform higher throughput computing by taking advantage of many networked computer-s resources to solve large-scale computation problems. As the popularity of the Grid networks has increased, there is a need to efficiently distribute the load among the resources accessible on the network. In this paper, we present a stochastic network system that gives a distributed load-balancing scheme by generating almost regular networks. This network system is self-organized and depends only on local information for load distribution and resource discovery. The in-degree of each node is refers to its free resources, and job assignment and resource discovery processes required for load balancing is accomplished by using fitted random sampling. Simulation results show that the generated network system provides an effective, scalable, and reliable load-balancing scheme for the distributed resources accessible on Grid networks.

Keywords: Complex networks, grid networks, load-balancing, random sampling.

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

References:

[1] Foster, I. & Kesselman, K. (1999) The Grid: Blueprint for A Future Computing Infrastructure. Morgan Kaufmann.
[2] L├╝ling R., Monien B. & Ramme F. (1991) A Study of Dynamic Load Balancing Algorithms. Proceedings of the Third IEEE SPDP, 686-689.
[3] Peixoto, L. P. (1996) Load Distribution: A Survey. Technical Report. Dept. De inf, Escola De Engenharia, Universidade Do Minho.
[4] Murata, Y., et al. (2006) A distributed & cooperative load balancing mechanism for large-scale P2P systems. SAINT-W. USA.
[5] Mitzenmacher, M. (2001) The Power of Two Choices in Randomized Load Balancing. IEEE Transactions on Parallel Distribution Systems, 12(10).
[6] Drougas, Y., Repantis, T., and Kalogeraki, V. (2006) Load Balancing Techniques for Distributed Stream Processing Applications in Overlay Environments. ISORC'06, USA.
[7] Bustos, J., Denis Caromel, D., (2006) Load Balancing: Toward the Infinite Network, 12th Workshop on Job Scheduling Strategies for Parallel Processing, Saint-Malo, France.
[8] Theimer, M. M. & Lantz, K. A. (1989) Finding Idle Machines in A Workstation-Based Distributed System. IEEE Transactions on Software Engineering, 15(11).
[9] Oppenheimer, D., Albrecht, J., Patterson, D. & Vahdat, A. (2004) Scalable Wide-Area Resource Discovery. Technical Report, CA, USA.
[10] Subramanian, R. & Scherson, I. (1994) An Analysis of Diffusive Load Balancing. Proc. of the sixth Annual ACM Symposium on Parallel Algorithms & Architectures, ACMPress.
[11] Montresor, A., Meling, H. & Babaoglu, O. (2002) Messor: Load- Balancing Through a Swarm of Autonomous Agents. First Intl. Workshop on Agents & P2P Computing, Italy.
[12] Litzkow, M., Livny, M., & Mutka, M. (1988) Condor: A Hunter of Idle Workstations. Proceedings of the Eighth International Conference of Distributed Computing Systems.
[13] Yagoubi, B., and Slimani, Y. (2007) Task Load Balancing Strategy for Grid Computing. Journal of Computer Science, 3 (3): 186-194.
[14] L├╝ling, R. & Monien, B. (1993) A Dynamic Distributed Load Balancing Algorithm with Provable Good Performance. SPAA -93, ACM Press, New York, USA.
[15] Kremien, O. & Kramer, J. (1992) Methodical Analysis of Adaptive Load Sharing Algorithms. IEEE Trans. On Parallel Distribution System, 3(6).
[16] Erdös, P. & Rényi, A. (1959) On Random Graphs. Publicationes Mathematicae, (6).
[17] Bollobás, B. (1985) Random Graphs. Academic Press, London, England.
[18] Avin, C. & Brito, C. (2004) Efficient and Robust Query Processing in Dynamic Environments Using Random Walk Techniques, Proc. of the third Intl. Symp on Info. Processing in Sensor Networks. ACMPress.
[19] Lov'asz, L. & Winkler, P. (1995) Mixing of Random Walks and Other Diffusions on a Graph. Surveys in Combinatorics, London Mathematical Society Lecture Note Series.
[20] Kleinrock, L. (1975) Queueing Systems. Volume I: Theory. John Wiley & Sons, NY.
[21] Abramowitz, M. & Stegun, I. A. (1972) Handbook of Mathematical Functions with formulas, Graphs, and Mathematical Tables. Dover Publications, 9th Edition, New York.
[22] Adabala, S., Chadha, V., Chawla, P., Figueiredo, R., fortes, J., et al. (2005) From Virtualized Resources to Virtual Computing Grids: the In-Vigo System. Future Generation Computer Systems, 21(6).
[23] Blair, G.S., F. Costa, G. Coulson, H. Duran, et al. (1999) The Design of a Resource-Aware Reflective Middleware Architecture, Proceedings of the 2nd international Conference on Meta-Level Architectures and Reflection, St. Malo, France.
[24] Schantz, R. E. & Schmidt, D. C. (2001) Middleware for Distributed Systems: Evolving the Common Structure for Network-Centric Applications. Encyclopaedia of Software Engineering, Wiley&Sons, New York.