Sharp Waiting-Time Bounds for Multiserver Jobs

References

• Abadi M, Barham P, Chen J, Chen Z, Davis A, Dean J, Devin M, et al. (2016) Tensorflow: A system for large-scale machine learning. Keeton K, Roscoe T, eds. Proc. USENIX Conf. Operating Systems Design Implementation (OSDI) (USENIX Association, Berkeley, CA), 265–283.Google Scholar
• Afanaseva L, Bashtova E, Grishunina S (2019) Stability analysis of a multi-server model with simultaneous service and a regenerative input flow. Methodology Comput. Appl. Probab. 22(4):1–17.Google Scholar
• Arthurs E, Kaufman J (1979) Sizing a message store subject to blocking criteria. Arató M, Butrimenko A, Gelenbe E, eds. Proc. Internat. Sympos. Computer Performance Model. Measurements Evaluation (IFIP Performance) (North-Holland, Amsterdam), 547–564.Google Scholar
• Asmussen S, Glynn PW (2007) Steady-State Simulation (Springer, New York), 96–125.Google Scholar
• Ata B, Gurvich I (2012) On optimality gaps in the Halfin–Whitt regime. Ann. Appl. Probab. 22(1):407–455.Google Scholar
• Atar R (2012) A diffusion regime with nondegenerate slowdown. Oper. Res. 60(2):490–500.Link, Google Scholar
• Atar R, Mandelbaum A, Reiman MI (2004) Scheduling a multi class queue with many exponential servers: Asymptotic optimality in heavy traffic. Ann. Appl. Probab. 14(3):1084–1134.Google Scholar
• Bean NG, Gibbens RJ, Zachary S (1995) Asymptotic analysis of single resource loss systems in heavy traffic, with applications to integrated networks. Adv. Appl. Probab. 27(1):273–292.Google Scholar
• Benameur N, Fredj S, Delcoigne F, Oueslati-Boulahia S, Roberts J (2001) Integrated admission control for streaming and elastic traffic. Smirnov MI, Crowcroft J, Roberts J, Boavida F, eds. Internat. Workshop Quality Future Internet Services (QofIS) (Springer, Berlin, Heidelberg), 69–81.Google Scholar
• Brill PH, Green L (1984) Queues in which customers receive simultaneous service from a random number of servers: A system point approach. Management Sci. 30(1):51–68.Link, Google Scholar
• Dasylva A, Srikant R (1999) Bounds on the performance of admission control and routing policies for general topology networks with multiple call centers. Ephremides T, Tripathi SK, eds. Proc. IEEE Internat. Conf. Comput. Comm. (INFOCOM), vol. 2 (IEEE Computer Society, Alamitos, CA), 505–512.Google Scholar
• Daw A, Pender J (2019) On the distributions of infinite server queues with batch arrivals. Queueing Systems 91(3–4):367–401.Google Scholar
• Daw A, Fralix B, Pender J (2020) Non-stationary queues with batch arrivals. Preprint, submitted August 3, https://arxiv.org/abs/2008.00625.Google Scholar
• Daw A, Hampshire RC, Pender J (2019) How to staff when customers arrive in batches. Preprint, submitted July 30, https://arxiv.org/abs/1907.12650.Google Scholar
• Eryilmaz A, Srikant R (2012) Asymptotically tight steady-state queue length bounds implied by drift conditions. Queueing Systems 72(3–4):311–359.Google Scholar
• Filippopoulos D, Karatza H (2008) A two-class parallel system with general service times of the parallel class. J. Comput. System Sci. 74(6):942–964.Google Scholar
• Google (2022) Google Kubernetes engine. The most scalable and fully automated Kubernetes service. Accessed January 22, 2023, https://cloud.google.com/kubernetes-engine.Google Scholar
• Grosof I, Harchol-Balter M, Scheller-Wolf A (2020) Stability for two-class multiserver-job systems. Preprint, submitted October 1, https://arxiv.org/abs/2010.00631.Google Scholar
• Grosof I, Harchol-Balter M, Scheller-Wolf A (2022a) WCFS: A new framework for analyzing multiserver systems. Queueing Systems 102(1):143–174.Google Scholar
• Grosof I, Scully Z, Harchol-Balter M, Scheller-Wolf A (2022b) Optimal scheduling in the multiserver-job model under heavy traffic. ACM SIGMETRICS Performance Evaluation Rev. 51(1):99–100.Google Scholar
• Halfin S, Whitt W (1981) Heavy-traffic limits for queues with many exponential servers. Oper. Res. 29(3):567–588.Link, Google Scholar
• Harchol-Balter M (2013) Performance Modeling and Design of Computer Systems: Queueing Theory in Action, 1st ed. (Cambridge University Press, New York).Google Scholar
• Harrison JM, Zeevi A (2004) Dynamic scheduling of a multiclass queue in the Halfin–Whitt heavy traffic regime. Oper. Res. 52(2):1–31.Google Scholar
• Hong Y, Wang W (2022) Sharp waiting-time bounds for multiserver jobs. Naghizadeh P, Sun Y, eds. ACM Internat. Sympos. Mobile Ad Hoc Networking Comput. (MobiHoc) (ACM, New York), 161–170.Google Scholar
• Hunt PJ, Kurtz TG (1994) Large loss networks. Stochastic Processes Their Appl. 53(2):363–378.Google Scholar
• Hunt PJ, Laws CN (1997) Optimization via trunk reservation in single resource loss systems under heavy traffic. Ann. Appl. Probab. 7(4):1058–1079.Google Scholar
• Lin SH, Paolieri M, Chou CF, Golubchik L (2018) A model-based approach to streamlining distributed training for asynchronous SGD. Wildani A, Wang M, eds. IEEE Internat. Sympos. Model. Anal. Simulation Comput. Telecomm. Systems (MASCOTS) (IEEE Computer Society, Los Alamitos, CA), 306–318.Google Scholar
• Liu X (2019) Steady state analysis of load balancing algorithms in the heavy traffic regime. PhD thesis, Arizona State University, Tempe.Google Scholar
• Liu X, Ying L (2020) Steady-state analysis of load-balancing algorithms in the sub-Halfin–Whitt regime. J. Appl. Probab. 57(2):578–596.Google Scholar
• Liu X, Ying L (2022) Universal scaling of distributed queues under load balancing in the super-Halfin–Whitt regime. IEEE/ACM Trans. Networking 30(1):190–201.Google Scholar
• Liu X, Gong K, Ying L (2022) Steady-state analysis of load balancing with Coxian-2 distributed service times. Naval Res. Logist. 69(1):57–75.Google Scholar
• Maguluri ST, Srikant R (2014) Scheduling jobs with unknown duration in clouds. IEEE/ACM Trans. Netw. 22(6):1938–1951.Google Scholar
• Maguluri ST, Srikant R (2016) Heavy traffic queue length behavior in a switch under the maxweight algorithm. Stochastic Systems 6(1):211–250.Link, Google Scholar
• Maguluri ST, Srikant R, Ying L (2012) Stochastic models of load balancing and scheduling in cloud computing clusters. Greenberg AG, Sohraby K, eds. Proc. IEEE Internat. Conf. Comput. Comm. (INFOCOM) (IEEE Computer Society, Los Alamitos, CA), 702–710.Google Scholar
• Maguluri ST, Srikant R, Ying L (2014) Heavy traffic optimal resource allocation algorithms for cloud computing clusters. Performance Evaluation 81:20–39.Google Scholar
• Melikov A (1996) Computation and optimization methods for multiresource queues. Cybernetics Systems Anal. 32(6):821–836.Google Scholar
• Miller RG (1959) A contribution to the theory of bulk queues. J. Roy. Statist. Soc. Ser. B Methodological 21(2):320–337.Google Scholar
• Morozov E, Rumyantsev AS (2016) Stability analysis of a MAP/M/s cluster model by matrix-analytic method. Fiems D, Paolieri M, Platis AN, eds. Eur. Workshop Comput. Performance Engrg. (EPEW), vol. 9951 (Springer, Cham, Switzerland), 63–76.Google Scholar
• Olliaro D, Ajmone Marsan M, Balsamo S, Marin A (2023) The saturated multiserver job queuing model with two classes of jobs: Exact and approximate results. Performance Evaluation 162:102370.Google Scholar
• Ponomarenko L, Kim CS, Melikov A (2010) Performance Analysis and Optimization of Multi-Traffic on Communication Networks (Springer Science & Business Media, New York).Google Scholar
• Psychas K, Ghaderi J (2018) On non-preemptive VM scheduling in the cloud. SIGMETRICS Perform. Eval. Rev. 46(1):67–69.Google Scholar
• Psychas K, Ghaderi J (2019) Scheduling jobs with random resource requirements in computing clusters. Rawat D, Tang J, eds. Proc. IEEE Internat. Conf. Comput. Comm. (INFOCOM) (IEEE Computer Society, Los Alamitos, CA), 2269–2277.Google Scholar
• Rumyantsev A, Morozov E (2017) Stability criterion of a multiserver model with simultaneous service. Ann. Oper. Res. 252(1):29–39.Google Scholar
• Stolyar AL, Zhong Y (2021) A service system with packing constraints: Greedy randomized algorithm achieving sublinear in scale optimality gap. Stochastic Systems 11(2):83–111.Link, Google Scholar
• Tikhonenko OM (2005) Generalized Erlang problem for service systems with finite total capacity. Problems Inform. Transmission 41(3):243–253.Google Scholar
• Tirmazi M, Barker A, Deng N, Haque ME, Qin ZG, Hand S, Harchol-Balter M, Wilkes J (2020) Borg: The next generation. Bilas A, Magoutis K, Markatos EP, Kostic D, Seltzer MI, eds. Proc. Eur. Conf. Comput. Systems (EuroSys) (ACM, New York), 30:1–30:14.Google Scholar
• van der Boor M, Zubeldia M, Borst S (2020) Zero-wait load balancing with sparse messaging. Oper. Res. Lett. 48(3):368–375.Google Scholar
• van Dijk NM (1989) Blocking of finite source inputs which require simultaneous servers with general think and holding times. Oper. Res. Lett. 8(1):45–52.Google Scholar
• Verma A, Pedrosa L, Korupolu M, Oppenheimer D, Tune E, Wilkes J (2015) Large-scale cluster management at Google with Borg. Réveillère L, Harris T, Herlihy M, eds. Proc. Eur. Conf. Comput. Systems (EuroSys) (ACM, New York), 18:1–18:17.Google Scholar
• Wang W, Xie Q, Harchol-Balter M (2021) Zero queueing for multi-server jobs. Proc. ACM Measurement Anal. Comput. Systems 5(1):7.Google Scholar
• Wang W, Maguluri ST, Srikant R, Ying L (2018) Heavy-traffic delay insensitivity in connection-level models of data transfer with proportionally fair bandwidth sharing. ACM SIGMETRICS Perform. Eval. Rev. 45(3):232–245.Google Scholar
• Weng W, Wang W (2020) Achieving zero asymptotic queueing delay for parallel jobs. Proc. ACM Measurement Anal. Comput. Systems 4(3):42.Google Scholar
• Weng W, Zhou X, Srikant R (2020) Optimal load balancing with locality constraints. Proc. ACM Measurement Anal. Comput. Systems 4(3):45.Google Scholar
• Whitt W (1985) Blocking when service is required from several facilities simultaneously. ATT Tech. J. 64(8):1807–1856.Google Scholar
• Xie Q, Dong X, Lu Y, Srikant R (2015) Power of d choices for large-scale bin packing: A loss model. ACM SIGMETRICS Performance Evaluation Rev. 43(1):321–334.Google Scholar
• Zubeldia M (2020) Delay-optimal policies in partial fork-join systems with redundancy and random slowdowns. Proc. ACM Measurement Anal. Comput. Systems 48(1):39–40.Google Scholar
• Zychlinski N, Chan CW, Dong J (2023) Managing queues with different resource requirements. Oper. Res. 71(4):1387–1413.Link, Google Scholar