Tail Optimality and Performance Analysis of the Nudge*(M) Scheduling Algorithm

References

• Abate J, Choudhury L, Whitt W (1994) Waiting-time tail probabilities in queues with long-tail service-time distributions. Queueing Systems 16:311–338.Crossref, Google Scholar
• Charlet N, Van Houdt B (2024) Tail optimality of the nudge-M scheduling algorithm. Proc. ACM Sigmetrics MAMA Workshop, vol. 52 (ACM, New York), 21–23.Google Scholar
• Boxma O, Zwart B (2007) Tails in scheduling. SIGMETRICS Performance Evaluation Rev. 34(4):13–20.Crossref, Google Scholar
• da Silva Soares A (2005) Fluid queues: Building upon the analogy with QBD processes. PhD thesis, Université Libre de Bruxelles, Brussels, Belgium.Google Scholar
• De Clercq S, Steyaert B, Wittevrongel S, Bruneel H (2016) Analysis of a discrete-time queue with time-limited overtake priority. Ann. Oper. Res. 238(1):69–97.Crossref, Google Scholar
• De Muynck M, Bruneel H, Wittevrongel S (2017) Tail probabilities of the delay under a reservation-based scheduling mechanism. Yue W, Li QL, Jin S, Ma Z, eds. Queueing Theory and Network Applications (Springer International Publishing, Cham, Switzerland), 265–281.Crossref, Google Scholar
• De Vuyst S, Wittevrongel S, Bruneel H (2008) Place reservation: Delay analysis of a novel scheduling mechanism. Comput. Oper. Res. 35(8):2447–2462.Crossref, Google Scholar
• Dzial T, Breuer L, da Silva Soares A, Latouche G, Remiche M (2005) Fluid queues to solve jump processes. Performance Evaluation 62(1):132–146.Crossref, Google Scholar
• Feldmann A, Whitt W (1998) Fitting mixtures of exponentials to long-tail distributions to analyze network performance models. Performance Evaluation 31(3):245–279.Crossref, Google Scholar
• Goldberg HM (1977) Analysis of the earliest due date scheduling rule in queueing systems. Math. Oper. Res. 2(2):145–154.Link, Google Scholar
• Grosof I, Yang K, Scully Z, Harchol-Balter M (2021) Nudge: Stochastically improving upon FCFS. Proc. ACM Measures Anal. Comput. Systems 5(2):1–29.Google Scholar
• Horv’th G, Van Houdt B (2012) A multi-layer fluid queue with boundary phase transitions and its application to the analysis of multi-type queues with general customer impatience. Proc. QEST (IEEE, Piscataway, NJ), 23–32.Google Scholar
• Kriege J, Buchholz P (2014) PH and MAP Fitting with Aggregated Traffic Traces (Springer International Publishing, Cham, Switzerland).Crossref, Google Scholar
• Larson RC (1987) Perspectives on queues: Social justice and the psychology of queueing. Oper. Res. 35(6):895–905.Link, Google Scholar
• Latouche G, Ramaswami V (1999) Introduction to Matrix Analytic Methods and Stochastic Modeling (SIAM, Philadelphia).Crossref, Google Scholar
• Liu CL, Layland JW (1973) Scheduling algorithms for multiprogramming in a hard-real-time environment. J. ACM 20(1):46–61.Crossref, Google Scholar
• Nuyens M, Wierman A, Zwart B (2008) Preventing large sojourn times using smart scheduling. Oper. Res. 56(1):88–101.Link, Google Scholar
• Panchenko A, Thümmler A (2007) Efficient phase-type fitting with aggregated traffic traces. Performance Evaluation 64(7–8):629–645.Crossref, Google Scholar
• Schrage L (1967) The queue M/G/1 with feedback to lower priorities. Management Sci. 13(7):466–474.Link, Google Scholar
• Van Houdt B (2012) Analysis of the adaptive MMAP[K]/PH[K]/1 queue: A multi-type queue with adaptive arrivals and general impatience. Eur. J. Oper. Res. 220(3):695–704.Crossref, Google Scholar
• Van Houdt B (2022) On the stochastic and asymptotic improvement of first-come first-served and nudge scheduling. Proc. ACM Measures Anal. Comput. Systems 6(3):1–22.Crossref, Google Scholar
• Yu G, Scully Z (2024) Strongly tail-optimal scheduling in the light-tailed M/G/1. SIGMETRICS Performance Evaluation Rev. 52(1):5–6.Crossref, Google Scholar