一种基于最长队列预测的CICQ交换结构调度算法

《一种基于最长队列预测的CICQ交换结构调度算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第32卷第6期电子与信息学报Vol.32No.62010年6月JournalofElectronics&InformationTechnologyJun.2010一种基于最长队列预测的CICQ交换结构调度算法彭来献恽姿赵文栋田畅(解放军理工大学通信工程学院南京210007)摘要：CICQ(CombinedInputCrosspointQueued)是一种在crossbar交叉点加入少量缓存的交换结构，具有无需内部加速比及分布并行调度的特性。为了自适应网络环境中各种业务流量，提高在非均匀流量下的性能，该

2、文提出了一种基于最长队列预测的高效CICQ交换结构调度算法——RR-LQD(RoundRobinwithLongestQueueDetecting)。RR-LQD算法复杂度为O(1)，具有良好的可扩展性；通过预测局部“最长”队列并尽力为其服务，保持调度中队列长度的均衡，能够适应各种非均匀流量的网络环境。仿真结果表明：在各种均匀和非均匀流量下，RR-LQD算法均能达到100%的吞吐量，并且具有优良的时延性能。该文使用FPGA芯片实现了RR-LQD算法仲裁器，能够满足高速、大容量交换结构的设计需要。关键词

3、：调度算法；CICQ；非均匀流量；最长队列预测中图分类号：TP393.05文献标识码：A文章编号：1009-5896(2010)06-1457-06DOI:10.3724/SP.J.1146.2009.00908ANovelSchedulingAlgorithmBasedonLongestQueueDetectingforCICQSwitchingFabricsPengLai-xianYunZiZhaoWen-dongTianChang(InstituteofCommunicationsEnginee

4、ring,PLAUniversityofScienceandTechnology,Nanjing210007,China)Abstract:CICQ(CombinedInputCrosspointQueued)isaswitchfabricwithbuffersincrosspoints,whichbringsitsnicedistributedparallelschedulingpropertywithnointernalspeeduprequired.Inordertoadapttovarious

5、trafficsinthenetworkenvironment,andimproveperformanceundernonuniformtraffics,anovelefficientschedulingalgorithmwithlongestqueuedetecting——RR-LQD(RoundRobinbasedonLongestQueueDetecting)isproposed.RR-LQDprovidesfinescalabilitywiththecomplexityofO(1).Thelo

6、callongestqueuebeingdetectedandservicedallalongguaranteeslengthbalanceamonginputqueues,whichmakesRR-LQDadapttothenetworkenvironmentofnonuniformtrafficautomatically.ThesimulationresultsshowthattheRR-LQDcanachieve100%throughputandlowdelayundervariousunifo

7、rmandnon-uniformtraffics.Inthispaper,thearbiterofRR-LQDisimplementedbyaFPGAchip.ThatprovesRR-LQDcanmeetthedemandsofhigh-speedandlargecapacityswitchingfabrics.Keywords:Schedulingalgorithm;CombinedInputCrosspointQueued(CICQ);Nonuniformtraffic;LongestQueue

8、Detecting(LQD)1引言制。因此，CICQ交换结构具有分布式实现、易扩展的良好特性，是构建高速、大容量、可扩展路由随着近年来VLSI技术的发展，在crossbar的[1]器的理想选择。同时，CICQ交换结构及其调度算交叉点能够植入少量缓存，依据目前的技术条件，法也成为高速交换技术领域近期一个研究热点。国交叉点缓存容量比较小，仍然需要与输入排队结合内外对此进行了大量的研究，文献[2]首次提出了在使用，这就形成了联合输入交叉点排队(CICQ)交换输