Insensitivity of the Hydrodynamic Limit of PS under Randomized SQ(d) Algorithms

Speaker : Ravi Mazumdar
University of Waterloo
Date: 21/02/2018
Time: 2:00 pm - 3:00 pm
Location: LINCS Seminars room

Abstract

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 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 Vve- denskaya 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 processor sharing models under power-of-d routing scheme when service time distributions are general with finite mean. Previous works on these models as- sume that the service times are exponentially distributed and insensitivity was suggested through simulations. Showing insensitivity to service time distributions has remained an open problem. The difficulty is that for general service times the underlying Markovian model is more complex. Indeed it can be viewed as a Markov process on Z+ × R?+ . Using a measure valued process approach we first derive the hydrodynamic limit or mean field equation (MFE) for the empirical measure. The MFE is now characterized by a pde whose stationary point coincides with the fixed point in the case with exponential service times. This establishes the insensitivity of the fixed point. 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.

This is joint work with Thirupathiah Vasantam (UW) and Arpan Mukhopadhyay (EPFL).