The Effect of Increasing Routing Choice on Resource Pooling

We consider a network of N identical /M/l or /M/∞ queues. There are two types of arriving customers, those that have no routing choice, and those that first pick r queues at random, and are then routed to the least busy of those queues. We derive the limiting distribution of queue lengths as N→∞, and investigate how this distribution varies with r. We show that even a small amount of routing choice can lead to substantial gains in performance through resource pooling. We corroborate these conclusions by carrying out some simulations of a related model, from which the previous model can be derived by an exchangeable queue simplification. We also observe that the exchangeable queue simplification results in a performance gain for some parameters, in contrast to earlier work.