More Web Proxy on the site http://driver.im/

article

Free access

High-speed switch scheduling for local-area networks

Editor: Anita K. Jones Authors:

Thomas E. Anderson,

Susan S. Owicki,

Charles P. ThackerAuthors Info & Claims

ACM Transactions on Computer Systems (TOCS), Volume 11, Issue 4

Pages 319 - 352

https://doi.org/10.1145/161541.161736

Published: 01 November 1993 Publication History

Abstract

Current technology trends make it possible to build communication networks that can support high-performance distributed computing. This paper describes issues in the design of a prototype switch for an arbitrary topology point-to-point network with link speeds of up to 1 Gbit/s. The switch deals in fixed-length ATM-style cells, which it can process at a rate of 37 million cells per second. It provides high bandwidth and low latency for datagram traffic. In addition, it supports real-time traffic by providing bandwidth reservations with guaranteed latency bounds. The key to the switch's operation is a technique called parallel iterative matching, which can quickly identify a set of conflict-free cells for transmission in a time slot. Bandwidth reservations are accommodated in the switch by building a fixed schedule for transporting cells from reserved flows across the switch; parallel iterative matching can fill unused slots with datagram traffic. Finally, we note that parallel iterative matching may not allocate bandwidth fairly among flows of datagram traffic. We describe a technique called statistical matching, which can be used to ensure fairness at the switch and to support applications with rapidly changing needs for guaranteed bandwidth.

References

[1]

