Document Type









Computer Sciences


Computing literature has being flooded recently with a plethora of dynamic load balancing strategies for multicomputer systems. The diversity of many strategies and their dependence on a number of parameters has made it difficult to compare their effectiveness on a unified basis. Not only does each strategy consider a different environment, but the simplified assumptions obscure the relative merits and demerits of each strategy. This paper presents a solution to compare different load balancing schemes on a unified basis. Our approach, which is an integration of simulation, statistical and analytical experiments, takes into account the fundamental system parameters that can possibly affect the performance. We show that a class of distributed load balancing strategies can be modeled by a central server open queuing network. Furthermore, these load balancing strategies can be characterized by only two queuing parameters - the average execution queue length and the probability that a newly arrived task is to be executed locally or migrated to another node. To capture the relation between these queuing parameters and various system parameters, a statistical analysis has been carried out on the empirical data obtained through simulation. The analytical queuing model is then used to predict the response time of a system with any set of system parameters. Experimental results are obtained for seven different load balancing strategies. The proposed model directly provides performance results in a straight forward manner and can be beneficial to the system designers in order to assess the system under varying conditions.

Additional Information

School of Computer and Information Science, Syracuse University, SU-CIS-91-12





To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.