A high-throughput scheduling algorithm for Partially Buffered Crossbar switches

The Partially Buffered Crossbar (PBC) switch maintains a small number of buffers per output. While having a cost close to unbuffered crossbars, a PBC switch overcomes the centralized scheduling complexity by means of distributed schedulers resulting in high speed switching and simplicity in its scheduling. Previously, a class of round-robin algorithms have been proposed for the PBC and demonstrated similar performance to an output queued (OQ) switch under bernoulli uniform traffic. However, it fails to deliver satisfactory performance under nonuniform traffic unless a high number of internal buffers is used. In this paper, we propose a novel scheduling algorithm, named ELSRR (Exhaustive-LQF-SRR), that enhances the performance of a PBC switch under nonuniform traffic. Through experimental study, we show that our algorithm is capable of delivering high throughput under non-uniform traffic with low requirement on the internal buffer per output; as few as two internal buffers per output are sufficient irrespective of the switch size, N.