混合优化的CICQ交换结构调度算法

摘要

Combined Input-Crosspoint-Queued (CICQ) Crossbar outperforms traditional switch fabrics. In this paper, the features of CICQ switches were discussed and a new scheduling algorithm called Hybrid Optimization Packet Scheduling (HOPS) was proposed. This algorithm was based on a hybrid optimization method. The throughput of the algorithm was guaranteed in the first stage of input scheduling and the delay performance was improved by serving the longer queue in the second stage. HOPS was mainly based on Round-Robin (RR) mechanism and at most one comparison operation was done at input port, so it had a complexity of O( 1) and easy to implement in hardware. With fluid model techniques, it was proved that HOPS algorithm can achieve 100% throughput for any admissible traffic without using speed-up. The simulation results show that HOPS algorithm exhibits favorable delay, throughput performance and stability under any admissible traffic.%联合输入端和交叉点排队(CICQ)的Crossbar是一种性能优于传统结构的交换结构,对CICQ交换结构的特点进行了讨论并提出一种新的混合优化调度(HOPS)算法,算法在输入端调度时采取混合优化的策略,首先尽力保证系统的吞吐率性能,然后根据长队列优先的原则优化系统的时延性能.算法以轮询调度为基础,最多只在输入端进行一次比较操作,其算法复杂度仅为O(1),实现简单.通过流体模型证明该算法对满足强大数定律的许可输入流量能够达到100％的吞吐率性能.仿真结果进一步表明HOPS调度算法在各种流量模型下都能稳定运行,且具有良好的时延和吞吐率性能.