路由器队列调度机制研究.pdf

《路由器队列调度机制研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、科技·探索·争鸣Sc科ience&技Tech视nologyPVision．-TT论坛路由器队列调度机制研究李琳(浙江工业大学，浙江杭州310023)【摘要】随着计算机技术的告高速发展，因特网规模的不断增大，各种各样的网络服务也越来越多。如视频点播、语音群聊等多媒体实时业务的出现以及文本页面的浏览．附件数据包的下载等各种不同业务的涌现使得现在网络的负载压力也越来越大尤其是针对一些实时性业务，对网络传输时延、延时抖动等特性都要求较高。这样更加导致网络负载压力的增大，同时也使得实时业务的服务质量难以得到保证。这就对路由器中的队列调度机制有着很高的要求本文主要介绍一下传统的路由

2、队列调度机制．以及针对一些特定服务模型如区分服务所提出的队列调度机制的改进进行介绍【关键词】视频点播：实时业务：队列调度：区分服务1常见路由器队列调度机制杂度为O(N)(N为总的队列数)．且具有较大的WFI，使得输出的突发度增加它虽然很好的解决了RR机制的不公平性．但是包含了GPS(1)先进先出队列FIFO调度算法调度机制的局限性．它调度的结果会带来带宽保证和时延保证的耦合(2)优先级队列PQ调度算法性(即低带宽保证总以为着不严格的时延保证)，这个特性使得WFQ(3)加权公平队列WFQ调度算法不适合调度某些类型的业务．这类业务的特点是带宽需求不大．但是(4)差值加权轮训

3、队列DWRR调度算法有着极严格的时延要求．如语音等实时业务2队列调度算法的性能指标3-3基于时延的调度算法基于轮询和WFQ的调度算法可以看成是基于速率的调度算法．队列调度算法性能的好坏主要涉及到时延性能、公平性、复杂性这种算法通常为每个队列提供一定的速率保证来达到提供时延保这三个方面。证的目的。而基于时延的调度算法则是以(为各队列)直接提供时延时延性能：队列调度算法应为不同的业务流提供端到端的时延保保证为目的．这类算法的代表是最早期限优先(EDF．EarliestDeadline证，而且只与此业务流的某些参数(如带宽需求等)有关，而与其他的业First)。务流无关Sti

4、liadis和VaIma首先提出了一种分析网络中不同队列调度算法带来的端到端时延的模型：时延速率调度器(LRS：Latency2Rate4基于区分服务的调度算法Server)。Francini随后又提出了另一种分析端到端时延的模型：速率分区分业务(DiffservDifferentiatedService)体系结构正成为解决因特隔(RST：Rate2Spaced2TimestampScheduler)．此模型的限制条件比LRS网上服务质量的一种有效的办法．能支持DifServ技术的一个子网被要少且在定长分组环境下应用时更加有效称为DiffSew域。它由一些边缘路由器和域

5、内路由器组成．边缘路由器公平性：可用的链路带宽必须以公平的方式分配给共享此链路的执行较为复杂的业务流分类、业务量调节及队列管理和调度的功能，各业务流：此外队列调度算法必须能够隔离不同的业务流。让不同的流而域内路由器则执行较为简单的队列管理和调度的功能。之前介绍的只享用自己可以享用的带宽，这样即使存在恶意或高突发性业务，它也队列调度都没有边缘交换节点和域内交换节点。都是基于每个业务流不致影响到其他的正常业务流。关于算法公平的定义有：／R务公平指数的调度算法．他们需要交换节点维护每个业务流的一些状态信息．尽(SFI：ServiceFairnessIndex)和最坏公平指数r

6、WFI：Worst2caseFairness管这样可以达到很好的调度性能．但同时带来了不易扩展和不强壮的Index)~种。缺点。复杂性和可扩展性：调度算法实现起来应该比较简单．在高速网基于这种考虑．Stocia提出了两种新的调度算法：CSFQ(C0reStateless络中传输一个分组的时间很小．所以调度算法必须在短时间里完成对FairQueueing)和CJVC(CoreJitterVirtualClock)，其核心在于对交换节分组的调度，这就要求调度算法尽量简单易于实现另外当业务流点进行了“边界交换节点”和“域内交换节点”的区分．从而不需要每个数量增加和链路速率变化

7、范围较大时调度算法仍应有效工作：这要求交换节点都维护所有业务流的状态信息调度算法应该具有良好的可扩展性3现有队列调度算法．眭能比较5结论队列调度算法的目的都是以可实现的复杂性为代价来提供更好3．1基于轮询的调度算法的服务质量：公平性和时延性能。除了先人先出、优先级和传统轮循调传统的轮循(RR：RoundRobin)算法对不同队列务流1进行无区度外。先进的队列调度算法都是把分组放到不同的队列里然后再为其别的循环调度服务．这样，如果不同的队列具有不同的分组长度，则分计算一个时签根据时签的大小来对分组进行调度．对于PFQ算法．其组长度大的队列可