Beyond heavy-traffic regimes: Universal bounds and controls for the single-server queue

Junfei Huang*, Itai Gurvich

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

11 Scopus citations

Abstract

Central-limit (Brownian) approximations are widely used for the performance analysis and optimization of queueing networks because of their tractability relative to the original queueing models. The stationary distributions of the approximations are used as proxies for those of the queues. The convergence of suitably scaled and centered processes provides mathematical support for the use of these Brownian models. As with the central limit theorem, to establish convergence, one must impose assumptions directly on the primitives or indirectly on the parameters of a related optimization problem. These assumptions reflect an interpretation of the underlying parameters-a classification into so-called heavy-traffic regimes that specify a scaling relationship between the utilization and the arrival rate. Here, it matters whether a utilization of 90% in a queue with an arrival rate of? 100 is read as?.,?" 0:9 1-1/p? or as?.,?" = 0:9, because different interpretations lead to different limits and, in turn, to different approximations. However, from a heuristic point of view, there is an immediate Brownian (i.e., normal) analogue of the queueing model that is derived directly from the primitives and requires no scaling interpretation of the parameters. In this model, the drift is that of the original queue, and the noise term is replaced by a Brownian motion with the same variance. This is intuitive and appealing as a tool, but it lacks mathematical justification. In this paper, we prove that for the fundamental M/GI/1 + GI queue, this direct intuitive approach works: the Brownian model is accurate uniformly over a family of patience distributions and universally in the heavy-traffic regime. The validity of this approach extends to dynamic control in that the solution of the directly derived diffusion control problem is universally accurate. To build mathematical support for the accuracy of this model, we introduce a framework built around "queue families" that allows us to treat various patience distributions simultaneously, and it uncovers the role of a concentration property of the queue.

Original languageEnglish (US)
Pages (from-to)1168-1188
Number of pages21
JournalOperations Research
Volume66
Issue number4
DOIs
StatePublished - Jul 1 2018
Externally publishedYes

Keywords

  • M/GI/1 + GI
  • Stationary distribution
  • Stein's method
  • Universal approximation

ASJC Scopus subject areas

  • Computer Science Applications
  • Management Science and Operations Research

Fingerprint

Dive into the research topics of 'Beyond heavy-traffic regimes: Universal bounds and controls for the single-server queue'. Together they form a unique fingerprint.

Cite this