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):
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.
N. Chrysos, M. Katevenis:
"Weighted Fairness in Buffered Crossbar Scheduling",
Proceedings of the IEEE Workshop on
High Performance Switching and Routing
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).
"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.
[Previous, outdated version: June 2003, 12 pages, in pdf (220 KBytes)].
"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.
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.
"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.
|Up to Buffered Crossbar (CICQ) Switch Architecture at FORTH||Last updated: Apr. 2004 (major) - Apr. 2007 (minor), by M. Katevenis.|