CICQ结构中逼近work-conserving的分组调度算法

Work-conserving-based packet scheduling algorithm for CICQ switches

联合输入交叉点排队(CICQ)结构的分组调度算法是一个得到了充分研究的领域,但已有算法在吞吐率和分组平均时延方面与输出排队(OQ)的结果相比,依然不够令人满意,其关键在于OQ交换机可以工作于work-conserving状态。不同于已有的研究,本文提出了以使得交换机最大程度工作于work-conserving状态为目标的新的研究思路,给出并证明了CICQ交换机实现work-conserving状态的充分且必要条件。以此为基础,提出了一种新的CICQ输入调度的算法即交叉缓存队列均衡(CQB)算法,并将经典的最大队长优先(LQF)算法用于输出调度,结合得到CQB-LQF算法。仿真结果显示,与经典的及最新的CICQ分组调度算法相比,CQB-LQF算法显著提高了吞吐率及分组平均时延性能。

Although packet scheduling for combined input-crosspoint-queued （CICQ） switches has been extensively investigated, the performance in terms of throughput and average delay of packets is not satisfied, especially compared to the results obtained by employing output queued architecture. The key reason is that output queneing（OQ） switch can operate in work-conserving state. Different from the popular approaches ap- peared in the literatures, our work focuses on scheduling packet so that the switch works approximately in work-conserving state to the largest extent. First, the sufficient and necessary conditions for the switch with CICQ architecture to work in work-conserving state are investigated and proved. Then, a new CICQ input scheduling algorithm called crossbuffer queue balance （CQB） is put forward, which is combined with the clas- sical longest queue first （LQF） scheduling used for output arbiter to obtain CQB-LQF algorithm. Simulation results show that the performance in terms of throughput and average packet delay obtained by CQB-LQF is much better than the classical and popular algorithms.