Pipelined memory shared buffer for VLSI switches

ABSTRACT

Switch chips are building blocks for computer and communication systems. Switches need internal buffering, because of output contention; shared buffering is known to perform better than multiple input queues or buffers, and the VLSI implementation of the former is not more expensive than the latter. We present a new organization for a shared buffer with its associated switching and cut-through functions. It is simpler and smaller than wide or interleaved organizations, and it is particularly suitable for VLSI technologies. It is based on multiple memory banks, addressed in a pipelined fashion. The first word of a packet is transferred to/from the first bank, followed by a "wave" of similar operations for the remaining words in the remaining banks. An FPGA-based prototype is operational, while standard-cell and full-custom chips are being submitted for fabrication. Simulation of the full-custom version indicates that, even in a conservative 1-micron CMOS technology, a 64 Kbit central buffer for an 8×8 switch operates at 1 Gbps/link (worst case) and fits in 45 mm² including crossbar and cut-through.

REFERENCES

• AOST93: Thomas E. Anderson , Susan S. Owicki , James B. Saxe , Charles P. Thacker, High-speed switch scheduling for local-area networks, ACM Transactions on Computer Systems (TOCS), v.11 n.4, p.319-352, Nov. 1993 [doi>10.1145/161541.161736]
• Arno89: Emmanuel Arnould , H. T. Kung , Francois Bitz , Robert D. Sansom , Eric C. Cooperm, The design of nectar: a network backplane for heterogeneous multicomputers, ACM SIGARCH Computer Architecture News, v.17 n.2, p.205-216, April 1989
• AtSe88: William C. Athas , Charles L. Seitz, Multicomputers: Message-Passing Concurrent Computers, Computer, v.21 n.8, p.9-24, August 1988 [doi>10.1109/2.73]
• C104: "IMS C104 Packet Routing Switch- Preliminary Datasheet", INMOS Ltd, 1000 Aztec West, Almondsbury, Bristol, BS12 4SQ. UK, June 1993.
• Dally90: William J. Dally, Virtual-channel flow control, Proceedings of the 17th annual international symposium on Computer Architecture, p.60-68, May 28-31, 1990, Seattle, Washington, United States
• DeCS88: M. Devault, J-Y. Cochennec, M. Servel: "The "Prelude'' ATD Experiment: Assessments and Future Prospects", IEEE Journal on SeI. Areas in Communications, vol. 6, no. 9, December 1988, pp. 1528-1537.
• DeEI95: W. E. Denzel , A. P. J. Engbersen , I. Iliadis, A flexible shared-buffer switch for ATM at Gb/s rates, Computer Networks and ISDN Systems, v.27 n.4, p.611-624, Jan. 1995 [doi>10.1016/0169-7552(94)00004-D]
• HlKa88: M. Hluchyj, M. Karol: "Queueing in High- Performance Packet Switching", IEEE Journal on SeI. Areas in Communications, vol. 6, no. 9, December 1988, pp. 1587-1597.
• HoLa93: M. Homewood, M. McLaren: "Meiko CS-2 Interconnect Elan - Elite Design", Meiko Ltd., 650 Aztec West, Bristol, UK, May 1993.
• KaHM87: M. Karol, M. Hluchyj, S. Morgan: "Input versus Output Queueing on a Space-Division Packet Switch", IEEE Trans. on Communications, vol. COM-35, no. 12, December 1987, pp. 1347-1356.
• KaSC91: M. Katevenis, S. Sidiropoulos, C. Courcoubetis: "Weighted Round-Robin Cell Multiplexmg in a General-Purpose ATM Switch Chip", IEEE Journal on Sel. Areas in Communications, vol. 9, no. 8, October 1991, pp. 1265-1279.
• Kate94: M. Katevenis: "Telegraphos: High-Speed Communication Architecture for Parallel and Distributed Computer Systems" Technical Report FORTH- ICS/TR~ 123, 1CS, 'FORTH, Heraklio, Crete, GR, May 1994, 38 pages; on-line: ftp.ics.forth.gr: tech-reports/1994/94.TR 123 .Telegraphos.p s.Z
• KVES95: M. Katevenis, P. Vatsolaki, A. Efthymiou, S. Stratakis: "VC-level Flow Control and Shared Buffering in the Telegraphos Switch", Proceedings of the Hot Interconnects IIi Symposium, Stanford Univ., CA, USA, August 1995.
• Koza91: T Kozaki, N. Endo, Y. Sakurai, O. Matsubara, M. Mizukami, K. Asano: "32 x 32 Shared Buffer Type ATM Switch VLSI's for B-ISDN's", IEEE Journal on SeI. Areas in Communications, vol. 9, no. 8, October 1991, pp. 1239-1247.
• Kung92: H. T Kung: "Gigabit Local Area Networks: A Systems Perspective", IEEE Communications Magazine, vol. 30, no. 4, April 1992, pp. 79-89.
• LaSe95: Richard O. LaMaire , Dimitrios N. Serpanos, Two-dimensional round-robin schedulers for packet switches with multiple input queues, IEEE/ACM Transactions on Networking (TON), v.2 n.5, p.471-482, Oct. 1994 [doi>10.1109/90.336324]
• PaBr93: Achille Pattavina , Giacomo Bruzzi, Analysis of input and output queueing for nonblocking ATM switches, IEEE/ACM Transactions on Networking (TON), v.1 n.3, p.314-328, June 1993 [doi>10.1109/90.234854]
• Shob91: Y. Shobakate, M. Motoyama, E. Shobakate, T. Kamitake, S. Shimizu, M. Noda, K. Sakaue: "A One-Chip Scalable 8 * 8 ATM Switch LSI Employing Shared Buffer Architecture", IEEE Journal on Sel. Areas in Communications, vol. 9, no. 8, October 1991, pp. 1248-1254.
• Souz94: Robert J. Souza , P. G. Krishnakumar , Cüneyt M. Özveren , Robert J. Simcoe , Barry A. Spinney , Robert E. Thomas , Robert J. Walsh, GIGAswitch system: a high-performance packet-switching platform, Digital Technical Journal, v.6 n.1, p.9-22, Winter 1994
• Stun94: Craig B. Stunkel , Dennis G. Shea , Bülent Abali , Monty Denneau , Peter H. Hochschild , Douglas Joseph , Ben J. Nathanson , Mickey Tsao , Philip R. Varker, Architecture and Implementation of Vulcan, Proceedings of the 8th International Symposium on Parallel Processing, p.268-274, April 01, 1994
• TaFr88: 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
• TaCh93: Y. Tamir , H. C. Chi, Symmetric Crossbar Arbiters for VLSI Communication Switches, IEEE Transactions on Parallel and Distributed Systems, v.4 n.1, p.13-27, January 1993 [doi>10.1109/71.205650]
• Turn93: J. Turner: "An Optimal Nonblocking Multicast Virtual Circuit Switch", Technical Report WUCS-93-30. Washington Univ., St. Louis, MO, USA, June 1993, 22 pages.
• WeEs93: Neil H. E. Weste , Kamran Eshraghian, Principles of CMOS VLSI design: a systems perspective, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1985
• YeHA87: Y. Yeh, M. Hluchyj, A. Acampora: "The Knockout Switch: A Simple, Modular Architecture for High- Performance Packet Switching", IEEE Journal on Sel. Areas in Communications, vol. SAC-5, no. 8, October 1987, pp. 1274-1283.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES

Additional Classification:
  B. Hardware
  B.4 INPUT/OUTPUT AND DATA COMMUNICATIONS

  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.1 Single Data Stream Architectures
          Subjects: Pipeline processors**
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Interconnection architectures (e.g., common bus, multiport memory, crossbar switch)
  C.5 COMPUTER SYSTEM IMPLEMENTATION

General Terms:
Algorithms, Design, Performance

Keywords:
crossbar switch, gigabit VLSI switch buffer, input queueing, multiport buffer, pipelined memory, shared buffering