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

Richard James Randon Cruise; Matthieu Jonckheere; Vsevolod Shneer

doi:10.1007/s11134-020-09656-w

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

Richard James Randon Cruise
, Matthieu Jonckheere
, Vsevolod Shneer

Research output: Contribution to journal › Article › peer-review

6 Citations (Scopus)

71 Downloads (Pure)

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 language	English
Pages (from-to)	271-279
Number of pages	9
Journal	Queueing Systems
Volume	95
Issue number	3-4
Early online date	3 Jun 2020
DOIs	https://doi.org/10.1007/s11134-020-09656-w
Publication status	Published - Aug 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

Access to Document

10.1007/s11134-020-09656-w

Download pdf
This is a post-peer-review, pre-copyedit version of an article published in Queueing Systems. The final authenticated version is available online at: http://dx.doi.org/10.1007/s11134-020-09656-w
Accepted author manuscript, 217 KB

Cite this

@article{976512f8adf547d0a438e9a1e0c12746,

title = "Stability of JSQ in queues with general server-job class compatibilities",

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.",

keywords = "Hypergraph, JSQ load balancing, Stability",

author = "Cruise, \{Richard James Randon\} and Matthieu Jonckheere and Vsevolod Shneer",

year = "2020",

month = aug,

doi = "10.1007/s11134-020-09656-w",

language = "English",

volume = "95",

pages = "271--279",

journal = "Queueing Systems",

issn = "0257-0130",

publisher = "Springer Netherlands",

number = "3-4",

}

TY - JOUR

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

AU - Cruise, Richard James Randon

AU - Jonckheere, Matthieu

AU - Shneer, Vsevolod

PY - 2020/8

Y1 - 2020/8

N2 - 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.

AB - 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.

KW - Hypergraph

KW - JSQ load balancing

KW - Stability

UR - https://www.scopus.com/pages/publications/85086040646

U2 - 10.1007/s11134-020-09656-w

DO - 10.1007/s11134-020-09656-w

M3 - Article

SN - 0257-0130

VL - 95

SP - 271

EP - 279

JO - Queueing Systems

JF - Queueing Systems

IS - 3-4

ER -

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

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this