A Low Complexity Scheduling Algorithm for CICQ Switches
Yu Xia · Journal of Sichuan University · 2011
Focusing on the problem of high computational complexity of weighted arbitration scheme for Combined Input and Crosspoint Queued(CICQ) switches,a new scheduling algorithm called Long Queue Prioritized-Round Robin(LQP-RR) was proposed.By using the local variation feature of virtual output queues,the complex sorting operation at input scheduling was simplified.In addition,a secondary pointer was adopted to guarantee the fairness of the algorithm.The new algorithm only need one time compare operation at input port,which indicates that the algorithm has a low complexity and is easy to implement.Theoretical analysis illustrated that the proposed algorithm can achieve 100% throughput for any admissible traffic that satisfies the strong law of large numbers.Finally,simulation showed that LQP-RR exhibits good delay and throughput performance under any admissible traffic.