Behaviour of critically loaded systems with randomized shortest queue routing


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 first 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-field 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 Halfin-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 nite sized systems but yields information on the convergence rates of the empirical distribution to the fixed point of the mean-field.This work with Thirupathiah Vasantam (Waterloo).

The Speaker

The speaker was educated at the Indian Institute of Technology, Bombay (B.Tech, 1977), Imperial College, London (MSc, DIC, 1978) and obtained his PhD in Control Theory under A. V. Balakrishnan at UCLA in 1983. He is currently a University Research Chair Professor in the Dept. of ECE at the University of Waterloo, Ont., Canada where he has been since September 2004. Prior to this he was Professor of ECE at Purdue University, West Lafayette, USA. Since 2012 he is a D.J. Gandhi Distinguished Visiting Professor at the Indian Institute of Technology, Bombay, India. He is a Fellow of the IEEE and the Royal Statistical Society. He is a recipient of the INFOCOM 2006 Best Paper Award, the ITC-27 2015 Best Paper Award, the Performance 2015 Best Paper Award and was runner-up for the Best Paper Award at INFOCOM 1998. Since May 2019 he is an Adjunct Professor at TIFR, Mumbai. His research interests are in stochastic modelling and analysis applied to complex networks and systems and in issues of network science.