EUVIMEDEUVIMED entdecken
Crossref

A Tale of Two Traffics: Optimizing Tail Latency in the Light-Tailed M/G/k

George Yu, Amit Harlev, Reevu Adakroy, Ziv Scully

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →