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.
Ahmad, Ishfaq; Ghafoor, Arif; and Mehrotra, Kishan, "Performance Prediction for Distributed Load Balancing in Multicomputer Systems" (1991). Electrical Engineering and Computer Science Technical Reports. 117.