Adaptive Max-Min Fair Scheduling in Buffered Crossbar Switches Without Speedup

A good crossbar switch scheduler should be able to sustain full bandwidth and maintain fairness among competing flows. A pure input-queued (IQ) non-buffered switch requires an impractically complex scheduler to achieve this goal. Common solutions are to use crossbar speedup and/or buffered crossbar. In this paper, we explore this issue in a buffered crossbar without speedup. We first discuss the conflict between fairness and throughput and the fairness criteria in crossbar switch scheduling, and justify that a desirable scheduler should sustain full bandwidth for admissible traffic and ensure max-min fairness for non-admissible traffic. Then we describe an adaptive max-min fair scheduling (AMFS) algorithm and show by analysis and simulation that it can provide both 100% throughput and max-min fairness. Finally we briefly discuss the hardware implementation of the AMFS algorithm.