Analysis of Dynamic Load Balancing Strategies Using a Combination of Stochastic Petri Nets and Queueing Networks

This paper is concerned with the analytical evaluation of two well known dynamic load balancing strategies, namely, shortest queue rout-ing (SQR) and shortest expected elay routing (SEDR). We overcome the limitations of existing analysis methodologies, using a well known hybrid performance model that combines generalized stochastic Petri nets and product form queueing networks. Our methodology is applicable to both open queueing network and closed queueing network models of load bal-ancing in distributed computing systems. The results how that for ho-mogeneous distributed systems, SQR outperforms all other policies. For heterogeneous systems, SEDR surprisingly performs worse than SQR at low levels of imbalance in loads. However, with increase in imbalance in load, SEDR expeetedly performs better than SQR. 1 In t roduct ion The problem of balancing the load over the entire system so that its overal