The DOI matches its Crossref record; 11 of the 11 references it cites were found in a registry or an index.
Matching output queueing with a combined input/output-queued switch
Abstract
The Internet is facing two problems simultaneously: there is a need for a faster switching/routing infrastructure and a need to introduce guaranteed qualities-of-service (QoS). Each problem can be solved independently: switches and routers can be made faster by using input-queued crossbars instead of shared memory systems; QoS can be provided using weighted-fair queueing (WFQ)-based packet scheduling. Until now, however, the two solutions have been mutually exclusive-all of the work on WFQ-based scheduling algorithms has required that switches/routers use output-queueing or centralized shared memory. This paper demonstrates that a combined input/output-queueing (CIOQ) switch running twice as fast as an input-queued switch can provide precise emulation of a broad class of packet-scheduling algorithms, including WFQ and strict priorities. More precisely, we show that for an N/spl times/N switch, a "speedup" of 2-1/N is necessary, and a speedup of two is sufficient for this exact emulation. Perhaps most interestingly, this result holds for all traffic arrival patterns. On its own, the result is primarily a theoretical observation; it shows that it is possible to emulate purely OQ switches with CIOQ switches running at approximately twice the line rate. To make the result more practical, we introduce several scheduling algorithms that with a speedup of two can emulate an OQ switch. We focus our attention on the simplest of these algorithms, critical cells first (CCF), and consider its running time and implementation complexity. We conclude that additional techniques are required to make the scheduling algorithms implementable at a high speed and propose two specific strategies.
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
College Admissions and the Stability of Marriage
Gale, D., & Shapley, L. S. (1962) · The American Mathematical Monthly · doi:10.1080/00029890.1962.11989827 · Cited by 5,985
On the self-similar nature of Ethernet traffic (extended version)
Leland, W. E., Taqqu, M. S., Willinger, W., & Wilson, D. V. (1994) · IEEE/ACM Transactions on Networking · doi:10.1109/90.282603 · Cited by 5,233
Analysis and simulation of a fair queueing algorithm
Demers, A., Keshav, S., & Shenker, S. (1989) · ACM SIGCOMM Computer Communication Review · doi:10.1145/75247.75248 · Cited by 2,614
College Admissions and the Stability of Marriage
Gale, D., & Shapley, L. S. (1962) · American Mathematical Monthly · doi:10.2307/2312726 · Cited by 2,082
Analysis and simulation of a fair queueing algorithm
Demers, A., Keshav, S., & Shenker, S. (1989) · Symposium proceedings on Communications architectures & protocols · doi:10.1145/75246.75248 · Cited by 1,729
On the self-similar nature of Ethernet traffic
Leland, W. E., Taqqu, M. S., Willinger, W., & Wilson, D. V. (1993) · Conference proceedings on Communications architectures, protocols and applications · doi:10.1145/166237.166255 · Cited by 1,077
Achieving 100% throughput in an input-queued switch
McKeown, N., Mekkittikul, A., Anantharam, V., & Walrand, J. (1999) · IEEE Transactions on Communications · doi:10.1109/26.780463 · Cited by 838
Self-citationVirtualClock: a new traffic control algorithm for packet-switched networks
Zhang, L. (1991) · ACM Transactions on Computer Systems · doi:10.1145/103720.103721 · Cited by 509
On the speedup required for combined input- and output-queued switching
Balaji Prabhakar, B., & McKeown, N. (1999) · Automatica · doi:10.1016/s0005-1098(99)00129-6 · Cited by 134
Self-citationExact emulation of an output queueing switch by a combined input output queueing switch
Stoica, I. G., & Zhang, H. (2002) · International Workshop on Quality of Service · doi:10.1109/iwqos.1998.675242 · Cited by 121
Cited by
The iSLIP scheduling algorithm for input-queued switches
McKeown, N. (1999) · IEEE/ACM Transactions on Networking · doi:10.1109/90.769767 · Cited by 1,185
Self-citationAlgorithmics of Matching Under Preferences
Manlove, D. F. (2013) · Series on Theoretical Computer Science · doi:10.1142/8591 · Cited by 515
ProjecToR: Agile Reconfigurable Data Center Interconnect
Ghobadi, M., Mahajan, R., Phanishayee, A., Devanur, N., Kulkarni, J., Ranade, G., Blanche, P.-A., Rastegarfar, H., Glick, M., & Kilper, D. (2016) · Proceedings of the 2016 ACM SIGCOMM Conference · doi:10.1145/2934872.2934911 · Cited by 286
Programmable Packet Scheduling at Line Rate
Sivaraman, A., Subramanian, S., Alizadeh, M., Chole, S., Chuang, S.-T., Agrawal, A., Balakrishnan, H., Edsall, T., Katti, S., & McKeown, N. (2016) · Proceedings of the 2016 ACM SIGCOMM Conference · doi:10.1145/2934872.2934899 · Cited by 276
Self-citationThroughput and Fairness Guarantees Through Maximal Scheduling in Wireless Networks
Chaporkar, P., Kar, K., Luo, X., & Sarkar, S. (2008) · IEEE Transactions on Information Theory · doi:10.1109/tit.2007.913537 · Cited by 253
Metadata
- Authors
- Chuang, S.-T., Goel, A., McKeown, N., & Prabhakar, B.
- Venue
- IEEE Journal on Selected Areas in Communications
- Published
- 1999-06
- Volume
- 17
- Issue
- 6
- Pages
- 1030-1039
- ISSN
- 0733-8716 (ISSN-L)
- OpenAlex
- W2079931475
- Cited by
- 390
- References
- 11
- FWCI
- 25.86
- 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: Matching output queueing with a combined input/output-queued switch. https://app.cochat.ai/papers/10.1109/49.772430
- The paper
- Chuang, S.-T., Goel, A., McKeown, N., & Prabhakar, B. (1999). Matching output queueing with a combined input/output-queued switch. IEEE Journal on Selected Areas in Communications. https://doi.org/10.1109/49.772430
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.