Queue-length-aware dispatching in large-scale heterogeneous systems

Jazeem Abdul Jaleel (), Sherwin Doroudi () and Kristen Gardner ()
Additional contact information
Jazeem Abdul Jaleel: University of Minnesota
Sherwin Doroudi: University of Minnesota
Kristen Gardner: Amherst College

Queueing Systems: Theory and Applications, 2024, vol. 108, issue 1, No 4, 125-184

Abstract: Abstract One dominant approach for reducing response times in large-scale systems is Join-the-Shortest-Queue-d: whenever a job arrives, the dispatcher queries d servers at random and then assigns the job to the queried server with the shortest queue. While $$\textsf{JSQ}$$ JSQ -d is known to perform quite well in systems where all servers run at the same speed, this is not the case in systems that exhibit heterogeneity with respect to server speeds. Unfortunately, there is no straightforward way to extend $$\textsf{JSQ}$$ JSQ -d (or other so-called power-of-d policies) to heterogeneous systems. Should a job be assigned to the queried server with the shortest queue even if much faster servers were among those queried? Should a job be assigned to the queried server where it is expected to complete the soonest even if there is an idle, albeit slower, server available among those queried? And for that matter, should we query faster servers more often than their slower counterparts? Recent work has introduced a framework for developing strong dispatching policies by pairing suitably chosen querying and assignment rules. Within this framework, prior work has focused on finding strong-performing dispatching policies that use only the idle/busy statuses of the queried servers, rather than detailed queue length information. In this paper, we overcome the challenge of evaluating the performance of—and finding strong-performing—general scalable dispatching policies that make use of both server speed and detailed queue length information, through a combination of mean field analysis and a sequence of modified optimization problems. We find that well-designed length-aware dispatching policies can significantly outperform their idleness-based counterparts in large-scale heterogeneous systems. While the best policies of this kind are often complicated to describe, we find that in the vast majority of cases the relatively simple Shortest Expected Wait policy performs nearly as well, without the need for an especially sophisticated and time-consuming optimization procedure.

Keywords: Queueing; Markov chains; Dispatching; Mean field analysis (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s11134-024-09918-x 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:108:y:2024:i:1:d:10.1007_s11134-024-09918-x

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

DOI: 10.1007/s11134-024-09918-x

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 ().