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

2020/01/27 by Cruise, James, Jonckheere, Matthieu, Shneer, Seva
#60K25 #68M12 #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.2001.09921

Abstract

We consider Poisson streams of exponentially distributed jobs arriving at each edge of a hypergraph of queues. Upon arrival, an incoming job is rooted 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 provide a generic condition for stability of this model. We show that some graph topologies lead to a loss of capacity, implying more restrictive stability conditions than in, e.g., complete graphs.

Related

• Stability of Join the Shortest Queue Networks
• Load Balancing Under Strict Compatibility Constraints
• Load Balancing in the Non-Degenerate Slowdown Regime
• The stability of join-the-shortest-queue models with general input and output processes
• Asymptotic Optimality of Speed-Aware JSQ for Heterogeneous Systems