（计算机软件与理论专业论文）主动式队列管理算法研究及仿真分析.pdf

哈尔滨丁程大学硕士学位论文 摘要 随着互联网规模的快速增长，拥塞已经成为一个十分重要的问题。近年 来主动式队列管理算法已经成为端到端拥塞控制的一个研究热点。它通过评 估网络状态、预测早期拥塞的出现，有目的地对分组进行丢弃，从而可以使 源端更及时地了解到网络状况并调整发送速率。r e d ( 随机早期检测) 算法 是i e t f 推荐的主动式队列管理算法的唯一候选算法，然而算法在响应速度、 稳定性及参数设置等方面仍有缺陷。对此，本文对r e d 算法的参数设置进行 了修正，并在网络仿真器n s 2 上对修正算法进行了验证。本文主要研究工作 包括： 首先研究r e d 算法的参数设置问题：r e d 算法中的权值w a 、最大丢包 率m a x p 、最小阈值m i n 血和最大阈值m a 孙。其次在保持原算法思想不变的前 提下，针对小的r t t ( 往返时延) 场景，修正r e d 算法的参数配置：修正 权值w a 的设置来更好地计算平均队列长度，修正a d a p t i v er e d 算法中的 i n t e r v a l 设置来使算法响应速度更快。最后使用网络仿真器n s 2 验证算法修 正后的有效性。 本文的研究成果对主动式队列管理算法的研究有一定的参考意义，对 r e d 算法在路由器上的部署有重要价值。 关键词：拥塞控制；主动式队列管理；随机早期检测；网络仿真器 哈尔滨t 程大学硕十学位论文 a b s t t a c t a st h er a p i dd e v e l o p m e n to fi n t e r a c t ，n e t w o r kc o n g e s t i o nh a sb e c o m ea n i m p o r t a n ti s s u e r e c e n t l ya q m ( a c t i v eq u e u em a n e g e m e n t ) h a sb e e nah o t s p o t i ns t u d i e so nt h ee n d t o - e n dc o n g e s t i o nc o n t r 0 1 b ye v a l u a t i n gt h en e t w o r ks t a t e a n dp r e d i c t i n gt h ei n c i p i e n tc o n g e s t i o n , i tg a l ld r o pp a c k e t sp u r p o s e f u l l y , t h u s s o u r e , e sc a l lb ew e l li n f o r m e dt h en e t w o r ks t a t ea n dt h e na d j u s ti t ss e n d i n gr a t e a s t h eo n l yc a n d i d a t e a l g o r i t h mf o ra q mr e c o m m e n d e db yi e t f ( i n t e m e t e n g i n e e r i n gt a s kf o r c e ) ，t h er e d ( r a n d o me a r l yd e t e c t i o n ) a l g o r i t h mi ss t i l ln o t p e r f e c ti nt e r m so f r e s p o s et i m e s t a b i l i t ya n dp a r a m e t e rs e t t i n g t i l i sp a p e rr e v i s e s t h ep a r a m e t e rs e t t i n go f r e da l g o r i t h m , a n dv a l i d a t e st h er e v i s e da l g o r i t h mu s i n g n s 2 ( n e t w o r ks i m u l a t o rv e r s i o nt w o ) m a i nr e a s e r e hw o r ki n c l u d e st h e f o l l o w i n g ： t h i st h e s i sf i r s tw o r k so nt h ep a r a m e t e rs a t i n gi s s u eo f r e d ：t h ew e i g h tw q , t h em a x i m u md r o pp r o b a b i l i t ym a x p ，t h em i n i m u mt h r e s h o l dm i n t ha n dt h e m a x i m u mt h r e s h o l dm a x t h t h e nw h i l el e a v i n gt h eb a s i ci d e ai n t a c t , t h i sp a p e r r e v i s e sp a r a m e t e rs e t t i n go ft h er e da l g o r i t h mo ns c e n a r i o sw i t hs m a l lr 兀 ( r o u n dt r i pt u n e ) ：r e v i s i n gt h ew e i g h tw qt ob e t t e re a l e n l a t et h ea v e r a g eq u e u e l e n t ha n dr e v i s i n gt h ep a r a m e t e ri n t e r v a lt 0s h o r t e na d a p t i v er e d sr e s p o s et i m e l a s t , t h i sp a p e rv a l i d a t e st h em o d i f i e dr e d u s i n gn s 2 t h er e s e a r c hi nt h i st h e s i sp r o v i d e sav a l u a b l er e f e r e n c ef o rf u r t h e rs t u d yo n a q ma l g o r i t h m ；f u r t h e l t f l o r ei t i so fg r e a tv a l u et ot h er e dd e p l o y m e n to n r o u t e r s k e y w o r d s ：c o n g e s t i o nc o n t r o l ，a c t i v eq u e u em a n a g e m e n t , r a n d o me a r l y d e t e c t i o n , n e t w o r ks i m u l a t o r 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指 导下，由作者本人独立完成的。有关观点、方法、数据 和文献的引用己在文中指出，并与参考文献相对应。除 文中已注明引用的内容外，本论文不包含任何其他个人 或集体已经公开发表的作品成果。对本文的研究做出重 要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 作者( 签字) ：盆盎 e t 期：二d 年月“日 i 哈尔滨工程犬学硕+ 学位论文 1 1 引言 第1 章绪论 在研究新的网络协议的过程中，实验测试和验证是非常必要的，但用物 理网络进行测试和验证往往是代价较高甚至是不现实的。在这种情况下，仿 真就成了重要手段之一。网络仿真周期小、成本低，它可以使研究者更容易 利用他人的研究成果，更专注于自己所研究的部分而不必为系统的其它部分 耗费过多的精力。 近年来，随着网络技术的快速发展和变化，研究者提出了各种新的协议 和算法，以满足q o s ( q u a l i t yo fs e r v i c e ) 、多播、安全、移动网络、策略管 理等新的需求，但设计和评估这些协议和算法却要涉及许多问题。虽然在实 验室、测试床等真实环境下进行实际试验都很有价值，但它们都缺乏相当的 灵活性和扩展性，并且成本太高，而多协议的网络仿真器( n s 2 ，n e t w o r k s i m u l a t o r v e r s i o nt w o ) 以极低的成本提供了丰富的实验环境，同时，由于网 络的快速增长而导致的扩展性和异构性对现在的协议机制和相关的设计方法 提出了挑战，因此，无论对于新的网络协议开发，还是对现有网络规划设计， 网络的仿真都有其重要意义。 端到端的拥塞控制是目前i n t e m e t 的一个研究热点。虽然t c p 端到端的、 基于窗口的拥塞控制算法对于拥塞控制很有必要，也非常有效，但是随着越 来越多需要q o s 支持的应用的快速发展( 基于实时传输协议( r t p ，r e a l - t i m e t r a n s p o r tp r o t o c 0 1 ) 的视频会议，远程医疗，网络教学等实时应用程序) ，仅 仅依靠t c p 拥塞控制已不足以保证q o s 。因为路由器能够有效地监控队列的 长度，所以它能有效地检测早期的拥塞。因此，近来的研究越来越强调网络 中间节点( 路由器) 在拥塞控制中的作用。 网络中的拥塞来源于网络资源和网络流量分布的不均衡性。拥塞不会随 着网络处理能力的提高而消除( 例如，增加网关缓冲会增大报文通过网关的 延迟，如果总延迟超过端系统重传时钟的值，就会导致报文重传，反而加重了 拥塞) ，拥塞控制算法的分布性、网络的复杂性和对拥塞控制算法的性能要求 哈尔滨t 程大学硕十学t i ) = 论文 又使拥塞控制算法的设计具有很高的难度。 1 2 国内外研究现状 下面分别介绍n s 2 和拥塞控制算法的研究概况。 1 2 ，1n s 2 研究现状 随着仿真技术快速发展，其应用领域越来越广，作为仿真领域一个分支 的网络仿真技术也获得了快速发展。国外网络仿真技术已经相当的成熟，已 经由小型网络仿真器向大型混合网络仿真器发展，甚至有的发达国家已经实 现了联合网络仿真平台。但国内相对比较落后，主要是对一些小型网络进行 仿真，仿真方法主要还是停留在经验、实验和计算基础上，对网络仿真技术 还没有进行系统地研究。 n s 2 是一种针对网络技术的源代码公开的、免费的软件模拟平台。目前， 它所包含的模块已经非常丰富，几乎涉及了网络技术的所有方面，所以，n s 2 成为了学术界广泛使用的一种网络模拟软件，在每年国内外发表的有关网络 技术的学术论文中，利用n s 2 给出模拟结果的文章最多，通过这种方法得出 的研究结果也是被学术界所普遍认可的。此外，n s 2 也可作为一种辅助教学 的工具，目前已被广泛应用在了网络技术的教学方面。 1 2 2 拥塞控制算法的研究概况 从控制理论的角度，拥塞控制算法可以分为开环控制和闭环控制两大类 n ，。当流量特征可以准确规定、性能要求可以事先获得时，适于使用开环控制； 当流量特征不能准确描述或者当系统不提供资源预留时，适于使用闭环控制。 i n t e r a c t 中主要采用闭环控制方式。 闭环的拥塞控制分为以下三个阶段：检测网络中拥塞的发生；将拥塞信 息报告到拥塞控制点；拥塞控制点根据拥塞信息进行调整以消除拥塞。闭环 的拥塞控制可以动态地适应网络的变化，但它的一个缺陷是算法性能受到反 馈延迟的严重影响。当拥塞发生点和控制点之间的延迟很大时，算法性能会 严重下降。 2 哈尔滨t 程大学硕士学位论文 根据算法的实现位置，可以将拥塞控制算法分为两大类：链路算法( l i n k a l g o r i t h m ) 和源算法( s o u r c ea l g o r i t h m ) 。链路算法在网络设备( 如路由器 和交换机) 中执行，作用是检测网络拥塞的发生，产生拥塞反馈信息。源算 法在主机和网络边缘设备中执行，作用是根据反馈信息调整发送速率。拥塞 控制算法设计的关键问题是如何生成反馈信息和如何对反馈信息进行响应。 源算法中使用最广泛的是t c p ( t r a n s p o r tc o n t r o lp r o t o c o l ，传输控制协 议) 协议中的拥塞控制算法。t c p 是目前在i n t e m e t 中使用最广泛的传输协 议，根据m c i ( 美国著名的通讯公司) 的统计，总字节数的9 5 和总报文数 的9 0 使用t c p 传输m 。近年来，t c p 中采用了很多新的算法，包括慢启动 ( s l o ws t a r t ) 、拥塞避免、快速重传( f a s tr e t r a n s m i t ) 、快速恢复( f a s t r e c o v e r y ) 、选择性应答( s a c k ) 等，大大提高了网络传输的性能。t c p 中 使用的拥塞控制算法已经成为保证i n t e m e t 稳定性的重要因素。 t c p 算法已经过了t a h o e 、r e n o 、n e wr e n o 、s a c k 和v e g a s 等多个版 本的增强与改进，目前在n s 2 中提供的发送代理有：t c p ，t c p r e n o ， t c p n e w r e n o ，t c p v e g a s ，t c p s a c k l ，t c p f a c k ，t c p f u l l t c p 等，接 收代理有：t c p s 玳k ，t c p s 玳d e l a c k ，t c p s 科s a c k l ， t c p s i n k s a c k l d e l a c k 等。 链路算法中r e d t ，是最著名的算法，1 9 9 8 年，b b r a d e n 等人提出了主动 式队列管理( 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 在减小排队时延的同时保证较高的吞吐 量，r e d ( r a n d o me a r l yd e t e c t i o n ，随机早期检测) 符合a q m 的技术目标， i u c 2 3 0 9 m 摊荐它为主动队列管理的惟一候选算法。 随后的研究和实践表明，r e d 在鲁棒性( r o b u s t n e s s ) 方面存在一定问 题，它的性能对于设计参数和网络状况比较敏感，在特定的网络负载状况下 依然会导致多个t c p 的同步，造成队列振荡、吞吐量降低和时延抖动加剧。 鲁棒的a q m 策略成为目前i n t e r a c t 研究领域的一个技术热点，相继产生不少 有影响力的算法，如s r e d m ，f 趾n ，a r e dz ”，n e wa r e d m ，b l u e “一， a v q ，r e m ”1 ，p i “峰# 。 国内的a q m 算法研究相当少一些，都是对已有算法的改进，主要有 e b l u e “”( e n h a n c e db l u e ) 、基于内模补偿的网络拥塞控制新算法：i c a q m “”、 3 哈尔滨工稃大学硕士学位论文 延时补偿主动队列管理算法“”( d e l a yc o m p e n s a t i o n - a c t i v eq u e u em a n a g e m e n t ， 简称d c a q m ) 等。 1 3 课题的目的、意义及研究内容 1 3 1 课题的目的和意义 主动式队列管理是近年来端到端拥塞控制研究的热点。本课题第一个目 标是研究r e d 算法及其改进算法的参数设置问题；第二个目标是分析a r e d 算法的不足，在保持原算法主要思想不变的前提下，作出修正( 或补充) ， 并利用n s 2 来检验修正算法的性能是否比原有算法性能更优。 本课题介绍了几种主要的a q m 算法，并且深入研究了r e d 算法及其改 进算法的参数设置问题，这对于网络设计者和网络规划者有一定的指导意义， 另外，本课题还对钳汪d 算法的一些不足之处作出修正，并通过n s 2 验证了 修正后的算法性能确有改进，这对于i n t c r n c t 拥塞控制的研究和r e d 在路由 器中的部署有一定的推动作用。 1 3 2 论文内容及组织结构 本文的内容和章节的安排如下： 第2 章介绍几种主要的a q m 算法及其优缺点。 第3 章介绍n s 2 的类结构、组件结构和相关工具并给出在n s 2 下进行仿 真实验的一般过程。 第4 章重点研究r e d 算法的参数配置问题，并对其作出修正。 第5 章使用n s 2 测试修正算法的性能，并和原算法性能作比较，验证其 有效性( v a l i d i t y ) 。 结论部分对本文的主要工作进行概括，并指出了下一步的研究重点。 4 哈尔滨丁稃大学硕十学位论文 第2 章主动式队列管理算法 2 1 主动式队列管理( a q m ) 简介 由于i n t c m c t 采用的是统计时分复用( s t a t i s t i c a lt i m ed i v i s i o n m u l t i p l e x i n g ) 技术，因此必须提供拥塞控制机制。t c p 端到端的拥塞控制机 制是确保i n t e r n e t 鲁棒性的重要因素。在发生拥塞时，t c p 源端会降低发送 数据的速度，使得多个t c p 连接能够共享一条拥塞链路。t c p 拥塞控制机制 已被证明在防止拥塞崩溃( c o n g e s t i o nc o l l a p s e ) 方面取得了巨大的成功。 但随着近几年来计算机网络的迅猛发展，特别是多媒体业务的广泛应用， 尽管t c p 拥塞控制机制是不可或缺的并且非常强大，仍然需要采用基于路由 器的拥塞避免机制对端节点的拥塞控制机制进行补充。 拥塞避免机制的首要任务是检测早期的拥塞，因为路由器能够有效地监 控队列的长度，所以它能有效地检测早期的拥塞( m c i p i e n tc o n g e s t i o n ) ；拥 塞避免机制的另一个任务是选择哪个流发出拥塞通知，因为路由器能够全面 地审视各个流对产生拥塞的影响，因此它能够有效地决定将拥塞信息通知哪 个源端，使其降低数据发送速度。 因为路由器是基于包交换的设备，每个端口采用带宽统计复用，所以路 由器必须在端口上维护一个或多个队列，否则路由器无法处理多个数据包同 时向同一端口转发以及端口q o s 等问题。对队列进行管理直接影响路由器性 能、拥塞管理能力以及q o s 能力。路由器有两类控制队列的算法：队列管理 算法和队列调度算法m 。前者主要是在必要时通过丢包来管理队列长度而后者 决定下一个要发送哪个包，主要用来管理各流之间带宽的分配。 i n t e m e t 数据本质上是突发的，因此允许传输突发的数据包非常必要，而 路由器缓存的重要作用就是吸收( a b s o r b ) 突发的数据包。较大的缓存能够 吸收更多的突发数据，提高吞吐量，但t c p 机制往往会保持较高的队列占用， 从而增加了数据包的排队延迟，因此需要路由器对队列进行管理，维持较小 的队列长度。因为维持较小的队列长度不但可以降低排队延迟，提高吞吐量， 而且能保持较大的队列空间来吸收突发数据包。拥塞控制机制就是要使网络 哈尔滨下稃大学硕+ 学位论文 维持低延迟高吞吐量的状态。 当前的队列管理算法可以分为两大类：被动式队列管理( p a s s i v eq u e u e m a n a g e m e n t ，p q m ) 和主动式队列管理( a c t i v eq u e u em a n a g e m e n t ，a q m ) ， 下面分别予以介绍。 2 1 1 被动式队列管理及其缺点 管理路由器队列长度的传统技术是对每个队列设置一个最大值( 以包为 单位) ，然后接收包进入队列直到队列长度达到最大值，接下来到达的包就要 被拒绝进入队列直到队长下降。这种技术也就是所谓的“丢尾”( d r o p t a i l ) 算法。虽然这个方法在当前i n t e r n c 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 ) 问题：由于“丢尾”算法只有在队列满时才 会发出拥塞信号，因此会使得队列在相当长时间内处于充满( 或几乎充满) 的状态。而队列管理最重要的目标之一就是降低稳定状态下队列的长度，因 为端到端的延迟主要就是由于在队列中排队等待造成的。 ( 3 ) 全局同步( g l o b a ls y n c h r o n i z a t i o n ) 问题：由于i n t e m e t 上数据的 突发本质，到达路由器的包也往往是突发的。如果队列是满的或者几乎是满 的，就会导致在短时间内连续大量地丢包。而t c p 流具有自适应特性，源端 发现包丢失就急剧地减小发送窗口，包到达速率就迅速下降，于是网络拥塞 得以解除，但源端得知网络不再拥塞后又开始增加发送速度，最终又造成网 络拥塞，而且这种现象常常会周而复始地进行下去，从而在一段时间内网络 处于链路利用率很低的状态，降低了整体吞吐量，这就是所谓的“t c p 全局 同步”现象。 除了“丢尾”机制，另外两种在队列满时进行队列管理的机制是“随机 丢弃”( r a n d o md r o p ) 和“从前丢弃”( d r o pf r o n t ) 机制“1 。当队列满时， 前者从队列中随机丢弃一个包以让新来的包进入队列；后者从队列头部丢包， 6 哈尔滨t 程大学硕十学位论文 以便让新包进入队列。这两种方法虽然都解决了“死锁”问题，但仍然没有 解决“满队列”问题。由于上面几种方法都是在队列满了被迫丢包，因此称 为被动式队列管理。 2 1 2 主动式队列管理及其优点 在当前的i n t e r a c t 上，丢包是对端节点进行拥塞通知的重要机制，解决 路由器“满队列”的方法就是在队列充满之前丢包，这样端节点便能在队列 溢出前对拥塞作出反应。这种方法就称为“主动式队列管理”。 a q m 是一族基于f i f o ( f i r s ti nf i r s to u t ) 调度策略的队列管理机制， 使得路由器能够控制在什么时候丢多少包，以支持端到端的拥塞控制。a q m 有以下几点优势“，： ( 1 ) 减少了路由器中丢弃的包的数量：i n t e m e t 中数据包的突发本质是 不可避免的，a q m 通过保持较小的平均队列长度( a v e r a g eq u e u es i z e ) ，能 提供更大的容量吸收突发数据包，从而大大减少了丢包数。进一步说，如果 没有a q m ，会有更多的包被丢弃，这主要是因为以下三个原因： 由于使用共享的队列和p q m ，会不可避免地产生全局同步，导致很 低的平均带宽利用率，也即吞吐量很低。 t c p 从突发包的丢弃中恢复要比从单个包丢弃中恢复更复杂。 如果一个数据包在到达目的端之前被丢弃，则其在传输过程中所消耗 的资源都被浪费，降低了网络带宽的利用率。因此，不必要的包丢弃也就意 味着带宽的浪费。 ( 2 ) 对交互式服务提供了更低的延迟：a q m 通过保持较小的平均队列 长度，队列管理能够减少包的排队延迟( q u e u e i n gd e l a y ) ，而排队延迟是造 成端到端延迟( e n dt oe n dd e l a y ) 的主要原因。这对交互式应用比如w e b 浏 览、t e l n e t 业务和视频会议等非常重要。 ( 3 ) 避免了“死锁”现象：a q m 能够通过确保到来的包几乎总是有可 用的队列空间，从而阻止“死锁”行为的发生。也因为这个原因，a q m 能防止 路由器对低带宽高突发流的偏见。 下面本文将分别介绍使用比例控制器的r e d 算法( 及其改进算法) 及使 7 哈尔滨工程大学硕十学位论文 用积分控制器的几种算法。 2 2r e d 算法及其改进算法 首先介绍由j a c o b s o n 、f l o y d 等人在1 9 9 3 年提出的主动式队列管理唯一 候选算法- r e d 算法，其次介绍几种主要的改进算法。 2 2 1r e d 算法 r e d t ”拥塞控制机制的基本思想是通过监控路由器输出端口队列的平均 长度来探测拥塞，一旦发现拥塞逼近，就随机地选择连接来通知拥塞，使他 们在队列溢出导致丢包之前减小拥塞窗口，降低发送数据速度，从而缓解网 络拥塞。由于r e d 是基于f i f o 队列调度策略的，并且只是丢弃正进入路由 器的数据包，因此其实施起来也较为简单。 r e d 主要试图达到以下目标： ( 1 ) 最小化包丢失率和排队延迟； ( 2 ) 避免全局同步现象； ( 3 ) 避免对突发业务的偏见：网络中含有大量的突发数据，而“丢尾” 算法对突发业务有很大的偏见。在采用“丢尾”算法的路由器中，如果某个 流的突发性越高，则当该流的包进入队列时越容易造成队列溢出，从而导致 连续地丢弃大量的该流的包。 ( 4 ) 即使在缺乏传输层协议有效配合的情况下也能控制平均队列长度， 从而避免拥塞。 为了达成以上目标，r e d 按照指数权值移动均值e w m a ( e x p o n e n t i a l w e i g h t e dm o v i n ga v e r a g e ) 的方法来计算平均队列长度，并且随机地选择正 进入路由器的包进行丢弃。这种方法能被有效地实施而无需在路由器中维持 每个流( p e r - f l o w ) 的状态信息。 r e d 算法主要分为两个部分。首先是计算平均队列长度，以此作为对拥 塞程度的估计。另一个就是计算丢弃包的概率。 1 计算平均队列长度 由于i n t e m e t 数据的突发性，如果一个队列在很多时候是空的，然后迅 8 哈尔滨工程大学硕十学侮论文 速被充满，又很快被取空，这时就不能判定路由器发生拥塞而向源端发送拥 塞指示。因此，r e d 在计算平均队长a v g 时采用了类似低通滤波器( l o w - p a s s f i l t e r ) 带权值的方法：a v g - - ( 1 - w q ) + a v g + q * w q 。其中，w q 为权值，q 为采样测 量时实际队列长度。这样由于i n t e r a c t 数据的突发本质或者短期拥塞导致的 实际队列长度暂时的增长将不会使平均队长有明显变化，从而“过滤”掉短 期的队长变化，尽量反映长期的拥塞变化。 在计算平均队长的公式中，权值w a 相当于低通滤波器的时间常数，它决 定了路由器对输入流量变化的反应程度。因此对嘁的选择非常重要，如果 w q 过大，那么r e d 就不能有效地过虑短暂的拥塞；如果w q 太小，那么a v g 就会对实际队列长度的变化反应过慢，不能合理地反映拥塞状况，在这种情 况下，路由器就不能有效检测到早期的拥塞。w a 的值应根据不同情况预先设 置，一般来说，它是由路由器允许发生的突发业务的大小和持续的时问所决 定的。 2 计算丢包概率 计算平均队长的目的就是为了反映拥塞状况，根据拥塞的程度来计算丢 弃包的概率，从而有效地控制平均队列长度。 r e d 有两个和队列长度相关的阈值：n l i 弛和m a 硒。当有包到达路由器 时，r e d 计算出平均队长a v g 。若a v g 小于m i l l d i ，则不需要丢弃包；当 m j n m s a v 鍪m a x m 时，计算出概率p a ，并以此概率丢弃包；当a v g 大于m a x t h 时，所有的包都被丢弃( 如图2 1 所示) 。由于r e d 使用的是基于时间的平 均队长，就有可能会发生实际队长大于平均队长的情况，如果队列已满，则 到达的包只能被丢弃。 计算丢包概率p a 的方法如下： f 0 0 _ a v g m i n n 见= n l a x p * ( a v g m i n m ) ( m a x m - r a i n n ) m i n m m , g m a x m ( 2 1 ) l 1 m a ) ( m m , g b u f f e r 见2 去 q 之 1 9 9 9 年，f l o y d 又提出改进的r e d 法- - g e n t i e r e d ，其数据包的丢失 9 哈尔滨工程人学硕士学位论文 率与平均队列长度的关系如图2 2 所示。相应的计算概率p 。的方法如下： 0 0 a v g m i n m m 默一( d v g m i n m ) “m 觚m m i n m ) r n j n m 甜曙 m a x “( 2 - 3 ) ( 1 - m a x ，) ( a v g m a x , h ) m a x , h + m a x pm a x t h a v g m a x 。h ) 或者长时连续随 机地标记包( a v g m a x q ) 的次数( s t r i k e ) 。当某个流 缓存占用量频繁超过胧i ) 【a 时，将被认定为非响应流，将对其进行惩罚，即增 加该流的分组丢弃概率。如果某一个流持续占用大量的缓存空间，f r e d 将 限制它的占用空间，这种机制在大多数情况下能提供一定的公平性。但在缓 存空间不够时，无响应流进入队列的分组个数不能触发检测机制，f r e d 很 难鉴别无响应流。另外，在无响应流将其在拥塞队列中的分组清除后，立即 被归入有响应流类，在队列空间较小时，无响应流能利用这一特性绕过f r e d 的保护机制。因此，在存在大量的无响应流时，f r e d 性能较差。 f r e d 的主要目的是解决r e d 算法的公平性问题。其主要优点有： ( 1 ) 对非适应流进行了有效的鉴别和限制。 ( 2 ) 丢包率依赖于该流对缓冲区的占用，从而保护了脆弱的流。 ( 3 ) 和r e d 相比，其平均传输时间更为公平。 其主要缺点在于： ( 1 ) 计算量较大，需要维持每个流的状态表。增加了路由器的额外负担。 ( 2 ) 在平均传输延时上会产生偏见。 2 2 4a r e d 算法 在拥塞严重的网络中，路由器必须将足够多的拥塞信息通知到源端，以 充分降低负载，避免由于队列溢出而丢包。另一方面，路由器也要防止拥塞 信息过多地传给源端，从而造成瓶颈链路利用率的下降。因此，进行拥塞通 知时应充分考虑到瓶颈链路上流的数量。而r e d 并没有考虑到这一点。为此 哈尔滨丁程大学硕士学位论文 a r e d ( a s e l f - c o n f i g u r i n g r e d ) 提出了一种自动配置机制，根据流量的变化 来配置适当的参数n ，。 r e d 中，拥塞指示的发送速度是由参数m a x p 来体现的。如果m f l x p 太大， 那么丢包主要就是由于早期拥塞检测中产生的丢包造成的；如果m a x p 太小， 丢包主要就是由于队列溢出造成的。r e d 的一个弱点是平均队长对拥塞程度 和参数设置很敏感。如果拥塞不太严重或者m a x 。很大，则平均队长接近m i n t h ； 如果拥塞很严重或者m a ) 【d 很小，则平均队长接近或大于l i i r x t h 。结果造成平 均排队时延对流量负荷和参数设置很敏感。 a r e d 的基本思想就是通过检查平均队长的变化来感知r e d 是应更激 进( a g g r e s s i v e ) 还是更保守( c o n s e r v a t i v e ) 。如果平均队长是在m i n t h 附近振 荡，那么拥塞控制就太激进了；如果在m a x t h 附近振荡，那么拥塞控制就太 保守了。根据所观察到的平均队长，a r e d 动态地m a x p 调整的值。其算法如 下： e v e r ya v gu p d a t e - i f ( m i n t h a v g & & a v g t a r g e t & & m a x p _ f f e e z e _ t i m e ) p 。= p ，棚l ； l a s t _ u p d a t e = n o w ； b l u e 的主要参数有d l 、d 2 和f r e e z et i m e 。其中，d 1 决定了当队列溢 出时p 日l 增加的量，d 2 决定了当链路空闲时p l l l 减少的量。f r e e z e _ t i m e 决定了 连续改变p i i l 的最小时间间隔，使得p l l l 改变之后在再次变化之前能有效发挥 作用。一般来说，d l 要比d 2 大很多，这主要是因为当拥塞管理太保守或太 激进时，都会导致链路使用率很低；而丢包只发生在拥塞管理太保守时。这 样，通过赋予丢包事件更大的比重，b l u e 能够对流量大量迅速地增加很快 地作出反应。 b l u e 最大的贡献在于，使用相对较小地缓冲区就能够完成拥塞控制。 这样，b l u e 减少了端到端延迟，提高了t c p 流的吞吐量。另外，较小的缓 冲区需求也使得路由器有更多的自由空间来执行其它的路由器功能，比如存 储更大的路由表，从而提高了路由器的性能。而要达到类似的效果，r e d 则 需要大很多的缓冲区。 b l u e 基于丢包事件和链路空闲事件的拥塞管理，能够较好地估计拥塞 程度，从而作出适当的反应。因此其标记包的比率相对较稳定，这又使得队 长也相对稳定，减少了延迟抖动。 2 2 7r e d 算法改进策略分析 前面给出的几种算法分别从不同的角度采取不同的方法做了改进，取得 了较好的效果，但是仍存在各种缺陷。 就改进的角度来说，a p e d ，n e wa r e d 从调整配置参数的角度，s r e d 和b l u e 从获得低时延抖动和低丢包率的角度，f r e d 从获得高公平性的角 度分别改进了r e d 算法。就方法来说，a r e d ，n e wa r e d 仍采用r e d 丢 哈尔滨下稃大学硕+ 学竹论文 包概率p b 计算方法，但是它根据平均队列长度的变化自动调整p b ，使算法在 各种负载环境下均获得较高的吞吐量和较低的丢包率，减轻了r e d 参数配置 带来的网络性能不稳定问题；s p e d 算法采用不同于r e d 的丢包概率计算方 式，根据当前连接数目、当前队列长度和连接带宽占用三个因素来计算数据 包丢弃概率，显著增强了平均队列长度a v g 的稳定性，解决了r e d 算法存在 的时延抖动问题；b l u e 算法也采用不同于r e d 的丢包概率计算方式，它 基于包丢失概率和当前链路利用率来计算包丢弃概率，使用较小的缓冲区完 成了拥塞控制，同时获得了较高的吞吐量和较低的网络时延；f r e d 算法改 进了r e d 带来的公平性问题，它通过记录每个连接的信息来区分对待不同数 据流，有效地遏制了非适应流大量侵占网络带宽，提高了各连接共享带宽的 公平性。 就缺陷来说，a r e d 的主要问题是a 、b 等参数的设置；n e w a r e d 有、 1 3 和i n t e r v a l 等参数设置的问题；s p e d 存在p _ t l 。和2 5 6 等参数的设置问题； b l u e 同样存在f r e e z e t i m e 、d l 、d 2 等参数的合理选择问题；f r e d 的主要 缺陷是计算量太大，增加了路由器的负载。 2 0 0 1 年，在a q m 算法研究方面又提出了r e m ( r a n d o me x p o n e n t i a l m a r k i n g ) ，p i 和a v q ( a d a p t i v ev i r t u a lq u e u e ) 等。它们的基本思想都是在 a q m 中使用p i 控制器，下面分别对其进行简单介绍。 2 3p i 控制器算法 在r e d 和a d a p t i v er e d 中使用比例( p r o p o r t i o n a l ) 控制器。比例控制 器的基本形式为：p i = k q i 。其中k 是计算使用的比例系数。比例控制器非常容 易实现，而且在反应速度方面性能很好。 r e d 在比例控制器的基础上做了以下一些修改。为了减小“瞬时抖动” 对反馈计算的影响，r e d 引入了低通滤波器，将上式中的q i 使用平均队列长 度g 代替。平均队列长度使用e w m a ( e x p o n e n t i a lw e i g h t e dm o v i n ga v e r a g e ) 计算： = ( 1 一w ) + + w + g f ( 2 - 5 ) 其中w 是计算的权重。只有在平均队列长度位于m i n 和m a x m 之间的时 1 7 哈尔滨丁程大学硕七学位论文 候，r e d 才使用比例控制器来计算，这使得r e d 的控制中存在不连续的地 方。r e d 使用低通滤波器降低了系统的反应速度，固定的w 不能适应不同负 载的网络链路。 比例控制器的缺点是控制存在“稳态误差”( s t e a d y s t a t ee r r o r ) ，稳态误 差的大小依赖于网络的环境，这是平均队列随网络流量增长的主要原因。有 时可能出现误差超过缓冲的大小，从而引起振荡现象的发生。a d a p t i v er e d 通过增加自适应机制来解决这个问题。 p i 控制器通过增加积分因素来消除比例控制器中存在的稳态误差n ”。p i 控制器的基本形式为： p i + 1 = n + a ( q j “一g ) + 6 吼+ l ( 2 6 ) g ，“= 吼“一吼 ( 2 - 7 ) 其中q 是控制的目标，a 和b 是比例系数。通过在反馈计算中引入积分 项，p i 控制器可以有效的消除p r o p o r t i o n a l 控制器中出现的“稳态误差”， 从而保证队列长度的稳定。给出了确定p i 控制器参数的方法。a q m 算法中 使用p i 控制器虽然可以消除“稳态误差”，但同时也会减慢系统的反应速 度。当网络中的流量发生很大变化时，使用p i 控制器需要的收敛时间要远远 长于使用比例控制器的情况。另外，p i 控制器设置的一组参数只能适应比较 有限范围的网络环境。这使得在实际网络环境中使用p i 控制器存在一定的困 难。 2 4 自适应虚队列算法 a v q 是基于虚拟队列分组标记算法之一，与r e d 算法依据平均队列长 度判断系统的拥塞状态不同，a v q 算法认为直接对队列长度进行控制是导致 算法鲁棒性较差的原因，在系统的t c p 流