The DOI matches its Crossref record; 9 of the 9 references it cites were found in a registry or an index.
Achieving 100% throughput in an input-queued switch
Abstract
It is well known that head-of-line blocking limits the throughput of an input-queued switch with first-in-first-out (FIFO) queues. Under certain conditions, the throughput can be shown to be limited to approximately 58.6%. It is also known that if non-FIFO queueing policies are used, the throughput can be increased. However, it has not been previously shown that if a suitable queueing policy and scheduling algorithm are used, then it is possible to achieve 100% throughput for all independent arrival processes. In this paper we prove this to be the case using a simple linear programming argument and quadratic Lyapunov function. In particular, we assume that each input maintains a separate FIFO queue for each output and that the switch is scheduled using a maximum weight bipartite matching algorithm. We introduce two maximum weight matching algorithms: longest queue first (LQF) and oldest cell first (OCF). Both algorithms achieve 100% throughput for all independent arrival processes. LQF favors queues with larger occupancy, ensuring that larger queues will eventually be served. However, we find that LQF can lead to the permanent starvation of short queues. OCF overcomes this limitation by favoring cells with large waiting times.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Tassiulas, L., & Ephremides, A. (1992) · IEEE Transactions on Automatic Control · doi:10.1109/9.182479 · Cited by 2,834
An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
Hopcroft, J. E., & Karp, R. M. (1973) · SIAM Journal on Computing · doi:10.1137/0202019 · Cited by 2,802
Data Structures and Network Algorithms
Tarjan, R. E. (1983) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611970265 · Cited by 2,057
High-speed switch scheduling for local-area networks
Anderson, T. E., Owicki, S. S., Saxe, J. B., & Thacker, C. P. (1993) · ACM Transactions on Computer Systems · doi:10.1145/161541.161736 · Cited by 892
Scheduling algorithms for input-queued cell switches
McKeown, N. (1996) · Cited by 369
Self-citationStability of queueing networks and scheduling policies
Kumar, P. R., & Meyn, S. (1995) · IEEE Transactions on Automatic Control · doi:10.1109/9.341782 · Cited by 280
Neural network architecture for crossbar switch control
Troudet, T., & Walters, S. M. (1991) · IEEE Transactions on Circuits and Systems · doi:10.1109/31.101302 · Cited by 78
Neural network design of a banyan network controller
Brown, T. X., & Liu, K.-H. (1990) · IEEE Journal on Selected Areas in Communications · doi:10.1109/49.62821 · Cited by 61
A neural network implementation of an input access scheme in a high-speed packet switch
Ali, M. M., & Nguyen, H. T. (2003) · Globecom · doi:10.1109/glocom.1989.64143 · Cited by 36
Cited by
Stochastic Network Optimization with Application to Communication and Queueing Systems
Neely, M. J. (2010) · Synthesis lectures on communication networks · doi:10.2200/s00271ed1v01y201006cnt007 · Cited by 2,218
A Distributed CSMA Algorithm for Throughput and Utility Maximization in Wireless Networks
Jiang, L., & Walrand, J. (2010) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2009.2035046 · Cited by 635
Self-citationEfficient coflow scheduling with Varys
Chowdhury, M., Zhong, Y., & Stoica, I. (2014) · Proceedings of the 2014 ACM conference on SIGCOMM · doi:10.1145/2619239.2626315 · Cited by 438
Matching output queueing with a combined input/output-queued switch
Chuang, S.-T., Goel, A., McKeown, N., & Prabhakar, B. (1999) · IEEE Journal on Selected Areas in Communications · doi:10.1109/49.772430 · Cited by 390
Self-citationOnline Matching and Ad Allocation
Mehta, A. (2010) · Foundations and Trends® in Theoretical Computer Science · doi:10.1561/0400000057 · Cited by 387
Metadata
- Authors
- McKeown, N., Mekkittikul, A., Anantharam, V., & Walrand, J.
- Venue
- IEEE Transactions on Communications
- Published
- 1999
- Volume
- 47
- Issue
- 8
- Pages
- 1260-1267
- ISSN
- 0090-6778 (ISSN-L)
- OpenAlex
- W2003346154
- Cited by
- 838
- References
- 9
- FWCI
- 49.27
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Achieving 100% throughput in an input-queued switch. https://app.cochat.ai/papers/10.1109/26.780463
- The paper
- McKeown, N., Mekkittikul, A., Anantharam, V., & Walrand, J. (1999). Achieving 100% throughput in an input-queued switch. IEEE Transactions on Communications. https://doi.org/10.1109/26.780463
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.