A Fuzzy Dynamic Load Balancing Algorithm for Homogenous Distributed Systems

Authors: Ali M. Alakeel

Abstract:

Load balancing in distributed computer systems is the process of redistributing the work load among processors in the system to improve system performance. Most of previous research in using fuzzy logic for the purpose of load balancing has only concentrated in utilizing fuzzy logic concepts in describing processors load and tasks execution length. The responsibility of the fuzzy-based load balancing process itself, however, has not been discussed and in most reported work is assumed to be performed in a distributed fashion by all nodes in the network. This paper proposes a new fuzzy dynamic load balancing algorithm for homogenous distributed systems. The proposed algorithm utilizes fuzzy logic in dealing with inaccurate load information, making load distribution decisions, and maintaining overall system stability. In terms of control, we propose a new approach that specifies how, when, and by which node the load balancing is implemented. Our approach is called Centralized-But-Distributed (CBD).

Keywords: Dynamic load balancing, fuzzy logic, distributed systems, algorithm.

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

References:

[1] I. Ahmed and A. Ghafoor, "Semi-Distributed Load Balancing for Massively Parallel Multicomputers," IEEE Trans. Software Eng., vol. 17, no. 10, pp 987-1004, October 1991.
[2] T. L. Casavant, "A Taxonomy of Scheduling in General-Purpose Distributed Computing Systems," IEEE Trans. Software Eng., vol 14, no. 2, pp 141-154, February 1988.
[3] Y. Wang and R. Morris, "Load Sharing in Distributed Systems," IEEE Trans. Comput., vol. C-34, no. 3, pp. 204-217, Mar. 1985.
[4] K. Ramamritham, J. A. Stankovic, and W. Zhao, "Distributed Scheduling of Tasks with Deadlines and Resource Requirements," IEEE Trans. Comput., vol. 38, no. 8, pp 1110-1123, August 1989.
[5] J. A. Stankovic, K. Ramamritham, and S. Cheng, "Evaluation of a Flexible Task Scheduling Algorithm for Distributed Hard Real-Time Systems," IEEE Trans. Comput., vol. C-34, no. 12, pp. 1130-1143, December 1985.
[6] D.L. Eager, E.D. Lazowski, and J. Zahorjan, "Adaptive Load Sharing in Homogeneous Distributed Systems," IEEE Trans. Software Eng., vol. SE-12, no. 5, pp. 662-675, May 1986.
[7] L. M. Ni, C. Xu, and T. B. Gendreau, "A Distributed Drafting Algorithm for Load Balancing," IEEE Trans. Software Eng., vol.SE-11, no. 10, pp. 1153-1161, October 1985.
[8] D. L. Eager and E. D. Lazowski, and J. Zahorjan, "A Comparision of Receiver-Inititated and Sender Initiated Adaptive Load Sharing," Performance Evaluation, 6, pp. 53-68, March, 1986.
[9] G. Cybenko, "Dynamic load balancing for distributed memory multiprocessors," J. Parallel Distrib. Comput. 7 (1989), pp. 279-301.
[10] J. Watts, S. Taylor, "A practical approach to dynamic load balancing," IEEE Trans. Parallel Distrib. Systems 9 (3) (March 1998), pp. 235-248.
[11] P. Krueger, N.G. Shivaratri, "Adaptive location policies for global scheduling," IEEE Trans. Software Eng. 20 (6), pp. 432-444, June 1994.
[12] S. Dhakal, M. M. Hayat, J.E.Pezoa, C. Yang, and D. Bader, "Dyanmic Load Balancing in Distributed System in the Presence of Delays: A Regeneration-Therory Approach,", IEEE Transactions on Parallel and Distributed Systems, vol. 18, no. 4, April 2007.
[13] D. J. Evans and W.U.N. Butt," Dynamic load balancing using tasktransfer probabilities," Parallel Computing, Vol. 19, No. 8, pp. 897-916, August 1993.
[14] A. M. Alakeel, "Load Balancing in Distributed Computer Systems," Int. Journal of Computer Science and Information Security, Vol. 8, No. 4, pp. 8-13, July 2010.
[15] A. M. Alakeel, "A Guide to Load Balancing in Distributed Computer Systems," Int. Journal of Computer Science and Network Security, Vol. 10, No. 6, pp. 153-160, June 2010.
[16] K. Abini, "Fuzzy Decision Making for Load Balancing in a Distributed System, " Proceedings of the 36th Midwest Symposium Circuits and Systems, pp. 500-502, 1993.
[17] Yu-Kwong Kwok, Lap-Sun Cheung, "A new fuzzy-decision based load balancing system for distributed object computing," Journal of Parallel and Distributed Computing, Volume 64, Issue 2, pp. 238-253, February 2004.
[18] L. Singh, A. Narayan, and S. Kumar, "Dynamic fuzzy load balancing on LAM/MPI clusters with applications in parallel master-slave implementations of an evolutionary neuro-fuzzy learning system," IEEE International Conference on Fuzzy Systems, pp.1782-1788, , June 2008.
[19] C.W. Cheong, V. Ramachandran, "Genetic Based Web Cluster Dynamic Load Balancing in Fuzzy Environment," Proceedings of the Fourth International Conference on High Performance Computing in the Asia- Pacific Region, Beijing, China, Vol. 2, pp. 714-719, 2000.
[20] P. Chulhye, J.G. Kuhl, "A fuzzy-based distributed load balancing algorithm for large distributed systems," Proceedings of the Second International Symposium on Autonomous Decentralized Systems, pp. 266-273, April 1995.
[21] M. Rantonen, T. Frantti, and K. Leiviskä, "Fuzzy expert system for load balancing in symmetric multiprocessor systems," Journal of Expert Systems with Applications, Vol. 37 No. 12, pp. 8711-8720, December, 2010.
[22] L. Singh, A. Narayan, and S. Kumar, "Dynamic fuzzy load balancing on LAM/MPI clusters with applications in parallel master-slave implementations of an evolutionary neuro-fuzzy learning system," IEEE International Conference on Fuzzy Systems, pp.1782-1788, June 2008.
[23] I. Barazandeh, S. S. Mortazavi, and A. M. Rahmani, "Intelligent fuzzy based biasing load balancing algorithm in distributed systems," IEEE 9th Malaysia International Conference, pp.713-718, Dec. 2009.
[24] E. El-Abd, "Load blancing in distrubuted computing systesms using fuzzy sexpert ssytems, " Int. Confernce on Modern Probmesn of Radio Engiennering, Telecommunications and Computer Scinece, Lviv- Slavsko, Ukraine, pp. 141-144, 2000.
[25] S. Dierkes, "Load balancing with a fuzzy-decision algorithm," Inform. Sci. 97 (1-2), pp. 159-177, March 1997.
[26] Shaout, P. McAuliffe, "Job scheduling using fuzzy load balancing in distributed system," Electron. Lett. 34 (20), pp. 1983-1985, October 1998.
[27] K.-W.Wong, "Fuzzy routing control of service request messages in an individual computing environment," Proceedings of ACM Symposium on Applied Computing, Nashville, TN, pp. 548-551, 1995.
[28] Ajoy Kumar, Mukesh Singhal, Ming T(M&e) Liu, "A Model for Distributed Decision Making: An Expert System for Load Balancing in Distributed Systems", IEEE computer software and applications conference, 1987.
[29] L. A. Zadeh, "Fuzzy Sets," Information and Control, No. 8, pp. 338-353, 1965.
[30] B. Kosko, "Neural Networks and Fuzzy Systems: A Dynamical Systems Approach to Machine Intelligence," Prentice-Hall, Englewood Cliffs, NJ, 1992.
[31] J. Giarratano, "Expert Systems: Principles and Programming," PWSKENT Publishing Company, Boston, 1989.