（计算机应用技术专业论文）基于red算法改进策略的网络服务质量研究.pdf

山东大学硕士学位论文 摘要 随着互联网规模的不断发展， 人们对网络服务质量( q o s ) 的需求越来越 高，当今高速网络中的多媒体应用不但对网络有很高的带宽要求，而且要求信 息传输的低延迟和低抖动等，需要提供端到端的q o s 控制和保证。而网络拥塞 是影响网络服务质量的重要因素，实施拥塞控制也是其它q o s 机制正常工作的 必要前提。因此，拥塞控制机制及网络服务质量是当前的研究热点。 主动式队列管理机$ 0 a q m 是i e t f 推荐的基于路由器拥塞控制的关键技术， 它和t c p 端到端的拥塞控制相结合，是解决目前h t e r n e t 拥塞控制问题的一个主要 途径。a q m 通过评估网络状态、预测拥塞的出现，对分组进行有目的的丢弃， 从而可以使发送端更及时地了解到网络状况并调整发送速率。但是现有算法在响 应速度、稳定性及环境敏感性等方面仍有缺陷。对此，本文在对当前较流行的 r e d 算法进行详细分析的基础上，总结出已有算法的优势和不足，提出了一种新 的主动队列管理算法n m r e d 算法。 n m r e d 算法分别对原有r e d 算法的分组丢弃概率p b 的计算方法和参数 m a x p 进行了改进。其一：利用模糊理论中的升半哥西分布的隶属函数代替原来 的线性增加分组丢弃概率的函数。原r e d 算法根据平均队列长度线性地调整数据 包的分组丢弃概率，而当平均队列长度超过最大阈值q m a x 时是不连续的，直接 由m a x p 变为1 ，这种跳变将加剧缓冲队列的抖动。改进r e d 的分组丢弃概率计算 采用升半哥西分布函数，以平均队列长度为样本来获得，将控制范围扩展为最小 阈值到最大缓冲之间，实现了分组丢弃概率变化的平滑化。其二：n m r e d 算法 通过计算出路由器队列单位时间间隔内的平均队列长度，让它分别与最大阂值和 最小阈值的比较，得出差值，根据差值的大小动态地调整m a x p 的大小，从而及 时调整向源端发送拥塞通知的速率，维持队列长度的稳定，避免不必要的传输延 时和抖动。 在n s 2 网络仿真器上对算法进行了验证，一系列仿真实验表明，n m r e d 能 够有效地适应网络流量的变化，保持队列长度的稳定，减少了队列溢出和空闲现 象的发生，在保持队列长度稳定以及提高链路利用率方面明显优于r e d 算法。 关键词：拥塞控制；主动队列管理；早期随机检测；网络服务质量 山东大学硕士学位论文 a b s t r a c t w i t ht h eu n c e a s i n gd e v e l o p m e n to fi n t e r n e t s c a l e ，p e o p l eh a v e a n e v e r - g r o w i n gd e m a n df o rt h eq u a l i t yo fs e r v i c eo fc o m p u t e rn e t w o r k s ( q o s ) a n d n o w a d a y s ，i nt h eh i g h s p e e dn e t w o r km u l t i m e d i a sa p p l i c a t i o nn o to n l yh a s t h ev e r y h i g hb a n d w i d t hr e q u i r e m e n tt o t h en e t w o r k ，b u ta l s o r e q u i r e si n t e l l i g e n c e t r a n s m i s s i o nl o wd e l a ya n dt h el o wv i b r a t i o na n ds oo n ，n e e d st op r o v i d et h e e n d t o e n dc o n t r o la n dg u a r a n t e eo fq o s t h en e t w o r kc o n g e s t i o ni sag r e a tf a c t o r t oa f f e c tt h en e t w o r kq u a l i t yo fs e r v i c e ，s ot h ei m p l e m e n t a t i o nc o n g e s t i o nc o n t r o l i sp r e r e q u i s i t ef o ro t h e rq o sm e c h a n i s mn o r m a lw o r k a tp r e s e n t ，c o n g e s t i o n c o n t r o lm e c h a n i s mo fi n t e m e ta n dq u a l i t yo fs e r v i c ea r et h ec e n t r a li s s u e so ft h e c u r r e n tr e s e a r c h t h 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 m ( a q m ) i s ，w h i c ht h ei e t f r e c o m m e n d s ，t h ee s s e n t i a lt e c h n o l o g yb a s e do nt h er o u t e rc o n g e s t i o nc o n t r o l ， w h i c hc o m b i n e sw i t ht h et c pe n d t o e n d c o n g e s t i o nc o n t r o l b e i n gam a i n m e t h o dt 0s o l v et h e c o n g e s t i o nc o n t r o lq u e s t i o no ft h ep r e s e n ti n t e r a c t b y e v a l u a t i o nt h es t a t eo fn e t w o r ka n df o r e t e l l i n gt h ea p p e a r a n c eo ft h ec o n g e s t i o n ， a q m c a nd r o pt h ep a c k e tp u r p o s e f u l l ys ot h a tt h es e n d i n ge n dc a nb ei n f o r m e do f t h es t a t eo fn e t w o r ka n dt h e na d j u s ti t ss e n d i n gr a t e b u tt h ec u r r e n ta l g o r i t h m s a r e s ts t i l lp e r f e c ti nt e r m so fr e s p o n s e st i m e ，s t a b i l i t ya n ds e n s i t i v i t yt ot h e e n v i r o n m e n ta n ds of o r t h i nt h i sp a p e r ，t h ea d v a n t a g e sa n dd i s a d v a n t a g e so ft h e e x i s t e n t a l g o r i t h m sa r ec o n c l u d e db a s e do na n a l y s i n g t h ec u r r e n tp r e v a l e n t c o n g e s t i o nc o n t r o la l g o r i t h m sr e di nd e t a i l ，a ni m p r o v e da l g o r i t h mn m r e do f a c t i v eq u e u em a n a g e m e n t ( a q m ) i sp r o p o s e d a sar e s d t ，n m r e da l g o r i t h mh a sm a d et h em o d i f i c a t i o n so fo r i g i n a lr e d a l g o r i t h mi nt h ec o m p u t a t i o n a lm e t h o do fp r o b a b i l i t yo fp a c k e td r o p p ba n dt h e a d a p t i n go ft h ep a r a m e t e r m a x p f i r s t , b a s e do nt h ef u z z ym a t h ，i n s t e a do ft h e p r o b a b i l i t yf u n c t i o no fd r o p ，w eu s et h em e m b e r s h i pf u n c t i o no fa s c e n dh a l f - c a n c h y d i s t r i b u t i o n o r i g i n a lr e da l g o r i t h mb a s e do nt h ea v e r a g eq u e u es i z eo ft h eb u f f e r i i 山东大学硕士学位论文 t oa d j u s t p r o b a b i l i t yo fd r o p ，a n dw h e nt h ea v e r a g eq u e u es i z er e a c h e st h e m a x t h r e s h ( d e n o t e db yq m a x ) ，t h ed r o p p i n gr a t ei n c r e a s e sl i n e a r l yf r o mm a x pt o1 t h i sj u m pw i l la g g r a v a t et h ej i t t e ro fb u f f e rq u e u e n m r e di m p r o v ep r o b a b i l i t y c a l c u l a t i o nu s e daa s c e n dh a l f - c a u c h yd i s t r i b u t i o nf u n c t i o n ，t oe x t e n dt h es c o p eo f c o n t r o lf r o mt h em i n i m u mt h r e s h o l dt ot h eb u f f e r s i z e i tc a na l s oa c h i e v et h e s m o o t h n e s s f r o mp a r tt oc o m p l e t em a r k i n go rd i s c a r d i n g s e c o n d ：n m r e d c a l c u l a t e st h ea v e r a g eq u e u el e n g t hi nt h er o u t e ru n i t t i m e g a p ，a n db yc o m p a r i n g i tw i t ht h em a x i m u mv a l u ea n dt h em i n i m u mv a l u e , t h ei n t e r p o l a t i o nc a l lb eo b t a i n e d b a s e do nt h ei n t e r p o l a t i o n ss i z e ，n m r e dc a na d j u s td y n a m i c a l l yt h es i z eo f m a x p ， a n dt h e r e f o r ea d j n s tt h es e n d i n gr a t eo fc o n g e s t i o nn o t i f i c a t i o nt ot h es o u r c ee n di n t i m ea n dm a i n t a i nt h es t a b i l i t yo f t h eq u e u e l e n g t h ，i no r d e rt oa v o i dt h eu n n e c e s s a r y d e l a yo f t r a n s m i s s i o na n dv i b r a t i o n t h ea l g o r i t h mi sv e r i f i e di nn s 2n e t w o r ks i m u l a t i o nm a c h i n ea sw e l lb yt h e i n d i c a t i o no fas e r i e so fs i m u l a t i o ne x p e r i m e n t s ，n m r e dc a nv a l i d l ya d a p tt h e c h a n g eo fn e t w o r kf l o we f f e c t i v e l y ，h o l ds t a b i l i t yo fq u e u el e n g t h ， r e d u c e p h e n o m e n o no c c u l t e n c eo ft h eq u e u eo v e r f l o wo rt h ei d l e g r e a t l y a n di t i s s u p e r i o rt ot h er e da l g o r i t h mi nm a i n t a i n i n gt h es t a b i l i t yo fq u e u el e n g t ha n d e n h a n c i n gt h eu t i l i z a t i o nr a t i oo f t h el i n k s k e yw o r d s ：c o n g e s t i o nc o n t r o l ；a q m ( a c t i v eq u e u em a n a g e m e n t ) ； r e d ( r a n d o me a r l yd e t e c t i o n ) ；n e t w o r kq o s l i i 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写过的科研成果。对本 文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。 本声明的法律责任由本人承担。 论文作者签名：么金星 日期：逍：竺：多 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学校保留或向国家 有关部门或机构送交论文的复印件和电子版。允许论文被查阅和借阅，本人授权山东 大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或其他复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名： s s t h r e s h ，t c p 就执行拥塞避免算法：c w n d 在每次收到一个a c k 时只增 加l c w n d 个分组。所以在慢启动阶段和拥塞避免阶段中，c w n d 相应于每个r 2 t ， 分别对应指数变化和线性( 1 i n e a r ) 变化。 ( 3 ) 快速重传阶段 快速重传利用t c p 中这样一个规则：如果一个t c p 连接丢弃一个分组，接 收端对收到的每一个错序的分组发送相应的重复确认，直到丢失的分组收到为 止。如果t c p 发送端收到3 个重复的a c k ，则发送端立刻发送丢失的分组， 而不是等到超时。 ( 4 ) 快速恢复阶段 当数据包超时时，c w n d 要被设置为1 ，重新进入慢启动，这会导致过大地 减小发送窗口大小，降低t c p 连接的吞吐量。快速恢复就是在源端收到3 个或 3 个以上重复a c k 时，就判定数据包已经丢失，重传数据包，同时将s s t h r e s h 置为当前c w n d 的一半，进入拥塞避免阶段。 3 3 2 捅塞控制链路算法 链路算法的研究目前集中在主动队列管理( a c t i v eq u e u em a n a g e m e n t ，简称 a q m ) 算法方面。和传统的“队尾丢弃”( d r o p t a i l ) 相比，a q m 在网络设备的缓 冲溢出之前就丢弃或标记报文 6 1 。a q m 的主要优点是： ( 1 ) 减少网关的报文丢失。使用a q m 可以保持较小的队列长度，从而增强 网络中间节点容纳突发流量的能力。 ( 2 ) 减小报文通过网关的延迟。减小平均队列长度可以有效地减小报文在网 络设备中的排队延迟。 ( 3 ) 避免l o c k _ o u t 行为的发生1 。 2 l 山东大学硕士学位论文 a q m 的一个代表是r e d ( r a n d o me a r l yd e t e c t i o n ) 。研究表明，r e d 比 d r o p t a i l 具有更好的性能。在r f c 2 3 0 9 中，强烈推荐使用r e d 作为今后的标 准。但是进一步研究发现，r e d 的性能对算法的参数设置十分敏感，至今没有 在i n t e m e t 中得到广泛的使用。 3 4 拥塞控制算法的评价标准 在研究拥塞控制算法的过程中，需要一定的评价方法和评价标准来分析一 个算法的可行性、可靠性以及效率等。其中端系统的吞吐率、连接的丢失率和 延迟等指标，都是拥塞控制算法的重要的评价指标，而且这些更加是端系统所 关注的。但是拥塞控制算法主要是针对整个网络系统的，因此在评价算法时更 应该从整个系统的角度出发进行考虑。 3 4 1 资源分配的公平性 由于公平性是针对资源分配而言的，所以在评价前首先要确定“资源”的 含义。目前大多数研究在评价公平性时都针对吞吐量，这是从用户的角度出发 考虑的，并不完全适合网络中的资源状况。网络中的资源包括链路带宽、网关 的缓冲和网关的处理能力等，在考察公平性时应当将这些资源的分配情况综合 考虑。 公平性是指在网络发生拥塞时各连接能公平地共享网络资源。产生公平性 的根本原因在于拥塞发生必然导致数据包丢失，而数据包丢失会导致各数据流 之间为争抢有限的网络资源发生竞争，竞争能力强的数据流将到更多网络资源， 从而损害了其它流的利益。所以说没有拥塞，也就没有公平性问题。公平性问 题表现在两方面：一是拥塞响应的t c p 流和非拥塞响应的u d p 流之间资源享 用不公平；二是t c p 流之间资源享用的不公平。 前者主要是在发生拥塞时对拥塞指示作出的不同反应造成的。由于t c p 流 具有拥塞控制机制，在收到拥塞指示后，源端会主动降低发送速率；而u d p 流 由于没有端到端的拥塞控制机制，因此在收到拥塞指示后，u d p 不会降低数据 发送速率。结果在网络拥塞时，拥塞响应的t c p 流得到的资源越来越少，非拥 塞响应的u d p 得到的资源越来越多，从而导致了网络资源分配的不公平。网络 山东大学硕士学位论文 资源分配的不公平反过来会加重拥塞情况，甚至可能导致拥塞崩溃。对于第二 个不公平性问题，研究表明，不同的窗口大小、r t t 值及数据包的尺寸都会影 响t c p 流对带宽的占用。窗口较大，或者r t t 较小，或者数据包较大的流往 往能占用更多的带宽。 公平性评价的主要方法包括m a x - m i nf a i r n e s s l 4 4 ，f a i r n e s si n d e x l 4 5 1 和 p r o p o r t i o n a lf a i r n e s s t “q 等。m a x m i nf a i r n e s s 被非正式的定义为：每个用户的吞吐 量至少和其它共享相同瓶颈的用户的吞吐量相同。m a x - m i n f m m e 鼹是一种理 想的状况，但是它不能给出公平的程度。 3 4 2 资源分配的效率 拥塞控制算法的目的就在于有效的管理网络资源，使有限的资源能够得到 合理运用以达到资源最大化，因此资源分配的效率就是评价拥塞控制算法有效 性的一个重要的指标。 资源分配的效率可以用p o w e 一目【4 3 函数来评价。p o w e r 函数定义为： p o w e r = t h r o u g h p u t a r e s p o n s e t i m e 在上式中，般取a - - i 。如果评价偏重吞吐量，则取a l ：如果评价偏重反 应时间，则取a l 。但是p o w e r 函数更加侧重于单一资源分配的合理性问题， 因而对于整个网络的拥塞控制的有效性不能给出一个好的评价。 3 5 队列管理 队列管理通过选择何时丢弃何种业务流分组来控制队列长度，队列管理和 拥塞控制存在着密切的联系。目前关于路由器的管理机制可分为两类：被动式 队列管理( p a s s i v eq u e u em a n a g e m e n t ，p q m ) 和主动式队列管理( a c t i v eq u e u e m a n a g e m e n t ，a q m ) 。 3 5 1 被动式队列管理 管理路由器队列长度的传统技术是对每个队列设置一个最大值( 以包为单 位) ，然后接受包进入队列直到队长达到最大值，接下来到达的包就要被拒绝进 入队列直到队长下降。这种技术也就是所谓的“去尾”( d r o p t a i l ) 算法。从拥塞 山东大学硕士学位论文 控制的角度分析，它是一种拥塞恢复机制，已经在i n t e r n e t 上成功使用了许多年， 但其存在几个重要缺陷： ( 1 ) 死锁( l o c k o u t ) ：在某些情况下，由于同步( s y n c h r o n i z a t i o n ) 或其它定时作 用的结果，“去尾”算法会让某个流或者少数几个流独占队列空间，阻止其它流 的包进入队列。 ( 2 ) 满队列( f u l lq u e u e s ) ：由于“去尾”算法只有在队列满时才会发出拥塞信 号，因此会使得队列在相当长时间内处于充满( 或几乎充满) 的状态。而队列管 理最重要的目标之一就是降低稳定状态下队列的长度，因为端到端的延迟主要 就是由于在队列中排队等待造成的。 ( 3 ) t c p 全局同步( t c pg l o b a ls y n c h r o n i z a t i o n ) ：由于互联网上数据的突发本 质，到达路由器的包也往往是突发的。如果队列是满的或者几乎是满的，就会 导致在短时间内连续大量地丢包。而t c p 流具有自适应特性，源端发现包丢失 就会急剧地减小拥塞窗口，包到达速率就迅速下降，于是网络拥塞得以解除， 但源端得知网络不再拥塞后又开始增加发送速度，最终又造成网络拥塞。而且 这种现象常常会周而复始地进行下去，从而在一段时间内网络处于链路利用率 很低的状态，降低了整体吞吐量，这就是所谓的“t c p 全局同步”现象。 除了“去尾”机制，另外两种在队列满时进行队列管理的机制是“随机丢 弃”( r a n d o m d r o p ) 和“前部丢弃”( d r o p f r o n t ) 机制。当队列满时，前者从队列 中随机找出一个包丢弃以让新来的包进入队列；后者从队列头部丢包，以便让 新包进入队列。这两种方法虽然都解决了“死锁”问题，但仍然没有解决“满 队列”问题。由于这几种方法都是在队列满了之后被迫丢包，因此称为被动式 队列管理。 3 5 2 主动式队列管理 “首丢弃”和“随机丢弃”对死锁和全局同步是有效的，但没有解决持续 的满队列问题。如果路由器在拥塞发生前采取一些预防措施，那么满队列问题 是可以得到解决的。主动的而非响应性的分组丢弃就是一种有效的手段，相应 的队列管理策略被称为“主动队列管理”( a c t i v eq u e u em a n a g e m e n t ，a q m ) ， 它是近来端到端拥塞控制研究中的一个热点。a q m 与e c n 结合，通告拥塞的 山东大学硕士学位论文 信号不再是唯一的分组丢弃，而可以采用标记分组来通知信源减速，这样会进 一步提高连接的有效吞吐量。a q m 的主要技术目标是在减小排队时延的同时保 证较高的吞吐量，具体分析a q m 解决的问题主要包括以下4 方面： ( 1 ) 早期探测路由器可能发生的拥塞，并通过随机丢弃或标记分组来通知源 端采取措施避免可能发生的拥塞。 ( 2 ) 公平地处理包括突发性、持久性和间隙性的各种t c p 业务流。 ( 3 ) 避免多个t c p 连接由于队列溢出而造成同步进入“慢启动”状态。 ( 4 ) 较小的队列长度，在高吞吐量和低时延之间做出合理平衡。 虽然b r a d e n 等人在i e t f 提出a q m 的研究是在1 9 9 8 年1 6 1 ，但与其密切相 关的r e d ( r a n d o m a r l ye a r l yd e t e c t i o n ) 算法的研究却是由来已久了。早在1 9 9 3 年， f l o y d 和j a c o b s o n 就提出了r e d l 4 7 1 ，当时的主要目的是克服“早期随机丢弃” ( e a r l yr a n d o md r o p ) 网关偏袒突发业务而造成的不公平问题。因为在提出a q m 的研究时，r e d 是唯一一个能实现这一技术目标的算法，所以r f c 2 3 0 9 将其 推荐为a q m 的唯一候选算法，随后，围绕着a q m 和r e d 的研究逐渐丰富起 来。 3 5 3 随机早期检测算法r e d r e d ( r a n d o m e a r l y d e t e c t i o n ) 是“主动队列管理”算法中最著名的一个。 它的基本思想是通过概率丢失或标记来通知端系统网络拥塞的情况。在r e d 中 使用平均队列长度来度量网络拥塞的程度，然后使用线性的方式将拥塞控制程 度反馈给端系统。 3 5 3 1r e d 算法的基本原理 r e d 队列管理增添了两种新机制：其一，不是等队列全满后再丢弃到来的 分组，而是利用概率判定机制事先丢掉部分分组来预防可能发生的拥塞；其二， 通过平均队列而非即时队列调整分组丢弃概率，由此来尽可能地吸收部分短暂 的突发流量。平均队列长度是用指数加权滑动平均( e w m a ) 来计算的： a v g 一( 1 一w q ) a v g + w q q ( 1 ) 当分组到达队列时，如果平均队列长度a v g 小于最小门限值r n i ，分组安 山东大学硕士学位论文 全进入队列；当a v g 大于m a x t h ，丢弃所有到达报文；如果平均队列长度a v g 位于 i n i 虬和m a x ( 最大门限值) 之间，按如下计算分组丢弃概率p b ： p b = m a x p ( a v g m i n n i ) ( m a x n i m i n n i ) ( 2 ) p = p d ( i c o u n txp b )( 3 ) 其中， m a x p 是最大丢弃概率，a v g 是加权平均队列长度，c o u n t 是连续成 功传输的分组数。式( 3 ) 是为了保证被丢弃分组间隔的均匀分布。 因为p b 是一 个很小的正数，1 - c o u n t * 1 ) l , 很接近于1 ，所以p b 是丢失率的主要决定因素，对 p 。的修正用于避免连续丢包，故以后仅考虑p 。由于p a 是随着当前队列长度的 变化而变动的，该机制的最大适应范围为丢包率在【o ， m a x p 流量，当然，实 际范围要小得多。 综上所述，总结出丢弃概率p b 的表达式： r 0 a v g m i n t h i p b = _ m a x p ( a v g m i n t h ) ( m a 】【血一m a n t h ) m m t h = a v g = m a x t h 平均队长与丢包概率的关系如图3 - 2 所示。 p l l m a x p r e d 算法描述如下： m i n t hm a 再 a - 譬 图3 - 2 r e d 的丢弃概率 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 et h en e wa v e r a g eq u e u es i z ea v g i fm i n t h = a v g = m a x q ( a v g _ o = m a x _ t h q l e n i 2 * a v g c q ) ( q l e n i = a v g c q s t r i k e i 1 ) ) s t r i k e i + + ： d r o pp a c k e tp ： e l s e o p e r a t ei nr a n d o md r o pm o d e ： i f ( q l e n i 一0 ) n a c t i v e + + ： c a l c u l a t ea v e r a g eq u e u el e n g t h a c c e p tp a c k e tp ： f o re a c hd e p a r t i n gp a c k e tp ： c a l c u l a t ea v e r a g eq u e u el e n g t h i f ( q l e n i = 0 ) n a c t i v e 一： d e l e t es t a t et a b l ef o rf l o wi ； i f ( n a c t i v e ) a v g c q = a v g _ q n a c t i v e ： e l s e a v g c q2a v g _ q ； a v g c q = m a x ( a v g c q ， 1 ) ： i fq = = 0 p a c k e td e p a r t e d q _ t i m e2t i m e ： 山东大学硕士学位论文 全局变量、函数： n a c t i v e ：活跃流数量 m i nt h ：队长最小阈值 m a x t h ：队长最大阂值 m a x p ：每流最多允许在缓冲区中排队的包的数量 m i n p：每流最少允许在缓冲区中排队的包的数量 q ：当前队列占用大小 t i m e ：当前时间 a v g _ q ：平均队长 a v g c q ：每流的平均队长 c o r m ( p ) ：包p 的流标识 q l e n i：排队的包的数量 s t r i k e i ：对拥塞通知没有反应的次数 当一个包进入路由器时，如果平均队长a v g 小于m a x t h ，并且该包所属流在缓 冲区中排队包的数量小于m i n q ，那么该包总被接收。这样，f r e d 就保护了脆弱的 流，比如小窗口的流。当该流的q l e n i m a x p 时，则标记该流的概率就会大大增 加。如果该流的s t r i k e 大于1 ，则说明该流为非适应流，那么就不允许该流占用 的队长q l e n i 超过平均值a v g e q 。从而保护适应流，惩罚非适应流。 f r e d 的主要目的是解决r e d 算法的公平性问题。其主要优点有： ( 1 ) 对非适应流进行了有效的鉴别和限制。 ( 2 ) 丢包率依赖于该流对缓冲区的占用，从而保护了脆弱的流。 ( 3 ) 和r e d 相比，其平均传输时间也更为公平。 其主要缺点在于计算量较大，需要维持每个流的状态表。增加了路由器的额外负 担，并且在平均传输延时上会产生偏见。 3 6 2a r e d 自适应r e d 算 法( a d a p t i v e r e d ，a r e d ) 提出了一种自动配置机制，根据流 量的变化来配置适当的参数。a r e d 的基本思想就是通过检查平均队长的变化 来感知r e d 是应更激进还是更保守。如果平均队长是在m i n _ t h 附近振荡，那 山东大学硕士学位论文 么拥塞控制就太激进了；如果在m a x _ t h 附近振荡，那么拥塞控制就太保守了。 基于所观察到的平均队长，a r e d 动态地调整m a x p 的值，a p e d 具体算法伪代 码如下所示： e v e r yq ( a v e ) u p d a t e ： i f ( m i n t h ( ( a v e ) 来记录第t 个包是否击中，如果击中，则h i t ( t ) 取值 为1 ，否则为0 。从恶意流相比较良好流更易引发”击中”这个意义上说，如果一个 包引发”击中”，则可认为该包属于恶意流。如果一个包”击中”并且该僵尸的c o u n t 值很大，就更明显了。 s r e d 克服t r e d 队长波动的缺点，在相当大的负荷范围内，s r e d 都能保持队 列的稳定而与活跃流的数量相独立，从而有效地减小了延迟抖动。s r e d 也给出了 鉴别恶意流的方法并且对其进行惩罚。 但是s r e d 的缺陷有： ( 1 ) 对异质的流量，p ( i ) - 1 不能很好地估计活跃流地数量。 ( 2 ) 参数设置问题：与r e d 中的参数设置问题一样，s r e d 中参数p s r e d 、p m a x 的 山东大学硕士学位论文 设置也需要依赖不同的网络流量情况而定，包括p z a p 中2 5 6 的选择等仍然是有待 研究的问题。 ( 3 ) s r e d 虽然给出了鉴别恶意流的方法，但并没有提高一种量化的标准，比如 通过对c o u n t 值进行分级，以此判断一个流是否为恶意流。而且s p e d 也没有给出 一个有效的限制恶意流的机制。 s r e d 具体算法伪代码如下： f o re a c hp a c k e ta r r i v a l i fp a c k e tb e l o n g st oan e wf l o w c r e a t ef l o ws t a t e ： i fq u e u ei sf u l l d r o pp a c k e t ： l a s t d r o p t i m e ： e l s ee n q u e u ep a c k e t ： e l s ei f ( p a c k e tb e l o n g st oab a t t e r e df l o w t i m e l a s r d r o p p t i m e ) i fq u e u ei sf u l l d r o pp a c k e t ： l a s t d r o p 一t i m e ： e l s ee n q u e u ep a c k e t ： e l s ep a c k e ti sh a n d l e db yr e d ： u p d a t ea v ga si nr e d l a s t a r r i v a l 一t i m e ： 3 6 4 小结 上述三种算法分别从不同的角度采取不同的方法对r e d 算法做了改进。就改 进的角度来说，通过数据分析可得知s r e d 从获得低延时抖动和低丢包率的角度改 进；s r e d 采用不同于r e d 的丢包率的计算方式，显著增强了平均队列长度的稳 定性，解决了r e d 算法时延抖动的问题。f r e d 从获得高公平性的角度做了改进， 通过记录每个连接的信息来区分对待不同数据流，有效地遏制了非适应流大量侵 占网络带宽，提高了各连接共享带宽的公平性，从而具有最大的t c 吞吐量。而a r e d 算法仅从调整配置参数的角度改进r e d 算法，使算法在各种负载环境下均获得较 高的吞吐量和较低的丢包率，减轻t p e d 参数配置带来的网络性能不稳定问题。 在瓶颈链路带宽较小的网络中，f r e d 和a p e d 算法适用于平均时间延迟较高的情 况。s r e d 贝o 有助于提高t c p 流服务质量。 山东大学硕士学位论文 另外，w r e d 通过为不同的业务等级设定不同的最大丢弃概率来提供不同 的服务质量；为克服负载变化对r e d 稳定性的影响，s t a b i l i z e d - r e d 通过判定 新到来的分组是否，命中0 ( h i t ) 从称为z o m b i e s 的列表中任意选出的记录项来估 计网络中激活的连接数，并用它修正分组丢弃概率，使s r e d 不再像r e d 一样 敏感连接数，能工作在较为广泛的网络环境中s r e d 采用瞬时队长，而非平均 队长探测拥塞，分组丢弃概率的计算也与r e d 完全不同。 s e l f - c o n f i g u r a t i o n r e d t