Randomized Load Balancing in Large Processor Sharing Systems

Speaker : Ravi R. Mazumdar
University of Waterloo, Canada
Date: 15/10/2013
Time: 11:30 am - 12:30 pm
Location: LINCS Meeting Room 40

Abstract

Processor sharing models occur in a wide variety of situations. They are good models forbandwidth sharing as well as being solutions to NUM for logarithmic utilities. In addition theypossess the desirable stochastic property of the stationary distribution being insensitive to the service time distribution. In this talk I will discuss new advances in understanding and characterizingthe behavior of randomized routing to PS servers that are heterogeneous in terms of their servercapacities.In particular, starting with the identical server case we will rst discuss the so-called Power-of-two rule where by a combination of routing to the least occupied server amongst two randomlychosen servers results in a very low server occupancy and a so-called propagation of chaos orasymptotic independence. Using these insights we analyze the case of heterogeneous servers wherethe server capacity can be one of M. We provide a complete characterization of the stationarydistribution and prove that the limiting system is insensitive. We then consider a modied criterionbased on routing to the server with lower Lagrange costs. We compare these dynamic routingstrategies with an optimal static state independent scheme. We show that the dynamic schemesare much better in terms of average delay with the Lagrange cost based being the best.The techniques are based on a mean eld analysis and an ansatz based on propagation of chaos.Joint work with Arpan Mukhopadhyay (Waterloo).