文档介绍：QoS队列调度算法概述
作者：上传时间：2011-04-22 关键字：网络大爬虫4-QoS专题
文常慧锋
【摘要】本文概述了常用队列调度算法的实现机制，并在此基础上对比了基于理想流模型的 WFQ队列算法与其他队列调度算法的公平性能。速率，将数据流累加可得。根据轮换对称性，任意数据流的保证速率 (最小服务速率)为。
GPS算法具有如下特性：
l假设是数据流的平均速率，只要，就可以保证数据流独立于其它数据流的吞吐率。还可以保证数据流的瞬时数据以大于等于的速率被处理。
l由于数据流i在任意时刻获得的服务独立于其他数据流，数据流的时延抖动是自己队列长度和达到时间的函数，独立于其它连接的队列长度和到达时间。其它调度算法如FIFO和PQ 没有这种性质。
l通过改变我们可以以不同的方式处理不同的数据流。例如，当所有的都相同时,GPS就退化为均衡处理器共享(Uniform Processor Sharing)。另外只要数据流的平均速率之和小于，不论怎么分配，系统总是稳定的。
l通过增加就可以减少数据包经历的时延，虽然这种方式是以牺牲其它数据包的时延作为代价的，但是当激活数据流稳定时，这种代价并不是很大。所以GPS算法和速率整形器联合使用时可以得到性能优良的调度器，为数据流提供最坏情况下的时延和时延抖动保证。
u加权公平队列算法(WFQ)
GPS算法最大的缺点是不能处理长度可变的数据包。WFQ算法是GPS算法的近似。假设是数据包在GPS算法中的离开时间，那么WFQ算法就是一个模拟GPS算法并按升序调度数据包的工作保留算法，也就是说WFQ算法总是选择值最小的数据包进行调度。下面介绍 WFQ算法的虚拟时间实现。
假设时间是事件的发生时间(同时发生的事件可以任意排序)，服务器的处理速率为。在服务器中，第一个发生事件的时间记为=0。可以看出在时间间隔(，)内处于激活状态的数据流是固定的，我们将它记为集合。当服务器空闲时，虚拟时间记为0,那么WFQ的计算如下：
的变化率为，每个暂存的数据流接收到的处理速度为。假设数据流的第个数据包的到达时间为，长度为，和分别表示这个数据包的开始虚拟时间和结束虚拟时间,，那么，我们可以得到：
从实现的角度来看，WFQ算法的虚拟时间实现有两个重要优点：
l数据包的完成时间决定于数据包的到达时间和上一个数据包的完成时间；
l数据包根据完成时间升序被处理；
WFQ使用虚拟时间存在的缺点：跟踪集合需要花费很大的开销。
(Virtual Clock)
虚拟时钟算法根据数据包的到达时间和用户定义的保留速率计算数据包的时间戳。假设是数据流的第个数据包的时间戳，是数据流的保留速率，是长度为的数据包的实际到达时间，那么数据包的时间戳定义如下：
如果数据包比预期的到达时间晚，那么经过最大延迟后数据包被传输；如果数据包比预期的
到达时间早，在最坏情况下，数据包被传输的时间为。最坏情况下的服务质量不受其它连接行为的影响。
（Stop-and-Go）
存储转发队列将输入和输出链路的时间轴分为固定长度的时隙'帧”。在两帧之间到达的数据包只能在下一帧中被传输，在同一帧中的数据包可以以任何次序传输，因此每个数据包都被引入一个固定的时延。如果数据包的最大到达速率小