Insensitivity of Loss Systems under Randomized SQ(d) Algorithms
2017-02-22 14:00 - 15:00 (Europe/Paris) | LINCS Meeting Room 40, 23, avenue d'Italie, Paris, 75013,France
Abstract:
In many applications such as cloud computing,managing server farm resources etc. an incoming task or job has to bematched with an appropriate server in order to minimise the latencyassociated with the processing. Ideally the best choice would be to match ajob to the fastest available server. However when there are thousands ofservers obtaining the information on server tasks is expensive. Pioneeredin the 1990's the idea of randomised sampling of a few servers was proposedby Vvedenskaya and Dobrushin in Russia and Mitzmenmacher in the US andpopularised as the "power of two" schemes which basically means thatsampling two servers randomly and sending the job to the "better" server(i.e. with the shortest queue, or most resources) provides most of thebenefits of sampling all the servers.In the talk I will discussmulti-server loss models under power-of-d routing scheme when service timedistributions are general with finite mean. Previous works on these modelsassume that the service times are exponentially distributed andinsensitivity was suggested through simulations. Showing insensitivity toservice time distributions has remained an open problem. We address thisproblem by considering service time distributions as Mixed-Erlangdistributions that are dense in the class of general distributions on (0,infty). We derive the mean field equations (MFE) of the empiricaldistributions for the system and establish the existence and uniqueness ofthe fixed point of the MFE. Furthermore we show that the fixed point of theMFE corresponds to the fixed point obtained from the MFE corresponding to asystem with exponential service times showing that the fixed point isinsensitive to the distribution. We provide numerical evidence of theglobal asymptotic stability of the fixed point, which would then implythat the fixed point is indeed the stationary distribution. We concludewith a brief discussion of the case of the MFE with general service timesshowing that the MFE is now characterized by a pde whose stationary pointcoincides with the fixed point in the case with exponential servicetimes.The techniques developed in this paper are applicable to study meanfield limits for Markov processes on general state spaces and insensitivityproperties of other queueing models.

Biography:
The speaker waseducated 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 ChairProfessor in the Dept. of ECE at the University of Waterloo,Ont., Canadawhere he has been since September 2004. Prior to this he was Professor ofECE at PurdueUniversity, West Lafayette, USA. He is a D.J. GandhiDistinguished Visiting Professor at the Indian Institute of Technology,Bombay. He is a Fellow of the IEEE and the Royal Statistical Society. He isa recipient of the Best Paper Awards at INFOCOM 2006, the InternationalTeletraffic Congress 2015, Performance 2015, and was runner-up for theBest Paper Award at INFOCOM 1998.His research interests are in modeling,control, and performance analysis of both wireline and wirelessnetworks,and in applied probability and stochastic analysis with applications toqueueing, filtering, and optimization.
