（计算机软件与理论专业论文）主动队列管理若干问题的研究.pdf

主动队列管理若干问题的研究 摘要 i p 网络传统的尽力而为服务模型已经使i n t e r n e t 获得了巨大的成功如果 能对网络采用恰当的控制机制，这种服务模型仍然可以在将来支持广泛的应用类 型。为了提高i p 流的端到端的转发性能，在路由器上引入主动队列管理机制成 为了必需。本文针对主动队列管理机制中的若干问题进行了深入的研究。 不响应流和非t c p 友好流妨碍了尽力而为服务网络的公平性，本文分析了现 有的一些依流调度机制和依流丢弃机制，分析了它们各自的优缺点。在此基础上， 提出了一种将公平带宽分配方案和主动队列管理机制相结合的公平排队算法，利 用r e d 分组丢弃机制对i p 分组传输的反馈作用，在单一链路上实现一种类似区 分效果的服务。 c s f q 算法是一种在核心路由器上的分布工无状态公平排队技术，它在降低 实现算法复杂度的同时保留了较好的公平性，但它仍有诸多需要改进之处。针对 其在吞吐量等性能上的不足，本文提出了一种结合c s f q 与f i f o 两种技术的公平 排队算法。算法能够达到近似公平的带宽分配，在保持了c s f q 的其它优点基础 上，更进一步地改善了总体吞吐量，减少了包的转发时延，并更有效地利用了链 路带宽，且仍能避免拥塞的产生。尤其对于小流量的和突发性间歇性流量陔算 法在性能上有露著地提高。 本文研究了现时应用的各种链路上的聚集流量的速率估算算法，并分析了它 们各自提出盼雷的和相应的优缺点，提出了一种结合流量变化趋势的速率估算算 法，通过对参数的设置，在一定条件下扩展了速率估算算法的适用范围。 主动队列管理机制的实现很大程度上受限于队列管理机制与缓存管理机制 的功能服务，本文提出了一种基于虚拟地址的方案扩展缓存地址空间，实现队列 管理与缓存管理的分离，增强了路由器上对于缓存队列中分组的操控的方法，增 大了新的主动队列管理机制的在设计上的灵活度。 关键词：i p 网络，主动队列管理，尽力而为服务，队列管理，速率估算 r e s e a r c ho na c t i v eq u e u em a n a g e m e n t a b s t r a c t t r a d i t i o n a ib e s t - e f f o r ts e r v i c em o d e li ni pn e t w o r k sh a sb r o u g h tg r e a t s u c c e s st ot h ei n t e r n e t ，i fc o n t r o l l e da n dp r o v i s i o n e da p p r o p r i a t e l y ，t h i sm o d e l w i l ls t i l lb ea b l et os a t i s f yt h em a j o r i t yo fp o p u l a ra p p l i c a t i o n si nt h ef u t u r e i ti s n e c e s s a r yt ou s ea c t i v eq u e u em a n a g e m e n tm e c h a n i s mi ni pt r a n s p o r t a t i o n t oi m p r o v ee n d - t o - e n dp e r f o r m a n c e s o l u t i o n st os e v e r a lp r o b l e m si nt h e s e s e r v i c em o d e l sa r ep r e s e n t e di nt h i sp a p e r u n r e s p o n s i v eo rt c p u n f r i e n d l yf l o w sb e g e tu n f a i rs e r v i c e si nb e s t - e f f o r t n e t w o r k s a n dan u m b e ro fp e r - f l o ws c h e d u l i n go rp e r - f l o wd r o p p i n gm e c h a nj s m sh a v eb e e np r o p o s e d t h e ya h a v et h e i ro w ns u c c e s sa n df a i l u r ei nt h i s i p a p e r , w ep r o p o s eaf a i rq u e u i n ga l g o r i t h mt h a tc o m b i n e sa c t i v eq u e u em a n a g e m e n ta l g o r i t h m ，u s i n gf e e d b a c ka f f e c tt oi pt r a n s m i s s i o no np a c k e td r o p - p i n gi nr e da l g o r i t h m , r e a l i z ed i f f e r e n ts e r v i c ec l a s so no n el i n k t h ec o r e - s t a t e l e s sf a i rq u e u i n ga l g o r i t h mi sar o u t i n gm e c h a n i s md e s = g n e dt oa c h i e v ef a i rb a n d w i d t ha l l o c a t i o nw i t hm i n i m a li m p l e m e n t a t i o nc o r n - p l e x i t y b u tt h e r ea r es t i l ls e v e r a lp o s s i b i l i t i e sf o ri m p r o v i n gc s f q i nt h i sp a p e r , w ep r e s e n tan e wa l g o r i t h m , w h i c hc o m b i n e dc s f qw i t hf i f o t h i sa l g o r i t h m i m p r o v e s t h ep e r f o r m a n c eo fc s f qa ts o m ea s p e c t ss u c ha st h r o u g h p u ty e t s t i l la c h i e v e sa p p r o x i m a t e l yb a n d w i d t ha l l o c a t i o n i td e c r e a s e st h et r a n s f e r d e l a ya n du s e st h eb a n d w i d t hm o r ee f f i c i e n t l y e s p e c i a l l y ，i ti m p r o v e st h ep e r - f o r m a n c ee f f i c i e n t l yf o rs h o r tf l o wa n db u r s tf l o w w es t u d i e ds o m ef l o w - r a t ee s t i m a t i o na l g o r i t h m s w h i c hw e r ew i d e l yi m p l e m e n t e df o rv a r i o u sa p p l i c a t i o n s 。b yc o m p a r i n gt h ep e r f o r m a n c ea m o n g t h e s ea l g o r i t h m sf r o ms e v e r a la s p e c t s w ep r e s e n tan e wr a t ee s t i m a t i o na l g o r i t h m ，w h i c hc o n s i d e r st h ed i r e c t i o no ft h er a t ec h a n g e sw h i l ee s t i m a t i n gt h e f l o w - r a t et h i sa l g o r i t h m i n c r e a s e st h ea v a i l a b i l i t yo ft h er a t ee s t i m a t i o na l g o r i t h mi ns o m ea s p e c tb yt h ep a r a m e t e rs e t t i n g s a c t i v eq u e u em a n a g e m e n ti sr e s t r i c t e db yt h es e r v i c ef u n c t i o nt h a tt h e q u e u em a n a g e m e n ta n db u f f e rm a n a g e m e n to fr o u t e r sp r o v i d e s i nt h i sp a p e r , w ep r o p o s eam e c h a n i s mt h a tu s e “v i r t u a la d d r e s s ”t oe x p a n da d d r e s ss p a c e ， t h e nm a k eq u e u em a n a g e m e n ta p ar tf r o mb u f f 色rm a n a g e m e n t e n r i c ht h e f u n c t i o nt h a tt h er o u t e r sa l t e rt h eq u e u e ，t oa d a p tt on e wa c t i v eq u e u em a n l l a g e m e n tm e c h a n i s m sn e e d s k e yw o r d s ：i pn e t w o r k s ，a c t i v eq u e u em a n a g e m e n t ，b e s t e f f o r ts e r v i c e q u e u em a n a g e m e n t ，r a t ee s t i m a t i o n v 第一章绪论 i n t e m e t 中的传统服务模型的机制称为“尽力而为”( b e s t e f f o r t ) 的服务模型， 它的这一模型是建立在i p 协议的实现基础之上的。这- - n 务模型自从于上个匿 纪六十年代开始投入使用以来，这几十年的实践证明了，这是一个非常行之有效， 而且获得了巨大的成功的服务模型。近十几年来，随着实时应用和流式多媒体应 用等的出现以及发展，对“尽力而为”的服务模型提出了一些新的要求。例如， 这些应用对服务质量 1 个分组，将它们与到达的分组作比较， 然后丢弃其中与到达分组有相同f l o wi d 的分组。事实上，在有多个非响应流的 条件下，必须选择多个预备丢弃分组。但是，对于完全无状态的设计，无法预先 知道在任何时候存在有多少个非响应流，即算法应能自动确定合适的m 值。一 种方法是引入一个中间阈值i n t 。，它把m i n 。和m a ) ( 。问的区域分成两部分。当平 均队列长度在m i n m 和i n t m 之间时，m = 1 ；当平均队列长度在i n t 。和m a x m 之间时， m = 2 。更具一般性的方法是引入多个中间阂值，把m i n ，。和m a x 。之间划分为多个 区域r i 、r 2 、r 、r k ，根据平均队列长度所落入的区域的不同而选择不i 卅 的m 值。 2 3 带区分的r e d 算法 r e d 算法自从于1 9 9 3 年提出以后，获得了较为深入的研究。这一算法作为 一种依赖于路由器平均队列长度的分组丢弃算法，相当于在端到端的分组发送系 统中，g 入了一种反馈机制，通过不同的分组丢弃策略，这一反馈系统将有不同 的响应特性和稳定状态。本节通过对这一反馈系统的研究与浇明，提出一种在单 一链路上通过引入不同的萎弃策略，从而在反馈系统中产生不同的响应，以满足 主动队列管理机制对于不同流量特性应用提供带“区分”的服务的需求。 2 3 1 基于队列长度的拥塞控制反馈系统 首先建立一个t c p 的拥塞控制模型，模型中包括了一个对分组进行丢弃的队 蔓 飞： 图2 - 4n 个流的控制反馈系统 剐系统。为简化超见，建立一个单瓶颈的模型如图2 - 4 所示： 在这一控制反馈系统中，n 个t c p 流通过个带宽力c 的共享键路，t c p 流，( 1 i 押) 的源为氐，目的为d ，。假设这些流都是单向的，反向流量只包括 a c k 分组，不会对链路的带宽分配起到影响。 假设所有的链路a b 和c d 。都拥有足够的带宽，因此，链路b 。c 是系统 中唯一的瓶颈，所有的分组丢弃都只可能发生在链路b c 上。同时，假设在一 段较长的时期内，t c p 流的数量n 是不变的，并假设系统中的流实现的是t c p r e n o 算法。 每个流：的发送速率为r ，所有的流的发送速率在b 上交汇，b 上的队列 长度为q ，分组丢弃模块根掘平均队列长度虿计算各分组的丢弃概率p ，对任一 流来说，所有来丢弃的分组以速率( ，通过链路c d 发送到d 。每一个t c p 流都根据分组丢弃概率p 来调整各自的发送速率。可以得出【j p a d h y em 8 c ，( p ，足) = t ( p ，r ) ，其中t ( p ，r ) = 其中t 为t c p 流的吞吐量，依赖于分组丢弃概率p 与平均r t t 值r ，平均分组 长度m ，每个a c k 回应的分组数b ( 一般实现为2 ) ，最大拥塞窗口w 。以及 t c p 超时长度t o 。式中其它的函数为 m ) = 百2 + b + j 等+ ( 等) 2 q ( p ，w ) = r i l i n ( 1 ，蚶生幽竺型旦型立) ，( 2 - 3 ) f ( p ) = 1 + p + 2 p 2 + 4 p3 + 8 p4 + 1 6 p 5 + 3 2 p 6 为更进步化简，假设所有的流的r t t 值都相同，w 一值足够大，则可以 得出，( p ，r ) = i ，( ，：r ) ，其中1 兰f ，j ”。于是，我们可以把n 个流的反馈控制 图2 - 5 单流反馈控制系统 系统简化成个单流的系统，如图2 - 5 所示。一个反馈控制系统，它的稳定：恢念 决定于它的激励函数和控制函数。在这罩，函数彳= g ( p ) 是系统激励，反映的是 平均队列长度对于分组丢弃概率的一个函数关系。控制函数p ：( 虿) 通过丢弃 模块( d r o pm o d u l e ) 来实现，例如，r e d 的d r o p t a i l 算法。 图2 - 6 单流的开环控制系统 为了确定函数彳= g ( p ) ，考虑如图2 - 6 所示的开坏控制系统，其中分组丢弃 概率p 是一个自由变量。前面已经假设链路f 是系统中的唯一瓶颈，可以得出， 系统中各分组的平均r t t 为分组在队列中等待时间与传输延迟的和，即有 r = r o + 彳c ， ( 2 - 4 ) 成立a 根据不同的p 值，系统可能存在两种状态。当p 大于某一特定值p 。时， 链路带宽没有被充分利用，此时有 ( p ，r ) 风(2-6) c 盯c i ” 当p 小于等于p 。时，链路的带宽被全部占用，“( p ) = 1 ，此时，平均队列长 度值可从等式( p ，+ 彳c ) = c n 得出： q ( p ) = c ( 巧( p ，c n ) 一r o ) ，( 2 7 ) 函数巧是函数r ( p ，r ) 在r 上的反函数。当分组丢弃概率p 足够小，使得 彳( p ) = c ( 巧l ( p ，c n ) 一r 。) b 成立( b 为缓冲空间) 时，则将有额外多的分组由 于缓冲空间不足而被丢弃。考虑到缓冲空间b 的存在，有 孑( p ) = m a x ( b ，c ( 巧l ( p ，c n ) 一r o ) ) ，p p 。( 2 8 ) 因为p 。是链路从不饱和到饱和转换的临界值，可以通过下式汁算它的值： ( j j ，o ，r o ) = c n ，( 2 9 ) 如果记函数r ( n r ) 在p 上的反函数为巧，可以得到 风2 l j 。( c n ，r o ) 。 这时，可以得到最后结果，如下式： 彳( p ) ：j m 戕( b 。( 石( p , c n ) - r o ) ) ，? p ? 0 o t h e r w i s e f1 ，p p 。 “( p ) 。 t ( p , r o ) 。t h p m 地 2 3 2r e d 算法在反馈控制系统中形成的稳定点 f 2 1 0 ) ( 2 - 1 1 ) 在上一节，得出了在分组丢弃反馈控制系统中，平均队列长度是分组丢弃概 率的一个函数，记为可( p ) = g ( p ) ，当在反馈系统中的分组丢弃模块中引x - + 控制函数p = 日( 玩) ，其中瓦为队列平均长度的一个估算值时，从反馈系统的性 质可以得出，这一反馈系统将有一个稳定状态，且稳定状态的特征值( p 。，玩) 为 方程佐黑懈腻撕映了反馈系统中的长期的分组平均丢弃髀 c t i b a c k t l r ( 1 b 1 1 c m ，” 图2 7 反馈系统中的稳定点 玩反映了长期的平均队列长度，如图2 7 所示。 应用以上的结果，给出r e d 算法的分组丢弃控制函数 p = h ( 瓦) = 0 ，0 蔓瓦q 。 里二坠l 。，q 。玩q 。， ( 2 1 2 ) q m a x q 。i n 1 ， q 。玩b 其中，玩是队列平均长度的估算值，b 是队列缓冲空间的大小。叮1 1 1 l n 、q 。和p 。 是r e d 算法的可配置参数。 2 3 3 带区分的r e d 算法的提出 从上一节的结果可以知道，在r e d 算法中采用不同的配置参数( n 、。 和p 一) 时，在反馈控制系统中会形成不同的稳定状态点，换言之，对分组可以 产生不同的转发效果，这包括不同的分组丢弃率，不同的队列平均长度( 即不同 的转发延迟) 。考虑公式( 2 1 2 ) ，无论r e d 算法如何配置，这一稳定状态点一 定落在公式的第二项中，即在分析中我们可以进一步忽略r e d 配置算法中的链 路欠饱和区与拥塞发生区，将r e d 控制曲线近似为线性函数，这将不会影响本 图2 8 不同的控制函数实现不同策略 章中的结论和方法。简化近似后重画图2 7 如图2 8 所示。在图2 8 中，h 与 h 2 是两种不同的r e d 参数配置策略，与系统激励函数g ( p ) 作用后，将形成不同 的稳定状态点。令h l 与g 交会的稳定状态为( p l ，q i ) ，h 2 与g 交会的稳定状态为 ( p 2 ，q 2 ) 。从图中可以得出，p 1 = w c ) t i m e = n o w f o re a c hc l a s sin o tr e s e r v e d b i = b 。r i 】r r i = 0 r=0 图2 一i 0d r e o 算法更新各策略类带宽部分 f o re a c hp a c k e ta r r i v a lb e l o n gt oc l a s si c a i c u l a t en e wa v g q u e u es i z ea v g ： i ft h eq u e u ei sn o n e m p t y a v g i = ( 1 一w q ) a v g i + w qq e l s e m2f ( t i m e q t i m e ) a v g i = ( 1 一w 。) “a v g i i fm i n t hc i a v g i m a 。t h i i n c r e m e n tc o u n t i c a i c u l a t ep r o b a b i i i t yp a ： p b = m a x “i 】( a v g i 一m i n t h i 】 p a i l = p b ( 1 一c o u n t + p b ) w i t hp r o b a b i l i t yp 。 i ： m a r kt h ea r r i v i n g p a c k e t c o u n t 【i 】= 0 e l s ei fm a x t h a v g m a r j ( t h ea r r i v i n g p a c k e t c o u n t 【i = 0 e l s ec o u n t i = 一1 w h e nq u e u eb e c o m e se m p t y q t i m e = t i m e 图2 一l ld r e d 算法中各策略类的标记丢弃算法 虑到不同策略类中分组流量的大小，反而会造成不公平性。 带区分的r e d 算法采用依据策略类中聚集流量速率按比例动态划分的方法 来划分虚拟空间的大小。路由器对各未预留空间的策略类统计其聚集流量的到达 速率，在固定的窗口时间内w 。中对这些策略类的聚集流量进行跟踪更新，将未 预留缓冲区空删按照最近的跟踪估算结果在各策略类之间按比例进行划分。在这 罩，使用窗口时矧法估算流量速率而不是采用指数平均算法在每个分组到达时估 算聚集流量速率是为了避免算法实现过于复杂，同时也避免了过度频繁地调整各 虚拟缓冲区空间的大小。 图2 - 9 ，图2 1 0 ，图2 1l 给出了带区分的r e d 算法的详细实现。 2 4 小结 路由器上的公平排队机制可以有效地控制侵占性流或行为不端流对其它流 的影响。r e d 算法自从被提出后得到了较为广泛的研究与应用。不少研究对于 如何自动对r e d 算法中的参数进行配置以获得较好的性能结果和适应更多的网 络环境作了深入的分析。 我们提出的在单一链路上实现对不固聚集流采慝魂；同策略的“带区分的 r e d 算法”，依据r e d 分组丢弃行为对端到端分组转发产生的反馈作用，获得 了反馈的基本模型。不同的反馈可以产生不同的系统稳定状态，相应地对聚集流 分组提供了不嗣的服务性能。在单一链路上实现不嗣的服务策略，在尽力丽为服 务模型基础上提供类似于区分服务的功能，是这算法的特点。带区分的r e d 算法可以同时服务于多个策略类，并可咀人工对不同的策略类进行带宽资源预 留，在算法的实现复杂度上，和r e d 算法近戗。而且其实现思路与现有对r e d 算法的各种改进互不矛盾，类似带区分的功能图样可以实现在s r e d 等算法中； 需要指出的是，这一算法只适用于不提供端至4 端带宽保证的“尽力而为”服 务，实现一种分类的q o s 服务，而不适用于有特定的q o s 要求而需要网络实现 一种湿式的接纳控翎的类似“奖赏服务”( p r e m i u ms e r v i c e ) f r f c 娜8 】的流量。 第三章分布式主动队列管理算法研究 在前一章节中，采用了依流调度或依流丢弃的主动队列管理机制，实现了带 宽的公平分配。但这些机制都有一个共同的缺点，它们都要求维护依流的状态， 在路由器上保持依流状态，并以此为基础对分组进行各种操作。在路由器上保持 依流状态并对其维护，对路由器引入了不小的处理要求，较高的实现复杂度和较 差的可扩展性，使得这两种机制并不适用于高速核心路由器。 大型网络要求将大部分的处理保留在网络边界，而只有轻量级( 1 i 曲t w e i g h t ) 机制引入网络的核心。因此第三种实现带宽的公平分配机制以分布式的无状 态公平排队算法为基础的主动队列管理机制，如c s f q ”“。8 目和r f q 怔c a o 加0 0 】，这类算法的设计和研究已经成为一个当前新的活跃的研究领域。 3 1 分布式主动队列管理c s f q 算法 前一章中提到的各类诸如r e d 等的带宽公平分配机制都要求在网络节点上 维护某种形式的依流状态，这严重妨碍了这些机制的实际应用，特别是对于那些 需要处理数十万个流的核心网络节点。c s f q 算法正是针对这个问题而提出的， 即实现了一种带宽近似公平的分配而不需要在每个网络节点上保存依流的状态。 c s f q 算法通过在一个路由器岛中的多个路由器中分布式地部署公平排队 算法来实现主动队列管理机制以达到拥塞避免，而且提供了在核心路由器上的较 低的实现及算法复杂度。 这种机制存在着两个关键的方面：第一，为了避免在每一个路由器上保存依 流的状态，它使用了一种分布式的部署方法，仅在边界路由器之上维护依流的：伏 态，而在核心( 非边界) 路由器上则不用保存依流的状态，直接使用接收到的分 组头部携带的由边界路由器标记的信息。这些标记信息中包含了对于聚集流量速 率的估算值，这个估算值是由边界路由器依据依流状态进行估算，并沿着整个分 组转发路径在每一个途经的路由器上被相应地更新以反映分组丢弃引起的流量 速率的变化。 第二，为了避免对不同的流进行依流缓冲和调度，c s f q 算法在输入端采取 了f i f o 队列来处理插入队列的各个分组，并根据一定的丢弃概率进行丢弃。在 输入端分组被丢弃的概率是一个由在分组头部标记的流量速率和当前路由器l ： 浚分组所属聚集流所占有的公平带宽所决定的一个函数。在当前路由 上浚聚集 流所占的公平带宽是由聚集流的流量速率数据计算得出的。 这样，c s f q 算法既避免了在核心路由器上保存依流状态，又避免了存蹄i | i 器上进行复杂的依流缓冲与调度机制，极大地简化了核心路由器上对分组的处理 过程，对于要求快速处理大量数据转发的高速核一i i , 路由器柬蜕，有着非常重要的 图3 - 1c s f q 算法核心路由器与边界路由器功能框架 应用意义。 c s f q 算法的在边界路由器和核心路由器上实现功能框架如图3 1 所示。 3 , 1 1 流量模型 首先考虑在一个路由器上的无缓冲的流量模型，把所有的流看作是一个连续 的比特流，假设它的输出链路容量为c 。并假设每一个流的到达速率f ( f ) 是可以 精确知道的。m a x m i n 公平带宽分配要求在通过某一个瓶颈上的所有的流全都有 相同的输出速率，我们称这个相同的输出速率为公平速率，并标记在时间t 上的 公平速率为a ( t ) 。一般来说，根据m a x m i n 公平带宽分配原则，每一个流( f l o w i ) 所获得的服务带宽应该是m i n ( 1 ( f ) ，日( ，) ) 。我们记聚集的到达速率为x ( t ) ，即 n a ( t ) = ：。l ( ，) 。如果一( r ) c ，也就是当网络在输出链路上出现拥塞时，公 平速率的值应满足公式 c = m i n ( ( f ) ，口( f ) ) ， ( 3 1 ) 如果a ( t ) sc ，即在输出链路上没有发生拥塞时，则不会有分组被丢弃，有 a ( t ) = m a x ，l ( f ) 成立。 对于单个的流，如果l ( ，) a ( t ) ，即当一个流的到达速率小于公平速率时， 流的所有分组将得到转发。如果( ，) a ( t ) ，则该流的每个分组被丢弃的概率为 ( 1 - 墨娑) ，使得该流的接受速率等于口( f ) 。通过对上面情况的分析，我们得出一 r ，j 个简单的分组转发算法，可以达到带宽的公平分配，即，对于流( f l o wi ) 中的 每一个比特，将按照下式的丢弃概率被丢弃： m a x ( 0 ，1 一鬻) ( 1 - 2 ) 同时，如果按照上式的丢弃概率，流( f l o wi ) 在下一个路由器的到达速率 将被重新标记为m i n ( r ，口1 。 3 1 2 分组算法 上面的流量模型分析基于一个假设，即每一个比特流都是连续的，其到达速 率都是可以精确地知道的，并且路由器上是无缓冲的。但在实际路由器中，所有 的流量都是以分组为单位被传送的，在路由器上存在着缓冲的空间，对于每一个 流来说，它的到达速率是不可知的。 根据上面的分析，可以得出，对于每一个流，它的每一个b i t 的丢弃速率只 和它的到达速率( f ) 与公平速率口( f ) 有关，因此，我们可以将每一个比特( b i t ) 的丢弃概率直接应用到分组上。 整个算法集中在边界路由器如何估算各个流的到达速率f ( f ) 以及在路由器 上各流的公平速率口( f ) 上。 ( 1 ) 估算流的到达速率 在c s f q 算法中，各个流的到达速率在边界路由器上进行估算，并将估算值 插入分组标记中，由分组携带转发到路径中的下一个节点一k 。在算法中，边界路 由器用指数平均算法来估算一个流的到达速率。令f ! 和r 分别表示流( f l o w i ) 中第k 个分组的到达时刻和分组的长度，则每当流f l o wi 有新的分组到达时，算 法对流的到达速率的估算值进行更新： 夺k 喀”“ ( 3 3 ) 其中= r j f 为当前分组到达时间距同属该流的村个分组到达的时间 间隔，k 为一个常数。 ( 2 ) 估算链路的公平速率 根据上文的流量模型，假设各个流的到达速率是精确可知的，且路由器按照 公式( 3 2 ) 决定的丢弃概率对分组进行丢弃。那么，可以得出，路由器的接收 速率将是公平速率估算值的一个函数。令公平速率估算值表示为j ( ，) ，令路由器 的接收速率表示为f ( 文啪，我仍有 f ( 钠) = m i n ( r i ( t ) ，酮) ( 3 4 ) j ；l 当链路发生拥塞( a ( t ) c ) 时，我们取鑫( ，) 为方程f ( x ) = c 的唯一解。如 果链路没有发生拥塞( a ( t ) c ) ，我们取鑫( f ) 为通过这一链路的所有流的到达速 率的最大僵，即有d 0 ) = m a x 。；。( i ( f ) ) 成立。从公式( 3 - 4 ) 可以看出，如果能够 知道i ( f ) 的精确值，则舀值可以直接得到，但为了避免在路卣器上保存和维护 依流状态，这里通过对转发速率f 和到达速率a 的估算来间接得出公平速率的 估算德鑫。 在这里，在路由器上对聚集流维护三个变量：令鑫为链路上聚集流的公平速 率的估算值，令叠为聚集到达速率的估算值，令户为聚集接收速率的估算健。每 当一个分组到达时，我们对后两个聚榘变量进行更薪。路盛器使用参数为e - t 也 的指数平均算法来更新叠的估算值，其中t 为当前分组和前一个分组的到达时 间的问隔： 五= ( 1 一e - t i e t ) 妻4 - e - f k 量。“( 3 ，5 ) 更新户的算法与之类似。 对于盎的更新算法取决于链貉上是否发生了拥塞。为了减少指数平均鲜法中 的不准确性，算法中g l 入了一个窗口时间参数拦一如聚在整个窗h - 时划；内， j c 一直成立，我们认为在链路上发生了拥塞。反之，在整个窗口时间内 如果jsc 始终成立，则我们认为在链路上未发生拥塞。a 的值仅在根据以上定 义在上一个窗口时间内发生拥塞或未发生拥塞后才在窗口时间段到达时进行更 新。当链路上发生了拥塞时，我们根据方程f ( = c 来对a 进行更新，我们把函 数f ( ) 近似为线性函数，并具有斜率户a 。，则有 a 。m ，罢( 3 - 6 ) w ”“i 如果在链路上未发生拥塞，则占被更新为在上一窗口时问段内活动的流中 的最大速率( 即为路由器接收到分组中标记速率值的最大值) 。随后，新的估算 值a 。将用于公式( 3 2 ) 来计算得出对各流的丢弃概率。下面是c s f q 算法实 现的完整伪代码： o nr e c e i v i n gp a c k e tp i f ( e d g er o u t e r ) i = c l a s s i f y ( p ) j p 1 a b e l = e s t i m a t e r a t e ( r i ，p ) j + i s ee q ( 3 - 3 ) + p r o b = m a x ( 0 ，l c c p 1 a b e l ) ； i f ( p r o b u n i f r a n d ( 0 ，1 ) ) o2e s t i m a t ec f ( p ，1 ) ； d r o p ( p ) j e 1 s e c c 。e s t i m a t e d ( p ，0 ) ； e n q u e u e ( p ) j i f ( p r o b 0 ) p 1 a b e l = a ；+ r e l a b e lp + e s t i m a t e c ( p ，d r o p p e d ) e s t i m a t e r a t e ( a ，p ) j + e s t a r r i v a lr a t e ( u s ee q ( 3 - 5 ) f i f ( d r o p p e d = = f a l s e ) e s t i m a t er a t e ( f ，p ) j + e s t a c c e p t e dt r a f f i c r a t e + i f ( 彳c ) i f ( c o n g e s t e d = = f a l s e ) c o n g e s t e d = t r u e ； s t a r tt i m e ；c r tt i m e j e 1 s e i f ( c r t t i m e s t a r t t i m e + k c ) a = a c f s t a r tt i m e = c r tt i m e j e l s e + 一 c + i f ( c o n g e s t e d = 一t r u e ) c o n g e s t e d = f a l s e j s t a r t t i m e = c r t t i m e ； t m p c 20 ； + u s et oc o m p u t en e wd + e 1 s e i f ( c r tt i m e k c c e m p t y = ( c a ) + k c p r e v t i m e = n o w i f ( 1 0) p 1 a b e l = a ；pr e l a b e lp4 图3 3c s f q 改进算法的分组处理伪代码 pp or e d sle es le o p a 、 一， et p a m 1t e s u e eu = q n a e 性能问题则明显优于原始算法。 3 3 2 改进算法的具体实现 根据上一节引入的参数k ，改进算法将输出链路带宽虚拟划分为逻辑的两个 部分。汜输出链路的带宽为c ，其中，肥被使用于改进算法中的c s f q 算法使 用的输出链路，其余带宽将在改进算法中保留为“尽力而为”算法专用。 e s t i m a t e a ( p ，d r o p p e d ) e s t i m a t e r a t e ( a ，p ) ； i f ( d r o p p e d = = f a l s e ) e s t i m a t e r a t e ( f ，p ) ； if(ac) i f ( c o n g e s t e d = = f a l s e ) c o n g e s t e d = t r u e ； s t a r t t i m e2c r t t i m e ； e s e i f ( c r tt i m e s t a r tt i m e + k c ) a=a x c f ： s t a r tt i m e = c r tt i m e ； e l s e i f ( c o n g e s t e d = = t r u e ) c o n g e s t e d = f a l s e j s