International Journal of Information Technology and Computer Science (IJITCS)
IJITCS Vol. 6, No. 8, 8 Jul. 2014
Cover page and Table of Contents: PDF (size: 614KB)
An Efficient Diffusion Load Balancing Algorithm in Distributed System
Full Text (PDF, 614KB), PP.65-71
Views: 0 Downloads: 0
Author(s)
Rafiqul Z. Khan
1,*
Md F. Ali
1
Index Terms
Distributed System, Load Balancing, Under Loaded, Overloaded, Overheads
Abstract
In distributed computing system some nodes are very fast and some are slow and during the computation many fast nodes become idle or under loaded while the slow nodes become over loaded due to the uneven distribution of load in the system. In distributed system, the most common important factor is the information collection about loads on different nodes. The success of load balancing algorithm depends on how quickly the information about the load in the system is collected by a node willing to transfer or accept load. In this paper we have shown that the number of communication overheads depends on the number of overloaded nodes present in the domain of an under loaded nodes and vice-versa. We have also shown that communication overhead for load balancing is always fairly less than KN but in worst case our algorithm’s complexity becomes equal to KN.
Cite This Paper
Rafiqul Z. Khan, Md F. Ali, "An Efficient Diffusion Load Balancing Algorithm in Distributed System", International Journal of Information Technology and Computer Science(IJITCS), vol.6, no.8, pp.65-71, 2014. DOI:10.5815/ijitcs.2014.08.09
Reference
[1]Garshasbi M S and Effatparvar M. High Performance Scheduling in Parallel Heterogeneous Multiprocessor Systems Using Evolutionary Algorithms. I.J. Intelligent Systems and Applications, 2013, (11), 89-95.
[2]Fotohi R and Effatparvar M. A Cluster Based Job Scheduling Algorithm for Grid Computing. I.J. Information Technology and Computer Science, 2013, 12, 70-77
[3]Ali M. Alakeel, "Load Balancing in Distributed Computer Systems", International Journal of Computer Science and Information Security, Vol. 8, No. 4, 2010.
[4]Ali M. Alakeel, "A Guide to Dynamic Load Balancing in Distributed Computer Systems", International Journal of Computer Science and Network Security, VOL.10 No.6, June 2010.
[5]Haddad E. Dynamic Optimization of Load Distribution in Heterogeneous Systems. IEEE,1994, pp. 29-34.
[6]Weinrib and Shenker S. Greed is not Enough: Adaptive Load Sharing in Large Heterogeneous Systems. INFOCOM, 1988, pp. 986-994.
[7]Sánchez D, MacíasE Mª and Suárez Á. Effective Load Balancing on a LAN-WLAN Cluster. PDPTA 2003, pp. 473-479.
[8]Penmatsa S and Cronopoulos A T. Dynamic Multi User Load Balancing in Distributed Systems. IEEE International Parallel and Distributed Processing Symposium, 2007, pp. 1-10.
[9]Berenbrink P, Friedetzky T and Steger A. Randomized and Adversarial Load Balancing.CiteSeerx, 1997.
[10]Hamdi M and Lin C K. Dynamic Load Balancing of Data Parallel Applications on a Distributed Network. In 9th International Conference on Supercomputing, ACM, 170-179, 1995.
[11]Kabalan K Y, Smari W W and Hakimian J Y. Adaptive Load Sharing in Heterogeneous System: Policies, Modifications and Simulation.CiteSeerx, 2008.
[12]Penmatsa S. and Cronopoulos A.T. “Dynamic Multi User Load Balancing in Distributed Systems”. IEEE International Parallel and Distributed Processing Symposium, 2007.
[13]Weinrib and Shenker S. “Greed is not Enough: Adaptive Load Sharing in Large Heterogeneous Systems”. INFOCOM, 986-994, 1988
[14]Chhabra A, Singh G, Waraich S S, Sidhu B and Kumar G. Qualitative Parametric Comparison of Load Balancing Algorithms in parallel and Distributed Computing Environment. Word Academy of Science, Engineering and Technology, 39-42, 2006.
[15]Jain P and Gupta D. An Algorithm for Dynamic Load Balancing in Distributed Systems with Multiple Supporting Nodes by Exploiting the Interrupt Service. Academy Publisher, 2009, pp. 232-236.
[16]Valkalis I and Doncker E d. Parallel Global Adaptive Integration and Dynamic Load Balancing on Loosely Coupled Systems. ACM,1993, pp 454-561.
[17]Xu C. and Lau F.C.M. “Load Balancing in Parallel Computers: Theory and Practice”. Kluwer Academic Press, 1997.
[18]Yan K.Q., Wang S.C, Chang C.P and Lin J.S. A hybrid load balancing policy underlying grid computing environment, computer standards and Interfaces, 2007, 29 (2).
[19]Zaki M. J., Li W., Parthasarthy S. Customized dynamic load balancing for a netwok of workstations, Journal of Parallel and Distributed Computing , 1997, 43(2), 156-162.
[20]Ali M F and Khan R Z. The Study on Load Balancing Strategies in Distributed System. International Journal of Computer Science & Engineering Survey, 2012, Vol.3, No.2, April, pp. 19-30.
[21]Bernard G, Steve D and Simatic M. A Survey of Load Sharing in Networks of Workstations. The British Computer Society, The Institute of Electrical Engineers and IOP Publishing Ltd,199, pp. 375-86.
[22]Xu C and Lau F C .M. Load Balancing in Parallel Computers: Theory and Practice. Kluwer Academic Press,1997.
[23]Evans D J and Butt W U N. Dynamic Load Balancing Using Task-Transfer Probabilities”. Parallel Computing, Aug. 1993, Vol. 1 9, No. 8, pp. 897-916.
[24]Bernard G, Steve D and Simatic M. A Survey of Load Sharing in Networks of Workstations. The British Computerm Society, The Institute of Electrical Engineers and IOP Publishing Ltd, 1993,75-86.
[25]Eager D L, Lazowska E D and Zahorjan J. A Comparison of Receiver Initiated and Sender Initiated Adaptive Load Sharing. Performance Evaluation, 1986, Vol. 6, pp. 53-68.
[26]Goswami K K., Devarakonda M, and Iyer R K. Prediction Based Dynamic Load-Sharing Heuristics”. IEEE Trans. Parallel and Distributed Systems, June 1993, Vol. 4, No. 6, pp. 638-648.
[27]Iqbal M A, Saltz J.H and Bokhari S H. A Comparative Analysis of Static and Dynamic Load Balancing Strategies. ACM Performance Evaluation Revision, 1985, Vol. 11, No. 1, pp. 1040 1047.
[28]Lin F C H and Keller R M. The Gradient Model Load Balancing Method. IEEE Trans. Software Eng., Jan. 1987, Vol. 13, No. l, pp. 32-38.
[29]Lin H -C. and Raghavendra C S. A Dynamic Load Balancing Policy with a Central Job Dispatcher (LBC). IEEE Trans. Software Eng., Feb. 1992, Vol. 8, No. 2, pp. 148-158.
[30]Loh, P K K, Hsu W J, Wentong C and Sriskanthan N. How network topology affects dynamic loading balancing. Parallel & Distributed Technology: Systems & Applications, IEEE, 1996. 4(3), pp. 25-35.
[31]Muniz F J and Zaluska E J. “arallel Load-Balancing: An Extension to the Gradient Model. Parallel Computing, 1995, Vol. 2 1, pp. 287-301.
[32]Willebeek-LeMair M H and Reeves A P, Strategies for Dynamic Load Balancing on Highly Parallel Computers. IEEE Trans. Parallel and Distributed Systems, 1993, Vol. 4, No. 9, Sept. pp. 979-993.
[33]Zhou S. A Trace-Driven Simulation Study of Dynamic Load Balancing. IEEE Trans. Software Eng., Sept. 1988, Vol. 14, No. 9, pp. 1327-1341.