On Queue-size Scaling for Input-Queued Switches

References

• G. Birkhoff. Tres observaciones sobre el algebra lineal. Univ. Nac. Tucumán. Revista A. 5, 147–151 (1946) MR0020547Google Scholar
• F. Chung. Complex graphs and networks. American Mathematical Society (2006) MR2248695Google Scholar
• J. G. Dai and B. Prabhakar. The throughput of switches with and without speed-up. Proceedings of IEEE Infocom, pp. 556–564 (2000)Google Scholar
• M. Jr. Hall. Combinatorial theory. Wiley-Interscience, 2nd edition (1998)Google Scholar
• J. M. Harrison. Brownian models of open processing networks: canonical representation of workload. The Annals of Applied Probability 10, 75–103 (2000). URL http://projecteuclid.org/euclid.aoap/1019737665. Also see [6] MR1765204Google Scholar
• J. M. Harrison. Correction to [5]. The Annals of Applied Probability 13, 390–393 (2003) MR1952004Google Scholar
• F. P. Kelly and R. J. Williams. Fluid model for a network operating under a fair bandwidth-sharing policy. The Annals of Applied Probability 14, 1055–1083 (2004) MR2071416Google Scholar
• I. Keslassy and N. McKeown. Analysis of scheduling algorithms that provide 100% throughput in input-queued switches. Proceedings of Allerton Conference on Communication, Control and Computing (2001)Google Scholar
• E. Leonardi, M. Mellia, F. Neri and M. A. Marsan. Bounds on average delays and queue size averages and variances in input queued cell-based switches. Proceedings of IEEE Infocom, pp. 1095–1103 (2001)Google Scholar
• W. Lin and J. G. Dai. Maximum pressure policies in stochastic processing networks. Operations Research, 53, 197–218 (2005) MR2131925Google Scholar
• S. T. Maguluri and R. Srikant. Heavy-traffic behavior of the MaxWeight algorithm in a switch with uniform traffic. Preprint available at http://arxiv.org/pdf/1503.05872v1.pdf, April 2015.Google Scholar
• N. McKeown, V. Anantharam and J. Walrand. Achieving 100% throughput in an input-queued switch. Proceedings of IEEE Infocom, pp. 296–302 (1996)Google Scholar
• M. Neely, E. Modiano and Y. S. Cheng. Logarithmic delay for n × n packet switches under the cross-bar constraint. IEEE/ACM Transactions on Networking 15(3) (2007)Google Scholar
• D. Shah and M. Kopikare. Delay bounds for the approximate Maximum Weight matching algorithm for input queued switches. Proceedings of IEEE Infocom (2002)Google Scholar
• D. Shah, J. N. Tsitsiklis and Y. Zhong. Optimal scaling of average queue sizes in an input-queued switch: an open problem. Queueing Systems 68(3-4), 375–384 (2011) MR2834209Google Scholar
• D. Shah, N. Walton and Y. Zhong. Optimal queue-size scaling in switched networks. Accepted to appear in the Annals of Applied Probability (2014) MR3262502Google Scholar
• R. Srikant and L. Ying. Communication networks: An optimization, control and stochastic networks perspective. Cambridge University Press (2014) MR3202391Google Scholar
• 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 37, 1936–1948 (1992) MR1200609Google Scholar
• G. de Veciana, T. Lee and T. Konstantopoulos. Stability and performance analysis of networks supporting elastic services. IEEE/ACM Transactions on Networking 9(1), 2–14 (2001)Google Scholar