Tight moments-based bounds for queueing systems

Abstract

We present a new tool to analyze three queueing systems which have defied exact analysis so far: (i) the classical M/G/k multi-server system, (ii) queueing systems with fluctuating arrival and service rates, and (iii) the M/G/1 round-robin queue. We argue that rather than looking for exact expressions for the mean response time as a function of the job size distribution, a more fruitful approach is to find distributions which minimize or maximize the mean response time given the first n moments of the job size distribution. We prove that for the M/G/k system in light traffic, and given n=2 and 3 moments, these 'extremal' distributions are given by principal representations of the moment sequence. Furthermore, if we restrict the distributions to lie in the class of Completely Mono-tone (CM) distributions, then for all the three queueing systems, for any n, the extremal distributions under the appropriate "light traffic" asymptotics are hyper-exponential distributions with finite number of phases. We conjecture that the property of extremality should be invariant to the system load, and thus our light traffic results should hold for general load as well.