Article

Free access

Work-conserving distributed schedulers for Terabit routers

Authors:

Prashanth Pappu,

Jonathan Turner,

Ken WongAuthors Info & Claims

SIGCOMM '04: Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications

Pages 257 - 268

https://doi.org/10.1145/1015467.1015496

Published: 30 August 2004 Publication History

PDF eReader

Abstract

Buffered multistage interconnection networks offer one of the most scalable and cost-effective approaches to building high capacity routers. Unfortunately, the performance of such systems has been difficult to predict in the presence of the extreme traffic conditions that can arise in the Internet. Recent work introduced distributed scheduling, to regulate the flow of traffic in such systems. This work demonstrated, using simulation and experimental measurements, that distributed scheduling can deliver robust performance for extreme traffic. Here, we show that distributed schedulers can be provably work-conserving for speedups of 2 or more. Two of the three schedulers we describe were inspired by previously published crossbar schedulers. The third has no direct counterpart in crossbar scheduling. In our analysis, we show that distributed schedulers based on blocking flows in small-depth acyclic flow graphs can be work-conserving, just as certain crossbar schedulers based on maximal bipartite matchings have been shown to be work-conserving. We also study the performance of practical variants of these schedulers when the speedup is less than 2, using simulation.

References

[1]

Ahuja, R., T. Magnanti and J. Orlin. Network Flows, Theory, Applications and Algorithms. Prentice-Hall, 1993.

Digital Library

Google Scholar

[2]

Anderson, T., S. Owicki., J. Saxe and C. Thacker. "High speed switch scheduling for local area networks," ACM Trans. on Computer Systems, 11/93.

Digital Library

Google Scholar

[3]

Bianchi, G. and J. Turner. "Improved Queueing Analysis of Shared Buffer Switching Networks," Proceedings of Infocom, 3/93.

Google Scholar

[4]

Chang, C. S., D.S. Lee and Y.S. Jou, "Load balanced Birkhoff-von Neumann switches, Part I: one-stage buffering". Computer Communications Vol. 25. pp. 611--622, 2002.

Digital Library

Google Scholar

[5]

Chuang, S.-T. A. Goel, N. McKeown, B. Prabhakar "Matching output queueing with a combined input output queued switch," IEEE Journal on Selected Areas in Communications, 12/99.

Digital Library

Google Scholar

[6]

Keslassy, I., S.-T. Chuang, K. Yu, D. Miller, M. Horowitz, O. Solgaard, N. McKeown, "Scaling Internet routers using optics." ACM SIGCOMM, 9/03.

Digital Library

Google Scholar

[7]

Krishna, P., N. Patel, A. Charny and R. Simcoe. "On the speedup required for work-conserving crossbar switches," IEEE J. Selected Areas of Communications, 6/99.

Digital Library

Google Scholar

[8]

McKeown, N., V. Anantharam and J. Walrand. "Achieving 100% throughput in an input-queued switch," Proceedings of Infocom, 1996.

Digital Library

Google Scholar

[9]

McKeown, N., M. Izzard., A. Mekkittikul, W. Ellersick and M. Horowitz. "The Tiny Tera: a packet switch core," Hot Interconnects, 1996.

Google Scholar

[10]

McKeown, Nick. "iSLIP: a scheduling algorithm for input-queued switches," IEEE Transactions on Networking, 4/99.

Digital Library

Google Scholar

[11]

Pappu, P., J. Turner and K. Wong. "Distributed Queueing in Scalable High Performance Routers," Proceedings of Infocom, 4/03.

Google Scholar

[12]

Szymanski, T. and S. Shaikh. "Markov Chain Analysis of Packet-Switched Banyans with Arbitrary Switch Sizes, Queue Sizes, Link multiplicities and Speedups," Proceedings of Infocom, 4/89.

Google Scholar

[13]

Tarjan., Robert. Data Structures and Network Algorithms. Society for Industrial and Applied Mathematics, 1983.

Digital Library

Google Scholar

Cited By

View all

Chrysos NChen LKachris CKatevenis M(2016)Discharging the network from its flow control headachesIEEE/ACM Transactions on Networking10.1109/TNET.2014.237801224:1(15-28)Online publication date: 1-Feb-2016
https://dl.acm.org/doi/10.1109/TNET.2014.2378012
Chrysos NMinkenberg CRudquist MBasso CVanderpool B(2015)SCOC: High-radix switches made of bufferless clos networks2015 IEEE 21st International Symposium on High Performance Computer Architecture (HPCA)10.1109/HPCA.2015.7056050(402-414)Online publication date: Feb-2015
https://doi.org/10.1109/HPCA.2015.7056050
Attiya HHay DKeslassy I(2010)Packet-Mode Emulation of Output-Queued SwitchesIEEE Transactions on Computers10.1109/TC.2009.18659:10(1378-1391)Online publication date: 1-Oct-2010
https://dl.acm.org/doi/10.1109/TC.2009.186
Show More Cited By

Index Terms

Work-conserving distributed schedulers for Terabit routers
1. Networks
  1. Network protocols
  2. Network types
    1. Packet-switching networks

Recommendations

Work-conserving distributed schedulers for Terabit routers

