Behaviour of Critically Loaded Systems with Randomized Shortest Queue Routing

Abstract: Recently there has been a great interest in the analytic understanding of the behavior of large server systems with randomized routing. The work of vvedenskaya and Dobrushin in Russia and Mitzenmacher in the USA rst brought to light the fact that randomized routing to large number of parallel servers based on the shortest of d sampled servers achieves delay performance that is close to the optimal delay performance when Join the Shortest Queue (JSQ) routing is used. These results have been extended to other models of interest such as processor sharing and loss models in the heterogeneous setting by Mukhopadhyay and Mazumdar, Yi and Srikant, Mukherjee and Borst, etc. The approach is via a mean-eld analysis. In recent work with Vasantam we showed that the insensitivity properties of processor sharing and loss models continues to hold for the fixed points of the mean field.

In this talk I will discuss the behavior of randomized routing when loads are close to critical, in the so-called Haln-Whitt regime. For loss models this regime is of interest due to a phase change in blocking behavior and so it is important to understand the blocking behavior with heavy loads. We approach this issue by studying the fluctuations of the empirical distributions around the mean field. We obtain FCLT results for both the transient and stationary behaviour.This allows us not only to obtain approximations for finite sized systems but yields information on the convergence rates of the empirical distribution to the fixed point of the mean-field.