Fluctuation Bounds for the Max-Weight Policy with Applications to State Space Collapse

References

• Andrews M, Kumaran K, Ramanan K, Stolyar A, Vijayakumar R, Whiting P (2004) Scheduling in a queuing system with asynchronously varying service rates. Probab. Engrg. Inform. Sci. 18(2):191–217.Google Scholar
• Bramson M (1998) State space collapse with application to heavy traffic limits for multiclass queueing networks. Queueing Systems 30(1–2):89–140.Google Scholar
• Dai J, Lin W (2008) Asymptotic optimality of maximum pressure policies in stochastic processing networks. Ann. Appl. Probab. 18(6):2239–2299.Google Scholar
• Dai JG, Lin W (2005) Maximum pressure policies in stochastic processing networks. Oper. Res. 53(2):197–218.Link, Google Scholar
• Dai JG, Prabhakar B (2000) The throughput of data switches with and without speedup. Proc. INFOCOM 2000, vol. 2 (IEEE, Piscataway, NJ), 556–564.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
• Eryilmaz A, Srikant R, Perkins JR (2005) Stable scheduling policies for fading wireless channels. IEEE/ACM Trans. Networking 13(2):411–424.Google Scholar
• Georgiadis L, Neely MJ, Tassiulas L (2006) Resource Allocation and Cross-Layer Control in Wireless Networks (Now Publishers, Hanover, MA).Google Scholar
• Hoeffding W (1963) Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. 58(301):13–30.Google Scholar
• Ji T, Athanasopoulou E, Srikant R (2009) Optimal scheduling policies in small generalized switches. Proc. INFOCOM 2009 (IEEE, Piscataway, NJ), 2921–2925.Google Scholar
• Kang W, Williams R (2012) Diffusion approximation for an input-queued switch operating under a maximum weight matching policy. Stochastic Systems 2(2):277–321.Link, 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. Probab. 19(5):1719–1780.Google Scholar
• Lin X, Shroff NB, Srikant R (2006) A tutorial on cross-layer optimization in wireless networks. IEEE J. Selected Areas Comm. 24(8):1452–1463.Google Scholar
• Maguluri ST, Srikant R (2015) Heavy-traffic behavior of the maxweight algorithm in a switch with uniform traffic. Performance Evaluation Rev. 43(2):72–74.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, Burle SK, Srikant R (2016) Optimal heavy-traffic queue length scaling in an incompletely saturated switch. ACM SIGMETRICS 44(1):13–24.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
• Mannor S, Tsitsiklis JN (2005) On the empirical state-action frequencies in Markov decision processes under general policies. Math. Oper. Res. 30(3):545–561.Link, Google Scholar
• Markakis MG, Modiano E, Tsitsiklis JN (2016) Delay stability of back-pressure policies in the presence of heavy-tailed traffic. IEEE/ACM Trans. Networking 24(4):2046–2059.Google Scholar
• Markakis MG, Modiano E, Tsitsiklis JN (2018) Delay analysis of the max-weight policy under heavy-tailed traffic via fluid approximations. Math. Oper. Res. 43(2):460–493.Google Scholar
• Neely MJ (2010) Stochastic Network Optimization with Application to Communication and Queueing Systems, Synthesis Lectures on Communication Networks, vol. 3 (Morgan & Claypool Publishers, Williston, VT).Google Scholar
• Reiman MI (1984) Some diffusion approximations with state space collapse. Baccelli F, Fayolle G, eds. Modelling and Performance Evaluation Methodology (Springer, Berlin, Heidelberg), 207–240.Google Scholar
• Rockafellar R (1970) On the maximal monotonicity of subdifferential mappings. Pacific J. Math. 33(1):209–216.Google Scholar
• Shah D, Wischik D (2006) Optimal scheduling algorithms for input-queued switches. Proc. INFOCOM 2006 (IEEE, Piscataway, NJ), 1–11.Google Scholar
• Shah D, Wischik D (2012) Switched networks with maximum weight policies: Fluid approximation and multiplicative state space collapse. Ann. Appl. Probab. 22(1):70–127.Google Scholar
• Shah D, Tsitsiklis JN, Zhong Y (2010) Qualitative properties of α-weighted scheduling policies. Performance Evaluation Rev. 38(1):239–250.Google Scholar
• Shah D, Tsitsiklis JN, Zhong Y (2016) On queue-size scaling for input-queued switches. Stochastic Systems 6(1):1–25.Link, Google Scholar
• Shakkottai S, Srikant R, Stolyar AL (2004) Pathwise optimality of the exponential scheduling rule for wireless channels. Adv. Appl. Probab. 34(6):1021–1045.Google Scholar
• Sharifnassab A, Tsitsiklis JN, Golestani J (2020) Sensitivity to cumulative perturbations for a class of piecewise constant hybrid systems. IEEE Trans. Automatic Control. Forthcoming.Google Scholar
• Stewart DE (2011) Dynamics with Inequalities: Impacts and Hard Constraints (SIAM, Philadelphia).Google Scholar
• Stolyar AL (2004) Maxweight scheduling in a generalized switch: State space collapse and workload minimization in heavy traffic. Ann. Appl. Probab. 14(1):1–53.Google Scholar
• Stolyar AL (2005) Maximizing queueing network utility subject to stability: Greedy primal-dual algorithm. Queueing Systems 50(4):401–457.Google Scholar
• Subramanian VG (2010) Large deviations of max-weight scheduling policies on convex rate regions. Math. Oper. Res. 35(4):881–910.Link, 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. Automatic Control 37(12):1936–1948.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. Performance Evaluation Rev. 45(2):232–245.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.Google Scholar
• Xie Q, Lu Y (2015) Priority algorithm for near-data scheduling: Throughput and heavy-traffic optimality. Proc. INFOCOM 2015 (IEEE, Piscataway, NJ), 963–972.Google Scholar