A Tale of Two Traffics: Optimizing Tail Latency in the Light-Tailed M/G/k
Proceedings of the ACM on Measurement and Analysis of Computing Systems · 2025-12 · 9 (3) · 1-40
DOI: 10.1145/3771561 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Measurement and Analysis of Computing Systems, online erschienen am 02.12.2025. Verfasst von George Yu und 3 weiteren Autor:innen. Die Arbeit wurde bisher 3-mal zitiert (Crossref) und nennt 49 Literaturangaben. Gefördert von: NSF, NDSEG.
Abstract (Originalsprache)
We consider the problem of scheduling to minimize asymptotic tail latency in the M/G/ k queue with light-tailed job size distribution. This problem combines the challenges of scheduling for tail latency and scheduling in multiserver queues, but there is hope. In the simpler setting of the single-server M/G/1, the recently proposed ɣ-Boost policy is tail constant optimal, and it has excellent empirical tail latency. And for the simpler objective of mean latency, it is known that the optimal policy in the M/G/1, namely SRPT (shortest remaining processing time), is also excellent in the M/G/ k : it is provably optimal in heavy traffic and has state-of-the-art empirical performance in lighter traffic. One might therefore hope that ɣ -Boost is similarly effective in the M/G/ k , but our results paint a more complicated picture. In heavy traffic, we prove that ɣ -Boost is indeed tail constant optimal. We also prove an analogous result for scheduling with unknown sizes, where ɣ -Boost is replaced by its unknown-size counterpart. But in lighter traffic, we find empirically that ɣ -Boost can be even worse than FCFS (first-come, first-served). This is a significant shortcoming, as the boundary between ''lighter'' and ''heavy'' traffic occurs at higher load when the number of servers k is larger. To overcome this, we design a new variant of ɣ -Boost that outperforms the original by, counterintuitively, giving more priority to larger jobs. The new variant, which we prove is also heavy-traffic optimal, has state-of-the-art empirical tail latency at lighter loads, outperforming even a much more computationally intensive mixed-integer-programming heuristic.
Förderung
- NSF
- NDSEG
Zitieren
APA
Yu, G., Harlev, A., Adakroy, R., & Scully, Z. (2025). A Tale of Two Traffics: Optimizing Tail Latency in the Light-Tailed M/G/k. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 9(3), 1-40. https://doi.org/10.1145/3771561
Vancouver
Yu G, Harlev A, Adakroy R, Scully Z. A Tale of Two Traffics: Optimizing Tail Latency in the Light-Tailed M/G/k. Proceedings of the ACM on Measurement and Analysis of Computing Systems. 2025;9(3):1-40. doi:10.1145/3771561
BibTeX
@article{Yu2025,
author = {Yu, George and Harlev, Amit and Adakroy, Reevu and Scully, Ziv},
title = {A Tale of Two Traffics: Optimizing Tail Latency in the Light-Tailed M/G/k},
journal = {Proceedings of the ACM on Measurement and Analysis of Computing Systems},
year = {2025},
volume = {9},
number = {3},
pages = {1--40},
doi = {10.1145/3771561}
}
EUVIMED