Choosing amongst heterogeneous servers with applications to cloud computing

Abstract:

Many cloud systems such as the Amazon EC2 provide resources for clients to use. These resources are shared between many tasks. A natural model is to use a processor sharing. In this talk I will discuss new advances in understanding good policies to choose amongst heterogeneous servers in order to obtain low latencies for job execution.

We will first discuss the so-called Power-of-two rule in the homogeneous case of identical servers where routing to the least occupied server amongst two randomly chosen servers results in a very low server occupancy and a so-called propagation of chaos or asymptotic independence. The hetero- geneous case has not been treated in the literature. In the heterogeneous case we will see that the stability region for randomized routing is strictly included in the maximal stability region that can be achieved by state independent routing. Therefore the average sojourn of tasks can be longer in randomized routing in heterogeneous systems. When the system is stable we completely character- ize the steady-state behavior of the server occupancies and show that it exhibits super-exponential decay and asymptotic independence among servers. To overcome the reduction in the stability region we show that a combination of state independent routing (biased sampling) to a server class combined with JSQ within the class recovers the stability region as well as the benefits of small server occupancies. We conclude with the situation when the server speeds at different clusters are not known

The techniques are based on a mean field analysis. Joint work with Arpan Mukhopadhyay (Waterloo).

Biography:

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. 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 and was runner-up for the Best Paper Award at INFOCOM 1998.

His research interests are in stochastic modelling and analysis applied to complex networks and systems and in issues of network science.