EUVIMEDEUVIMED entdecken
Crossref

Heavy-Traffic Optimal Size- and State-Aware Dispatching

Runhan Xie, Isaac Grosof, Ziv Scully

Proceedings of the ACM on Measurement and Analysis of Computing Systems · 16.02.2024 · 8 (1) · 1-36

DOI: 10.1145/3639035 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the ACM on Measurement and Analysis of Computing Systems, online erschienen am 21.02.2024. Verfasst von Runhan Xie und 2 weiteren Autor:innen. Die Arbeit wurde bisher 11-mal zitiert (Crossref) und nennt 61 Literaturangaben. Gefördert von: Tennenbaum Postdoctoral Fellowship at the Georgia Institute of Technology School of Industrial and Systems Engineering, US National Science Foundation.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Dispatching systems, where arriving jobs are immediately assigned to one of multiple queues, are ubiquitous in computer systems and service systems. A natural and practically relevant model is one in which each queue serves jobs in FCFS (First-Come First-Served) order. We consider the case where the dispatcher is size-aware, meaning it learns the size (i.e. service time) of each job as it arrives; and state-aware, meaning it always knows the amount of work (i.e. total remaining service time) at each queue. While size- and state-aware dispatching to FCFS queues has been extensively studied, little is known about optimal dispatching for the objective of minimizing mean delay. A major obstacle is that no nontrivial lower bound on mean delay is known, even in heavy traffic (i.e. the limit as load approaches capacity). This makes it difficult to prove that any given policy is optimal, or even heavy-traffic optimal. In this work, we propose the first size- and state-aware dispatching policy that provably minimizes mean delay in heavy traffic. Our policy, called CARD (Controlled Asymmetry Reduces Delay), keeps all but one of the queues short, then routes as few jobs as possible to the one long queue. We prove an upper bound on CARD's mean delay, and we prove the first nontrivial lower bound on the mean delay of any size- and state-aware dispatching policy. Both results apply to any number of servers. Our bounds match in heavy traffic, implying CARD's heavy-traffic optimality. In particular, CARD's heavy-traffic performance improves upon that of LWL (Least Work Left), SITA (Size Interval Task Assignment), and other policies from the literature whose heavy-traffic performance is known.

Förderung

  • Tennenbaum Postdoctoral Fellowship at the Georgia Institute of Technology School of Industrial and Systems Engineering
  • US National Science Foundation

Zitieren

APA

Xie, R., Grosof, I., & Scully, Z. (2024). Heavy-Traffic Optimal Size- and State-Aware Dispatching. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 8(1), 1-36. https://doi.org/10.1145/3639035

Vancouver

Xie R, Grosof I, Scully Z. Heavy-Traffic Optimal Size- and State-Aware Dispatching. Proceedings of the ACM on Measurement and Analysis of Computing Systems. 2024;8(1):1-36. doi:10.1145/3639035

BibTeX
@article{Xie2024,
  author = {Xie, Runhan and Grosof, Isaac and Scully, Ziv},
  title = {Heavy-Traffic Optimal Size- and State-Aware Dispatching},
  journal = {Proceedings of the ACM on Measurement and Analysis of Computing Systems},
  year = {2024},
  volume = {8},
  number = {1},
  pages = {1--36},
  doi = {10.1145/3639035}
}
Kostenlos starten →