A Novel Scheduling Algorithm Based on Longest Queue Detecting for CICQ Switching Fabrics

CICQ (Combined Input Crosspoint Queued) is a switch fabric with buffers in crosspoints, which brings its nice distributed parallel scheduling property with no internal speedup required. In order to adapt to various traffics in the network environment, and improve performance under nonuniform traffics, a novel efficient scheduling algorithm with longest queue detectingRR-LQD (Round Robin based on Longest Queue Detecting) is proposed. RR-LQD provides fine scalability with the complexity of O(1). The local longest queue being detected and serviced all along guarantees length balance among input queues, which makes RR-LQD adapt to the network environment of nonuniform traffic automatically. The simulation results show that the RR-LQD can achieve 100% throughput and low delay under various uniform and non-uniform traffics. In this paper, the arbiter of RR-LQD is implemented by a FPGA chip. That proves RR-LQD can meet the demands of high-speed and large capacity switching fabrics.