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

A Low Complexity Scheduling Algorithm for CICQ Switches

作　　者：高志江[1] 曾华燊[1] 夏羽[1] 

机构地区：[1]西南交通大学信息科学与技术学院,四川成都610031

出　　处：《四川大学学报（工程科学版）》2011年第5期163-167,共5页Journal of Sichuan University (Engineering Science Edition)

基　　金：国家自然科学基金资助项目(60773102);"中国工程科技中长期发展战略研究"联合基金资助项目(U0970122);四川大学基金资助项目(下一代Inter-net体系结构)

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

关 键 词：包交换 调度算法 计算复杂度 吞吐率 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]