Stability of join the shortest queue networks

Maury Bramson

Research output: Contribution to journalArticlepeer-review

29 Scopus citations

Abstract

Join the shortest queue (JSQ) refers to networks whose incoming jobs are assigned to the shortest queue from among a randomly chosen subset of the queues in the system. After completion of service at the queue, a job leaves the network.We show that, for all nonidling service disciplines and for general interarrival and service time distributions, such networks are stable when they are subcritical. We then obtain uniform bounds on the tails of the marginal distributions of the equilibria for families of such networks; these bounds are employed to show relative compactness of the marginal distributions. We also present a family of subcritical JSQ networks whose workloads in equilibrium are much larger than for the corresponding networks where each incoming job is assigned randomly to a queue. Part of this work generalizes results in [Queueing Syst. 29 (1998) 55-73], which applied fluid limits to study networks with the FIFO discipline. Here, we apply an appropriate Lyapunov function.

Original languageEnglish (US)
Pages (from-to)1568-1625
Number of pages58
JournalAnnals of Applied Probability
Volume21
Issue number4
DOIs
StatePublished - Aug 2011

Keywords

  • Join the shortest queue
  • Stability

Fingerprint Dive into the research topics of 'Stability of join the shortest queue networks'. Together they form a unique fingerprint.

Cite this