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

《CICQ结构中逼近work-conserving的分组调度算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、2016年11月北京航空航天大学学报November2016第42卷第11期JoumalofBeijingUniversityofAeronauticsandAstronauticsVol·42No·11http：ffbhxb．buaa．edu．cnjbuaa@buaa．edu．cnOOl：10．13700／j．bh．1001—5965．2015．0688CICQ结构中逼近work．conserving的分组调度算法张元昊，熊庆旭+(北京航空航天大学电子信息工程学院，北京100083)摘要：联合输入交叉点排队(CICQ)结构的分组调度算法是一个得到了充分

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

3、算法相比，CQB—LQF算法显著提高了吞吐率及分组平均时延性能。关键词：分组交换；联合输入交叉点排队(CICQ)；work-conserving；调度算法；时延性能中图分类号：TP393文献标识码：A文章编号：1001．5965(2016)11—2481-07互联网技术的发展使得以InternetProtocol(IP)为核心的分组交换网络对传输速度和效率的需求随之加大。而交换机的吞吐率与时延性能作为Besteffort服务的重要指标，直接影响着整个网络的效率和速度。为高性能交换机设计良好的交换结构和调度算法，以提高吞吐率与时延性能，成为一个重要的问题。

4、输出排队(OutputQueueing，OQ)结构由于其work—conserving的特性，具有良好的吞吐率和时延性能，但由于其需要与端口数Ⅳ等量的加速比，可扩展性不足。而输入排队(InputQueueing，IQ)结构的加速比为1，具有良好的可扩展性¨。，但存在信头(Head—of-Line，HoL)堵塞问题旧o。虚拟输出排队(VirtualOutputQueuing，VOQ)结构∞1克服了HoL堵塞问题HJ，但VOQ在调度控制过程中较为复杂，根本原因是输入输出竞争的密切耦合。联合输入交叉点排队(CombinedInput—Crosspoint-Qu

5、eued，CICQ)结构¨1通过在所有交叉节点(crosspoint)上配置一定容量(单个或多个信元)的缓存(crossbuffer)来解耦输入竞争和输出竞争，使得分组调度更有效地进行。本文讨论交叉缓存容量为单个信元(cell)的情况。到目前为止，人们对CICQ结构的调度进行了大量研究，经典算法有输入端采用Round-Robin(RR)或其改进算法的RR—RR∞。、DifferentialRound．Robin(DRR)⋯、TrackingFairQuotaAllo—cation(TFQA)哺。及Round-RobinwithLongestQueueDe

6、tecting(RR—LQD)一1等；以及以队长、交叉缓存占用率、阻塞时间为权重的最大权重匹配法例如LongestQueueFirstandRR(LQF—RR)¨⋯、MostCriticalBufferFirst(MCBF)㈨、ShoaestCrosspointBufferFirst(SCBF)‘121、theShortest收稿日期：2015．10-23；录用日期：2016-01-22；网络出版时间：2016-04-0117：07网络出版地址：WWW．cnki．net／kcms／detail／11．2625．V．20160401，1707．007．ht

7、ml基金项目：国家自然科学基金(61271196)}通讯作者：Tel．：010-82338616E-mail：qxxiong@buaa．edu．cn引用格式：张元吴，熊庆旭．c庀Q结构中逼近work-conserving的分组调度算法ⅣJ．北京航空航天大学学报，2016，42fJl)：2481—2487．ZHANGyH，XIONGQx．Work-conserving—basedpacketschedulingalgorithmforCICQswitchesfJJ．joumalofBeijingUniversityofAeronauticsandAstro

8、nautics，2016，42fJ1)：2481-2487(inChinese)