A Fitted Random Sampling Scheme for Load Distribution in Grid Networks
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.
[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.
[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.
@article{"International Journal of Information, Control and Computer Sciences:52217", author = "O. A. Rahmeh and P. Johnson and S. Lehmann", title = "A Fitted Random Sampling Scheme for Load Distribution in Grid Networks", 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.", volume = "1", number = "6", pages = "1592-6", }
