Heavy Traffic Queue Length Behavior in a Switch Under the MaxWeight Algorithm

References

• L. Tassiulas and A. Ephremides, “Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks,” IEEE Transactions on Automatic Control, vol. 37, no. 12, pp. 1936–1948, 1992. MR1200609Google Scholar
• N. McKeown, V. Anantharam, and J. Walrand, “Achieving 100% throughput in an input queued switch,” in Proceedings of IEEE INFOCOM, 1996, pp. 296–302.Google Scholar
• A. L. Stolyar, “Maxweight scheduling in a generalized switch: State space collapse and workload minimization in heavy traffic,” Annals of Applied Probability, pp. 1–53, 2004. MR2023015Google Scholar
• M. Andrews, K. Jung, and A. Stolyar, “Stability of the max-weight routing and scheduling protocol in dynamic networks and at critical loads,” in Proceedings of the Thirty-ninth Annual ACM Symposium on Theory of Computing, ser. STOC ’07, 2007, pp. 145–154. MR2402438Google Scholar
• D. Shah and D. Wischik, “Switched networks with maximum weight policies: Fluid approximation and multiplicative state space collapse,” The Annals of Applied Probability, vol. 22, no. 1, pp. 70–127, 2012. MR2932543Google Scholar
• W. N. Kang and R. J. Williams, “Diffusion approximation for an input-queued packet switch operating under a maximum weight algorithm,” Stochastic Systems, 2012.Google Scholar
• A. Eryilmaz and R. Srikant, “Asymptotically tight steady-state queue length bounds implied by drift conditions,” Queueing Systems, vol. 72, no. 3–4, pp. 311–359, 2012. MR2989493Google Scholar
• J. M. Harrison and R. J. Williams, “Brownian models of open queueing networks with homogeneous customer populations,” Stochastics, vol. 22, no. 2, pp. 77–115, 1987. MR0912049Google Scholar
• W. N. Kang, F. P. Kelly, N. H. Lee, and R. J. Williams, “State space collapse and diffusion approximation for a network operating under a fair bandwidth sharing policy,” The Annals of Applied Probability, pp. 1719–1780, 2009. MR2569806Google Scholar
• T. Ji, E. Athanasopoulou, and R. Srikant, “On optimal scheduling algorithms for small generalized switches,” IEEE/ACM Transactions on Networking, vol. 18, no. 5, pp. 1585–1598, 2010.Google Scholar
• D. Shah, J. Tsitsiklis, and Y. Zhong, “Optimal scaling of average queue sizes in an input-queued switch: an open problem,” Queueing Systems, vol. 68, no. 3–4, pp. 375–384, 2011. MR2834209Google Scholar
• M. J. Neely, E. Modiano, and Y.-S. Cheng, “Logarithmic delay for n × n packet switches under the crossbar constraint,” IEEE/ACM Transactions on Networking, vol. 15, no. 3, pp. 657–668, 2007.Google Scholar
• D. Shah, N. S. Walton, and Y. Zhong, “Optimal queue-size scaling in switched networks,” Ann. Appl. Probab., vol. 24, no. 6, pp. 2207–2245, 12 2014. MR3262502Google Scholar
• D. Shah, J. N. Tsitsiklis, and Y. Zhong, “On queue-size scaling for input-queued switches,” 2014, arxiv. MR3161642Google Scholar
• R. Srikant and L. Ying, Communication Networks: An Optimization, Control and Stochastic Networks Perspective. Cambridge University Press, 2014. MR3202391Google Scholar
• M. A. Readdy, “Polytopes,” Lecture Notes, http://www.ms.uky.edu/~readdy/Papers/readdy_WAM_lectures.pdf.Google Scholar
• G. Ziegler, Lectures on Polytopes, ser. Graduate Texts in Mathematics. Springer New York, 1995. MR1311028Google Scholar
• J. Dattorro, Convex Optimization & Euclidean Distance Geometry. Meboo Publishing, 2005.Google Scholar
• B. Hajek, “Hitting-time and occupation-time bounds implied by drift analysis with applications,” Advances in Applied Probability, pp. 502–525, 1982. MR0665291Google Scholar
• D. Bertsimas, D. Gamarnik, and J. N. Tsitsiklis, “Performance of multiclass Markovian queueing networks via piecewise linear Lyapunov functions,” Ann. Appl. Probab., vol. 11, no. 4, pp. 1384–1428, 11 2001. MR1878302Google Scholar
• R. Wu, Course project, ECE 567 Communication Network Analysis, Fall 2012, University of Illinois at Urbana Champaign.Google Scholar
• R. Singh and A. Stolyar, “Maxweight scheduling: Asymptotic behavior of unscaled queue-differentials in heavy traffic,” arXiv preprint arXiv:1502.03793, 2015.Google Scholar
• A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency, ser. Algorithms and Combinatorics. Springer, 2003, v. 24.Google Scholar
• A. Eryilmaz, R. Srikant, and J. R. Perkins, “Stable scheduling policies for fading wireless channels,” IEEE/ACM Trans. Network., vol. 13, no. 2, pp. 411–424, 2005.Google Scholar
• L. Comtet, Advanced Combinatorics: The Art of Finite and Infinite Expansions. Springer Netherlands, 1974. MR0460128Google Scholar