（计算机系统结构专业论文）基于网络处理器的队列管理和队列调度算法的研究.pdf

摘要 摘要 随着计算机网络的发展，人们对网络的服务质量的研究非常活跃，涉及到的 关键技术包括资源分配和业务控制。本文主要研究网络处理器中的队列管理和 队列调度算法。队列管理是对处理器中的缓冲资源进行管理和分配，而队列调 度是对链路带宽进行管理和分配。本文的主要工作和研究内容如下： 1 研究分析了现有的队列管理和队列调度算法。大部分的队列管理算法都以 r e d 算法为核心思想，包括s r e d 和b l u e 算法，他们的不同在于用不同的方法来 估计网络的拥塞状况并以之为依据来计算丢包率。调度算法的本质是从有多个 对象的集合中选择一个合适的对象进行服务，而关键在于如何确定合适的对象 和为对象服务的时间。 2 研究了现有的队列算法的评价方法并进行了部分改进。由于队列算法要满 足延时、吞吐率、等多重目标，因此不同的评估方法也各有侧重。新的评估方 法考虑了缓冲队列的资源限制问题，使其更加具有可操作性，同时它也是本文 算法设计的主要依据。 3 提出了一个队列管理和队列调度结合的算法并完成仿真实验。在队列管理 和队列调度结合的数学模型中，队列的管理和调度是一个机制的两个步骤，两 者之间具有对应的数学关系，因而把两者归结为一个最优化决策的问题，给出 了最优解，使系统的吞吐量和分组延迟的综合性能最优。大量仿真实验的结果 表明，新的算法在效果上优于当前最常用的r e d 和r r 算法，同时算法的复杂度 为0 ( n ) ，与以g p s 模型为目标的大多数调度算法相同。 关键词：服务质量队列管理队列调度结合算法延时吞吐量公平性 a b s t r a c t a b s t r a c t w i t ht h ed e v e l o p m e n to fc o m p u t e rn e t w o r k s ，t h er e s e a r c ho fn e t w o r ks e r v i c e q u a l i t yi sv e r ya c t i v e ，r e s o u r c ea l l o c a t i o na n do p e r a t i o n a lc o n t r o la r ek e yt e c h n o l o g i e s t h em a j o rs t u d yo ft h i sp a p e ri sq u e u em a n a g e m e n ta n dq u e u es c h e d u l i n ga l g o r i t h m s q u e u em a n a g e m e n to p e r a t e sa n da l l o c a t e st h eb u f f e rr e s o u r c e so ft h ep r o c e s s o r ，a n d q u e u es c h e d u l i n ga l l o c a t e sn e t w o r kb a n d w i d t h sf o re v e r yq u e u e t h em a i nw o r ka n d s t u d yo ft h i sp a p e ra r e ： 1 w er e s e a r c ha n da n a l y s i sa l m o s tp r e s e n tq u e u em a n a g e m e n ta n ds c h e d u l i n g a l g o r i t h m s ，f o re x a m p l e ，t h ec o r ei d e ao fs r e da n db l u ea l g o r i t h m sa r ef r o mr e d a l g o r i t h m ；t h ed i f f e r e n c ei st h a tt h e yu s ed i f f e r e n tm e t h o d st oe s t i m a t et h en e t w o r k c o n g e s t i o ns i t u a t i o na n db a s i n go nt h ed i f f e r e n te s t i m a t et h e yc a l c u l a t et h ep a c k e t d r o p p i n gr a t e s t h ee s s e n c eo fq u e u ea l g o r i t h mi st h a tw em u s ts e r v i c ea na p p r o p r i a t e o b j e c tw h i c hi sc h o s e nf r o mao b j e c ts e t ，b u tt h ek e yi sh o ww ei d e n t i f ys u i t a b l e o b j e c ta n dd e t e r m i n es e r v i c et i m et h a te v e r yq u e u eg e t 2 w er e s e a r c hp r e s e n te v a l u a t i o nm e t h o d so fq u e u ea l g o r i t h ma n di m p r o v ei t p a r t l y s i n c et h eq u e u es c h e d u l i n gm u s tm e e tm u l t i p l et a r g e t s ：d e l a y ，t h r o u g h p u t ， d r o p p i n ga n de t c ；s od i f f e r e n te v a l u a t i o nm e t h o d sf o c u so nd i f f e r e n tt a r g e t o u rn e w e v a l u a t i o nm e t h o dc o n s i d e r st h ec o n s t r a i n to ft h eb u f f e rt om a k ec r i t e r i o nm o r e w o r k a b l e ，a n di ti st h ep r i m a r yi d e af o rt h ea l g o r i t h md e s i g n i n go ft h ep a p e r 3 t h i sp a p e rp r e s e n t sa na l g o r i t h mt h a ti n t e g r a t e st h et w ok i n d so fq u e u e m e c h a n i s ma n dc o m p l e t e ds i m u l a t i o ne x p e r i m e n t s i nt h em a t h e m a t i c a lm o d e l so f q u e u em e c h a n i s m ，q u e u em a n a g e m e n ta n ds c h e d u l i n g a r et w o s t e p s ，t h e r e a r e c o r r e s p o n d i n gm a t h e m a t i c a lr e l a t i o n s h i pb e t w e e nt h e m t h e r e f o r e ，w ec a nc o n s i d e r t h e ma sa no p t i m a ld e c i s i o np r o b l e m ，a n dt h e ng i v eam a t h e m a t i c a lo p t i m i z a t i o n s o l u t i o n ，t h er e s u l ti st h a tw ec a ng e tt h eb e s tt r a d e o f fb e t w e e nt h r o u g h p u ta n dd e l a y m a s s i v es i m u l a t i o ne x p e r i m e n t ss h o wt h a tt h ep e r f o r m a n c eo fn e wa l g o r i t h mi s e n h a n c e dn e a r l y2 0 c o m p a r e dt ot h et r a d i t i o n a la l g o r i t h m a tt h es a m et i m et h e ab s t r a c t c o m p l e x i t yo fn e wa l g o r i t h mi s0 ( n ) ，a n di ti se q u a lt ot h es c h e d u l i n ga l g o r i t h m s w h i c hg o a l i sg p sm o d e l 一 k e yw o r d s ：q u a l i t yo fs e r v i c e ，q u e u em a n a g e m e n t ，q u e u es c h e d u l i n g ，i n t e g r a t e d a l g o r i t h m ，d e l a y ，t h r o u g h p u t ，f a i rq u a l i t y 第一章绪论 1 1 研究背景及意义 第1 章绪论 1 1 1 网络处理器简介 网络处理器【1 1 由两类硬件功能单元组成，即网络处理器单元和专用的智能协 处理器3 n 速器。网络处理器运行的软件是经过优化的，支持系统级应用和网络专 有功能。网络处理器单元是网络处理器核心，它提供高速、大容量智能处理数据 包功能，包括数据解析、分类和转发等等，因此网络处理器单元常常被称为数据包 处理引擎。不同的协处理器则实现帧的分段重组、加速查表、队列缓冲区管理、 顺序管理、存储器控制和多播支持等功能。 网络处理器的典型功能【2 j 有： 分段和重组：为转发而进行的数据帧分段、处理和重组。 协议识别和分类：根据数据帧内的协议类型、端口号、目的u r l 或其他应用 或专用协议信息来识别每一数据帧。 排队和存取控制：数据帧一经识别就根据一定的策略被放入合适的队列待作 进一步处理( 例如划分优先级或流量整形) 。同时，根据流量控制和安全存取 策略规则检查数据帧，判断转发或丢弃。 流量整形和流量工程：一些协议或应用需要该功能，当有突发数据流到达出 口或光纤时，要对数据流整形。可以规定不同信道或信息类型的数据流的优 先级来满足不同的服务要求。 服务质量：除了用适当的流量整形和输出调度来保证q o s 外，数据帧还可以 打上标记以被网络中其他设备作快速处n ( n ! z n8 0 2 1 或i p t o s ) 。 图1 1 说明了数据包在n p 中的大致流程。n p 周期性检测m a c 收到的数据 包，然后存入接收队列( i u i f o ) 【3j ，再进行分类、过滤，丢弃某些包；然后将包 分成固定大小的段，存入数据队列存储器；在存入之前，还要进行拥塞管理。 之后通过内部总线，读出数据包进行路由查找、队列管理等一系列操作，或者 第一章绪论 由微引擎实现安全算法等等。最后再从存储器读出段，各段重组成数据包，缓 冲到输出队列再被调度发送出去。 图卜1 ：数据包在n p 中的大致流程 1 1 2 队列管理和调度算法的研究意义 队列管理在网络中传输控制中发挥着相当大的作用，是网络服务质量( q o s ) ”j 控制的核心技术之一，也是实现网络拥塞控制的重要手段。就单个网络传输节 点而言，其控制目标在于解决输出链路的带宽资源分配问题，把有限的资源公 平而有效地分配给不同地服务类别( 数据流等) 。而在众多网络传输节点构成传输 网的基础上，网络传输控制需要整合，规划所有的带宽资源的使用，为用户提 供端到端的有服务质量保障的网络传输服务，这也就是q o s 控制目标。 带宽资源的分配在网络传输节点上主要通过基于多个队列的分组调度( 队列 调度) 机制来实现。虽然队列管理机制直接涉及到的是单个节点中的队列缓冲资 源，直接影响到的也只是分组丢失率性能，然而对整个系统带宽分配的性能有 着重要的影响：( 1 ) 合理的系统队列缓冲容量，对于平衡系统吞吐量和分组排队 延时起着至关重要的作用：( 2 ) 在多队列情况下，缓冲资源在不同队列( 服务类别) 之间的分配只有在与输出带宽的分配相互一致时，才能获得最佳的缓冲效果。 因此，现在一些研究者把传统上相互独立、缺乏联系的队列管理机制和队列调 度机制相结合，研究更优的资源分配方案，以期获得更优的系统性能。如何与 分组调度机制有效配合，解决网络带宽资源的有效、公平分配问题，是队列管 理机制设计的关键。 第一章绪论 早期的计算机网络中并没有网络传输控制的概念，网络传输节点采用先进先 出队歹；t j ( f i r s ti nf i r s to u t ，f i f o ) 配合尾部丢弃的队列控制策略对到达的数据分组 排队。1 9 8 6 年，计算机网络遭遇了历史上大的第一次拥塞崩溃( c o n g e s t i o n c o l l a p s e ) ，从伯克利到l b l 的链路有效网络流量从3 2 k b p s 降到4 0 b p s ，下降了近 1 0 0 0 倍。从那时起人们开始研究解决网络拥塞问题的机制和方案。 最早的拥塞控制机制出现在t c p 协议中，由网络用户根据丢包、超时等现 象来判断网络是否出现拥塞，并采用慢速启动和拥塞避免算法来调整自己的数 据发送速率，缓解传输网络的压力。随着显示拥塞通告( e x p l i c i tc o n g e s t i o n n o t i f i c a t i o n ，e c n ) l 【5 j 和主动队列管理( a c t i v eq u e u em a n a g e m e n t ，a q m ) 6 1 的思想的 提出，拥塞控制不再只是网络用户的责任，在网络的传输节点中也引入了拥塞 控制的机制。 与队列管理一样，队列调度也是系统资源管理的核心机制，是解决多个业务 竞争共享资源问题的有效手段，它对链路带宽进行管理，按照一定的规则来解 决从等待队列中选择哪个分组进行发送，使得所有的输入业务流能够按照预定 的方式共享输出链路带宽。队列调度算法的优劣直接影响到吞吐率、时延、时 延抖动等网络的主要性能参数。 图1 2 给出了采用输出输入队列结构网络处理器的分组流程。通常情况下， 队列结构放在输出端，队列管理机制位于队列的输入端，负责管理系统中缓冲 资源的分配，根据系统策略和到达分组的信息来决定是否允许其进入队列，而 在队列的输出端，则有队列调度机制负责带宽分配和延迟调整，两者互相配合 完成完整的队列操作。而在队列操作机制之前，根据系统采取的策略和控制算 法，可以辅助以分组分类、流量整形调节等机制来配合队列管理机制的要求。 第一章绪论 图1 - 2 ：具有q o s 支持的输入输出排队网络处理器中的分组处理流程| 7 1 2 研究现状 f l o y d 等人提出的随机早期检n i j ( r a n d o me a r l yd e t e c t i o n ，r e d ) 8 】算法，是 最早的一种主动队列管理算法。它不是等队列满b , - t 刁一丢弃分组，而是在队列长 度达到一定值时就按一定概率来丢弃。丢弃概率随着队列长度的增加而增大。 r e d 试图用一种“提前通知”的手段来避免网络进入拥塞的状态，从而提高网 络的性能。虽然r e d 算法的性能对参数十分敏感，但是在某些情况下仍然会造 成队列的振荡【9 】，后来的研究者提出了很多r e d 的改进算法，如s r e d ，f r e d ， b l u e 等。这种通过一定概率丢弃数据包来“提前通知”源端改变发送速率的方 法成为后来几乎所有a q m 算法的核心思想。不同的a q m 算法主要区别就在于 用不同的方法来估计网络的拥塞状态，并计算丢包率。目前a q m 主要通过两种 参数估计网络的拥塞状态：平均队列长度和平均包到达率。比如：r e d 及其改 进算法都是根据平均队列长度来计算丢包概率的：而a e ，a v q ( a d a p t i v ev i r t u a l q u e u i n g ) 等算法则是利用到达率来更新一个虚拟链路( v i r t u a ll i n k ) 的带宽，从而 决定丢包概率。s a n j e e w a 等人提出的r e m ( r a n d o me x p o n e n t i a lm a r k i n g ) 算法由 于同时采用了队列长度和到达率这两种参数来计算丢包概率，因而取得了更好 的效果，但由于步长固定，使得队列长度在目标值附近仍然有较大幅度的振荡。 2 0 0 0 年v i s h a lm i s r a 等研究者提出了t c p 的非线性模型后，该模型成为分析和 设计a q m 控制器的主要方法，h o l l o t 分析了r e d 的稳定性【10 1 ，并为a q m 设 计了比例积分( p r o p o n i o n a l i n t e g r a t o r ，p i ) 控制器j ，仿真显示，p i 与r e d 相比的 第一章绪论 确增强了队列的控制能力，但是其参数严重依赖于网络环境，比如连接数目、 往返时i b - ( r o u n dt r i pt i m e ，r t t ) 1 2 j 等，这使得p i 控制器不能适应动态变化的网 络环境，健壮性较差。 队列调度算法的研究一直是一个热门课题，到目前为止，产生的算法已经 有了几十种，分别有着不同的控制目的和复杂度。有些综述性的文章对常用算 法进行了归类。但是，对于一种调度算法根据不同的归类规则，可以属于多个 不同类别，应此并没有统一的归类标准。一般根据队列调度算法的本质，根据 工作原理和控制目标会把算法归为以下几类：基于静态优先级、基于轮循、基 于g p s ( g e n e r a l i z e dp r o c e s s o rs h a r i n g ) 模型的p f q 算法、基于时延、分层链路共 享的算法、比例区分算法，结合缓冲管理的算法等。 1 3 论文的主要工作 与本文相关联的课题研究的主要成果有： 研究并分析了现有的队列管理和队列调度算法。 研究了现有队列算法的评估方法并给出了一个改进的评估方法。 给出了一个队列管理和队列调度算法结合的数学模型。 提出了一个队列管理和队列调度结合的算法并完成仿真实验。 1 4 论文组织 本文各个章节的主要内容如下： 第一章介绍课题研究背景、课题研究的意义、论文成果及组织结构。 第二章研究了目前的队列管理和调度算法，并对算法进行详细分析。 第三章研究了目前的队列算法的目标及控制策略并改进了部分评估方法。 第四章研究了一种队列管理和队列调度结合的方法，提出了一种新的算法并 进行实验验证。 第五章是全文总结和未来工作展望。 第二章队列管理及调度算法 第2 章队列管理及调度算法研究 t c p 端到端的拥塞控制机制是确保计算机网络健壮性的重要因素。在发生 拥塞时，t c p 源端会降低发送数据的速度，从而使得大量的t c p 连接能够共享 一条拥塞的链路。t c p 拥塞控制机制的有效性依赖于两个基本的假设：( 1 ) 所有( 或 者几乎所有) 的流都采用了拥塞控制机制( 2 ) 这些流采用的机制是同质的或者大 体上相同即在相似的环境下按可比条件( 丢包率、r t t 、m t u ) 不会占用比t c p 流更多的带宽，也即是t c p 友好的( t c p f r i e n d l y ) 流。 但随着近二十年来计算机网络的爆炸式增长，计算机网络已经不可能再仅 仅依靠端节点提供的拥塞控制机制。这是因为：( 1 ) 一些应用没有采用拥塞控制 机制因而不能对拥塞做出反应。许多多媒体应用和组播应用都属于这种情况。( 2 ) 有些应用使用了拥塞控制算法，但并不是t c p 友好的，比如接受端驱动分层组 播( r e c e i v e r d r i v e nl a y e r e dm u l t i c a s t ，r l m ) 采用的就是这种算法。( 3 ) 一些用户由 于有意或无意的原因，使用了n o n t c p 的拥塞控制算法。比如修改t c p ，使得 窗口的初始值很大并且保持不变，即所谓的“快速t c p ”0 3 】。另外，计算机网 络上的流量是由无数条异质的数据流混合而成的。从是否有有效拥塞控制机制 的角度可以将这些异质的流分为以下三类：t c p f r i e n d l y 流、适应流、非适应 流；非适应流：这种流是由于上述原因( 1 ) 造成的；适应流是由于上述原因( 2 ) 和 ( 3 ) 引起的。这些不受t c p 拥塞控制的应用会进一步增加计算机网络拥塞崩溃的 可能，并且t c p 拥塞控制还存在着效率、公平性等方面的问题。因此要在网络 的中间节点采用拥塞避免机制，队列管理算法就是其中的核心部分。 队列调度算法也工作在网络中发生冲突需排队等待调度的节点上，它按照 一定的服务规则对交换节点的不同输入业务流分别进行调度和服务，使所有的 业务流能按预定的方式共享交换节点的输出链路带宽。输入业务到达交换节点 后分别暂存到相应的队列中，假设共有n 个队列，队列调度算法的任务是如何 从这n 个队列中选择下一个要传输的分组。至于不同的业务流对应到不同的队 列是业务流分类算法的工作，业务流的分类有很多标准，较为复杂的分类算法 第二章队列管理及调度算法 都是按照 【1 4 】中的子集进行划 分。 队列调度算法一直是一个比较热门的方向，目日，j 已经有几十种算法，根据 不同的服务规则，队列调度算法可以分为以下几类：基于静态优先级的算法， 基于轮循的算法，基于g p s ( g e n e r a l i z e dp r o c e s s o rs h a r i n g ) 模型的算法，基于时 延的算法，基于服务曲线的算法，结合缓冲管理的算法等。下面对主要的算法 进行研究和分析。 2 1 r e d 类算法分析 随机早期检测算法( r a n d o me a r l yd e t e c t i o n ，r e d ) 的基本思想是通过监控输 出端口队列的平均长度来探测拥塞，一旦发现拥塞逼近，就随机地选择链接来 通知拥塞，使他们在队列溢出导致丢弃分组之前减小拥塞窗口，降低发送数据 速度，从而缓解网络拥塞。由于r e d 是基于f i f o 队列调度策略的，并且只是 丢弃正进入队列的数据分组，因此其实施起来也较为简单。 r e d 主要试图达到以下目标：最小化分组丢失率和排队延迟，避免全局同 步现象，避免对突发业务的偏见。网络中含有大量的突发数据，而传统的“去 尾”算法对突发业务有很大的偏见。在采用“去尾”算法的时候，如果某个流 的突发性越高，则当该流的分组进入队列时越容易造成队列溢出，从而导致连 续地丢弃大量的该流的分组。为了达成以上目标，r e d 采用了基于时间的平均 队列长度，并且随机地选择正进入队列的分组进行丢弃。这种方法能被有效地 实施而无需维持每个流( p e r f l o w ) 的状态信息。 2 1 1 r e d 算法 1 r e d 算法的计算步骤 r e d 算法主要分为两个部分【l 川。首先是计算平均队列长度，以此作为对拥 塞程度的估计。然后是是计算丢弃包的概率。 ( 1 ) 一个队列很多时候是空的，然后迅速被充满，又很快被取空，这时并不 能说发生了塞。因此，r e d 在计算平均队长a v g q 时，采用了带权值的方法： 第二章队列管理及惆度算法 a v g q = ( 1 一w ) x a v g q + q x w ( 2 1 ) 其中，w 为权值，q 为采样测量时实际队列长度。这样由于网络数据的突发 本质或者短暂拥塞导致的实际队列长度暂时的增长将不会使得平均队长有明显 的变化，从而”过虑”掉短期的队长变化，尽量反映长期的拥塞变化。 在计算平均队长的公式中，权值w 为日, - t l 、司常数，它决定了算法对输入流量 变化的反应程度。因此对w 的选择非常重要，如果w 过大，那么r e d 就不能有 效地过虑短暂的拥塞；如果w 太小，那么a v g q 就会对实际队列长度的变化反应 过慢，不能合理地反映拥塞状况，在这种情况下，算法就不能有效检测到早期 的拥塞。w 的值应根据不同情况预先设置，一般来说，它是由允许发生的突发业 务量大小和持续的时间所决定的。 ( 2 ) 平均队长的目的就是为了反映拥塞状况，根据拥塞的程度来计算丢弃包 的概率，从而有效地控制平均队列长度。 r e d 有两个和队列长度相关的阈值：m i n t h 和m a x t h 。当有包达到路由器时， r e d 计算出平均队长a v g q 。若a v g q 小于m i n t h ，则没有包需要丢弃；当 m i n t h m a x t h ) 或者 长时连续随机地标记包( a v g q f r e e z et i m e ) p m = p m d 2 ； l a s t _ u p d a t e2n o w ； u p o np a c k e tl o s se v e n t ： i f ( ( n o w l a s t _ u p d a t t e ) f r e e z e t i m e ) p m = p m + d 1 1 a s tu p d a t e = p l o w ； b l u e 地主要参数有d 1 、d 2 和f r e e z et i m e 。其中，d i 决定了当队列溢出时 p m 增加的量，d 2 决定了当链路空闲时p m 减少的量。f r e e z et i m e 决定了连续改 变p m 的最小时间间隔，使得p m 改变之后在再次变化之前能有效发挥作用。 般来说，d 1 要比d 2 大很多，这主要是因为当拥塞管理太保守或太激进时，都会 导致链路使用率很低：而丢包只发生在拥塞管理太保守时。这样，通过赋予丢 包事件更大的比重，b l u e 能够对流量大量迅速地增加很快地做出反应。 b l u e 最大地贡献在于，使用相对较小地缓冲区就能够完成拥塞控制。这样， b l u e 减少了端到端延迟，提高了t c p 流的吞吐量。另外，较小的缓冲区需求 也使得路e t f a 有更多的自由空间来执行其他的路由器功能，比如存储更大的路 由表，从而提高了路由器的性能。而要达到类似的效果，r e d 则需要大很多的 缓冲区。 b l u e 基于丢包事件和链路空闲事件的拥塞管理，能够较好地估计拥塞程 第二章队列管理及调度算法 度，从而作出适当的反应。因此其标记包地比率相对较稳定，这又使得队长也 相对稳定，减少了延迟抖动。而r e d 基于平均队长地拥塞管理，由于不能正确 及时地估计拥塞严重性，特别是在负荷很重，变化很快的情况下，常常导致队 长波动很大。增加了丢包数和延迟抖动，甚至产生全局同步现象，降低链路使 用率。 ： 2 2 2 随机公平b l u e ( s t o c h a s t i cf a i rb l u e ，s f b ) 现在，越来越多的应用不采用t c p 的拥塞控制机制，这些流会对适应流带 来很大地影响，甚至在竞争带宽时使它们陷入”饥饿”。因此必须对适应流进行保 护。 s f b 1 8 】的基本思想就是采用记帐的方法鉴别非适应流并对它们进行速度限 制。s f b 持有一些用于记帐的“柜子”( a c c o u n t i n gb i n s ) 。这些柜子以l 层，每 层n 个的形式组织起来。另外，s f b 拥有l 个独立的h a s h 函数，每个函数和一 层柜子相关联。每个h a s h 函数将一个流映射到该层的一个柜子。每个柜子有一 个标记包的概率p m ，此概率是基于队列占用的。如果映射到某个柜子的包的数 量超过了一定的阈值，则该柜子的p m 便会增加：如果该柜子中包的数量降为0 ， p m 便会下降。s f b 取该包所映射到的l 个柜子的标记包概率的最小值p m i n ， 如果该值为l ，就认为该包所属的流是非适应流，从而对其限速。否则以p m i n 的概率来标记包。s f b 算法如下所示： b 【l 】 n ：l ，na r r a yo f b i n s f o re a c hp a c k e ta r r i v a l ： c a l c u l a t eh a s hf u n c t i o nv a l u e sh o ，h i ，h u 1 ； u p d a t eb i n sa te a c hl e v e l f o ri = ot ol 1 i f ( b i h i q l e n b i n s i z e ) b i h i 】p m + = d e l t a ； d r o pp a c k e t ； e l s ei f ( b i h i q l e n2 = 0 、 第二章队列管理及调度算法 b i h i p m 一= d e l t a ； p m i n = m i n ( b o h o p m b l 】 h l 】p m ) ； i f ( p m i n = = l 、 r a t e l i m i t ( ) ； e l s e m a r k d r o pw i t hp r o b a b i l i t yp m i n ； s f b 鉴别非适应流地原理在于，此类流会迅速地使其所映射到的l 个柜子 的标记概率增加到1 。即使适应流会和非适应流共享一、两个柜子，但除非非适 应流的个数比柜子的个数多很多，适应流总会被h a s h 函数映射到至少有一个 口口口口 图2 - 1 ：s f b 不意图 柜子没有被非适应流“污染”过，该柜有一个正常的概率p m 。因此，适应流最 终得到的标记包的概率p m i n 往往总是小于1 。从而鉴别出适应流和非适应流( 如 图2 1 所示) 。s f b 能够在非适应流不是很多时，将其精确地鉴别出来，而不会 影响适应流的性能。但当非适应流的数量增加时，被非适应流”污染”的柜子也就 大大增加，从而增加了适应流被鉴别为非适应流的可能性。 解决这个问题地方法是采用移动h a s h 函数( m o v i n gh a s hf u n c t i o n s ) 。其基本 思想是周期性地或随机地重新设置柜子并更改h a s h 函数。因为无论使用什么 h a s h 函数，非适应流总是能被鉴别出，而被鉴别为非适应流地适应流就有可能 被重新映射到至少一个没被“污染”地柜子。这种方法有些类似于c d m a 系统 中的信道跳转。但用这种方法，在更改h a s h 函数和重置柜子期间，非适应流会 有如被“假释”一样消耗更多地带宽。解决此问题地一个方法是使用两套柜子。 第二章队列管理及调度算法 当一套柜子正在进行队列管理时，第二套使用另一组h a s h 函数地柜子就作“准 备活动”。当某个流被鉴别为非适应流时，更改第二套柜中相应柜子标记包的 概率，然后使用第二套柜子进行鉴别。从而大大减少了适应流被错误鉴别地可 能性。 2 2 3 b l u e 和s f b 的不足 ( 1 ) 由于发生丢包事件后b l u e 会相对大地增加丢包地概率，从而会产生连续 丢包，导致t c p 陷入超时，严重时会降低链路利用率。 ( 2 ) 参数f r e e z et i m e 的设置问题。如果f r e e z et i m e 太小，会导致p m 的变化 过于频繁，使得拥塞管理很激进；如果f r e e z et i m e 太大，p m 的变化很缓慢，从 而使得拥塞概率很保守，不能适应流量的变化。f r e e z et i m e 的设置问题和r e d 中权重wq 的问题有些类似。 ( 3 ) s f b 虽然较好地解决了区分适应流和非适应流地问题，但过于复杂，会大 大增加路由器的额外开销 2 2 4 队列管理算法总结 一个理想的队列管理算法应该是根据即将到达的数据流量最优地调整资源 分配，在满足服务质量要求地同时，最大限度地利用系统地缓冲资源。但是在 实际情况下，下一时间段内的流量到达情况是无法确切获得的。而且绝大多数 队列管理算法和队列调度算法是孤立的，缺乏一定的联系，导致缓冲资源和带 宽资源的分配互相独立，协作性差。以上算法虽然有些很成熟，并且有各自的 侧重，但是都是针对缓冲资源单独考虑的，没有考虑到带宽的分配；只有当缓 冲资源和带宽资源的分配相互一致才+ 能最大限度地利用缓冲队列的特性，使得 系统吞吐量和分组丢失率的综合性能最优，在下一节中会对队列管理和调度联 合算法j o b s 进行简单的分析。 第二章队列管理及调度算法 2 3 常用队列调度算法 2 3 1 基于静态优先级的队列调度算法分析 常见的基于静态优先级的队列调度算法有p q ( p r i o r i t yq u e u i n g ) 和 q l t ( q u e u el e n g t ht h r e s h o l d ) 1 9 】。p q 算法给每个队列赋予不同的优先级，每次 需要调度时，具有最高优先级的非空队列中的分组最先被选择服务。如果最高 优先级的队列为空，则服务具有次优先级的队列，如此类推。这样，最重要的 分组就能得到最好的服务，比如最小的时延。此类算法简单，容易实现，然而 在高优先级队列源源不断有分组到达时，低优先级的队列容易被“饿死”，即 在很长时间内得不到服务，因而公平性很差。而且，优先级时静态配置的，不 能动态适应变化的网络要求。 解决p q 算法中低优先级队列“饿死”现象的一个有效手段就是设置调度阈 值。q l t 给每个队列设置调度阈值，需要进行调度时从最高优先级开始比较队 列的长度和调度阈值。当最高优先级队列的长度大于等于其调度阈值时，该队 列头部的分组首先被选择服务。当最高优先级队列的长度小于其调度阈值时， 不再服务调度队列，而是检查具有次高优先级的队列，如此类推。通过设置合 理的调度阈值，q l t 算法在保证优先级关系的基础上提高了公平性。 2 3 2 基于轮循的队列调度算法分析 传统的轮循( r o u n dr o b i n ，r r ) 算法对不同队列( 业务流) 进行无区别的循环调 度服务。这样，如果不同的队列具有不同的分组长度，则分组长度大的队列可 能会比分组长度小的队列接受更多的服务，使队列之间产生不公平的现象；而 且，这种算法不能对业务提供时延保证。为了改进r r 算法的时延特性和其在变 长分组环境下的不公平性，出现了一些改进型的算法，如加权轮循( w e i g h t e d r o u n dr o b i n ，w r r ) t 2 0 1 ，差额轮循( d e f i c i tr o u n dr o b i n ，d r r ) 2 ，紧急轮循 ( u r g e n c y b a s e dr o u n dr o b i n ，u r r ) 。这些算法力图在尽量保持r r 算法实现简单 性的同时，从不同方面改进r r 算法的时延特性和其在可变长分组环境下的不公 平性。 w r r 算法最初是用在a t m 交换机上，它在r r 的基础上为每个队列赋予了 第二章队列管理及调度算法 一个权值( 信元数) ，同时为每个队列维持一个计数器。在每次轮循时，计数器的 计算方法为：初值为权值；每发送一个信元就减一，当所有队列的计数器为零 时，则都重置为权值。w r r 算法能提供很好的公平性，且同时以较为平滑的方 式调度输出业务。 提出d r r 算法主要是为了解决传统r r 算法的不公平性，与w r r 有一些相 似之处。d r r 也为每个队列赋予了一个计数器。在每次轮循时，只有待发分组 长度小于计数器值，才允许发送分组。计数器的计算方法为：初值为定植额； 每发送一个分组就减去此分组的长度值：每经过一次轮循就加上定值额。d r r 算法解决了传统r r 算法中由于变长分组带来的队列间的不公平性，从而可以应 用变长分组带来的环境，且实现较为简单。d r r 的缺陷在于不月e - , 匕匕，t f i t 好地满足业 务的时延特性，不能有效地支持实时业务，不能像w r r 那样以较为平滑的方式 调度输出业务。 u r r 算法的主要目的是在不过度提高复杂性的情况下，改善传统r r 算法 的时延特性【2 2 】。在u r r 算法中，系统给每个队列赋予一个紧急参数u i ( t ) ，在每 一轮循环开始之前，算法都要计算一个队列的u i ( t ) 参数( 等于其队列长度与其速 率的比值) ，并按降速排列，服务顺序从大n d , 。u r r 算法改善了r r 算法的时 延特性，但仍然存在传统r r 算法中的不公平性。另外可以在d r r 算法的基础 上在引入u r r 算法中“动态改变队列循环调度次序”的思想来实现在变长分组 环境下的公平性和可以得到改善的时延特性，对时延特性的改进效果有待进一 步的分析和探讨。 2 3 3 基于g p s 模型的算5 去( p f q 算法) 分析 g p s 是一个理想化的模型【2 3 1 ，它根据各队列的共享比例对所有的活动队列 同时服务，所以能使各业务流真正公平地共享链路带宽。g p s 对每个队列业务 流有明确的端到端的时延上限，而且与其他队列业务流无关。g p s 模型是流系 统( 即分组可以无限小) ，但是实际的系统都是分组系统：在任何给定的时刻只能 有一个分组可以得到服务，分组的传输是不能被抢占的。g p s 模型在实际网络 系统中是无法实现的。因此就出现了一类用来逼近基于流的g p s 模型的分组算 第二章队列管理及调度算法 法：分组公平排队( p a c k e tf a i rq u e u i n g ，p f q ) 算法。