Abstract A sliding strategy for load balancing is introduced. The strategy groups a certain number of adjacent nodes to perform a load balancing process. Upon the completion of a given period, the groups are to be rotated by shifting each group one position to the right, thus produces different groups. This strategy (sort of clustering) not only reduces the load balancing overheads, but also it could be utilized as a backbone by any load balancing strategy. The proposed load balancing strategy always converges, and tends to be in a steady state in a negligible processing time. In this paper, the load status and the locations of the nodes regarding the system’s topology are irrelevant to load balancing process. The new algorithm can be always applied to any distributed system, even if it is heavily loaded, since the cost of scheduling is very low due to the highly reduced number of messages. This is achieved by reducing dramatically the overheads incurred from attached information tables, message passing, job thrashing, and response time.

References

[1] Chen M. S. and Shin K. G., Sub Cube Allocation and Task Migration in Hypercube Multiprocessor, IEEE Transactions on Computers , vol. 39, no. 9, September 1990.

[2] Dalal ah A. and Al-Dahoud A., Dynamic Load Balancing with Token-Passing in a Distributed System, IEEE International Conference on Systems, Man, and Cybernetics , San Diego, California, USA, pp. 398-400, October 1998.

[3] Eager D. L., Lazowska E. D., and Zahorjan J., Adaptive Load Sharing in Homogeneous Distributed Systems, IEEE Transactions on Software Engineering , vol. SE-12, no. 5, May 1986.

[4] Eager D. L., Lazowska E. D., and Zahorjan J., The Limited Performance Benefits of Migration Active Processes for Load Sharing, in Proceedings of ACM Sigmetrics Conference , pp. 662-675, 1988.

[5] Efe K. and Groselj B., Minimizing Control Overheads in Adaptive Load Sharing, The Center for Advanced Computer Studies , University of Southwestern Louisiana, Lafayette, USA, 1989.

[6] Hac A., Dynamic Load Balancing in a Distributed System Using a Sender-Initiated Algorithm, Journal of System Software, vol. 11, no. 2, pp. 79-94, 1990. 0 50000 100000 150000 1 3 5 7 9 11 13 15 Number of nodes ALL NO_LB OUR OTHER Num ber o f s u ccessfu l j o bs 0 50 100 150 200 250 300 1 3 5 7 9 11 13 15 Number of nodes Num ber o f m essa g es Central Distributed Rot_2 Rot_3 182 The International Arab Journal of Information Technology, Vol. 3, No. 2, April 2006

[7]Hagmann R. B., Process Server, in Proceedings of the 8thInternational Conference of Distributed Computing Systems , Cambridge, Mass, pp. 260-267, May 1986.

[8] Kara M., Using Dynamic Load Balancing in Distributed Information Systems, Report 94.18, School of Computer Studies, University of Leeds, May 1994.

[9] Krueger P. and Shivaratri N. G., Adaptive Location Policies for Global Scheduling, IEEE Transactions on Software Engineering , vol. 20, no. 6, June 1994.

[10] Leland W. and Ott T., Load Balancing Heuristics and Process Behavior, in Proceedings of ACM Sigmetrics Conference , pp. 54-69, May, 1988.

[11] Ni L. M. and Hwang K., Optimal Load Balancing in a Multiple Processor System with Many Job Classes, IEEE Transactions on Software Engineering , vol. SE-11, no. 5, May 1985.

[12] Ni L. M., Xu C., and Gendreau T. B., A Distributed Drafting Algorithm for Load Balancing, IEEE Transactions on Software Engineering , vol. SE-11, no. 10, October 1985.

[13] Pinter S. S. and Woltstahl Y., On Mapping Processes to Processor in Distributed Systems, International Journal of Parallel Programming, vol. 16, no. 1, 1987.

[14] Rao G. S., Stone H. S., and Hu T. C., Assignment of Tasks in a Distributed Processor System with Limited Memory, IEEE Transactions on Computers , vol. C-28, no. 4, April 1979.

[15] Shin K. G. and Chang Y., Load Sharing in Distributed Real Time Systems with State- Change Broadcasts, IEEE Transactions on Computers , vol. 38, no. 8, August 1989.

[16] Tantawi A. N. and Towsley D., Optimal Static Load Balancing in Distributed Computer Systems, Journal of the ACM, vol. 32, no. 2, pp. 445-465, April 1985.

[17] Xu J. and Hwang K., Heuristic Methods for Dynamic Load Balancing in a Message-Passing Multicomputer, Journal of Parallel and Distributed Computing , vol. 18, no. 1, pp. 1-13, 1993.

[18] Zein O., El-Toweisy M., and Mukkamala R., A Distributed Scheduling Algorithm for Heterogeneous Real-Time Systems, in Proceedings of Advances in Computing and Information (ICCA 91) , Ottawa, Canada, pp. 27- 29, May 1991.

[19] Zhou S., A Trace-Driven Simulation Study of Dynamic Load Balancing, IEEE Transactions on Software Engineering , vol. 14, no. 9, pp. 1327-1341, September 1988.

[20] Zhou S. and Ferrari D., An Empirical Investigation of Load Indices for Load Balancing Applications, in Proceedings of the International Symposium on Computer Performance Modeling Measurement and Evaluation (Performance 87) , Brussels, Belgium, pp. 515-528, 1987.

[21] Zhou S. and Ferrari D., An Experimental Study of Load Balancing Performance, Technical Report UCB/CSD 87/336 , University of California, USA, January 1987. Ahmad Dalal'ah received his BSc in computer science from Yarmouk University, Jordan in 1985. During the period 1989-1993 he was a TA at Mu'tah University, Jordan. He received his PhD in computer networks in 1998 from Genoa University, Italy. Currently, he is with the Computer Science Department at Jordan University of Science and Technology. His research interests include ad hoc networks and load balancing in distributed systems.