Home | Articles | Past volumes | About | Login | Notify | Contact | Search
 Stochastic Systems > Vol. 6 (2016) open journal systems 

On queue-size scaling for input-queued switches

Devavrat Shah, Massachusetts Institute of Technology
John N. Tsitsiklis, Massachusetts Institute of Technology
Yuan Zhong, Columbia University

We study the optimal scaling of the expected total queue size in an \(n\times n\) input-queued switch, as a function of the number of ports \(n\) and the load factor \(\rho\), which has been conjectured to be \(\Theta(n/(1-\rho))\) (cf. [15]). In a recent work [16], the validity of this conjecture has been established for the regime where \(1-\rho= O(1/n^2)\). In this paper, we make further progress in the direction of this conjecture. We provide a new class of scheduling policies under which the expected total queue size scales as \(O\big(n^{1.5} (1-\rho)^{-1} \log\big(1/(1-\rho)\big)\big)\) when \(1-\rho= O(1/n)\). This is an improvement over the state of the art; for example, for \(\rho= 1-1/n\) the best known bound was \(O(n^3)\), while ours is \(O(n^{2.5} \log n)\).

AMS 2000 subject classifications: Primary 60K20, 68M12; secondary 68M20.

Keywords: Input-queued switches, queue-size scaling.

Creative Common LOGO

Full Text: PDF

Shah, Devavrat, Tsitsiklis, John N., Zhong, Yuan, On queue-size scaling for input-queued switches, Stochastic Systems, 6, (2016), 1-25 (electronic). DOI: 10.1214/14-SSY151.


[1]    G. Birkhoff. Tres observaciones sobre el algebra lineal. Uniu. Nac. Tkcumdn Rev. Ser. A 5, 147–151 (1946) MR0020547

[2]    F. Chung. Complex graphs and networks. American Mathematical Society (2006) MR2248695

[3]    J. G. Dai and B. Prabhakar. The throughput of switches with and without speed-up. Proceedings of IEEE Infocom, pp. 556–564 (2000)

[4]    M. Jr. Hall. Combinatorial theory. Wiley-Interscience, 2nd edition (1998)

[5]    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] MR1765204

[6]    J. M. Harrison. Correction to [5]. The Annals of Applied Probability 13, 390–393 (2003) MR1952004

[7]    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) MR2071416

[8]    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)

[9]    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)

[10]    W. Lin and J. G. Dai. Maximum pressure policies in stochastic processing networks Operations Research, 53, 197–218 (2005) MR2131925

[11]    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.

[12]    N. McKeown, V. Anantharam and J. Walrand. Achieving 100% throughput in an input-queued switch. Proceedings of IEEE Infocom, pp. 296–302 (1996)

[13]    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)

[14]    D. Shah and M. Kopikare. Delay bounds for the approximate Maximum Weight matching algorithm for input queued switches. Proceedings of IEEE Infocom (2002)

[15]    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) MR2834209

[16]    D. Shah, N. Walton and Y. Zhong. Optimal queue-size scaling in switched networks. Accepted to appear in the Annals of Applied Probability (2014) MR3262502

[17]    R. Srikant and L. Ying. Communication networks: An optimization, control and stochastic networks perspective. Cambridge University Press (2014) MR3202391

[18]    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) MR1200609

[19]    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)

Home | Articles | Past volumes | About | Login | Notify | Contact | Search

Stochastic Systems. ISSN: 1946-5238