{
  "id": "1706.04628",
  "version": "v1",
  "published": "2017-06-14T18:14:10.000Z",
  "updated": "2017-06-14T18:14:10.000Z",
  "title": "Simple and explicit bounds for multi-server queues with universal 1 / (1 - rho) scaling",
  "authors": [
    "David A. Goldberg",
    "Yuan Li"
  ],
  "categories": [
    "math.PR"
  ],
  "abstract": "We consider the FCFS GI/GI/n queue, and prove the first simple and explicit bounds that scale gracefully and universally as 1 / (1 - rho) (and better), with rho the corresponding traffic intensity. In particular, we prove the first multi-server analogue of Kingman's bound, which has been an open problem for over fifty years. Our main results are bounds for the tail of the steady-state queue length and the steady-state probability of delay, where the strength of our bounds (e.g. in the form of tail decay rate) is a function of how many moments of the inter-arrival and service distributions are assumed finite. Supposing that the inter-arrival and service times, distributed as random variables A and S, have finite rth moment for some r > 2, our bounds are simple and explicit functions of only the normalized rth moments of A and S, r, and 1 / (1 - rho). Our simple and explicit bounds scale gracefully even when the number of servers grows large and the traffic intensity converges to unity simultaneously, as in the Halfin-Whitt scaling regime. Our proofs proceed by explicitly analyzing the bounding process which arises in the stochastic comparison bounds of Gamarnik and Goldberg for multi-server queues. Along the way we derive several novel results for suprema of random walks with stationary increments and negative drift, pooled renewal processes, and various other quantities which may be of independent interest.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-06-14T18:14:10.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60K25"
    ],
    "keywords": [
      "multi-server queues",
      "traffic intensity converges",
      "stochastic comparison bounds",
      "steady-state queue length",
      "tail decay rate"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}