A Fuzzy Dynamic Load Balancing Algorithm for Homogenous Distributed Systems
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).
[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.
[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.
@article{"International Journal of Information, Control and Computer Sciences:64226", author = "Ali M. Alakeel", title = "A Fuzzy Dynamic Load Balancing Algorithm for Homogenous Distributed Systems", 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.", volume = "6", number = "1", pages = "128-4", }