Buffered multistage interconnection networks offer one of the most scalable and cost-effective approaches to building high capacity routers. Unfortunately, the performance of such systems has been difficult to predict in the presence of the extreme ...
Adaptive work stealing with parallelism feedback
PPoPP '07: Proceedings of the 12th ACM SIGPLAN symposium on Principles and practice of parallel programming

We present an adaptive work-stealing thread scheduler, A-Steal, for fork-join multithreaded jobs, like those written using the Cilk multithreaded language or the Hood work-stealing library. The A-Steal algorithm is appropriate for large parallel servers ...
A distributed shifting bottleneck heuristic for complex job shops

In this paper, we consider distributed versions of a modified shifting bottleneck heuristic for complex job shops. The considered job shop environment contains parallel batching machines, machines with sequence-dependent setup times and reentrant ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SIGCOMM '04: Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications

August 2004

402 pages

ISBN:1581138628

DOI:10.1145/1015467

General Chair:
Raj Yavatkar
Intel Corporation
,
Program Chairs:
Ellen Zegura
Georgia Institute of Technology
,
Jennifer Rexford
AT&T Labs -- Research

ACM SIGCOMM Computer Communication Review Volume 34, Issue 4
October 2004
385 pages
ISSN:0146-4833
DOI:10.1145/1030194
Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 30 August 2004

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SIGCOMM04

Sponsor:

SIGCOMM04: ACM SIGCOMM 2004 Conference

August 30 - September 3, 2004

Oregon, Portland, USA

Acceptance Rates

Overall Acceptance Rate 462 of 3,389 submissions, 14%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
550
Total Downloads

Downloads (Last 12 months)64
Downloads (Last 6 weeks)19

Reflects downloads up to 16 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Chrysos NChen LKachris CKatevenis M(2016)Discharging the network from its flow control headachesIEEE/ACM Transactions on Networking10.1109/TNET.2014.237801224:1(15-28)Online publication date: 1-Feb-2016
https://dl.acm.org/doi/10.1109/TNET.2014.2378012
Chrysos NMinkenberg CRudquist MBasso CVanderpool B(2015)SCOC: High-radix switches made of bufferless clos networks2015 IEEE 21st International Symposium on High Performance Computer Architecture (HPCA)10.1109/HPCA.2015.7056050(402-414)Online publication date: Feb-2015
https://doi.org/10.1109/HPCA.2015.7056050
Attiya HHay DKeslassy I(2010)Packet-Mode Emulation of Output-Queued SwitchesIEEE Transactions on Computers10.1109/TC.2009.18659:10(1378-1391)Online publication date: 1-Oct-2010
https://dl.acm.org/doi/10.1109/TC.2009.186
Hu YMa XLan JWang H(2009)A central-stage buffered three-stage Clos switching fabric and the scheduling algorithmJournal of Electronics (China)10.1007/s11767-007-0134-926:1(113-119)Online publication date: 1-Jan-2009
https://doi.org/10.1007/s11767-007-0134-9
He SSun SGuan HZheng QZhao YGao W(2008)On guaranteed smooth switching for buffered crossbar switchesIEEE/ACM Transactions on Networking10.1109/TNET.2007.90040216:3(718-731)Online publication date: 1-Jun-2008
https://dl.acm.org/doi/10.1109/TNET.2007.900402
Chrysos NYavatkar RGrunwald DRamakrishnan K(2007)Congestion management for non-blocking clos networksProceedings of the 3rd ACM/IEEE Symposium on Architecture for networking and communications systems10.1145/1323548.1323569(117-126)Online publication date: 3-Dec-2007
https://dl.acm.org/doi/10.1145/1323548.1323569
Wiseman CTurner JWong KHeller BYavatkar RGrunwald DRamakrishnan K(2007)Experimental evaluation of a coarse-grained switch schedulerProceedings of the 3rd ACM/IEEE Symposium on Architecture for networking and communications systems10.1145/1323548.1323555(37-38)Online publication date: 3-Dec-2007
https://dl.acm.org/doi/10.1145/1323548.1323555
Attiya HHay DKeslassy IGibbons PVishkin U(2006)Packet-mode emulation of output-queued switchesProceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures10.1145/1148109.1148134(138-147)Online publication date: 30-Jul-2006
https://dl.acm.org/doi/10.1145/1148109.1148134
Chrysos NKatevenis M(2006)Scheduling in Non-Blocking Buffered Three-Stage Switching FabricsProceedings IEEE INFOCOM 2006. 25TH IEEE International Conference on Computer Communications10.1109/INFOCOM.2006.134(1-13)Online publication date: Apr-2006
https://doi.org/10.1109/INFOCOM.2006.134
Chrysos NChen LKachris CKatevenis M(2016)Discharging the network from its flow control headachesIEEE/ACM Transactions on Networking10.1109/TNET.2014.237801224:1(15-28)Online publication date: 1-Feb-2016
https://dl.acm.org/doi/10.1109/TNET.2014.2378012

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Work-conserving distributed schedulers for Terabit routers

Adaptive work stealing with parallelism feedback

A distributed shifting bottleneck heuristic for complex job shops