一种交叉点小缓存CICQ交换机高性能调度算法  

A High-Throughput Scheduling Algorithm with Small Crosspoint Buffers for CICQ Switches

作　　者：李勇[1] 罗军舟[1] 吴俊[2] 

机构地区：[1]东南大学计算机科学与工程学院,南京210096 [2]扬州大学信息工程学院,扬州225009

出　　处：《计算机研究与发展》2006年第12期2033-2040,共8页Journal of Computer Research and Development

基　　金：国家自然科学基金重大研究计划基金项目(90412014;90604004);高等学校博士学科点专项科研基金项目(20030286014)~~

摘　　要：CICQ(combinedinput crosspoint queued/queuing)结构具有内部无需提速及输入和输出的分组调度可以分布并行执行的优点,使用RR(round robin)算法在高性能交换机设计中具有独特优势·然而,CICQ交换机使用RR算法在非均匀流量下不能达到100%的吞吐率·RR-RR算法在非均匀流量下性能有两个关键因素组成:中央缓存容量大小和输入端长队列未能及时服务导致的服务损失·基于理论分析,提出了一种小缓存高性能调度算法,仿真结果表明,即使在1个信元缓存的情况下新算法在均匀与非均匀流量下均能达到100%吞吐率·新算法仅具有O(1)的复杂度,保持了RR-RR算法简单有效特性,同时克服了RR-RR算法在非均匀流量下的不稳定性·With no internal speed-up required and parallel scheduling at input and output, the CICQ （combined input crosspoint queued） switch architecture using RR （round robin） algorithm provides unique advantage of designing high performance switches. However, it cannot achieve 100% throughput under non-uniform traffic. The performance of RR algorithm under non-uniform traffic comes from two critical factors： one is the buffer capacity of each crosspoint and the other is the service loss. Based the theoretical study, a high-throughput scheduling algorithm with small crosspoint buffers is presented. Simulations demonstrate that the new algorithm can achieve 100% throughput under arbitrary traffic using only one buffer cell in each crosspoint. The new algorithm keeps the high simplicity and efficiency of RR-RR with O （1） complexity while overcoming the instability problem of RR-RR.

关 键 词：CICQ交换机 调度算法 ROUND robin 性能分析 

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