A high-throughput scheduling algorithm for a buffered crossbar switch fabric

We examine high-throughput scheduling algorithms for buffered crossbar witch fabrics containing one buffer per crosspoint. We propose a scheduling system that uses longest queue first (LQF) scheduling for virtual output queues (VOQs) at the inputs and round-robin (RR) scheduling for the crosspoints. It is shown, through fluid model techniques, that this system achieves 100% throughput for input traffic that satisfies the strong law of large numbers and that produces a load less than or equal to 1/N for any input/output pair of an N x N switching fabric. Simulations indicate that 100% throughput may be attained for a much larger class of admissible loads.