Approximations, Inapproximability, and Tight Bounds for Queueing Systems
Jan 12, 2011
ABSTRACT: From computing server farms to call centers and supermarket checkout counters, a fundamental question that faces system designers is: How many servers are necessary to guarantee good performance (e.g, average response time smaller than a desired threshold)? Queuing theorists have been analyzing multi-server systems for over 100 years, yet an exact analysis of the average response time of one of the most basic models of multi-server systems, the M/G/K First-Come-First-Served queue, has been elusive. The state-of-the-art approximations involve only the first two moments of the job size distribution.

We challenge the status quo by showing that the first two moments of the job size distribution are insufficient to approximate the M/G/K mean response time. In particular, we prove that the inapproximability gap increases with the variance of the job size distribution. Since most real world computing workloads are heavy-tailed and exhibit high variance, and hence have a high inapproximability gap, our results motivate the need for more accurate approximations. Towards this goal, we propose a framework to obtain tight upper and lower bounds on the mean response time of the M/G/K queue given successively higher moments of the job size distribution. We achieve these bounds by identifying the distributions which satisfy the given moment conditions but attain minimum or maximum mean response time in a suitable asymptotic regime. Our work draws on classical results in the theory of Tchebycheff systems of functions. A similar schema applies to other, seemingly very different, queuing systems for which no exact analyses are known. Towards a unified approach for proving tight moments-based bounds for such diverse queuing systems, I will end with an open problem which should be of broader appeal.