Distributed WFQ Scheduling in Buffered Crossbar (CICQ) Switches

Nikolaos Chrysos, George F. Georgakopoulos, Manolis Katevenis

Computer Architecture and VLSI Systems (CARV) Laboratory,
Institute of Computer Science (ICS), FORTH, Heraklion, Crete, Greece
Dept. of Computer Science, University of Crete, Heraklion, Crete, Greece

© copyright 2002-2003 by FORTH and the Univ. of Crete, Greece

The crossbar is the most frequently used switching element topology. It offers simplicity and non-blocking operation. However, when bufferless, it also requires a centralized scheduler, which must simultaneously satisfy --in each cell time-- all input and all output link constraints. The cost and complexity of this scheduler increases considerably with switch size. Moreover, it is an open problem whether and how such schedulers can efficiently implement sophisticated policies like weighted-fair-queueing (WFQ) / weighted-round-robin (WRR). Also, bufferless crossbars are traditionally only used with fixed-size cells arriving from mutually-synchronized line cards.

Modern technology allows small buffers (on the order of a few cells) to be included at each crosspoint of a crossbar. In such a buffered crossbar, the scheduling task is dramatically simplified: distinct servers at each input and each output collectively but still independently schedule the set of flows through the interconnect; they are loosely coordinated through backpressure signals from the crosspoint buffers. Also, buffered crossbars do not require synchronized line cards, and can operate efficiently even with variable-size packets (our next research topic):

[ Up to Buffered Crossbar (CICQ) Switch Architecture at FORTH ]

We have analyzed such distributed scheduling policies in buffered crossbars using weighted fair queueing (WFQ) schedulers at each input and output. Initially, we assumed fixed-size cell traffic. We found, using extensive simulations and analysis, that this system approximates very well the ideal weighted max-min fair allocation of throughput. We also studied the convergence time, and we quantified the unfairness during the convergence process. Further, we studied saturation throughput under various assumptions on the form of traffic. Crosspoint buffers of size just 1 cell each suffice for the scheduling operation; crosspoint buffers of size 4 to 5 cells each yield excellent performance, at least for switches up to 32x32.

1.   Introductory Paper: simulation results on WMMF allocation

N. Chrysos, M. Katevenis: "Weighted Fairness in Buffered Crossbar Scheduling", Proceedings of the IEEE Workshop on High Performance Switching and Routing (HPSR 2003), Torino, Italy, June 2003, pp. 17-22.
Available in PDF (120 KBytes) or Postscript (180 KBytes) or gzip'ed Postscript (50 KBytes) format; © Copyright 2003 IEEE. The slides of the presentation are also available, in PDF format (220 KBytes).

2.   Analysis Papers: WMMF allocation

G. Georgakopoulos: "Nash Equilibria as a Fundamental Issue Concerning Network-Switches Design", Proc. IEEE International Conference on Communications (ICC 2004), Paris, France, 20-24 June 2004, vol. 2, pp. 1080-1084.
- Preprint in PDF (200 KBytes); © Copyright 2004 by IEEE.

G. Georgakopoulos: "Few buffers suffice: Explaining why and how crossbars with weighted fair queuing converge to weighted max-min fairness", Dept. of Computer Science, University of Crete, Heraklion, Crete, Greece, July 2003, 6 pages.
Available in PDF format (240 KBytes); © Copyright 2003 University of Crete.

3.   Transient Behavior Papers: simulation results

N. Chrysos, M. Katevenis: "Transient Behavior of a Buffered Crossbar Converging to Weighted Max-Min Fairness", Inst. of Computer Science, FORTH, Heraklion, Crete, Greece, August 2002, 13 pages.
Available in PDF (540 KBytes) or Postscript (585 KBytes) or gzip'ed Postscript (145 KBytes) format; © Copyright 2002 FORTH.

N. Chrysos: "Weighted Max-Min Fairness in a Buffered Crossbar Switch with Distributed WFQ Schedulers: a First Report", Technical Report FORTH-ICS/TR-309, Inst. of Computer Science, FORTH, Heraklio, Crete, Greece; M.Sc. Thesis, Univ. of Crete (advisor: M. Katevenis); April 2002, 150 pages.
Available in Postscript (5.4 MBytes) or gzip'ed Postscript (1.4 MBytes) format; © Copyright 2002 FORTH.
The M.Sc. Thesis in Greek (81 pages) is also available, in Postscript (1.4 MBytes) format; © Copyright 2002 Univ. of Crete.

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

© Copyright 2002-2003 by FORTH, Univ. of Crete, and 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 Univ. of Crete 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) and/or the University of Crete and/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.
Up to Buffered Crossbar (CICQ) Switch Architecture at FORTH Last updated: Apr. 2004 (major) - Apr. 2007 (minor), by M. Katevenis.