Performance prediction of distributed load balancing on multicomputer systems

The authors present a performance evaluation approach for comparing different distributed load balancing schemes on a unified basis. This approach is an integration of simulation, statistical, and analytical models, and takes into account the fundamental system parameters that can possibly affect the performance. It is shown that all the sender-initiated 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 executed locally 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 combination of system parameters. Experimental results are obtained for six different load balancing strategies. The proposed model provides performance results in a straightforward manner and can be beneficial to the system designers in assessing the system under varying conditions.