Heavy Traffic Limits for Join-the-Shortest-Estimated-Queue Policy Using Delayed Information

Rami Atar () and David Lipshutz ()
Additional contact information
Rami Atar: Viterbi Faculty of Electrical Engineering Technion–Israel Institute of Technology, Haifa 32000, Israel
David Lipshutz: Viterbi Faculty of Electrical Engineering Technion–Israel Institute of Technology, Haifa 32000, Israel

Mathematics of Operations Research, 2021, vol. 46, issue 1, 268-300

Abstract: We consider a load-balancing problem for a network of parallel queues in which information on the state of the queues is subject to a delay. In this setting, adopting a routing policy that performs well when applied to the current state of the queues can perform quite poorly when applied to the delayed state of the queues. Viewing this as a problem of control under partial observations, we propose using an estimate of the current queue lengths as the input to the join-the-shortest-queue policy. For a general class of estimation schemes, under heavy traffic conditions, we prove convergence of the diffusion-scaled process to a solution of a so-called diffusion model, in which an important step toward this goal establishes that the estimated queue lengths undergo state-space collapse. In some cases, our diffusion model is given by a novel stochastic delay equation with reflection, in which the Skorokhod boundary term appears with delay. We illustrate our results with examples of natural estimation schemes, discuss their implementability, and compare their relative performance using simulations.

Keywords: load balancing; delays; oscillations; join the shortest estimated queue; heavy traffic limits; state-space collapse (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1287/moor.2020.1056 (application/pdf)

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:inm:ormoor:v:46:y:2021:i:1:p:268-300

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().