The performance of resource sharing schemes can be immensely enhanced by the use of dynamic policies. One such policy in the context of routing tasks to distributed resources is the Join-the-Shortest-Queue (JSQ) scheme. Such a dynamic scheme that routes tasks to least loaded servers provides an exponential order of improvement in average sojourn times. The price to pay is requiring dynamic, global information that might be too expensive when there are a large number of resources to choose from. It turns out that randomized schemes popularized as "Power of Two" schemes that only require information from two randomly chosen resources provides most of the gains of the full JSQ scheme and has obvious advantages in requiring no detailed dynamic global information to be maintained. In the talk I 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. This property is key to being able to analyze large systems. The heterogeneous case when servers have different speeds is a more difficult one but has very interesting properties not exhibited in the homogeneous context. New results for this scenario will be given that shows that performance amelioration need not occur due to loss of stability. A simple combination of biased sampling with classical JSQ can help us recover the gains associated with JSQ and much improved performance. The techniques are based on a mean field analysis and we show that "propagation of chaos" exists in the limit. Joint work with Arpan Mukhopadhyay (Waterloo)
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 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.