通用高速分组交换调度算法

《通用高速分组交换调度算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第39卷第1期电子科技大学学报Vol.39No.12010年1月JournalofUniversityofElectronicScienceandTechnologyofChinaJan.2010·计算机工程与应用·通用高速分组交换调度算法王俊芳，张思东(北京交通大学电子信息工程学院北京海淀区100044)【摘要】在iSLIP算法的基础上，应用二部图匹配中对角线数据无竞争的数学原理，采用关联指针的处理方法，提出了一种基于虚拟输出排队(VOQ)缓冲模式下的高速交换调度算法——迭代的关联指针轮转(i-CPRR)算法。该算法简化

2、了指针的轮转方式，降低了设计难度。仿真表明，该算法减少了调度过程中的迭代次数，提高了算法在高负载条件下的带宽利用率，从而降低了交换系统的数据延时和VOQ队列深度，在高速交换系统中具有广泛的应用价值。关键词i-CPRR算法;iSLIP;匹配;分组交换;调度算法;虚拟输出排队中图分类号TP393.07文献标识码Adoi:10.3969/j.issn.1001-0548.2010.01.017High-SpeedPacketSwitchingSchedulingAlgorithmWANGJun-fangandZHANGSi-don

3、g(SchoolofElectronicsandInformationEngineering,BeijingJiaotongUniversityHaidianBeijing100044)AbstractOnthebasisofiSLIP(iterativeslip)algorithm,aVOQ(virtualoutputqueuing)basedhighspeedswitchingschedulingalgorithm,i-CPRR(iterative-correlativedpointerround-robin)algor

4、ithmispresented.Inthisalgorithm,themathprincipleofuncontesteddiagonaldatainbipartitegraphsmatchingisutilizedandthecorrelativepointerprocessingmethodisadopted.Thisalgorithmsimplifiestheround-robinmodeofthepointerandreducesthedesigndifficulty.Thesimulationresultsshow

5、thatthealgorithmdecreasestheiterativetimesintheschedulingprocedure,improvesthebandwidthutilizationunderheavyload,reducesthetimedelayandthedepthofVOQqueueintheswitchingsystem.Ithaswideapplicationprospectiveinhighspeedswitchingsystems.Keywordsi-CPRRalgorithm;iSLIP;ma

6、tching;packetswitching;schedulingalgorithm;virtualoutputqueuing随着Internet的高速发展，高速交换系统中服务入排队的调度算法，交换架构采用Crossbar的交换架[1]质量已成为网络发展的核心技术和热点问题之一。构或多平面级联(MPMS)的交换结构。MPMS可以服务质量控制是指网络能够提供有保证的、可控制很好地解决交换容量的扩展问题，但其调度问题非的、可预测的数据传输服务，满足不同用户的应用常复杂，对于高速率和多端口的MPMS是难以实现[2]需求。对服务质量

7、的要求不仅体现在民用市场，在的。调度CRRD算法不需要内部加速即可在均匀流一些特殊应用场合，如军事、航天等领域的表现更量下获得100%的吞吐率，但在非均匀流量下仅能获[3-4]加突出。得63%的吞吐率。基于Crossbar交换架构的调度分组调度是实现网络服务质量控制的基础，通算法很多，以指针滑动多次迭代循环优先级匹配过控制不同类型的分组对链路带宽的使用，可以使(iSLIP)算法应用最为广泛，但它在应用中仍有许多不同的数据流得到不同等级的服务。在IETF提出的需改进之处。综合服务(Int-serv)框架中，保证服务可为单个流提

8、基于VOQ输入缓冲的交换调度算法—迭代的关供有严格端到端时延和低分组丢失率的电路型服联指针轮转(i-CPRR)算法，属于无权重二部图匹配务，这种服务需要在路由器中实现基于流的加权服算法，它充分应用了二部图匹配中对角线上数据无务公平调度。目前常用的调度方法多是基于VOQ输竞争的数学原理，采用