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.

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.