Abstract
We review some known results and state a few versions of an open problem related to the scaling of the total queue size (in steady state) in an n×n input-queued switch, as a function of the port number n and the load factor ρ. Loosely speaking, the question is whether the total number of packets in queue, under either the maximum weight policy or under an optimal policy, scales (ignoring any logarithmic factors) as O(n/(1−ρ)).
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Birkhoff, G.: Tres observaciones sobre el algebra lineal. Univ. Nac. Tucumán. Rev, Ser. A 5, 147–151 (1946)
Hajek, B., Sasaki, G.: Link scheduling in polynomial time. IEEE Trans. Inf. Theory 34(5), 910–917 (1988)
Harrison, J. Michael: Brownian models of open processing networks: canonical representation of workload. Ann. Appl. Probab. 10, 75–103 (2000)
McKeown, N., Anantharam, V., Walrand, J.: Achieving 100% throughput in an input-queued switch. In: Proceedings of IEEE Infocom, pp. 296–302 (1996)
Meyn, S.P., Tweedie, R.L.: Markov Chains and Stochastic Stability. Springer, New York (1993)
Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)
Neely, M., Modiano, E., Cheng, Y.-S.: Logarithmic delay for n×n packet switches under the cross-bar constraint. IEEE/ACM Trans. Netw. 15(3) (2007)
Shah, D., Tsitsiklis, J.N.: Bin packing with queues. J. Appl. Probab. 45, 922–939 (2008)
Shah, D., Wischik, D.J.: Optimal scheduling algorithms for input-queued switches. In: Proceedings of IEEE Infocom (2006)
Shah, D., Wischik, D.J.: Switched networks with maximum weight policies: fluid approximation and multiplicative state space collapse. Ann. Appl. Probab. (2011, to appear)
Tassiulas, L., Ephremides, A.: Stability properties of constrained queuing systems and scheduling policies for maximum throughput in multihop radio networks. IEEE Trans. Autom. Control 37, 1936–1948 (1992)
von Neumann, J.: A certain zero-sum two-person game equivalent to the optimal assignment problem. Contrib. Theory Games 2, 5–12 (1953)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Shah, D., Tsitsiklis, J.N. & Zhong, Y. Optimal scaling of average queue sizes in an input-queued switch: an open problem. Queueing Syst 68, 375–384 (2011). https://doi.org/10.1007/s11134-011-9234-1
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11134-011-9234-1