Benes Fabrics with Internal Backpressure
for Scalable Non-Blocking Switching

Outline of Research

• Buffered switching fabrics are an efficient method for building packet switches with a very large number of ports.
• Multilane backpressure in the switching fabric allows the switching elements to only use on-chip buffer memory, while the majority of the packets are buffered at the inputs, in virtual-output queues (VOQ), thus greatly reducing the cost of the fabric.
• In this work, we extend the above ideas to the Benes network, which is the lowest-cost topology that is known to yield operation free of internal blocking.

Papers

• G. Sapountzis, M. Katevenis: "Benes Switching Fabrics with O(N)-Complexity Internal Backpressure", IEEE Communications Magazine (special theme on "Next Generation Switching and Routing"), vol. 43, no. 1, January 2005, pp. 88-94.
• G. Sapountzis, M. Katevenis: "Benes Switching Fabrics with O(N)-Complexity Internal Backpressure", Proceedings of the IEEE Workshop on High Performance Switching and Routing (HPSR 2003), Torino, Italy, June 2003, pp. 11-16.
  Similar to the Communications Magazine (Jan. 2005) paper; available in PDF (180 KBytes) or Postscript (290 KBytes) or gzip'ed Postscript (85 KBytes) format; © Copyright 2003 IEEE. The slides of the presentation are also available, in PDF format (190 KBytes).

  ABSTRACT: Multistage buffered switching fabrics are the most efficient method for scaling packet switches to very large numbers of ports. The Benes network is the lowest-cost switching fabric known to yield operation free of internal blocking. Backpressure inside a switching fabric can limit the use of expensive off-chip buffer memory to just virtual-output queues (VOQ) in front of the input stage. This paper extends the known backpressure architectures to the Benes network. To achieve this, we had to successfully combine per-flow backpressure, multipath routing (inverse multiplexing), and cell resequencing. We present a flow merging scheme that is needed to bring the cost of backpressure down to O(N) per switching element. We prove freedom from deadlock for a wide class of multipath cell distribution algorithms. Using a cell-time-accurate simulator, we verify operation free of internal blocking, we evaluate various cell distribution and resequencing methods, we compare performance to that of ideal output queueing and the iSLIP crossbar scheduling algorithm, and we show that the delay of well-behaved flows remains unaffected by the presence of congested traffic to oversubscribed output ports.

• G. Sapountzis, M. Katevenis: "Benes Switching Fabrics with O(N)-Complexity Internal Backpressure", Inst. of Computer Science, FORTH, Heraklio, Crete, Greece, July 2003, 11 pages.
  Available in PDF (150 KBytes) or Postscript (450 KBytes) or gzip'ed Postscript (125 KBytes) format; © Copyright 2003 FORTH.

  This is a longer version of the above HPSR-2003 paper. In addition to the more detailed presentation, it also contains the proof of freedom from deadlock.

• Georgios Sapountzis: "Benes Switching Fabrics with O(N)-Complexity Internal Backpressure", Technical Report FORTH-ICS/TR-316, Inst. of Computer Science, FORTH, Heraklio, Crete, Greece; M.Sc. Thesis, Univ. of Crete (advisor: M. Katevenis); December 2002, 12+64 = 76 pages.
  Available in PDF (500 KBytes); © Copyright 2002 FORTH.
  This is the full-length version of our research; it covers in more details the topics covered by the above papers.
  In addition, this thesis uses simplified models of the Benes fabric to analytically show that cell distribution does not result in throughput limitations, and to identify the points of the fabric where contention is resolved. This latter point may be the key to a future design of appropriate distributed scheduling algorithms that provide weighted max-min fairness for the overall system.

 

Acknowledgements

Vasilios Siris, Paraskevi Fragopoulou, and Nikos Chrysos helped us shape our ideas; we deeply thank them.

Older (outdated) papers

• G. Sapountzis, M. Katevenis: "Benes Switching Fabrics with O(N)-Complexity Internal Backpressure", Inst. of Computer Science, FORTH, Heraklio, Crete, Greece, August 2002, 12 pages.
  Available in PDF (260 KBytes) or Postscript (490 KBytes) or gzip'ed Postscript (135 KBytes) format; © Copyright 2002 FORTH.

  [Superseded by the July 2003 version, above].

• G. Sapountzis, M. Katevenis: "Benes Fabrics with Internal Backpressure: First Work-in-Progress Report", Technical Report FORTH-ICS/TR-303, Inst. of Computer Science, FORTH, Heraklio, Crete, Greece, March 2002, 27 pages.
  Available in Postscript (1.1 MBytes) or gzip'ed Postscript (200 KBytes) format; © Copyright 2002 FORTH.

  [Superseded by TR-316, above].

• Manolis Katevenis: "Wide Links: 2logN-Stage Non-Blocking Networks with In-Order Packet Delivery", Inst. of Computer Science, FORTH, Heraklio, Crete, Greece, June 1995, unpublished internal working paper.
  [This (unfinished) paper presented our August 1994 work on how to use multilane backpressure in multipath (Benes) fabrics and how to merge flows so as to keep the number of lanes manageable, while guaranteeing freedom from deadlock and maintaining non-blocking operation.]

 

---

© Copyright 2002-2003 by FORTH or the IEEE

These papers are protected by copyright. Permission to make digital/hard copies of all or part of this material without fee is granted provided that the copies are made for personal use, they are not made or distributed for profit or commercial advantage, the FORTH or IEEE copyright notice, the title of the publication and its date appear, and notice is given that copying is by permission of the Foundation for Research & Technology -- Hellas (FORTH) or the IEEE. To copy otherwise, in whole or in part, to republish, to post on servers, or to redistribute to lists, requires prior specific written permission and/or a fee.