IDEAS home Printed from https://ideas.repec.org/a/spr/queues/v97y2021i1d10.1007_s11134-020-09684-6.html
   My bibliography  Save this article

Open problems in queueing theory inspired by datacenter computing

Author

Listed:
  • Mor Harchol-Balter

    (Carnegie Mellon University)

Abstract

Datacenter operations today provide a plethora of new queueing and scheduling problems. The notion of a “job” has become more general and multi-dimensional. The ways in which jobs and servers can interact have grown in complexity, involving parallelism, speedup functions, precedence constraints, and task graphs. The workloads are vastly more variable and more heavy-tailed. Even the performance metrics of interest are broader than in the past, with multi-dimensional service-level objectives in terms of tail probabilities. The purpose of this article is to expose queueing theorists to new models, while providing suggestions for many specific open problems of interest, as well as some insights into their potential solution.

Suggested Citation

  • Mor Harchol-Balter, 2021. "Open problems in queueing theory inspired by datacenter computing," Queueing Systems: Theory and Applications, Springer, vol. 97(1), pages 3-37, February.
    • Handle: RePEc:spr:queues:v:97:y:2021:i:1:d:10.1007_s11134-020-09684-6
    DOI: 10.1007/s11134-020-09684-6
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s11134-020-09684-6
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s11134-020-09684-6?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Kristen Gardner & Samuel Zbarsky & Sherwin Doroudi & Mor Harchol-Balter & Esa Hyytiä & Alan Scheller-Wolf, 2016. "Queueing with redundant requests: exact analysis," Queueing Systems: Theory and Applications, Springer, vol. 83(3), pages 227-259, August.
    2. Peter Iseger & Paul Gruntjes & Michel Mandjes, 2013. "A Wiener–Hopf based approach to numerical computations in fluctuation theory for Lévy processes," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 78(1), pages 101-118, August.
    3. Hunt, P. J. & Kurtz, T. G., 1994. "Large loss networks," Stochastic Processes and their Applications, Elsevier, vol. 53(2), pages 363-378, October.
    4. Alexander Rumyantsev & Evsey Morozov, 2017. "Stability criterion of a multiserver model with simultaneous service," Annals of Operations Research, Springer, vol. 252(1), pages 29-39, May.
    5. Weina Wang & Mor Harchol-Balter & Haotian Jiang & Alan Scheller-Wolf & R. Srikant, 2019. "Delay asymptotics and bounds for multitask parallel jobs," Queueing Systems: Theory and Applications, Springer, vol. 91(3), pages 207-239, April.
    6. L. G. Afanaseva & S. A. Grishunina, 2020. "Stability conditions for a multiserver queueing system with a regenerative input flow and simultaneous service of a customer by a random number of servers," Queueing Systems: Theory and Applications, Springer, vol. 94(3), pages 213-241, April.
    7. Kristen Gardner & Mor Harchol-Balter & Alan Scheller-Wolf & Mark Velednitsky & Samuel Zbarsky, 2017. "Redundancy-d: The Power of d Choices for Redundancy," Operations Research, INFORMS, vol. 65(4), pages 1078-1094, August.
    8. Bezalel Gavish & Paul J. Schweitzer, 1977. "The Markovian Queue with Bounded Waiting time," Management Science, INFORMS, vol. 23(12), pages 1349-1357, August.
    9. Larisa Afanaseva & Elena Bashtova & Svetlana Grishunina, 2020. "Stability Analysis of a Multi-server Model with Simultaneous Service and a Regenerative Input Flow," Methodology and Computing in Applied Probability, Springer, vol. 22(4), pages 1439-1455, December.
    10. Percy H. Brill & Linda Green, 1984. "Queues in Which Customers Receive Simultaneous Service from a Random Number of Servers: A System Point Approach," Management Science, INFORMS, vol. 30(1), pages 51-68, January.
    11. Syed Hamid Hussain Madni & Muhammad Shafie Abd Latiff & Mohammed Abdullahi & Shafi’i Muhammad Abdulhamid & Mohammed Joda Usman, 2017. "Performance comparison of heuristic algorithms for task scheduling in IaaS cloud computing environment," PLOS ONE, Public Library of Science, vol. 12(5), pages 1-26, May.
    12. Ward Whitt, 1992. "Understanding the Efficiency of Multi-Server Service Systems," Management Science, INFORMS, vol. 38(5), pages 708-723, May.
    13. Joseph Abate & Ward Whitt, 2006. "A Unified Framework for Numerically Inverting Laplace Transforms," INFORMS Journal on Computing, INFORMS, vol. 18(4), pages 408-421, November.
    14. Linus E. Schrage & Louis W. Miller, 1966. "The Queue M / G /1 with the Shortest Remaining Processing Time Discipline," Operations Research, INFORMS, vol. 14(4), pages 670-684, August.
    15. Youri Raaijmakers & Sem Borst & Onno Boxma, 2019. "Redundancy scheduling with scaled Bernoulli service requirements," Queueing Systems: Theory and Applications, Springer, vol. 93(1), pages 67-82, October.
    16. Linus Schrage, 1968. "Letter to the Editor—A Proof of the Optimality of the Shortest Remaining Processing Time Discipline," Operations Research, INFORMS, vol. 16(3), pages 687-690, June.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Youri Raaijmakers & Sem Borst & Onno Boxma, 2023. "Fork–join and redundancy systems with heavy-tailed job sizes," Queueing Systems: Theory and Applications, Springer, vol. 103(1), pages 131-159, February.
    2. Samuli Aalto & Ziv Scully, 2023. "Minimizing the mean slowdown in the M/G/1 queue," Queueing Systems: Theory and Applications, Springer, vol. 104(3), pages 187-210, August.
    3. Neil Walton, 2022. "Queueing: a perennial theory," Queueing Systems: Theory and Applications, Springer, vol. 100(3), pages 557-559, April.
    4. Rein Vesilo, 2024. "Core allocation to minimize total flow time in a multicore system in the presence of a processing time constraint," Queueing Systems: Theory and Applications, Springer, vol. 108(3), pages 475-577, December.
    5. Alexander Dudin & Sergei Dudin & Olga Dudina, 2023. "Analysis of a Queueing System with Mixed Service Discipline," Methodology and Computing in Applied Probability, Springer, vol. 25(2), pages 1-19, June.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Kristen Gardner & Rhonda Righter, 2022. "The cost of collaboration," Queueing Systems: Theory and Applications, Springer, vol. 100(1), pages 7-40, February.
    2. Kristen Gardner & Pascal Moyal, 2024. "Editorial introduction: second part of the special issue on product forms, stochastic matching, and redundancy," Queueing Systems: Theory and Applications, Springer, vol. 107(3), pages 199-203, September.
    3. Kristen Gardner & Rhonda Righter, 2020. "Product forms for FCFS queueing models with arbitrary server-job compatibilities: an overview," Queueing Systems: Theory and Applications, Springer, vol. 96(1), pages 3-51, October.
    4. Mor Harchol-Balter, 2022. "The multiserver job queueing model," Queueing Systems: Theory and Applications, Springer, vol. 100(3), pages 201-203, April.
    5. Michael Dreyfuss & Yair Y. Shaki & Uri Yechiali, 2022. "The double-space parking problem," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 44(4), pages 1131-1147, December.
    6. Thomas Kittsteiner & Benny Moldovanu, 2005. "Priority Auctions and Queue Disciplines That Depend on Processing Time," Management Science, INFORMS, vol. 51(2), pages 236-248, February.
    7. Yonatan Shadmi, 2022. "Fluid limits for shortest job first with aging," Queueing Systems: Theory and Applications, Springer, vol. 101(1), pages 93-112, June.
    8. Douglas G. Down & H. Christian Gromoll & Amber L. Puha, 2009. "Fluid Limits for Shortest Remaining Processing Time Queues," Mathematics of Operations Research, INFORMS, vol. 34(4), pages 880-911, November.
    9. Łukasz Kruk & Ewa Sokołowska, 2016. "Fluid Limits for Multiple-Input Shortest Remaining Processing Time Queues," Mathematics of Operations Research, INFORMS, vol. 41(3), pages 1055-1092, August.
    10. Kristen Gardner, 2022. "Correlation in redundancy systems," Queueing Systems: Theory and Applications, Springer, vol. 100(3), pages 197-199, April.
    11. Youri Raaijmakers & Sem Borst & Onno Boxma, 2019. "Redundancy scheduling with scaled Bernoulli service requirements," Queueing Systems: Theory and Applications, Springer, vol. 93(1), pages 67-82, October.
    12. Predrag Jelenković & Xiaozhu Kang & Jian Tan, 2009. "Heavy-tailed limits for medium size jobs and comparison scheduling," Annals of Operations Research, Springer, vol. 170(1), pages 133-159, September.
    13. Jing Dong & Rouba Ibrahim, 2021. "SRPT Scheduling Discipline in Many-Server Queues with Impatient Customers," Management Science, INFORMS, vol. 67(12), pages 7708-7718, December.
    14. Jan-Pieter Dorsman & Kristen Gardner, 2024. "New directions in pass-and-swap queues," Queueing Systems: Theory and Applications, Springer, vol. 107(3), pages 205-256, September.
    15. Isaac Grosof & Mor Harchol-Balter & Alan Scheller-Wolf, 2022. "WCFS: a new framework for analyzing multiserver systems," Queueing Systems: Theory and Applications, Springer, vol. 102(1), pages 143-174, October.
    16. Hyytiä, Esa & Penttinen, Aleksi & Aalto, Samuli, 2012. "Size- and state-aware dispatching problem with queue-specific job sizes," European Journal of Operational Research, Elsevier, vol. 217(2), pages 357-370.
    17. Łukasz Kruk & Robert Gieroba, 2022. "Local edge minimality of SRPT networks with shared resources," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 96(3), pages 459-492, December.
    18. Łukasz Kruk, 2022. "Heavy traffic analysis for single-server SRPT and LRPT queues via EDF diffusion limits," Annals of Operations Research, Springer, vol. 310(2), pages 411-429, March.
    19. Konstantin Avrachenkov & Patrick Brown & Natalia Osipova, 2009. "Optimal choice of threshold in Two Level Processor Sharing," Annals of Operations Research, Springer, vol. 170(1), pages 21-39, September.
    20. Achal Bassamboo & J. Michael Harrison & Assaf Zeevi, 2006. "Design and Control of a Large Call Center: Asymptotic Analysis of an LP-Based Method," Operations Research, INFORMS, vol. 54(3), pages 419-435, June.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:queues:v:97:y:2021:i:1:d:10.1007_s11134-020-09684-6. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.