路由器队列调度机制研究

路由器队列调度机制研究

李 琳

（浙江工业大学，浙江 杭州 310023）

【摘 要】随着计算机技术的告高速发展，因特网规模的不断增大，各种各样的网络服务也越来越多。如视频点播、语音群聊等多媒体实时业务的出现。以及文本页面的浏览，附件数据包的下载等各种不同业务的涌现使得现在网络的负载压力也越来越大。尤其是针对一些实时性业务，对网络传输时延、延时抖动等特性都要求较高。这样更加导致网络负载压力的增大，同时也使得实时业务的服务质量难以得到保证。这就对路由器中的队列调度机制有着很高的要求。本文主要介绍一下传统的路由队列调度机制，以及针对一些特定服务模型如区分服务所提出的队列调度机制的改进进行介绍。

【关键词】视频点播；实时业务；队列调度；区分服务

1 常见路由器队列调度机制

（1）先进先出队列FIFO调度算法

（2）优先级队列PQ调度算法

（3）加权公平队列WFQ调度算法

（4）差值加权轮训队列DWRR调度算法

2 队列调度算法的性能指标

队列调度算法性能的好坏主要涉及到时延性能、公平性、复杂性这三个方面。

时延性能：队列调度算法应为不同的业务流提供端到端的时延保证，而且只与此业务流的某些参数（如带宽需求等）有关，而与其他的业务流无关。Stiliadis 和Varma首先提出了一种分析网络中不同队列调度算法带来的端到端时延的模型；时延速率调度器（LRS：Latency2Rate Server）。Francini随后又提出了另一种分析端到端时延的模型：速率分隔（RST：Rate2Spaced2Timestamp Scheduler），此模型的限制条件比LRS 要少且在定长分组环境下应用时更加有效。

公平性：可用的链路带宽必须以公平的方式分配给共享此链路的各业务流：此外队列调度算法必须能够隔离不同的业务流，让不同的流只享用自己可以享用的带宽，这样即使存在恶意或高突发性业务，它也不致影响到其他的正常业务流。关于算法公平的定义有：服务公平指数（SFI ：Service Fairness Index）和最坏公平指数（WFI ：Worst2case Fairness Index）两种。

复杂性和可扩展性：调度算法实现起来应该比较简单. 在高速网络中，传输一个分组的时间很小，所以调度算法必须在短时间里完成对分组的调度，这就要求调度算法尽量简单，易于实现。 另外当业务流数量增加和链路速率变化范围较大时，调度算法仍应有效工作；这要求调度算法应该具有良好的可扩展性。

3 现有队列调度算法性能比较

3.1 基于轮询的调度算法

传统的轮循（RR：Round Robin） 算法对不同队列（业务流）进行无区别的循环调度服务. 这样，如果不同的队列具有不同的分组长度，则分组长度大的队列可能会比分组长度小的队列接受更多的服务，使队列之间产生不公平的现象；而且，这种算法不能对业务提供时延保证.后来为了改进RR算法，出现了一些改进型的算法。如加权轮询（WRR Weighted Round Robin），差额轮询（DRR Deficit Round Robin），紧急轮询（URR Urgencybased Round Robin）。

3.2 加权公平队列WFQ调度算法

WFQ调度机制是由Demers等人提出，又由Parekh等人实现基于报文的PGPS（packet by packet generalized processor sharing）的排队算法。

WFQ调度机制主要分为基于流的WFQ和基于类的WFQ（CBWFQ）2种。它们的主要区别在于：前者的队列数在理论上没有限制，但队列数目太多会增大调度的复杂度，而后者最多为64个队列。WFQ算法能到达很好的公平性和时延保证，但是系统其系统需时间函数计算复杂度为O（N）（N为总的队列数），且具有较大的WFI，使得输出的突发度增加。它虽然很好的解决了RR机制的不公平性，但是包含了GPS调度机制的局限性，它调度的结果会带来带宽保证和时延保证的耦合性（即低带宽保证总以为着不严格的时延保证），这个特性使得WFQ不适合调度某些类型的业务，这类业务的特点是带宽需求不大，但是有着极严格的时延要求，如语音等实时业务。

3.3 基于时延的调度算法

基于轮询和WFQ的调度算法可以看成是基于速率的调度算法，这种算法通常为每个队列提供一定的速率保证来达到提供时延保证的目的。而基于时延的调度算法则是以（为各队列）直接提供时延保证为目的，这类算法的代表是最早期限优先（EDF，Earliest Deadline First）。

4 基于区分服务的调度算法

区分业务（Diffserv Differentiated Service）体系结构正成为解决因特网上服务质量的一种有效的办法，能支持DiffServ技术的一个子网被称为DiffServ 域，它由一些边缘路由器和域内路由器组成，边缘路由器执行较为复杂的业务流分类、业务量调节及队列管理和调度的功能，而域内路由器则执行较为简单的队列管理和调度的功能。之前介绍的队列调度都没有边缘交换节点和域内交换节点。都是基于每个业务流的调度算法，他们需要交换节点维护每个业务流的一些状态信息，尽管这样可以达到很好的调度性能，但同时带来了不易扩展和不强壮的缺点。

基于这种考虑，Stocia提出了两种新的调度算法：CSFQ（Core Stateless Fair Queueing）和CJVC（Core Jitter Virtual Clock），其核心在于对交换节点进行了“边界交换节点”和“域内交换节点”的区分，从而不需要每个交换节点都维护所有业务流的状态信息。

5 结论

队列调度算法的目的都是以可实现的复杂性为代价来提供更好的服务质量：公平性和时延性能。除了先入先出、优先级和传统轮循调度外，先进的队列调度算法都是把分组放到不同的队列里，然后再为其计算一个时签，根据时签的大小来对分组进行调度. 对于PFQ 算法，其出发点在于为每个队列提供带宽保证（从而时延得到一定的保证） ，所以在其时签的计算中只用到了速率参数和分组长度参数；而基于时延的调度算法，则以提供时延保证为主要目的，所以在其时签的计算中，只引入了队列的时延参数。本文首先介绍了几种传统的队列调度机制的算法如FIFO、PQ、WFQ和DWRR这四种传统的调度算法。然后接下来对队列调度算法的性能指标及几种队列调度算法的优缺点进行了阐述和比较。最后在这些算法的基础上，根据现有的区分服务模型的提出了新的调度机制，并对其进行了改进。总之，未来的队列调度机制一定要适合网络带宽的高速化和业务多样化的发展趋势。首先要保证高的分组调度速度，同时在时延特性和公平性方面有较好的保证。