[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
research-article

Strongly Tail-Optimal Scheduling in the Light-Tailed M/G/1

Published: 29 May 2024 Publication History

Abstract

We study the problem of scheduling jobs in a queueing system, specifically an M/G/1 with light-tailed job sizes, to asymptotically optimize the response time tail. This means scheduling to make \mathbfP [T > t], the chance a job's response time exceeds t, decay as quickly as possible in the t \to \infty limit. For some time, the best known policy was First-Come First-Served (FCFS), which has an asymptotically exponential tail: \mathbfP [T > t] \sim C e^-γ t . FCFS achieves the optimal *decay rate* γ, but its *tail constant* C is suboptimal. Only recently have policies that improve upon FCFS's tail constant been discovered. But it is unknown what the optimal tail constant is, let alone what policy might achieve it. In this paper, we derive a closed-form expression for the optimal tail constant C, and we introduce *γ-Boost*, a new policy that achieves this optimal tail constant. Roughly speaking, γ-Boost operates similarly to FCFS, but it pretends that small jobs arrive earlier than their true arrival times. This significantly reduces the response time of small jobs without unduly delaying large jobs, improving upon FCFS's tail constant by up to 50% with only moderate job size variability, with even larger improvements for higher variability. While these results are for systems with full job size information, we also introduce and analyze a version of γ-Boost that works in settings with partial job size information, showing it too achieves significant gains over FCFS. Finally, we show via simulation that γ-Boost has excellent practical performance.

References

[1]
Joseph Abate, Gagan L. Choudhury, and Ward Whitt. 1994. Waiting-Time Tail Probabilities in Queues with Long-Tail Service-Time Distributions. Queueing Systems, Vol. 16, 3--4 (Sept. 1994), 311--338. https://doi.org/10.1007/BF01158960
[2]
Joseph Abate and Ward Whitt. 1997. Asymptotics for $M/G/1$ Low-Priority Waiting-Time Tail Probabilities. Queueing Systems, Vol. 25, 1 (June 1997), 173--233. https://doi.org/10.1023/A:1019104402024
[3]
Albert Gran Alcoz, Alexander Dietmüller, and Laurent Vanbever. 2020. SP-PIFO : Approximating Push-in First-out Behaviors Using Strict-Priority Queues. In 17th USENIX Symposium on Networked Systems Design and Implementation (NSDI 2020). USENIX Association, Santa Clara, CA, 59--76. https://www.usenix.org/conference/nsdi20/presentation/alcoz
[4]
Franc cois Baccelli and Pierre Brémaud. 2003. Elements of Queueing Theory: Palm Martingale Calculus and Stochastic Recurrences 2 ed.). Number 26 in Stochastic Modelling and Applied Probability. Springer, Berlin, Germany. QA274.9. B33 2003 https://doi.org/10.1007/978--3--662--11657--9
[5]
Nicholas H. Bingham, Charles M. Goldie, and Jef L. Teugels. 1987. Regular Variation. Number 27 in Encyclopedia of Mathematics and Its Applications. Cambridge University Press, Cambridge, UK. QA331.5. B54 1987
[6]
Sem C. Borst, Onno J. Boxma, Rudesindo Nú nez-Queija, and Bert Zwart. 2003. The Impact of the Service Discipline on Delay Asymptotics. Performance Evaluation, Vol. 54, 2 (Oct. 2003), 175--206. https://doi.org/10.1016/S0166--5316(03)00071--3
[7]
Onno J. Boxma and Bert Zwart. 2007. Tails in Scheduling. ACM SIGMETRICS Performance Evaluation Review, Vol. 34, 4 (March 2007), 13--20. https://doi.org/10.1145/1243401.1243406
[8]
Pierre Brémaud. 2020. Probability Theory and Stochastic Processes. Springer, Cham, Switzerland. https://doi.org/10.1007/978--3-030--40183--2
[9]
Nils Charlet and Benny Van Houdt. 2024. Tail Optimality and Performance Analysis of the Nudge-M Scheduling Algorithm. arxiv: 2403.06588 [cs, math] http://arxiv.org/abs/2403.06588
[10]
Yan Chen and Jing Dong. 2021. Scheduling with Service-Time Information: The Power of Two Priority Classes. arxiv: 2105.10499 [cs, math] http://arxiv.org/abs/2105.10499
[11]
Val Andrei Fajardo and Steve Drekic. 2015. Controlling the Workload of $M/G/1$ Queues via the q-Policy. European Journal of Operational Research, Vol. 243, 2 (June 2015), 607--617. https://doi.org/10.1016/j.ejor.2014.12.036
[12]
Val Andrei Fajardo and Steve Drekic. 2017. Waiting Time Distributions in the Preemptive Accumulating Priority Queue. Methodology and Computing in Applied Probability, Vol. 19, 1 (March 2017), 255--284. https://doi.org/10.1007/s11009-015--9476--1
[13]
Eric J. Friedman and Shane G. Henderson. 2003. Fairness and Efficiency in Web Server Protocols. ACM SIGMETRICS Performance Evaluation Review, Vol. 31, 1 (June 2003), 229--237. https://doi.org/10.1145/885651.781056
[14]
Eric J. Friedman and Gavin Hurley. 2003. Protective Scheduling. Technical Report 1373. Cornell University, Ithaca, NY. 11 pages. https://hdl.handle.net/1813/9250
[15]
Bezalel Gavish and Paul J. Schweitzer. 1977. The Markovian Queue with Bounded Waiting Time. Management Science, Vol. 23, 12 (Aug. 1977), 1349--1357. https://doi.org/10.1287/mnsc.23.12.1349
[16]
John C. Gittins, Kevin D. Glazebrook, and Richard R. Weber. 2011. Multi-Armed Bandit Allocation Indices 2 ed.). Wiley, Chichester, UK. QA279. G55 2011
[17]
Isaac Grosof. 2023. Optimal Scheduling in Multiserver Queues. Ph.,D. Dissertation. Carnegie Mellon University, Pittsburgh, PA. https://isaacg1.github.io/assets/isaac-thesis.pdf
[18]
Isaac Grosof, Ziv Scully, and Mor Harchol-Balter. 2018. SRPT for Multiserver Systems. Performance Evaluation, Vol. 127--128 (Nov. 2018), 154--175. https://doi.org/10.1016/j.peva.2018.10.001
[19]
Isaac Grosof, Ziv Scully, and Mor Harchol-Balter. 2019. Load Balancing Guardrails: Keeping Your Heavy Traffic on the Road to Low Response Times. Proceedings of the ACM on Measurement and Analysis of Computing Systems, Vol. 3, 2, Article 42 (June 2019), bibinfonumpages31 pages. https://doi.org/10.1145/3341617.3326157
[20]
Isaac Grosof, Ziv Scully, Mor Harchol-Balter, and Alan Scheller-Wolf. 2022. Optimal Scheduling in the Multiserver-Job Model under Heavy Traffic. Proceedings of the ACM on Measurement and Analysis of Computing Systems, Vol. 6, 3, Article 51 (Dec. 2022), bibinfonumpages32 pages. https://doi.org/10.1145/3570612
[21]
Isaac Grosof, Kunhe Yang, Ziv Scully, and Mor Harchol-Balter. 2021. Nudge: Stochastically Improving upon FCFS. Proceedings of the ACM on Measurement and Analysis of Computing Systems, Vol. 5, 2, Article 21 (June 2021), bibinfonumpages29 pages. https://doi.org/10.1145/3460088
[22]
Mor Harchol-Balter. 2013. Performance Modeling and Design of Computer Systems: Queueing Theory in Action. Cambridge University Press, Cambridge, UK. QA76.545. H37 2013
[23]
Mor Harchol-Balter, Bianca Schroeder, Nikhil Bansal, and Mukesh Agrawal. 2003. Size-Based Scheduling to Improve Web Performance. ACM Transactions on Computer Systems, Vol. 21, 2 (May 2003), 207--233. https://doi.org/10.1145/762483.762486
[24]
Yige Hong and Ziv Scully. 2024. Performance of the Gittins Policy in the G /G /1 and G /G /k, with and without Setup Times. Performance Evaluation, Vol. 163, Article 102377 (Jan. 2024), bibinfonumpages26 pages. https://doi.org/10.1016/j.peva.2023.102377
[25]
J. F. C. Kingman. 1993. Poisson Processes. Number 3 in Oxford Studies in Probability. Oxford University Press, Oxford. QA274.42. K56 1993
[26]
Aryeh Kontorovich and Iosif Pinelis. 2019. Exact Lower Bounds for the Agnostic Probably-Approximately-Correct (PAC ) Machine Learning Model. The Annals of Statistics, Vol. 47, 5 (Oct. 2019), 2822--2854. https://doi.org/10.1214/18-AOS1766
[27]
Jan Karel Lenstra and David B. Shmoys. 2020. Elements of Scheduling. arxiv: 2001.06005 [cs] http://arxiv.org/abs/2001.06005
[28]
Andrea Marin, Sabina Rossi, and Carlo Zen. 2020. Size-Based Scheduling for TCP Flows: Implementation and Performance Evaluation. Computer Networks, Vol. 183, Article 107574 (Dec. 2020), bibinfonumpages15 pages. https://doi.org/10.1016/j.comnet.2020.107574
[29]
Jayakrishnan Nair, Adam Wierman, and Bert Zwart. 2010. Tail-Robust Scheduling via Limited Processor Sharing. Performance Evaluation, Vol. 67, 11 (Nov. 2010), 978--995. https://doi.org/10.1016/j.peva.2010.08.012
[30]
Rudesindo Nú nez-Queija. 2002. Queues with Equally Heavy Sojourn Time and Service Requirement Distributions. Annals of Operations Research, Vol. 113, 1/4 (July 2002), 101--117. https://doi.org/10.1023/A:1020905810996
[31]
Misja Nuyens, Adam Wierman, and Bert Zwart. 2008. Preventing Large Sojourn Times Using SMART Scheduling. Operations Research, Vol. 56, 1 (Feb. 2008), 88--101. https://doi.org/10.1287/opre.1070.0504
[32]
Misja Nuyens and Bert Zwart. 2006. A Large-Deviations Analysis of the $GI/GI/1$ SRPT Queue. Queueing Systems, Vol. 54, 2 (Oct. 2006), 85--97. https://doi.org/10.1007/s11134-006--8767--1
[33]
Michael Pinedo. 2016. Scheduling: Theory, Algorithms, and Systems 5 ed.). Springer, Cham, Switzerland.
[34]
Ziv Scully. 2022. A New Toolbox for Scheduling Theory. Ph.,D. Dissertation. Carnegie Mellon University, Pittsburgh, PA. https://ziv.codes/pdf/scully-thesis.pdf
[35]
Ziv Scully, Isaac Grosof, and Mor Harchol-Balter. 2020a. The Gittins Policy Is Nearly Optimal in the M /G /k under Extremely General Conditions. Proceedings of the ACM on Measurement and Analysis of Computing Systems, Vol. 4, 3, Article 43 (Nov. 2020), bibinfonumpages29 pages. https://doi.org/10.1145/3428328
[36]
Ziv Scully and Mor Harchol-Balter. 2018. SOAP Bubbles: Robust Scheduling under Adversarial Noise. In 56th Annual Allerton Conference on Communication, Control, and Computing. IEEE, Monticello, IL, 144--154. https://doi.org/10.1109/ALLERTON.2018.8635963
[37]
Ziv Scully and Mor Harchol-Balter. 2021. The Gittins Policy in the M /G /1 Queue. In 19th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt 2021). IFIP, Philadelphia, PA, 248--255. https://doi.org/10.23919/WiOpt52861.2021.9589051
[38]
Ziv Scully, Mor Harchol-Balter, and Alan Scheller-Wolf. 2018. SOAP : One Clean Analysis of All Age-Based Scheduling Policies. Proceedings of the ACM on Measurement and Analysis of Computing Systems, Vol. 2, 1, Article 16 (April 2018), bibinfonumpages30 pages. https://doi.org/10.1145/3179419
[39]
Ziv Scully and Lucas van Kreveld. 2024. When Does the Gittins Policy Have Asymptotically Optimal Response Time Tail in the M /G /1? Operations Research, Vol. 72, 2 (Feb. 2024). https://doi.org/10.1287/opre.2022.0038
[40]
Ziv Scully, Lucas van Kreveld, Onno J. Boxma, Jan-Pieter Dorsman, and Adam Wierman. 2020b. Characterizing Policies with Optimal Response Time Tails under Heavy-Tailed Job Sizes. Proceedings of the ACM on Measurement and Analysis of Computing Systems, Vol. 4, 2, Article 30 (June 2020), bibinfonumpages33 pages. https://doi.org/10.1145/3392148
[41]
J. George Shanthikumar and Ushio Sumita. 1987. Convex Ordering of Sojourn Times in Single-Server Queues: Extremal Properties of FIFO and LIFO Service Disciplines. Journal of Applied Probability, Vol. 24, 3 (Sept. 1987), 737--748. https://doi.org/10.2307/3214103
[42]
Anirudh Sivaraman, Suvinay Subramanian, Mohammad Alizadeh, Sharad Chole, Shang-Tse Chuang, Anurag Agrawal, Hari Balakrishnan, Tom Edsall, Sachin Katti, and Nick McKeown. 2016. Programmable Packet Scheduling at Line Rate. In Proceedings of the 2016 ACM SIGCOMM Conference (SIGCOMM 2016). ACM, Florianopolis, Brazil, 44--57. https://doi.org/10.1145/2934872.2934899
[43]
David A. Stanford, Peter Taylor, and Ilze Ziedins. 2014. Waiting Time Distributions in the Accumulating Priority Queue. Queueing Systems, Vol. 77, 3 (July 2014), 297--330. https://doi.org/10.1007/s11134-013--9382--6
[44]
Alexander L. Stolyar and Kavita Ramanan. 2001. Largest Weighted Delay First Scheduling: Large Deviations and Optimality. The Annals of Applied Probability, Vol. 11, 1 (Feb. 2001), 1--48. https://doi.org/10.1214/aoap/998926986
[45]
Benny Van Houdt. 2022. On the Stochastic and Asymptotic Improvement of First-Come First-Served and Nudge Scheduling. Proceedings of the ACM on Measurement and Analysis of Computing Systems, Vol. 6, 3 (Dec. 2022), 1--22. https://doi.org/10.1145/3570610
[46]
Adam Wierman and Bert Zwart. 2012. Is Tail-Optimal Scheduling Possible? Operations Research, Vol. 60, 5 (Oct. 2012), 1249--1257. https://doi.org/10.1287/opre.1120.1086
[47]
Ronald W. Wolff. 1982. Poisson Arrivals See Time Averages. Operations Research, Vol. 30, 2 (1982), 223--231. http://www.jstor.org/stable/170165
[48]
Bert Zwart and Onno J. Boxma. 2000. Sojourn Time Asymptotics in the M /G /1 Processor Sharing Queue. Queueing Systems, Vol. 35, 1/4 (2000), 141--166. https://doi.org/10.1023/A:1019142010994

