The DOI matches its Crossref record; 13 of the 13 references it cites were found in a registry or an index.
The iSLIP scheduling algorithm for input-queued switches
Abstract
An increasing number of high performance internetworking protocol routers, LAN and asynchronous transfer mode (ATM) switches use a switched backplane based on a crossbar switch. Most often, these systems use input queues to hold packets waiting to traverse the switching fabric. It is well known that if simple first in first out (FIFO) input queues are used to hold packets then, even under benign conditions, head-of-line (HOL) blocking limits the achievable bandwidth to approximately 58.6% of the maximum. HOL blocking can be overcome by the use of virtual output queueing, which is described in this paper. A scheduling algorithm is used to configure the crossbar switch, deciding the order in which packets will be served. Previous results have shown that with a suitable scheduling algorithm, 100% throughput can be achieved. In this paper, we present a scheduling algorithm called iSLIP. An iterative, round-robin algorithm, iSLIP can achieve 100% throughput for uniform traffic, yet is simple to implement in hardware. Iterative and noniterative versions of the algorithms are presented, along with modified versions for prioritized traffic. Simulation results are presented to indicate the performance of iSLIP under benign and bursty traffic conditions. Prototype and commercial implementations of iSLIP exist in systems with aggregate bandwidths ranging from 50 to 500 Gb/s. When the traffic is nonuniform, iSLIP quickly adapts to a fair scheduling policy that is guaranteed never to starve an input queue. Finally, we describe the implementation complexity of iSLIP. Based on a two-dimensional (2-D) array of priority encoders, single-chip schedulers have been built supporting up to 32 ports, and making approximately 100 million scheduling decisions per second.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
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
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
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
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
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
Packet Trains--Measurements and a New Model for Computer Network Traffic
Jain, R. K., & Routhier, S. (1986) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.1986.1146410 · Cited by 549
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-citationScheduling algorithms for input-queued cell switches
McKeown, N. (1996) · Cited by 369
Self-citationMatching output queueing with a combined input output queued switch
Chuang, S.-T., Goel, A., McKeown, N., & Prabhakar, B. (1999) · IEEE INFOCOM '99. Conference on Computer Communications. Proceedings. Eighteenth Annual Joint Conference of the IEEE Computer and Communications Societies. The Future is Now (Cat. No.99CH36320) · doi:10.1109/infcom.1999.751673 · Cited by 196
Self-citationNewman, P., Minshall, G., & Lyon, T. L. (1998) · IEEE/ACM Transactions on Networking · doi:10.1109/90.664261 · Cited by 160
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
Helios: a hybrid electrical/optical switch architecture for modular data centers
Farrington, N., Porter, G., Radhakrishnan, S., Bazzaz, H. H., Subramanya, V., Fainman, Y., Papen, G., & Vahdat, A. (2010) · Proceedings of the ACM SIGCOMM 2010 conference · doi:10.1145/1851182.1851223 · Cited by 918
A detailed and flexible cycle-accurate Network-on-Chip simulator
Jiang, N., Balfour, J., Becker, D. U., Towles, B., Dally, W. J., Michelogiannakis, G., & Kim, J. (2013) · 2013 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS) · doi:10.1109/ispass.2013.6557149 · Cited by 790
c-Through: part-time optics in data centers
Wang, G., Andersen, D. G., Kaminsky, M., Papagiannaki, K., Ng, T. S. E., Kozuch, M., & Ryan, M. (2010) · Proceedings of the ACM SIGCOMM 2010 conference · doi:10.1145/1851182.1851222 · Cited by 653
A Survey on Optical Interconnects for Data Centers
Kachris, C., & Tomkos, I. (2012) · IEEE Communications Surveys & Tutorials · doi:10.1109/surv.2011.122111.00069 · Cited by 594
DeTail: reducing the flow completion time tail in datacenter networks
Zats, D., Das, T., Mohan, P., Borthakur, D., & Katz, R. (2012) · Proceedings of the ACM SIGCOMM 2012 conference on Applications, technologies, architectures, and protocols for computer communication · doi:10.1145/2342356.2342390 · Cited by 383
Metadata
- Authors
- McKeown, N.
- Venue
- IEEE/ACM Transactions on Networking
- Published
- 1999-04
- Volume
- 7
- Issue
- 2
- Pages
- 188-201
- ISSN
- 1063-6692 (ISSN-L)
- OpenAlex
- W2111366547
- Cited by
- 1,185
- References
- 13
- FWCI
- 46.66
- 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
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.