Randomized Load Balancing in Large Bandwidth Sharing Systems

Processor sharing models occur in a wide variety of situations for example in models of internet
bottlenecks. They are good models for bandwidth sharing as well as being solutions to NUM for
logarithmic utilities. In addition they possess 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 characterizing the behavior of randomized routing to PS servers that are
heterogeneous in terms of their server speeds.
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 randomly
chosen servers results in a very low server occupancy and a so-called propagation of chaos or asymp-
totic independence. There were no known characterizations about the heterogeneous case. 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 characterize 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 benets of small server occupancies.
I will conclude with an extension of the results of randomized routing to servers with the best
instantaneous rates and to multi-rate Erlang models that are good models for cloud based services.
The techniques are based on a mean eld analysis and an ansatz based on propagation of chaos
that then establishes the asymptotic independence between servers.
Joint work with Arpan Mukhopadhyay (Waterloo).

Professor Mazumder 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. 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, ltering, and
optimization.