Cited By

View all
  • (2024)Strongly Tail-Optimal Scheduling in the Light-Tailed M/G/1ACM SIGMETRICS Performance Evaluation Review10.1145/3673660.365508452:1(5-6)Online publication date: 13-Jun-2024
  • (2024)Strongly Tail-Optimal Scheduling in the Light-Tailed M/G/1Abstracts of the 2024 ACM SIGMETRICS/IFIP PERFORMANCE Joint International Conference on Measurement and Modeling of Computer Systems10.1145/3652963.3655084(5-6)Online publication date: 10-Jun-2024

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Proceedings of the ACM on Measurement and Analysis of Computing Systems
Proceedings of the ACM on Measurement and Analysis of Computing Systems  Volume 8, Issue 2
POMACS
June 2024
344 pages
EISSN:2476-1249
DOI:10.1145/3669944
Issue’s Table of Contents
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 May 2024
Published in POMACS Volume 8, Issue 2

Permissions

Request permissions for this article.

Check for updates

Badges

  • Best Paper

Author Tags

  1. boost scheduling
  2. fcfs
  3. light-tailed distribution
  4. m/g/1 queue
  5. response time
  6. scheduling
  7. service level objective (slo)
  8. sojourn time
  9. tail latency

Qualifiers

  • Research-article

Funding Sources

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)97
  • Downloads (Last 6 weeks)8
Reflects downloads up to 31 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2024)Strongly Tail-Optimal Scheduling in the Light-Tailed M/G/1ACM SIGMETRICS Performance Evaluation Review10.1145/3673660.365508452:1(5-6)Online publication date: 13-Jun-2024
  • (2024)Strongly Tail-Optimal Scheduling in the Light-Tailed M/G/1Abstracts of the 2024 ACM SIGMETRICS/IFIP PERFORMANCE Joint International Conference on Measurement and Modeling of Computer Systems10.1145/3652963.3655084(5-6)Online publication date: 10-Jun-2024

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media