Optimal Routing to Parallel Servers in Heavy Traffic

References

• Altman E, Gaujal B, Hordijk A (2003) Discrete-Event Control of Stochastic Networks: Multimodularity and Regularity (Springer, Heidelberg, Germany).Crossref, Google Scholar
• Atar R, Mandelbaum A, Reiman MI (2004) Scheduling a multiclass queue with many exponential servers: Asymptotic optimality in heavy traffic. Ann. Appl. Probabilities 14(3):1084–1134.Crossref, Google Scholar
• Badonnel R, Burgess M (2008) Dynamic pull-based load balancing for autonomic servers. Proc. IEEE Network Oper. and Management Sympos. (IEEE, Piscataway, NJ) 751–754.Google Scholar
• Banawan SA, Zeidat NM (1992) A comparative study of load sharing in heterogeneous multicomputer systems. Proc. 25th Annual Simulation Sympos. (IEEE, New York), 22–31.Google Scholar
• Bell SL, Williams RJ (2001) Dynamic scheduling of a system with two parallel servers in heavy traffic with resource pooling: Asymptotic optimality of a threshold policy. Ann. Appl. Probabilities 11(3):608–649.Crossref, Google Scholar
• Borst S, Mandelbaum A, Reiman MI (2004) Dimensioning large call centers. Oper. Res. 52(1):17–34.Link, Google Scholar
• Bramson M (1998a) Stability of two families of queueing networks and a discussion of fluid limits. Queueing Systems 23:7–31.Crossref, Google Scholar
• Bramson M (1998b) State space collapse with application to heavy traffic limits for multiclass queueing networks. Queueing Systems 30:89–148.Crossref, Google Scholar
• Bramson M (2011) Stability of join the shortest queue networks. Ann. Appl. Probabilities 21(4):1568–1625.Crossref, Google Scholar
• Budhiraja A, Lee C (2009) Stationary distribution convergence for generalized Jackson networks in heavy traffic. Math. Oper. Res. 34(1):45–56.Link, Google Scholar
• Chao X, Liu L, Zheng S (2003) Resource allocation in multisite service systems with intersite customer flows. Management Sci. 49(12):1739–1752.Link, Google Scholar
• Chen H (1995) Fluid approximations and stability of multiclass queueing networks: Work-conserving discipline. Ann. Appl. Probabilities 5:637–655.Crossref, Google Scholar
• Chen H, Shanthikumar JG (1994) Fluid limits and diffusion approximations for networks of multi-server queues in heavy traffic. J. Discrete Event Dynamic Systems 4:269–291.Crossref, Google Scholar
• Chen H, Yao DD (2001) Fundamentals of Queueing Networks: Performance, Asymptotics and Optimization (Springer, New York).Crossref, Google Scholar
• Chen H, Ye HQ (2012) Asymptotic optimality of balanced routing. Oper. Res. 60(1):163–179.Link, Google Scholar
• Dai JG (1995) On positive Harris recurrence of multi-class queueing networks: A unified approach via fluid limit models. Ann. Appl. Probabilities 5:49–77.Crossref, Google Scholar
• Dai JG, Lin W (2008) Asymptotic optimality of maximum pressure policies in stochastic processing networks. Ann. Appl. Probabilities 18:2239–2299.Crossref, Google Scholar
• Dai JG, Meyn SP (1995) Stability and convergence of moments for multiclass queueing networks via fluid models. IEEE Trans. Automated Control 40:1899–1904.Crossref, Google Scholar
• Dai JG, Weiss G (1996) Stability and instability of fluid models for reentrant lines. Math. Oper. Res. 21:115–134.Link, Google Scholar
• Davis MHA (1984) Piecewise-deterministic Markov processes: A general class of nondiffusion models. J. Royal Statist. Soc. B 46:353–388.Crossref, Google Scholar
• der Boor MV, Borst SC, Van Leeuwaarden JS, Mukherjee D (2022) Scalable load balancing in networked systems: A survey of recent advances. SIAM Rev. 64(3):554–622.Crossref, Google Scholar
• Eschenfeldt P, Gamarnik D (2018) Join the shortest queue with many servers: The heavy traffic asymptotics. Math. Oper. Res. 43(3):867–886.Link, Google Scholar
• Foss S, Stolyar AL (2017) Large-scale join-idle-queue system with general service times. J. Appl. Probabilities 54(4):995–1007.Crossref, Google Scholar
• Gamarnik D, Zeevi A (2006) Validity of heavy traffic steady-state approximations in Generalized Jackson Networks. Ann. Appl. Probabilities 16:56–96.Crossref, Google Scholar
• Gupta V, Balter MH, Sigman K, Whitt W (2007) Analysis of jointhe-shortest-queue routing for web server farms. Performance Evaluation 64(9–12):1062–1081.Crossref, Google Scholar
• Gurvich I (2014) Validity of heavy traffic steady-state approximations in multiclass queueing networks: The case of queue-ratio disciplines. Math. Oper. Res. 39:121–162.Link, Google Scholar
• Gut A (2005) Probability: A Graduate Course (Springer, New York).Google Scholar
• Hajek B (1985) External splittings of point processes. Math. Oper. Res. 10(4):543–556.Link, 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
• Harrison JM (1996) The BIGSTEP approach to flow management in stochastic processing networks. Kelly FP, Zachary S, Ziedins I, eds. Stochastic Networks: Theory and Applications (Oxford University Press, Oxford, UK), 57–90.Crossref, Google Scholar
• Harrison JM (1998) Heavy traffic analysis of a system with parallel servers: Asymptotic analysis of discrete-review policies. Ann. Appl. Probabilities 8:822–848.Crossref, Google Scholar
• Harrison JM, López MJ (1999) Heavy traffic resource pooling in parallel-server systems. Queueing Systems 33:339–368.Crossref, Google Scholar
• Harrison JM, Wein LM (1990) Scheduling networks of queues: Heavy traffic analysis of a two-station closed network. Oper. Res. 38(6):1052–1064.Link, Google Scholar
• Hurtado-Lange D, Maguluri ST (2020) Transform methods for heavy traffic analysis. Stochastic Systems 10(4):275–309.Link, Google Scholar
• Hyytia E, Aalto S (2016) On round-robin routing with FCFS and LCFS scheduling. Performance Evaluation 97:83–103.Crossref, Google Scholar
• Katsuda T (2010) State-space collapse in stationarity and its application to a multiclass single-server queue in heavy traffic. Queueing Systems 65:237–273.Crossref, Google Scholar
• Kelly FP, Laws CN (1993) Dynamic routing in open queueing networks: Brownian models, cut constraints and resource pooling. Queueing Systems 13:47–86.Crossref, Google Scholar
• Kobayashi M, Sakuma Y, Miyazawa M (2013) Join the shortest queue among k parallel queues: Tail asymptotics of its stationary distribution. Queueing Systems 74(2–3):303–332.Crossref, Google Scholar
• Lee C, Ward AR, Ye HQ (2020) Stationary distribution convergence of the offered waiting processes for GI/GI/1+GI queues in heavy traffic. Queueing Systems 94(1):147–173.Crossref, Google Scholar
• Lee C, Ward AR, Ye HQ (2021) Stationary distribution convergence of the offered waiting processes in heavy traffic under general patience time scaling. Queueing Systems 99(3–4):283–303.Crossref, Google Scholar
• Liu Z, Righter R (1998) Optimal load balancing on distributed homogeneous unreliable processors. Oper. Res. 46(4):563–573.Link, Google Scholar
• Liu Z, Towsley D (1994) Optimality of the round robin routing policy. J. Appl. Probabilities 31(2):466–475.Crossref, Google Scholar
• Mandelbaum A, Stolyar AL (2004) Scheduling flexible servers with convex delay costs: Heavy traffic optimality of the generalized cμ-rule. Oper. Res. 52:836–855.Link, Google Scholar
• Martins LF, Shreve SE, Soner HM (1996) Heavy traffic convergence of a controlled, multiclass queueing system. SIAM J. Control Optim. 34(6):2133–2171.Crossref, Google Scholar
• Mitzenmacher M (2001) The power of two choices in randomized load balancing. IEEE Trans. Parallel Distributed Comput. 12:1094–1104.Crossref, Google Scholar
• Moyal P, Perry O (2022) Stability of parallel server systems. Oper. Res. 70(4):2456–2476.Link, Google Scholar
• Reiman MI (1984) Some diffusion approximations with state space collapse. Baccelli F, Fayolle G, eds. Modelling and Performance Evaluation Methodology (Springer-Verlag), 209–240.Crossref, Google Scholar
• Rybko AN, Stolyar AL (1992) Ergodicity of stochastic processed describing the operations of open queueing networks. Problemy Peredachi Informatsii 28:2–26.Google Scholar
• Selen J, Adan I, Kapodistria S, van Leeuwaarden J (2016) Steady-state analysis of shortest expected delay routing. Queueing Systems 84(3):309–354.Crossref, Google Scholar
• Shiryaev AN (1996) Probability, 2nd ed. (Springer-Verlag, New York).Crossref, Google Scholar
• Stolyar AL (1995) On the stability of multiclass queueing networks: A relaxed sufficient condition via limiting fluid processes. Markov Processes Related Fields 1(4):491–512.Google Scholar
• Stolyar AL (2004) Max-weight scheduling in a generalized switch: State space collapse and workload minimization in heavy traffic. Ann. Appl. Probabilities 14:1–53.Crossref, Google Scholar
• Stolyar AL (2005) Optimal routing in output-queued flexible server systems. Probability Engrg. Inform. Sci. 19(2):141–189.Crossref, Google Scholar
• Stolyar AL (2015) Pull-based load distribution in large-scale heterogeneous service systems. Queueing Systems 80(4):341–361.Crossref, Google Scholar
• Tsoukatos KP, Makowski AM (2006) Asymptotic optimality of the round-robin policy in multipath routing with resequencing. Queueing Systems 52:199–214.Crossref, Google Scholar
• Weber RR (1978) On the optimal assignment of customers to parallel servers. J. Appl. Probabilities 15(2):406–413.Crossref, Google Scholar
• Whitt W (1986) Deciding which queue to join: Some counterexamples. Oper. Res. 34(1):55–62.Link, Google Scholar
• Whitt W (1992) Understanding the efficiency of multi-server service systems. Management Sci. 38:708–723.Link, Google Scholar
• Whitt W (2002) Stochastic-Process Limits: An Introduction to Stochastic-Process Limits and Their Application to Queues (Springer, New York).Crossref, Google Scholar
• Williams RJ (1998) Diffusion approximations for open multiclass queueing networks: Sufficient conditions involving state space collapse. Queueing Systems 30(1–2):27–88.Crossref, Google Scholar
• Williams RJ (2000) On dynamic scheduling of a parallel server system with complete resource pooling. McDonald DR, Turner SRE, eds. Analysis of Communication Networks: Call Centres, Traffic and Performance. Fields Institute Communications, vol. 28 (American Mathematical Society), 49–71.Crossref, Google Scholar
• Winston W (1977) Optimality of the shortest line discipline. J. Appl. Probabilities 14(1):181–189.Crossref, Google Scholar
• Wu R, Down DG (2009) Round robin scheduling of heterogeneous parallel servers in heavy traffic. Eur. J. Oper. Res. 195:372–380.Crossref, Google Scholar
• Ye H, Yao DD (2008) Heavy traffic optimality of a stochastic network under utility-maximizing resource control. Oper. Res. 56(2):453–470.Link, Google Scholar
• Ye HQ, Yao DD (2012) A stochastic network under fair resource control—Diffusion limit with multiple bottlenecks. Oper. Res. 60(3):716–738.Link, Google Scholar
• Ye HQ, Yao DD (2016) Diffusion limit of fair resource control—Stationary and interchange of limits. Math. Oper. Res. 41(4):1161–1207.Link, Google Scholar
• Ye HQ, Yao DD (2018) Justifying diffusion approximations for multiclass queueing networks under a moment condition. Ann. Appl. Probabilities 28(6):3652–3697.Crossref, Google Scholar
• Zhang HQ, Hsu GH, Wang R (1995) Heavy traffic limit theorems for sequence of shortest queueing systems. Queueing Systems 21:217–238.Crossref, Google Scholar