research-article

Efficient Randomized Algorithms for Input-Queued Switch Scheduling

Authors:

Devavrat Shah,

Paolo Giaccone,

Balaji PrabhakarAuthors Info & Claims

IEEE Micro, Volume 22, Issue 1

Pages 10 - 18

https://doi.org/10.1109/40.988685

Published: 01 January 2002 Publication History

Publisher Site

Abstract

High-performance schedulers for input-queued (IQ) switches must find, for each time slot, a good matching between inputs and outputs to transfer packets. At high line rates or for large switches, finding good matchings is complicated. A suite of randomized algorithms for switch scheduling provides performance comparable to that of well-known, effective matching algorithms, yet is simple to implement.

References

[1]

M. Mitzenmacher, The Power of Two Choices in Randomized Load Balancing, doctoral dissertation, Dept. of EECS, Univ. of California, Berkeley, 1996.

Digital Library

Google Scholar

[2]

N. Vvedenskaya R. Dobrushin and F. Karpelevich, "Queueing System with Selection of the Shortest of Two Queues: An Asymptotic Approach," Problems of Information Transmission, Kluwer Academic Publishers, Dordrecht, The Netherlands, vol. 32, 1996, pp. 15-37.

Google Scholar

[3]

K. Psounis and B. Prabhakar, "A Randomized Web-Cache Replacement Scheme," IEEE Infocom 2001, IEEE Press, Piscataway, N.J., 2001.

Google Scholar

[4]

R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge Univ. Press, Cambridge, UK, 1995.

Digital Library

Google Scholar

[5]

N. McKeown V. Anantharan and J. Walrand, "Achieving 100% Throughput in an Input-Queued Switch," Proc. 15th Ann. Joint Conf. of the IEEE Computer and Comm. Societies (Infocom 96), IEEE CS Press, Los Alamitos, Calif., 1996, pp. 296-302.

Digital Library

Google Scholar

[6]

J. Dai and B. Prabhakar, "The Throughput of Data Switches with and without Speedup," IEEE Infocom 2000, IEEE Press, Piscataway, N.J., 2000, pp. 556-564.

Google Scholar

[7]

N. McKeown, "iSLIP: A Scheduling Algorithm for Input-Queued Switches," IEEE Trans. Networking, vol. 7, no. 2, Apr. 1999, pp. 188-201.

Digital Library

Google Scholar

[8]

N. McKeown, Scheduling Algorithms for Input-Queued Cell Switches, doctoral dissertation, Dept. of EECS, Univ. of California, Berkeley, 1995.

Digital Library

Google Scholar

[9]

M.M. Ajmone, et al., "RPA: A Flexible Scheduling Algorithm for Input Buffered Switches," IEEE Trans. Communications, vol. 47, no. 12, Dec. 1999, pp. 1921-1933.

Crossref

Google Scholar

[10]

H. Duan, et al., "A High Performance OC12/OC48 Queue Design Prototype for Input Buffered ATM Switches," INFOCOM 97: 16th Ann. Joint Conf. of the IEEE Computer and Comm. Societies (Infocom 97), IEEE CS Press, Los Alamitos, Calif., 1997, pp. 20-28.

Digital Library

Google Scholar

[11]

L. Tassiulas, "Linear Complexity Algorithms for Maximum Throughput in Radio Networks and Input Queued Switches," 1998 IEEE Infocom, IEEE Press, Piscataway, N.J., 1998, pp. 533-539.

Google Scholar

Cited By

View all

Jhunjhunwala P(2024)Design and Analysis of Stochastic Processing and Matching NetworksACM SIGMETRICS Performance Evaluation Review10.1145/3639830.363984551:3(33-37)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3639830.3639845
Agarwal RRajakrishnan SShmoys DMilani AWoelfel P(2022)From Switch Scheduling to Datacenter SchedulingProceedings of the 2022 ACM Symposium on Principles of Distributed Computing10.1145/3519270.3538443(313-323)Online publication date: 20-Jul-2022
https://dl.acm.org/doi/10.1145/3519270.3538443
Gong LTune PLiu LYang SXu J(2017)Queue-Proportional SamplingACM SIGMETRICS Performance Evaluation Review10.1145/3143314.307850945:1(4-4)Online publication date: 5-Jun-2017
https://dl.acm.org/doi/10.1145/3143314.3078509
Show More Cited By

Index Terms

