High-speed switch scheduling for local-area networks

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: A. Demers , S. Keshav , S. Shenker, Analysis and simulation of a fair queueing algorithm, Symposium proceedings on Communications architectures & protocols, p.1-12, September 25-27, 1989, Austin, Texas, United States
• 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: Joseph Yu Hui, Switching and Traffic Theory for Integrated Broadband Networks, Kluwer Academic Publishers, Norwell, MA, 1990
• 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: Mark J. Karol , Kai Y. Eng , Hitoshi Obara, Improving the performance of input-queued ATM packet switches, Proceedings of the eleventh annual joint conference of the IEEE computer and communications societies on One world through communications (Vol. 1), p.110-115, May 1992, Florence, Italy
• 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: R. M. Karp , U. V. Vazirani , V. V. Vazirani, An optimal algorithm for on-line bipartite matching, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.352-358, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100262]
• 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: Robert M. Metcalfe , David R. Boggs, Ethernet: distributed packet switching for local computer networks, Communications of the ACM, v.19 n.7, p.395-404, July 1976 [doi>10.1145/360248.360253]
• 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: Susan S. Owicki , Anna R. Karlin, Factors in the performance of the AN1 computer network, Proceedings of the 1992 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.167-180, June 01-05, 1992, Newport, Rhode Island, United States
• 22: Janak H. Patel, Processor-memory interconnections for multiprocessors, Proceedings of the 6th annual symposium on Computer architecture, p.168-177, April 23-25, 1979 [doi>10.1145/800090.802906]
• 23: K. K. Ramakrishnan , R. Jain, A binary feedback scheme for congestion avoidance in computer networks, ACM Transactions on Computer Systems (TOCS), v.8 n.2, p.158-181, May 1990 [doi>10.1145/78952.78955]
• 24: Michael D. Schroeder , Michael Burrows, Performance of the Firefly RPC, ACM Transactions on Computer Systems (TOCS), v.8 n.1, p.1-17, Feb. 1990 [doi>10.1145/77648.77653]
• 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: Y. Tamir , G. L. Frazier, High-performance multi-queue buffers for VLSI communications switches, Proceedings of the 15th Annual International Symposium on Computer architecture, p.343-354, May 30-June 02, 1988, Honolulu, Hawaii, United States
• 27: Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
• 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: Hui Zhang , Srinivasan Keshav, Comparison of rate-based service disciplines, Proceedings of the conference on Communications architecture & protocols, p.113-121, September 03-06, 1991, Zurich, Switzerland
• 31: Lixia Zhang, VirtualClock: a new traffic control algorithm for packet-switched networks, ACM Transactions on Computer Systems (TOCS), v.9 n.2, p.101-124, May 1991 [doi>10.1145/103720.103721]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network communications

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: Access schemes

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
ATM networks, iterative matching, statistical matching, switching scheduling