High-speed switch scheduling for local-area networks

ACM Transactions on Computer Systems - Tập 11 Số 4 - Trang 319-352 - 1993
Thomas E. Anderson1, Susan Owicki2, James B. Saxe2, Charles P. Thacker2
1University of California, Berkeley
2Digital Equipment Corp.

Tóm tắt

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.

Từ khóa


Tài liệu tham khảo

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

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

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

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

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 . 10.1145/75246.75248 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. 10.1145/75246.75248

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. 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.

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. 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.

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

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

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

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

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

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. 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.

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

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. 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.

KARP , R. , VAZ l RANI , 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. 10.1145/100216.100262 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. 10.1145/100216.100262

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

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

10.1145/360248.360253

OBAI~A , H. , AND YASUS tt I, 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. 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.

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 . 10.1145/133057.133102 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. 10.1145/133057.133102

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

10.1145/78952.78955

10.1145/77648.77653

SCHROEDER , M. , BIRRELL , A. , BURROWS , M. , MURRAY , H. , NEEDHAM , R. , RODEHEFFER , T , SA~I'ERTH - W AITE , 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. 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.

TAM m, Y., AND FRAZ m R, G . 1988 . High-performance multi-queue buffers for VLSI communication switches . In Proceedings of the 151h Annual Symposium on Computer Archttecture (June), 343-354 . 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.

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

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

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. 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.

ZHANG , H. , AN n 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. 10.1145/115992.116004 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. 10.1145/115992.116004

10.1145/103720.103721

Thông tin
Thông tin xuất bản

ACM Transactions on Computer Systems

Tập 11 Số 4

319-352

Thông tin tác giả