Stability of JSQ in queues with general server-job class compatibilities

Richard James Randon Cruise, Matthieu Jonckheere, Vsevolod Shneer

Research output: Contribution to journalArticle

Abstract

We consider Poisson streams of exponentially distributed jobs arriving at each edge of a hypergraph of queues. Upon arrival, an incoming job is routed to the shortest queue among the corresponding vertices. This generalizes many known models such as power-of-d load balancing and JSQ (join the shortest queue) on generic graphs. We prove that stability in this model is achieved if and only if there exists a stable static routing policy. This stability condition is equivalent to that of the JSW (join the shortest workload) policy. We show that some graph topologies lead to a loss of capacity, implying more restrictive stability conditions than in, for example, complete graphs.
Original languageEnglish
JournalQueueing Systems
Early online date3 Jun 2020
DOIs
Publication statusE-pub ahead of print - 3 Jun 2020

Keywords

  • Hypergraph
  • JSQ load balancing
  • Stability

ASJC Scopus subject areas

  • Statistics and Probability
  • Computer Science Applications
  • Management Science and Operations Research
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Stability of JSQ in queues with general server-job class compatibilities'. Together they form a unique fingerprint.

  • Cite this