Efficient Randomized Algorithms for Input-Queued Switch Scheduling
1. Computing methodologies
  1. Artificial intelligence
    1. Planning and scheduling
2. Theory of computation

Recommendations

Frame-based packet scheduling algorithms for input queued switches
FPCF Input-Queued Packet Switch for Variable-Size Packets
ICN '01: Proceedings of the First International Conference on Networking-Part 2

The existing forward planning conflict-free (FPCF) packet switches are designed for fixed-size packets and synchronous operation mode. In this paper an asynchronous FPCF packet switch for variable-size packets is proposed. The key problem of efficient ...
Efficient buffering and scheduling for a single-chip crosspoint-queued switch
ANCS '12: Proceedings of the eighth ACM/IEEE symposium on Architectures for networking and communications systems

The single-chip crosspoint-queued (CQ) switch is a self-sufficient switching architecture enabled by state-of-art ASIC technology. Unlike the legacy input-queued or output-queued switches, this kind of switch has all its buffers placed at the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

IEEE Micro Volume 22, Issue 1

January 2002

83 pages

ISSN:0272-1732

Issue’s Table of Contents

Publisher

IEEE Computer Society Press

Washington, DC, United States

Publication History

Published: 01 January 2002

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Jhunjhunwala P(2024)Design and Analysis of Stochastic Processing and Matching NetworksACM SIGMETRICS Performance Evaluation Review10.1145/3639830.363984551:3(33-37)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3639830.3639845
Agarwal RRajakrishnan SShmoys DMilani AWoelfel P(2022)From Switch Scheduling to Datacenter SchedulingProceedings of the 2022 ACM Symposium on Principles of Distributed Computing10.1145/3519270.3538443(313-323)Online publication date: 20-Jul-2022
https://dl.acm.org/doi/10.1145/3519270.3538443
Gong LTune PLiu LYang SXu J(2017)Queue-Proportional SamplingACM SIGMETRICS Performance Evaluation Review10.1145/3143314.307850945:1(4-4)Online publication date: 5-Jun-2017
https://dl.acm.org/doi/10.1145/3143314.3078509
Gong LTune PLiu LYang SXu J(2017)Queue-Proportional SamplingProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/30844401:1(1-33)Online publication date: 13-Jun-2017
https://dl.acm.org/doi/10.1145/3084440
Gong LTune PLiu LYang SXu JHajek BOh SChaintreau AGolubchik LZhang Z(2017)Queue-Proportional SamplingProceedings of the 2017 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems10.1145/3078505.3078509(4-4)Online publication date: 5-Jun-2017
https://dl.acm.org/doi/10.1145/3078505.3078509
Erkan ABarr JClear ACuadros-Vargas ECarter JTupac Y(2016)Algorithms + Organization = SystemsProceedings of the 2016 ACM Conference on Innovation and Technology in Computer Science Education10.1145/2899415.2899458(65-70)Online publication date: 11-Jul-2016
https://dl.acm.org/doi/10.1145/2899415.2899458
Duan RPettie S(2014)Linear-Time Approximation for Maximum Weight MatchingJournal of the ACM10.1145/252998961:1(1-23)Online publication date: 1-Jan-2014
https://dl.acm.org/doi/10.1145/2529989
Rhu MErez M(2013)Maximizing SIMD resource utilization in GPGPUs with SIMD lane permutationACM SIGARCH Computer Architecture News10.1145/2508148.248595341:3(356-367)Online publication date: 23-Jun-2013
https://dl.acm.org/doi/10.1145/2508148.2485953
Rhu MErez MMendelson A(2013)Maximizing SIMD resource utilization in GPGPUs with SIMD lane permutationProceedings of the 40th Annual International Symposium on Computer Architecture10.1145/2485922.2485953(356-367)Online publication date: 23-Jun-2013
https://dl.acm.org/doi/10.1145/2485922.2485953
Beheshti NBurmeister EGanjali YBowers JBlumenthal DMcKeown N(2010)Optical packet buffers for backbone internet routersIEEE/ACM Transactions on Networking10.1109/TNET.2010.204892418:5(1599-1609)Online publication date: 1-Oct-2010
https://dl.acm.org/doi/10.1109/TNET.2010.2048924
Show More Cited By

Abstract

References

Cited By

Index Terms

Recommendations

Frame-based packet scheduling algorithms for input queued switches

FPCF Input-Queued Packet Switch for Variable-Size Packets

Efficient buffering and scheduling for a single-chip crosspoint-queued switch

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations