Transform Methods for Heavy-Traffic Analysis

References

• Bertsimas D, Gamarnik D, Tsitsiklis JN (2001) Performance of multiclass markovian queueing networks via piecewise linear Lyapunov functions. Ann. Appl. Probability 11(4):1384–1428.Google Scholar
• Braverman A (2020) Steady-state analysis of the join-the-shortest-queue model in the Halfin–Whitt regime. Math. Oper. Res. 45(3):1069–1103.Google Scholar
• Braverman A, Dai J (2017) Stein’s method for steady-state diffusion approximations of M/Ph/n+ M systems. Ann. Appl. Probability 27(1):550–581.Google Scholar
• Braverman A, Dai J, Feng J (2017a) Stein’s method for steady-state diffusion approximations: An introduction through the Erlang-A and Erlang-C models. Stochastic Systems 6(2):301–366.Link, Google Scholar
• Braverman A, Dai J, Miyazawa M (2017b) Heavy traffic approximation for the stationary distribution of a generalized Jackson network: The BAR approach. Stochastic Systems 7(1):143–196.Link, Google Scholar
• Braverman A, Gurvich I, Huang J (2020) On the Taylor expansion of value functions. Oper. Res. 68(2):631–654.Google Scholar
• Chen H, Ye H (2012) Asymptotic optimality of balanced routing. Oper. Res. 60(1):163–179.Link, Google Scholar
• Dai J (2018) Steady-state approximations: Achievement lecture. ACM SIGMETRICS Performance Evaluation Rev. 46(1):1.Google Scholar
• Dai J, Lin W (2008) Asymptotic optimality of maximum pressure policies in stochastic processing networks. Ann. Appl. Probability 18(6):2239–2299.Google Scholar
• Ephremides A, Varaiya P, Walrand J (1980) A simple dynamic routing problem. IEEE Trans. Automatic Control 25(4):690–693.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
• Eschenfeldt P, Gamarnik D (2018) Join the shortest queue with many servers. The heavy-traffic asymptotics. Math. Oper. Res. 43(3):867–886.Google Scholar
• Foschini G, Salz J (1978) A basic dynamic routing problem and diffusion. IEEE Trans. Communications 26(3):320–327.Google Scholar
• Gamarnik D, Zeevi A (2006) Validity of heavy traffic steady-state approximations in Generalized Jackson Networks. Ann. Appl. Probability 16(1):56–90.Google Scholar
• Gaunt R, Walton N (2020) Stein’s method for the single server queue in heavy traffic. Statist. Probability Lett. 156:108566.Google Scholar
• Gupta G, Shroff N (2010) Delay analysis for wireless networks with single hop traffic and general interference constraints. IEEE/ACM Trans. Networks 18(2):393–405.Google Scholar
• Gurvich I (2014) Diffusion models and steady-state approximations for exponentially ergodic Markovian queues. Ann. Appl. Probability 24(6):2527–2559.Google Scholar
• Gurvich I, Huang J, Mandelbaum A (2013) Excursion-based universal approximations for the Erlang-A queue in steady-state. Math. Oper. Res. 39(2):325–373.Link, Google Scholar
• Gut A (2012) Probability: A Graduate Course, vol. 75 (Springer Science & Business Media, New York).Google Scholar
• Hajek B (1982) Hitting-time and occupation-time bounds implied by drift analysis with applications. Adv. Appl. Probability 14(3):502–525.Google Scholar
• Hajek B (2015) Random Processes for Engineers (Cambridge University Press, Cambridge, UK).Google Scholar
• Harrison J (1988) Brownian models of queueing networks with heterogeneous customer populations Fleming W, Lions PL, eds. Stochastic Differential Systems, Stochastic Control Theory and Applications (Springer, New York), 147–186.Google Scholar
• Harrison J (1998) Heavy traffic analysis of a system with parallel servers: Asymptotic optimality of discrete review policies. Ann. Appl. Probability 8(3):822–848.Google Scholar
• Harrison J, López M (1999) Heavy traffic resource pooling in parallel-server systems. Queueing Syst. 33(4):339–368.Google Scholar
• Harrison P, Patel N (1992) Performance Modeling of Communication Networks and Computer Architectures (Addison Wesley Longman, Upper Saddle River, NJ).Google Scholar
• Huang J, Gurvich I (2018) Beyond heavy-traffic regimes: Universal bounds and controls for the single-server queue. Oper. Res. 66(4):1168–1188.Link, Google Scholar
• Hurtado-Lange D, Maguluri ST (2019) Heavy-traffic analysis of queueing systems with no complete resource pooling. ACM SIGMETRICS Performance Evaluation Rev. 46(2):81–82.Google Scholar
• Kang W, Kelly F, Lee N, Williams R (2009) State space collapse and diffusion approximation for a network operating under a fair bandwidth sharing policy. Ann. Appl. Probability 19(5):1719–1780.Google Scholar
• Kingman J (1961) The single server queue in heavy traffic. Math. Proc. Cambridge Philosophy Soc. 57(4):902–904.Google Scholar
• Kingman J (1962a) On queues in heavy traffic. J. Roy. Statist. Soc. B 24(2):383–392.Google Scholar
• Kingman J (1962b) Some inequalities for the queue GI/G/1. Biometrika 49(3):315–324.Google Scholar
• Köllerström J (1974) Heavy traffic theory for queues with several servers. i. J. Appl. Probability 11(3):544–552.Google Scholar
• Lehoczky J (1996) Real-time queueing theory. 17th IEEE Real-Time Systems Symposium (Institute of Electrical and Electronics Engineers, Washington, DC), 186–195.Google Scholar
• Lehoczky J (1997) Using real-time queueing theory to control lateness in real-time systems. Performance Evaluation Rev. 25(1):158–168.Google Scholar
• Li B, Kong X, Wang L (2018) Optimal load-balancing for high-density wireless networks with flow-level dynamics. Proc. 18th ACM Internat. Sympos. Mobile Ad Hoc Networking Comput. (ACM, New York), 316–317.Google Scholar
• Lindley D (1952) The theory of queues with a single server. Math. Proc. Cambridge Philosophical Soc. 48(2):277–289.Google Scholar
• Liu X, Ying L (2019) A simple steady-state analysis of load balancing algorithms in the sub-Halfin-Whitt regime. Performance Evaluation Rev. 46(2):15–17.Google Scholar
• Lu Y, Xie Q, Kliot G, Geller A, Larus J, Greenberg A (2011) Join-idle-queue: A novel load balancing algorithm for dynamically scalable web services. Performance Evaluation 68(11):1056–1071.Google Scholar
• Lukacs E (1970) Characteristic Functions (Griffin, London).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.Google Scholar
• Maguluri ST, Burle S, Srikant R (2018) Optimal heavy-traffic queue length scaling in an incompletely saturated switch. Queueing Systems 88(3–4):279–309.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
• Marshall K (1968) Some inequalities in queuing. Oper. Res. 16(3):651–668.Link, Google Scholar
• Massoulié L, Roberts J (2000) Bandwidth sharing and admission control for elastic traffic. Telecomm. Systems 15(1–2):185–201.Google Scholar
• McKeown N, Anantharam V, Walrand J (1996) Achieving 100% throughput in an input queued switch. Proc. IEEE INFOCOM 47(8):296–302.Google Scholar
• Meyn S (2008) Stability and asymptotic optimality of generalized MaxWeight policies. SIAM J. Control Optim. 47(6):3259–3294.Google Scholar
• Mitzenmacher M (1996) Load Balancing and Density Dependent Jump Markov Processes (IEEE, Piscataway, NJ).Google Scholar
• Mitzenmacher M (2001) The power of two choices in randomized load balancing. IEEE Trans. Parallel Distribution Systems 12(10):1094–1104.Google Scholar
• Mood A (1950) Introduction to the Theory of Statistics (McGraw-Hill, New York).Google Scholar
• Skorokhod A (1961) Stochastic equations for diffusion processes in a bounded region. Theory Probability Appl. 6(3):264–274.Google Scholar
• Srikant R, Ying L (2014) Communication Networks: An Optimization, Control and Stochastic Networks Perspective (Cambridge University Press, Cambridge, UK).Google Scholar
• Stolyar A (2004) Maxweight scheduling in a generalized switch: State space collapse and workload minimization in heavy traffic. Ann. Appl. Probability 14(1):1–53.Google Scholar
• Stolyar A (2017) Pull-based load distribution among heterogeneous parallel servers: The case of multiple routers. Queueing Systems 85(1–2):31–65.Google Scholar
• Tassiulas L, Ephremides A (1992) Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. IEEE Trans. Automation Control 37(12):1936–1948.Google Scholar
• van der Boor M, Borst S, van Leeuwaarden J, Mukherjee D (2018) Scalable load balancing in networked systems: A survey of recent advances. Preprint, submitted June 14, https://arxiv.org/abs/1806.05444.Google Scholar
• Vlasiou M, Zhang J, Zwart B (2014) Insensitivity of proportional fairness in critically loaded bandwidth sharing networks. Preprint, submitted June 18, https://arxiv.org/abs/1411.4841.Google Scholar
• Vvedenskaya N, Dobrushin R, Karpelevich F (1996) Queueing system with selection of the shortest of two queues: An asymptotic approach. Problems Inform. Transmission 32(1):15–27.Google Scholar
• Wang CH, Maguluri ST, Javidi T (2017) Heavy traffic queue length behavior in switches with reconfiguration delay. INFOCOM 2017: IEEE Conf. Computer Commun. (IEEE, New York), 1–9.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. SIGMETRICS Performance Evaluation Rev. 45(3):232–245.Google Scholar
• Weber R (1978) On the optimal assignment of customers to parallel servers. J. Appl. Probability 15(2):406–413.Google Scholar
• Williams R (1998) Diffusion approximations for open multiclass queueing networks: Sufficient conditions involving state space collapse. Queueing Systems 30:27–88.Google Scholar
• Williams R (2000) On dynamic scheduling of a parallel server system with complete resource pooling. Fields Institute Commun. 28(5.1):49–71.Google Scholar
• Winston W (1977) Optimality of the shortest line discipline. J. Appl. Probability 14(1):181–189.Google Scholar
• Ye HQ, Yao D (2012) A stochastic network under proportional fair resource control—diffusion limit with multiple bottlenecks. Oper. Res. 60(3):716–738.Link, Google Scholar
• Ying L (2016) On the approximation error of mean-field models. Proc. 2016 ACM SIGMETRICS Internat. Conf. Measurement Model. Comput. Sci. (ACM, New York), 285–297.Google Scholar
• Ying L (2017) Stein’s method for mean field approximations in light and heavy traffic regimes. Proc. ACM Measurement Analysis Comput. Syst. 1(1):12:1–12:27.Google Scholar
• Ying L, Srikant R, Kang X (2017) The power of slightly more than one sample in randomized load balancing. Math. Oper. Res. 42(3):692–722.Link, Google Scholar
• Zhou X, Tan J, Shroff N (2018) Flexible load balancing with multi-dimensional state-space collapse: Throughput and heavy-traffic delay optimality. Performance Evaluation 127:176–193.Google Scholar