AHMADI, H., AND DENZEL, W. 1989. A survey of modern high-performance switching techniques. {BEE J. Selected Areas Commun. 7, 7 (Sept.), 1091-1103.

[2]

ANSI. 1987. Fiber distributed data interface (FDDI). Token ring media access control (MAC). ANSI Standard X3.139, American National Standards Institute, Inc., New York.

[3]

ANSI. 1988. Fiber distributed data interface (FDDI). Token ring physical layer protocol (PHY). ANSI Standard X3.148, American National Standards Institute, Inc., New York.

[4]

BATCHER, K. 1968. Sorting networks and their applications. In AFIPS Conference Proceedings. AFIPS, Reston, Va., 307-314.

[5]

DEMERS, A., KESHAV, S., AND SHENKER, S. 1989. Analysis and simulation of a fair queueing algorithm. In Proceedings of the' ACM SIGCOMM 89 Conference on Communicatwns Archztectures and Protocols (Sept.). ACM, New York, 1-12.

[6]

FERRARI, D., AND VERMA, D. 1990. A scheme for real-time channel establishment in wide-area networks. 1EEE J. Selected Areas Commun. 8, 3 (Apr.), 361-379.

[7]

GIACOPELLI, J., HICKEY, J., MARCUS, W., SINCOSKIE, W., AND LITTLEWOOD, M. 1991. Sunshine: A high-performance self-routing broadband packet switch architecture. IEEE J. Selected Areas Cornmun. 9, 8 (Oct.), 1289-1298.

[8]

GOLESTANI, S. 1990. Congestion-free transmission of real-time traffic in packet networks. In Proceedings of lNFOCOM '90. (June), 527 542.

[9]

HUANG, A., AND KNAUER, S. 1984. Starlite: A wideband digital switch. In Proceedmgs of GLOBECOM '84 (Dec.), 121-125.

[10]

Hm, J 1990. Switching and Traffic Theory for Integrated Broadband Networks. Kluwer Academic Press, Deventer, The Netherlands.

[11]

HuI, J., AND ARTHURS, E. 1987. A broadband packet switch for integrated transport. IEEE J. Selected Areas Cornmun. 5, 8 (Oct.), 1264-1273.

[12]

JAIN, R. 1990. Congestion control in computer networks: Issues and trends. IEEE Network Mag. (May), 24-30.

[13]

KALMANEK, C., KANAKIA, H., AND KESHAV, S. 1990. Rate controlled servers for very high-speed networks. In Proceedings of the IEEE Global Telecommuntcatwns Conference (Dec.). IEEE, New York, 300 3_1 300.3.9.

[14]

KAROL, M., ENG, K., AND OBARA, H. 1992. Improving the performance of input-queued ATM packet switches. In Proceedings oflNFOCOM '92 (May), 110-115.

[15]

KAROL, M., HLUCHYJ, M., AND MORGAN, S. 1987. Input versus output queueing on a spacedivision packet switch. IEEE Trans. Commun. 35, 12 (Dec,), 1347-1356.

[16]

KARP, R., VAZlRANI, U., AND VAZIRANI, V. 1990. An optimal algorithm for on-line bipartite matching. In Proceedzngs of the 22nd Annual ACM Symposium on Theory of Computing' (May). ACM, New York, 352 358.

[17]

KERMANI, P., AND KLEINROCK, L. 1979. Virtual cut-through: A new computer communication switching technique. Comput. Networks 3 (Sept.), 267-286.

[18]

LI, S.-Y. 1988. Theory of periodic contention and its application to packet switching. In Procee&ngs of INFOCOM '88 (Mar.), 320-325

[19]

METCALFE, R., AND BOGGS, D. 1976. Ethernet: Distributed packet switching for local computer networks. Commun. ACM 19, 7 (July), 395-404

[20]

OBAI~A, H., AND YASUSttI, T. 1989. An efficient contention resolution algorithm for input queuing ATM cross-connect switches. Int. J. D~gltal Analog Cabled Syst. 2, 4 (Oct.), 261-267.

[21]

OWICKI, S., AND KARLIN, A. 1992. Factors m the performance of the ANI computer network. In Proceedings of the 1992 ACM SIGMETRICS and Performance 92 Conference on Measurement and Modeling of Computer Systems (June). ACM, New York, 167-180.

[22]

PATEL, J. 1979. Processor-memory mterconnections for multiprocessors. In Proceedzngs of the 6th Annual Symposzum on Computer Architecture (Apr), 168-177.

[23]

RAMAKRISHNAN, K., AND JAIN, R. 1990. A binary feedback scheme for congestion avoidance in computer networks. ACM Trans. Con*put. Syst. 8, 2 (May), 158 181.

[24]

SCHROEDER, M., AND BURROWS, M. 1990. Performance of firefly RPC. ACM Trans. Comput. Syst. 8, i (Feb.), i 17.

[25]

SCHROEDER, M., BIRRELL, A., BURROWS, M., MURRAY, H., NEEDHAM, R., RODEHEFFER, T, SA~I'ERTH- WAITE, E., AND THACKER, C. 1991. Autonet: A high-speed self-configuring local area network using point-to-point links. {EEE J. Selected Areas Commun. 9, 8 (Oct.), 1318-1335.

[26]

TAMm, Y., AND FRAZmR, G. 1988. High-performance multi-queue buffers for VLSI communication switches. In Proceedings of the 151h Annual Symposium on Computer Archttecture (June), 343-354.

[27]

TARJAN, R. 1983. Data Structures and Network Algorzthms SIAM, Philadelphia, Pa.

[28]

XmINX. 1991. Xihnx: The Programmable Gate Array Data Book. Xilinx, Inc.

[29]

YEH, Y., HLUCHYJ, M., AND ACAMPORA, A. 1987. The knockout switch: A simple modular architecture for high-performance switching IEEE J. Selected Areas Commun. 5, 8 (Oct.), 1274-1283.

[30]

ZHANG, H., ANn I~SHAV, S. 1991. Comparison of rate-based service dlsmplines. In Proceedings of the ACM SIGCOMM 91 Conference on Cornmumcations Architectures and Protocols (Sept). ACM, New York, 113 122.

[31]

ZHANG, L. 1991. Virtual clock: A new traffic control algorithm for packet switching networks. ACM Trans. Comput. Syst. 9, 2 (May), 101-124

Cited By

Liang CSong XCheng JWang MLiu YLiu ZZhao SCui YSekar VYu MSeneviratne AVeitch D(2024)NegotiaToR: Towards A Simple Yet Effective On-demand Reconfigurable Datacenter NetworkProceedings of the ACM SIGCOMM 2024 Conference10.1145/3651890.3672222(415-432)Online publication date: 4-Aug-2024
https://dl.acm.org/doi/10.1145/3651890.3672222
Papaphilippou PSano KAdhi BLuk W(2023)Experimental Survey of FPGA-Based Monolithic Switches and a Novel Queue BalancerIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2023.324458934:5(1621-1634)Online publication date: 1-May-2023
https://dl.acm.org/doi/10.1109/TPDS.2023.3244589
Guan ZLi WHe XZhang SLi K(2023)dBFC: Destination-based Backpressure Flow Control for Incast2023 IEEE 29th International Conference on Parallel and Distributed Systems (ICPADS)10.1109/ICPADS60453.2023.00255(1853-1860)Online publication date: 17-Dec-2023
https://doi.org/10.1109/ICPADS60453.2023.00255
Show More Cited By

Index Terms

High-speed switch scheduling for local-area networks
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms
2. Networks
  1. Network properties
    1. Network structure
  2. Network protocols

Recommendations

High Speed Switch Scheduling for Local Area Networks
Modeling and regulation of host traffic in ATM networks
LCN '96: Proceedings of the 21st Annual IEEE Conference on Local Computer Networks

For any connection admission control (CAC) algorithm to work correctly and efficiently, accurate information of the traffic flow out of the host systems is required. We develop several approximation approaches for modeling the traffic flows of hard real-...
A new scheduling scheme for high-speed packet networks: Earliest-virtual-deadline-first

A new scheduling scheme, called earliest-virtual-deadline-first (EVDF), is proposed to improve resource utilization in a high-speed packet network. The proposed EVDF scheduling is a generalized form of the earliest-deadline-first (EDF) scheduling [D. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Computer Systems

ACM Transactions on Computer Systems Volume 11, Issue 4

Nov. 1993

109 pages

ISSN:0734-2071

EISSN:1557-7333

DOI:10.1145/161541

Editor:
Anita K. Jones
Univ. of Virginia, Charlottesville

Issue’s Table of Contents

Copyright © 1993 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 November 1993

Published in TOCS Volume 11, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

747
Total Citations
View Citations
2,975
Total Downloads

Downloads (Last 12 months)380
Downloads (Last 6 weeks)42

Reflects downloads up to 28 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Liang CSong XCheng JWang MLiu YLiu ZZhao SCui YSekar VYu MSeneviratne AVeitch D(2024)NegotiaToR: Towards A Simple Yet Effective On-demand Reconfigurable Datacenter NetworkProceedings of the ACM SIGCOMM 2024 Conference10.1145/3651890.3672222(415-432)Online publication date: 4-Aug-2024
https://dl.acm.org/doi/10.1145/3651890.3672222
Papaphilippou PSano KAdhi BLuk W(2023)Experimental Survey of FPGA-Based Monolithic Switches and a Novel Queue BalancerIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2023.324458934:5(1621-1634)Online publication date: 1-May-2023
https://dl.acm.org/doi/10.1109/TPDS.2023.3244589
Guan ZLi WHe XZhang SLi K(2023)dBFC: Destination-based Backpressure Flow Control for Incast2023 IEEE 29th International Conference on Parallel and Distributed Systems (ICPADS)10.1109/ICPADS60453.2023.00255(1853-1860)Online publication date: 17-Dec-2023
https://doi.org/10.1109/ICPADS60453.2023.00255
Patronas GVlassopoulos NBellos PReisis D(2023)Accelerating the scheduling of the network resources of the next-generation optical data centersParallel Computing10.1016/j.parco.2022.102993115:COnline publication date: 1-Feb-2023
https://dl.acm.org/doi/10.1016/j.parco.2022.102993
Andújar FColl SAlonso MMartínez JLópez PSánchez JAlfaro F(2023)Energy efficient HPC network topologies with on/off linksFuture Generation Computer Systems10.1016/j.future.2022.09.012139:C(126-138)Online publication date: 1-Feb-2023
https://dl.acm.org/doi/10.1016/j.future.2022.09.012
Chithra Devi RJemi Florinabel DPrasanth N(2022)High Throughput Scheduling Algorithms for Input Queued Packet SwitchesComputers, Materials & Continua10.32604/cmc.2022.01934370:1(1527-1540)Online publication date: 2022
https://doi.org/10.32604/cmc.2022.019343
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
Zhao JAgrawal ANikolic BAsanovic K(2022)Constellation: An Open-Source SoC-Capable NoC Generator2022 15th IEEE/ACM International Workshop on Network on Chip Architectures (NoCArc)10.1109/NoCArc57472.2022.9911299(1-7)Online publication date: 2-Oct-2022
https://doi.org/10.1109/NoCArc57472.2022.9911299
Forero PZhang PRadosevic D(2022)Toward Congestion Control in Lossy Networks via Local Queue-Management PoliciesMILCOM 2022 - 2022 IEEE Military Communications Conference (MILCOM)10.1109/MILCOM55135.2022.10017987(879-886)Online publication date: 28-Nov-2022
https://doi.org/10.1109/MILCOM55135.2022.10017987
(2022)ReferencesNetwork Algorithmics10.1016/B978-0-12-809927-8.00028-2(541-557)Online publication date: 2022
https://doi.org/10.1016/B978-0-12-809927-8.00028-2
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

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

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents