基于CICQ交换结构的低复杂度调度算法

针对CICQ权值仲裁策略复杂度高的不足,提出一种新的调度策略——LQP-RR（Long Queue Prioritized-Round Robin）。该算法利用VOQ队列局部变化的特性,简化了权值仲裁策略复杂的排序操作,只在输入端进行一次比较操作,并采用辅助轮询指针配合调度以保证算法的公平性,其算法复杂度仅为O（1）,硬件实现简单,扩展性能良好。通过流体模型证明该算法对满足强大数定律的许可输入流量能够达到100%的吞吐率性能。仿真结果进一步表明LQP-RR调度算法在各种流量模型下都能稳定运行,且具有良好的时延和吞吐率性能。

A Low Complexity Scheduling Algorithm for CICQ Switches

Base on analyzing the performance of several classical CICQ (Combined Input and Crosspoint Queued) scheduling algorithms, we propose a new scheduling scheme called LQP-RR (Long Queue Prioritized-Round Robin). By using the local variation feature of virtual output queues, the new algorithm simplifies the complex sorting operation of LQF-RR (Longest Queue First-Round Robin) at input scheduling. In addition, a secondary pointer was adopted to guarantee the fairness of the algorithm. The new algorithm only need one times compare operation at input port, so it has a complexity of O(1) and easy to implement in hardware. Through fluid model techniques, we prove that it achieves 100% throughput for any admissible traffic that satisfies the strong law of large numbers. Finally, simulation result shows that LQP-RR exhibits good delay and throughput performance and stability under any admissible traffic.