Replicate to the shortest queues

Rami Atar, Isaac Keslassy and Gal Mendelson ()
Additional contact information
Rami Atar: Technion–Israel Institute of Technology
Isaac Keslassy: Technion–Israel Institute of Technology
Gal Mendelson: Technion–Israel Institute of Technology

Queueing Systems: Theory and Applications, 2019, vol. 92, issue 1, No 1, 23 pages

Abstract: Abstract This paper introduces a load-balancing policy that interpolates between two well-known policies, namely join the shortest queue (JSQ) and join the least workload (JLW), and studies it in heavy traffic. This policy, which we call replicate to the shortest queues (RSQ(d)), routes jobs from a stream of arrivals into buffers attached to N servers by replicating each arrival into $$1\le d\le N$$ 1 ≤ d ≤ N tasks and sending the replicas to the d shortest queues. When the first of the tasks reaches a server, its $$d-1$$ d - 1 replicas are canceled. Clearly, RSQ(1) is equivalent to JSQ, and it has been shown that RSQ(N) is equivalent to JLW; intermediate values of d provide a trade-off between good performance measures of JSQ and those of JLW. In heavy traffic, a key property underlying asymptotic analysis of load-balancing policies is state space collapse (SSC). Unlike policies such as JSQ, where SSC is well understood, the treatment of SSC under RSQ(d) requires addressing the massive cancellations that highly complicate the queue length dynamics. Our first main result is that SSC holds under RSQ(d) for possibly heterogeneous servers. Based on this result, we obtain diffusion limits for the queue lengths in the form of one-dimensional reflected Brownian motion, asymptotic characterization of the short-time-averaged delay process and a version of Reiman’s snapshot principle. We illustrate using simulations that as d increases the server workloads become more balanced, and the delay distribution’s tail becomes lighter. We also discuss the implementation complexity of the policy as compared to that of the redundancy routing policy, to which it is closely related.

Keywords: Randomized load balancing; Replicate to shortest queues; Join the shortest queue; Join the least workload; Task redundancy; Job cancellations; Diffusion limits; Heavy traffic; State space collapse; 60F17; 60J60; 60K25 (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s11134-019-09605-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:queues:v:92:y:2019:i:1:d:10.1007_s11134-019-09605-2

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/11134/

DOI: 10.1007/s11134-019-09605-2

Access Statistics for this article

Queueing Systems: Theory and Applications is currently edited by Sergey Foss

More articles in Queueing Systems: Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().