基于输入队列的调度算法及其稳定性证明  

Input-queued Schedule Algorithm and Its Stability Proof

作　　者：王景存[1] 谢馨艾[1] 王沁[1] 樊勇[1] 刘兰军[1] 

机构地区：[1]北京科技大学信息工程学院,北京100083

出　　处：《计算机工程》2007年第22期130-133,157,共5页Computer Engineering

基　　金：中科院计算所知识创新工程"HPC-OG"模拟系统及相关技术研究基金资助项目(20036040)

摘　　要：当前高速交换机和路由器广泛采用iSLIP算法作为其输入队列的调度算法,但是该算法在处理非均匀和突发业务时性能严重恶化。该文在iSLIP算法的基础上提出了一种流量自适应的时隙间迭代算法TA-iSLIP。该算法根据队列长度智能判断当前流量情况,采取不同的发送策略,充分利用已经匹配的资源,使系统的匹配开销尽可能减小。仿真结果表明,TA-iSLIP在各种流量下都达到了较好的性能。文章给出了TA-iSLIP的算法描述和性能评价,并与iSLIP算法、FIRM算法以及EDDR算法进行了比较,证明了该算法在可接受的流量时的稳定性。iSLIP schedule algorithm is widely employed in high performance switches and routers, but its performance decreases dramatically Under non-uniform and burst traffics. Based on iSLIP algorithm, this paper proposes a traffic adaptive algorithm named TA-iSLIP, which iterates the Schedule decision between slots. ~To make good use of the matched resources and decrease the system matching overhead, it intelligently estimates the traffic type by using queue length, and then adopts different processing methods accordingly. Simulation results show that TA-iSLIP achieves high performance under uniform and non-uniform traffic. It provides the description and performance evaluation of TA-iSLIP, and compares it with iSLIP, FIRM and EDDR, The stability proof of TA-iSLIP is proposed.

关 键 词：iSLIP TA—iSLIP 调度算法 时隙间迭代 

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