Pulsa: non-blocking packet switching with shift-register rings

ABSTRACT

This paper discusses the design of a switch for high-speed computer networking at gigabit rates. We present the Pulsar switch, a non-blocking design based on a high-spin-rate, port-dedicated, word-parallel, shift-register ring. Several design alternatives address the problem of Head-Of-Line blocking. In contrast to Batcher-Banyan switches, access to the ring is asynchronous which facilitates low delay and arbitrary packet length. The switch can support ATM cells simultaneously with packets sized for applications such as single characters, memory words, disk blocks, memory pages, or video images. Pulsar can be used as a high-throughput computer backplane replacement. The design can be implemented with existing high-speed circuit technology.

REFERENCES

• 1: R. Campbell, V. Russo, and G. Johnston. A Class Hierarchical, Object-Oriented Appro#,ch to Virtual Memory Management in Multioroce:;sor Operating Systems Technical Report UIUCD #S-R-88- 1459, Department of Computer Science, University of Illinois at Urbana-Champaign, 1988.
• 2: I. Cidon and Y. Ofek. Metaring- A Full-Duplex Ring with Fairness and Spatial Reuse. Technical Report RC 14961(#66845), IBM Research Division, September 22 1989.
• 3: G. Delp , A. Sethi , D. Farber, An analysis of Memnet—an experiment in high-speed shared-memory local networking, ACM SIGCOMM Computer Communication Review, v.18 n.4, p.165-174, August 1988
• 4: A. Demers , S. Keshav , S. Shenker, Analysis and simulation of a fair queueing algorithm, ACM SIGCOMM Computer Communication Review, v.19 n.4, p.1-12, Sep. 1989
• 5: Edward Gehringer , Janne Abullarade , Michael H. Gulyn, A survey of commercial parallel processors, ACM SIGARCH Computer Architecture News, v.16 n.4, p.75-107, Sept. 1988 [doi>10.1145/54331.54338]
• 6: M. G. Hluchyj. Queueing; in High-Performance Packet Switching. IEEE Journal on Selected Areas in Communications, 6.9:1587-1597, December 1988.
• 7: Kurt Harold Horton, Multicomputer interconnection using word parallel shift register ring networks, 1984
• 8: A. Huang and S. Knauer. Starlite: A Wideband Digital Awitch. In Proceedings of lhe IEEE Globecom "84, pages 121-125, 1984.
• 9: J. Y. Hut and E. Arthurs. A Broadband Packet Switch for Integrated Packet Transport. IEEE Journal on Selected Areas in Communications, 5.8:1264-1273, October 1987.
• 10: A. E. Kamal , V. C. Hamacher, Approximate analysis of non-exhaustive multiserver polling systems with applications to local area networks, Computer Networks and ISDN Systems, v.17 n.1, p.15-27, June 10, 1989 [doi>10.1016/0169-7552(89)90020-2]
• 11: M. J. Karol, Optical interconnection using ShuffleNet multihop networks in multi-connected ring topologies, ACM SIGCOMM Computer Communication Review, v.18 n.4, p.25-34, August 1988
• 12: S. Keshav. Congestion Control in High Speed Networks, February 26 1990. presentation on HRR at the XUNET Student Meeting.
• 13: G. Kimura and Y. Takahashi. Diffusion Approximation for a Token Ring System with Nonexhaustive Service. IEEE Journal on Selected Areas in Communications, 4.6:794-801, September 1986.
• 14: T. T. Lee. Nonblocking Copy Networks for Multicast Packet Switching. IEEE Journal on Selected Areas in Communicaiions, 6.9:1455-1467, December 1988.
• 15: R. I. MacDonald. Terminology for Photonic Matrix Switches. 1EEE Journal on Selected Areas in Communications, 6.7:1141-1151, August 1988.
• 16: N. F. Maxemchuck. Routing in the Manhattan Street Network. Technical Report 11382-850905-01TM, AT&T Bell Laboratories, Murray Hill, NJ, September 1985.
• 17: Kazuaki Murakami , Akira Fukuda , Toshinori Sueyoshi , Shinji Tomita, An overview of the Kyushu University reconfigurable parallel processor, ACM SIGARCH Computer Architecture News, v.16 n.4, p.130-137, Sept. 1988 [doi>10.1145/54331.54341]
• 18: Y. Ofek. Design and Analysis of a Fiber-Optic Hypergraph Network. Technical Report UIUCDCS- R-87-1343, Department of Electrical and Computer Engineering, University of Illinois at Urbana- Champaign, 1987. also PhD Thesis.
• 19: Ivor Page , Jeff Niehaus, The Flex architecture, a high speed graphics processor, ACM SIGARCH Computer Architecture News, v.16 n.4, p.117-129, Sept. 1988 [doi>10.1145/54331.54340]
• 20: J. W. M. Pang and R. W. Donaldson. Approximate Delay Analysis and Results for Asymmetric Token-Passing and Polling Networks. 1EEE Journal on Selecied Areas in Communications, 4.6:783-793, September 1986.
• 21: J. W. Reedy. The TDM Ring -- A Fiber Optic Transport System for Campus or Metropolitan Networks. IEEE Journal on Selected Areas in Communications, 4.9:1474-1483, December 1986.
• 22: J. Sauer. An Optoelectronic Multi-Gb/s Packet Switching Network, February 1989. Seminar notes.
• 23: Hideaki Takagi, Queuing analysis of polling models, ACM Computing Surveys (CSUR), v.20 n.1, p.5-28, March 1988 [doi>10.1145/62058.62059]
• 24: T. Takine, Y. Takahashi, and T. Hasegawa. Performance Analysis of a Polling System with Single Buffers and Its Application to Interconnected Networks. {EEE Journal on Selected Areas in Communicaiions, 4.6:802-812, September 1986.
• 25: S. K. Tewksbury and L. A. Hornak. Communication Network Issues and High-Density Interconnects in Large-Scale Distributed Computing Systems. IEEE Journal on Selected Areas in Communications, 6.3:587-609, April 1988.

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:
  B. Hardware
  B.6 LOGIC DESIGN

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

General Terms:
Design, Performance