Insensitivity of Loss Systems under Randomized SQ(d) Algorithms [ISL Colloquium]

Insensitivity of Loss Systems under Randomized SQ(d) Algorithms
Monday, March 20, 2017 - 3:00pm
Packard 202
Ravi R. Mazumdar (University of Waterloo, Canada)
Abstract / Description: 

In many applications such as cloud computing, managing server farm resources etc. an incoming task or job has to be matched with an appropriate server in order to minimise the latency or blocking associated with the processing. Ideally the best choice would be to match a job to the fastest available server. However when there are thousands of servers requiring the information on all server tasks is an overkill.

Pioneered in the 1990's the idea of randomised sampling of a few servers was proposed by Vvedenskaya and Dobrushin in Russia and Mitzmenmacher in the US and popularised as the "power of two" schemes which basically means that sampling two servers randomly and sending the job to the "better" server (i.e. with the shortest queue, or most resources) provides most of the benefits of sampling all the servers.

In the talk I will discuss multi-server loss models under power-of-d routing scheme when service time distributions are general with finite mean. Previous works on these models assume that the service times are exponentially distributed and insensitivity was suggested through simulations. Showing insensitivity to service time distributions has remained an open problem. We address this problem by considering service time distributions as Mixed-Erlang distributions that are dense in the class of general distributions on (0, ∞). We derive the mean field equations (MFE) of the empirical distributions for the system and establish the existence and uniqueness of the fixed point of the MFE. Furthermore we show that the fixed point of the MFE corresponds to the fixed point obtained from the MFE corresponding to a system with exponential service times showing that the fixed point is insensitive to the distribution. Due to lack of uniformity of the mixed-Erlang convergence the true general case needs to be handled differently. I will conclude the case of the MFE with general service times showing that the MFE is now characterized by a pde whose stationary point coincides with the fixed point in the case with exponential service times.The techniques developed in this paper are applicable to study mean field limits for Markov processes on general state spaces and insensitivity properties of other queueing models.


The speaker was educated at the Indian Institute of Technology, Bombay (B.Tech, 1977), Imperial College, London (MSc, DIC, 1978) and obtained his PhD 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. He is a D.J. Gandhi Distinguished Visiting Professor at the Indian Institute of Technology, Bombay. He is a Fellow of the IEEE and the Royal Statistical Society. He is a recipient of the Best Paper Awards at INFOCOM 2006, the International Teletraffic Congress 2015, Performance 2015, and was runner-up for the Best Paper Award at INFOCOM 1998.

His research interests are in modeling, control, and performance analysis of both wireline and wireless networks, and in applied probability and stochastic analysis with applications to queueing, filtering, and optimization.