（计算机应用技术专业论文）基于智能控制的主动队列管理算法研究.pdf

摘要 摘要 在过去的二十年中，计算机网络经历了爆炸式的增长，随之而来的是 越来越严重的拥塞问题。拥塞控制是确保i n t e m e t 鲁棒性的关键因素，也 是其它服务质量机制正常工作的必要前提，因此成为当前网络研究的一个 热点问题。其中，a q m ( 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 算法，并分析了引入智能控制来改善拥塞控制的可行性。 其次，在深入研究分析p i ( p r o p o r t i o n a li n t e g r a l ) 控制器的基础上，将模 糊控制与p i 控制器相结合，提出了一种基于模糊控制的拥塞控制算法 a f p i ( a d a p t i v ef u z z yp r o p o r t i o n a li n t e g r a l ) ，并从模糊化、模糊推理、清晰 化三方面给予了详细的阐述。 然后，研究了再励学习r l ( r e i n f o r c e m e n tl e a r n i n g ) 的相关技术，利用 其中的瞬时差分t d ( t e m p o r a ld i f f e r e n c e ) 法结合二重梯度下降法，并引入 了拥塞控制信号优先传递的思想，提出了适用于网络中间节点拥塞控制的 p r l ( p r i o r i t yr e i n f o r c e m e n tl e a r n i n g ) 算法。 最后，在n s ( n e t w o r ks i m u l a t i o n ) 仿真平台上，模拟仿真了上述算法的 队列长度稳定性、鲁棒性、公平性和r t t ( r o u n dt r i pt i m e ) 多方面性能， 并分析讨论了实验结果，验证了a f p i 算法和p r l 算法的可行性。 关键字拥塞控制；模糊控制；再励学习；主动队列；n s 燕山大学工学硕士学位论文 a b s t r a c t i nt h ep a s tt w e n t yy e a r s ，t h ec o m p u t e rn e t w o r kh a se x p e r i e n c e de x p l o s i v e g r o w t h t h ec o n g e s t i o np r o b l e m sa r ea l s os e r i o u sd a yb yd a y t h ec o n g e s t i o n c o n t r o li si m p o r t a n tt og u a r a n t e et h ei n t e r n e tr o b u s t i ti sa l s oan e c e s s a r y p r e r e q u i s i t eo fo t h e rq u a l i t yo fs e r v i c ef o rt h en o r m a lw o r k t h e r e f o r ei t b e c o m e sah o tt o p i cc u r r e n t l y i nt h ec o n g e s t i o nc o n t r o ld o m a i n , a q mi sah o t s p o tr e s e a r c hd i r e c t i o n i tc a nm a k e ar e a s o n a b l eb a l a n c ei nt h eh i g ht h r o u g h p u t a n dl o w0 c l a y f r o mt h ep o i mo fv i e wo fc o n t r o ls y s t e m , t h i si st h eb e h a v i o r w h i c hg o v e r n ss y s t e m so v e r a l lp e r f o r m a n c e t h ec o n t r o lt h e o r yi saq u i t e m a t u r es y s t e mt h e o r y s o m em a n ym e t h o d sm a yp r o f i tt h ec o n g e s t i o nc o n t r o l , a n de n h a n c ei t sp e r f o r m a n c e f i r s t l y , t h ec o n g e s t i o nc o n t r o lm e c h a n i s mw h i c ha tp r e s e n to f t e nu s e si s a n a l y z e d ，a n dt h er e p r e s e n t a t i v ea q ma l g o r i t h mi si n t r o d u c e d , t h e nt h e f e a s i b i l i t yo ft h ei n t r o d u c t i o no fi n t e l l i g e n tc o n t r o lt oc o n g e s t i o nc o n t r o li s a n a l y z e di nd e t a i l s e c o n d l y , o nt h eb a s i so fa n a l y s i sa n dr e s e a r c ho n p ic o n t r o l l e ri n - d e p t h , a f p ia l g o r i t h mi sp r o p o s e db yc o m b i n i n gp ic o n t r o l l e rw i t hf u z z yc o n t r o l , a n d h a sb e e ng i v e nt h ed e t a i l e de l a b o r a t i o nf r o mt h et h r e ea s p e c t so f 蛹t h e f u z z yi n f e r e n c e ，a n dt h ec l e a r t h i r d l y , t h er e i n f o r c e m e n tl e a r n i n gt e c h n o l o g yi sr e s e a r c h e d n o to n l yt h e t e c h n o l o g yt h a ti sc o m b i n e dt h et e m p o r a ld i f f e r e n c et e c h n o l o g yw i t hd o u b l e g r a d i e n t d e s c e n tt e c h n o l o g yi sm a d eu s eo b u ta l s ot h et h o u g h tt h a t c o n g e s t i o nc o n t r o ls i g n a lf i r s tt r a n s m i t si sl e di n t o t h e n , p r la l g o r i t h mi s p r o p o s e d i ti ss u i t a b l et oc o n g e s t i o nc o n t r o li nt h em i d d l en o d e f i n a l l y , i nt h en ss i m u l a t i o np l a t f o r m , t h ee x p e r i m e n t a lp e r f o r m a n c e a b o v ea l g o r i t h mf r o mq u e u el e n g t hs t a b i l i t y ，r o b u s t n e s s ，f a i r n e s sa n dt h er 1 盯 a b s t r a c t a r es i m u l a t e d , a n dt h ee x p e r i m e n t a lr e s u l t sa r ea n a l y z e da n dd i s c u s s e d ，t h e nt h e f e a s i b i l i t yo f t h ea f p ia l g o r i t h ma n dp r la l g o r i t h ma r ev e r i f i e d k e y w o r d sc o n g e s t i o nc o n t r o l ；f u z z yc o n t r o l ；r e i n f o r c e m e n tl e a r n i n g ； a c t i v eq u e u e ；n e t w o r ks i m u l a t i o n 燕山大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文基于智能控制的主动队 列管理算法研究，是本人在导师指导下，在燕山大学攻读硕士学位期间独 立进行研究工作所取得的成果。据本人所知，论文中除己注明部分外不包 含他人已发表或撰写过的研究成果。对本文的研究工作做出重要贡献的个 人和集体，均已在文中以明确方式注明。本声明的法律结果将完全由本人 承担。 作者签字身毫痊埤日期：v 。1 年驴月i 罗日 燕山大学硕士学位论文使用授权书 基于智能控制的主动队列管理算法研究系本人在燕山大学攻读硕 士学位期间在导师指导下完成的硕士学位论文。本论文的研究成果归燕山 大学所有，本人如需发表将署名燕山大学为第一完成单位及相关人员。本 人完全了解燕山大学关于保存、使用学位论文的规定，同意学校保留并向 有关部门送交论文的复印件和电子版本，允许论文被查阅和借阅。本人授 权燕山大学，可以采用影印、缩印或其他复制手段保存论文，可以公布论 文的全部或部分内容。 保密口，在年解密后适用本授权书。 本学位论文属于 不保密囤。 ( 请在以上相应方框内打“4 ”) 作者签名：瓣 导师签名：苍缺屿 日期：v 叶年印月f 多日 日枷尹细7 踟 第1 章绪论 第1 章绪论 在过去的二十年中，计算机网络经历了爆炸式的增长，随之而来的是 越来越严重的拥塞问题。例如由于本地缓存溢出，i n t e m e t 网关会丢弃约1 0 的数据包【l 】。拥塞控制是确保i n t e m e t 鲁棒性( r o b u s t n e s s ) 的关键因素，据统 计，i n t e r n e t 上9 5 的数据流使用的是t c p i p 协议【2 】。i n t e m e t 主要互连协议 t c p s p 对控制拥塞具有特别重要的意义，因此成为当前网络研究的一个热 点问题。 1 1 拥塞产生的原因 网络产生拥塞的根本原因在于用户( 或叫端系统) 提供给网络的负载 ( l o a d ) 大于网络资源容量和处理能力( o v e fl o a d ) ，表现为数据包时延增加、 丢弃概率增大、上层应用系统性能下降等。 拥塞产生的直接原因有以下三点i ”。 ( 1 ) 存储空间不足几个输入数据流共同需要同一个输出端口，而在这 个端口就会形成排队。如果没有足够的存储空间存储，数据包就会被丢弃。 在某种程度上存储空间的增加可以缓解这一矛盾。但是当路由器的缓存达 到一定程度时，数据包经过长时间的排队而完成转发，此时源端认为它们 早己经超时而被丢弃，但这些数据包仍然会继续向下一个路由器转发，从 而浪费网络资源，加重网络拥塞。 ( 2 ) 带宽容量不足低速链路对高速数据流的输入也会产生拥塞。根据 香农信息理论，任何信道带宽最大值即信道的容量c = b l o g ，( 1 + s n ) ( n 为信道白噪声的平均功率，s 为信源的平均功率，占为信道带宽) 。所有信 源发送的速率胄必须小于或等于信道容量c 。如果r c ，那么在理论上 无差错的传输是不可能的，所以在网络低速链路处就会形成带宽瓶颈，当 其满足不了通过它的所有源端带宽要求时，网络就会发生拥塞。 燕山大学工学硕士学位论文 ( 3 ) 处理器处理能力弱如果路由器的c p u 在执行排队缓存，更新路由 表等功能时，因为处理速度跟不上高速链路，会产生拥塞；另外在低速链 路的情况下，使用高速c p u 也会产生拥塞。 要避免拥塞的发生，需针对以上三点原因综合考虑。例如，提高链路 速率而不改变处理器，只会转移网络瓶颈，而不能避免拥塞，所以拥塞往 往也是系统各部分不匹配的结果。拥塞一旦发生往往会形成一个不断加重 的过程。如果路由器没有空余的缓存，它就必须丢弃新到的数据包。当数 据包丢弃时，源端会超时，重传该包。由于没有得到确认，源端只能保留 数据包，结果缓存会进一步消耗，加重拥塞。 1 2 拥塞控制的研究意义 在刚刚过去的几年中，有相当多的研究都试图扩展i n t e r n c t 的体系结 构，为即将大量出现的实时多媒体应用提供服务质量q o s ( q u a l i t yo f s e r v i c e ) 保证。有关q o s 的研究引起了不少争议：一些基于网络中间节点上单个流 状态的业务模型通常具有较复杂的实现机制，可扩展性是该类业务模型存 在的严重问题，在现有的网络体系结构中，可以将业务等级的区分服务引 入拥塞控制机制中，这种思路己在i n t c m e t 中取得了较大的成功；另外一些 研究认为在具有充足资源的尽力传输网络中，所有的问题都会迎刃而解， 这种观点令人难以信服；倒是大多数人认为更多、更合理的控制机制对已 有网络的稳定运行无疑将是至关重要的，其中一个最基本和最重要的要求 就是防止网络出现拥塞崩溃，使网络运行在轻度拥塞的最佳状态，同时保 证一定的公平性1 4 j 。 随着网络的发展，区分业务应用领域不断拓展，应用模式不断丰富， 加之商业化进程的推动。越来越需要对网络所传输的业务类型有一个较为 具体和明确的定义，即所谓的网络业务模型。从早期的i s d n ，n i n t s e r v ， 再到后来的d i f f s e r v ，这些都是结合应用的需要和技术的发展提出来的例。 无论采用哪一种业务体系结构，其技术的核心都需要在恰当的层次和粒度 上对流量进行必要的管理，其中包括接纳控制、流量成形、队列管理、调 2 第1 章绪论 度和拥塞控制等诸多方面，但最基本和最核心的依旧是拥塞控制，因为很 难想象一个时常有可能出现严重拥塞且无法及时加以恢复的网络能够实现 良好的q o s 保证。实施拥塞控制是其它q o s 机制正常工作的必要前提。 当然，拥塞控制的研究并非是由q o s 的保证问题而引出，它一直是分 组交换网络中倍受关注的一个技术热点，对于它的研究，除了具有延续性 的技术意义之外，在强调业务模型的新网络体系结构中，如何通过增强的 拥塞控制为q o s 的实现提供一定的便利，也是拥塞控制研究的目标之一。 拥塞是一种持续过载的网络状态，此时用户对网络资源( 包括链路带 宽、存储空间和处理器处理能力等) 的需求超过了其固有的容量。就i n t e r n e t 的体系结构而言，拥塞的发生是其固有的属性。因为在事先没有任何协商 和请求许可机制的资源共享网络中，几个i p 分组同时到达路由器，并期望 经同一个输出端口转发的可能性是存在的，显然不是所有分组可以同时接 受处理，必须有一个服务顺序，中间节点上的缓存为等候服务的分组提供 一定保护，然而如果此状况具有一定的持续性，当缓存空间被耗尽时，路 由器只有丢弃分组。表面上，增大缓存总可以防止由于拥塞而引起的分组 丢弃，但是随着缓存的增加，端到端的时延也相应地增大，因为分组的持 续时间( l i f et i m e ) 是有限的，超时的分组同样需要重传。因此，过大的缓 存空间倒有可能妨碍拥塞的恢复，因为有些分组将会白白地浪费了网络的 可用带宽。 拥塞导致的直接结果是：分组丢失率提高，端到端时延加大，甚至有 可能致使整个系统发生崩溃。当网络处于拥塞崩溃状态时，即使微小的负 载增量都将会使网络的有效吞吐量( g o o dp u t ) 急剧下降。拥塞崩溃对 i m e r n e t 的威胁可以追溯到其早期的发展中，1 9 8 4 年n a g l e 报告了由于t c p 连接中没必要的重传所诱发的拥塞崩溃，1 9 8 6 - - 1 9 8 7 年间这种现象曾经多 次发生，严重时一度使l b l 至l j u c b e r k e l e y 之间的数据吞吐量从3 2k b p s 跌落 到了4 0b d s 叫。 除此之外，还有其他一些诱发拥塞崩溃的原因，例如不可达分组 ( u n d e l i v e r e dp a c k e t s ) 导致的网络崩溃，它与前一种有所不同，不是一种稳 定状态，当负载减小时，拥塞可以自动恢复。f l o y d 也报告了一种拥塞崩溃 燕山大学工学硕士学位论文 现象1 7 1 ，即分片拥塞崩溃，网络传输了大量的分组分片，但因为无法在接 收端重装成有效的分组而只好将它们丢弃。网络传输大量用户不再需要的 陈旧分组( s t a b l ep a c k e t s ) 会导致另一种形式的拥塞崩溃现象。图1 - 1 刻画了 负载与吞吐量、延时之间的关系，当负载较小时，吞吐量的增长和负载相 比基本呈线性关系，延时增长缓慢；到达膝点( k n e e ) 之后，随负载的增加， 吞吐量增长缓慢，延时增长较快；当负载越过崖点( p r e c i p i c e ) 之后，吞吐量 却急剧下降，延时急剧上升。通常将k e e n 点附近的区域称为拥塞避免区间； k e e n 和p r e c i p i c e 之间是拥塞恢复区间；p r e c i p i c e 之外是拥塞崩溃区间。为 最大限度地利用资源，网络工作在轻度拥塞状态时应该是较为理想的，但 这也增加了滑向拥塞崩溃的可能性，因此需要一定的拥塞控制机制来加以 约束和限制【8 】，这是研究拥塞控制最本质的意义。 l o a d 图1 1 负载与吞吐量、延时间的关系曲线 f i g , 1 - 1c u r v e so f l o a d , t h r o u g h p u ta n dd e l a y 1 3 拥塞控制的研究概况 从控制理论的角度，拥塞控制算法可以分为开环控制和闭环控制两大 类。当流量特征可以准确规定、性能要求可以事先获得时，适于使用开环 控制；当流量特征不能准确描述或者当系统不提供资源预留时，适于使用 闭环控制，在i n t e r n e t 中主要采用闭环控制方式。 闭环的拥塞控制分为以下三个阶段。 4 oop高e-o七 第1 章绪论 ( 1 ) 检测网络中拥塞的发生； ( 2 ) 将拥塞信息报告到拥塞控制点； ( 3 ) 拥塞控制点根据拥塞信息进行调整以消除拥塞。 闭环的拥塞控制可以动态地适应网络的变化，但它的一个缺陷是算法 性能受到反馈延时的严重影响。当拥塞发生点和控制点之间的延时很大时， 算法性能会严重下降。 根据算法的实现位置，可以将拥塞控制算法分为两大类1 9 ：链路算法 ( l i n ka 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 c p 是目前在 i n t e m e t 中使用最广泛的传输协议。根据m c i 的统计，总字节数的9 5 和总 报文数的9 0 使用t c p 传输。近年来，t c p 中采用很多新的算法，包括慢启 动( s l o ws t a r t ) 、拥塞避免( c o n g e s t i o na v o i d a n c e ) 、快速重传( f a s tr e t r a n s m i t ) 、快速恢复( f a s tr e c o v e r y ) 、选择性应答( s a c k ) 等，大大提高了网络传 输的性甜m 1 2 】。t c p 中使用的拥塞控制算法已经成为保证i n t e r n e t 稳定性的 重要因素。 链路算法的研究目前集中在主动队列管理a q m 算法方面，和传统的队 尾丢弃( d r o pt a i l ) 相比，a q m 是在网络设备的缓冲溢出之前就丢弃或标记 报文【1 3 1 。 a q m 的主要优点有以下几个方面。 ( 1 ) 减少网关的报文丢失使用a q m 可以保持较小的队列长度，从而增 强网关容纳突发流量的能力。 ( 2 ) 减小报文通过网关的延时减小平均队列长度可以有效地减小报 文在网络设备中的排队延时。 ( 3 ) 避免l o c k - o u t 行为的发生在某些情况下，d r o pt a i l 算法会让某个流 或少数几个流独占队列空间，阻止其它流的数据包进入队列，而a q m 算法 燕山大学工学硕士学位论文 则能解决这一问题【1 4 j 。 a q m 的一个代表是随机早期检测i 也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 pt a i l 具有更好的性能。但是r e d 的性能对算法 的参数设置十分敏感，至今没有在i m e m e t 中得到广泛的使用【l ”。 对于a q m 的研究，大多采用依赖于直觉的启发设计加通过仿真试验验 证的模式来进行。不可否认，这种模式为网络设计积累了不少经验，发掘 了不少新的方法与策略。在体系结构、协议和机制的研究中无疑是一种最 为理想的方式，但在有关算法的研究中，我们有理由怀疑这种设计模式的 有效性，因为启发式的设计不免带有盲目性和片面性。r e d 算法两次修正 设计参数的事实充分说明了这一点【1 。”。 a q m 策略在高吞吐量和低时延之间做出合理平衡的关键在于始终将 队列长度维持在一个较小的期望值，从控制系统的角度分析，这是典型的 调节系统的技术目标。控制理论是一门相当成熟的系统理论，有相当多的 方法可以借鉴到对现有拥塞控制的稳态与动态性能进行分析以及设计新的 拥塞控制算法中来【1 s 】。 1 4 本文研究的主要内容与结构安排 本文主要内容安排如下。 第2 章着重介绍和分析了在i p 层的控制中，目前常采用的拥塞控制机 制，即具有代表性的a q m 算法，如r e d 算法，比例p ( p r o p o r t i o n a l ) 和比例 积分p i 控制以及随机早期标记r e m ( r a n d o m e a r l ym a r k i n g ) 算法，并分析了 引入智能控制来改善拥塞控制的可行性。 第3 章在研究分析了p i 控制器的同时，提出了一种基于模糊控制的拥塞 控制算法a f p i ，并从输入输出变量的选择、模糊语言的描述、输入变量模 糊化、模糊规则等方面给予了详细的阐述，该算法将模糊控制与p i 控制器 相结合，更好地达到了拥塞控制的目的。 第4 章在研究了再励学习相关技术的基础上，利用再励学习中的瞬时差 分t d 法结合二重梯度下降法，提出了适用于中间节点拥塞控制的p r l 算 6 第1 章绪论 法，该算法在控制系统计算反馈方面进行了调整，并引入了拥塞控制信号 优先传递思想，使得该算法具有很好的鲁棒性。 第5 章简要介绍了网络仿真软件n s 2 ，给出了一个详细的实验配置方 案，并在n s 2 仿真软件的平台上，进行了算法的队列长度稳定性、鲁棒 性、公平性和r 1 盯等多项仿真实验，分析讨论了实验结果，验证了a f p i 算法和p r l 算法的可行性。 最后对未来工作进行了展望。 燕山大学工学硕士学位论文 第2 章主动队列管理 当网络用户提交给网络的负载超过路由器等网络设备的处理能力时， 网络就发生了拥塞，造成网络吞吐量急剧下降，数据包大量丢失，严重时 网络处于瘫痪状态。为了限制发送方不顾当前网络状态盲目发送数据，t c p 协议采用拥塞控制算法来调整数据发送速率，接到拥塞通知后，t c p 协议 根据拥塞控制算法调整数据发送速率，减少注入网络的流量，达到缓解拥 塞的目的。由于t c p 协议采取收到拥塞通知后再处理的策略，因此，仅靠 t c p 协议并不能避免拥塞的发生。路由器等中间结点采用主动队列管理算 法来管理缓存，这样就可以在拥塞发生之前通知发送方，发送方一旦收到 拥塞通知立即调整发送速率，从而有效地避免拥塞的发生。下面本章对常 用的主动队列管理算法进行了简短的介绍，并从控制论角度进行了简要的 分析，以及阐述了在智能控制论领域里主动队列管理应用的前景。 2 1 队尾丢弃算法 路由器管理缓存的传统方法是采用队尾丢弃算法。该算法简短描述为： 数据包到达路由器后，需要在不同的输出端口缓冲区中进行排队；将该缓 冲区的容量设置足够大，这样当网络发生拥塞的时候，所有新到达又来不 及处理的数据包都会被保存在缓冲区中，当系统空闲时再来处理这些保存 起来的数据包；当网络持续拥塞时，缓冲区就会被填满，所有新到达的数 据包将被丢弃。当发送方t c p 检测到有数据包被丢弃时就会降低数据发送 速率，直到拥塞消除，但是它主要存在以下两个方面的缺科”l 。 ( 1 ) 容易填满缓冲区缓冲区很容易被填满，无法容纳突发的数据流。 ( 2 ) 容易造成全局同步当缓冲区被填满后，所有新到达的数据包都会 被丢弃，所有发送方会同时降低发送速率；当拥塞消除后，所有发送方又 会同时增大发送速率，这样就导致了所有发送方发送速率同步化。 第2 章主动队列管理 2 2 随机早期检测算法 为了提高网络性能，互联网工程任务组i e t f ( i n t e m e te n g i n e e r 堍t a s k f o r c e ) 推荐在路由器中使用随机早期检测r e d 算法，该算法的基本思想是： 通过监控路由器输出端口队列的平均长度来探测拥塞，一旦发现接近拥塞， 就随机地选择连接来通知发送方，使它们在队列溢出之前减少发送窗口数， 降低数据发送速率，从而缓解网络拥塞 2 0 l 。r e d 算法流程如图2 1 所示。 图2 - 1r e d 算法 f i g 2 - 1r e da l g o r i t h m 9 燕山大学工学硕士学位论文 r e d 算法具体描述如下：数据包到达路由器后，需要在不同的输出端 口缓冲区中进行排队，每一个输出端口维护一个队列；当有新的数据包到 达时，采用指数加权滑动平均的方法计算平均队列长度a v g ( 这个平均是指 对时间的平均) ，并把a v g 与两个预先设定的门限( 最小门限r a i n 。和最大门 限m a x m ) 相比较，若平均队列长度a v g 小于m i n m ，则不丢弃分组；若a v g 大 于或等于l n a x n ，则丢弃所有分组；若a v g 大于或等于m i n m ，而小于m 戤* ， 则根据平均队列长度a v g 计算概率p 。，以概率p 。丢弃到达的分组。 其中，qt i m e 表示队列为空的起始时刻；c o u n t 表示上次丢弃分组后 收到的分组数目；表示计算队列的平均长度时采用的权重；n l a x 。表示 p 能够取得的最大值；以表示当前分组被丢弃的概率；q 表示当前队列的 实际长度；t i m e 表示当前时间：厂，) 表示时间t 的线性函数。 与2 1 节的队尾丢弃算法相比，r e d 算法在拥塞发生之前通知发送方调 整速率，能够有效地降低丢包率；r e d 随机通知发送方而不是通知所有发 送方，能够有效地消除全局同步；另外，r e d 还可以通过保持较短的队列 长度来容纳突发的数据流。 虽然r e d 能够有效避免拥塞，但是该算法仍然存在以下主要缺陷1 2 l 】。 ( 1 ) 公平性问题对于不响应拥塞通知的连接，r e d 算法无法有效处 理，因此这样的连接经常会挤占大量的网络带宽，导致了各种连接不公平 地共享带宽。 ( 2 ) 参数设置问题r e d 算法对参数设置很敏感。两个阀值r a i n 。、 i n f i x 。和最大丢包概率n l a x 。的细微变化经常会对网络性能造成很大影响， 如何根据具体业务环境选择最合适的参数是r e d 存在的一个重要问题。另 外，一组参数可能会获得较高的吞吐量，但是可能也会造成较高的丢包率 和较长的时间延迟。如何配置参数，使得算法在吞吐量、时间延迟和丢包 率等各方面均获得较好的性能也有待解决。 ( 3 1 网络性能问题r e d 算法控制的平均队列长度经常会随着连接数 目的增加而不断增大，造成传输时延抖动，引起网络性能不稳定。 针对这些状况，r e d 算法产生许多派生改进算法，如g e n t l er e d ， g e n t l ew r e d ，g e n t l ef r e d ，b a l a n c e di 疆d ，g e n t l eb l u e ，g e l i t l ec b t ， 第2 章主动队列管理 dc b t 等【2 2 埘1 。但是，这些算法的设计研究缺乏系统的理论，在很大程度 上依赖于直觉和启发性，使得最终形成的算法在稳定性和鲁棒性方面存在 不少问题。解决a q m 算法的理想途径是更多地吸取先进控制理论进行综合 设计。控制理论是一门相当成熟的系统理论，有相当多的方法可以借鉴到 对现有拥塞控制的稳态与动态性能以及设计新的拥塞控制算法中来【2 5 l 。 2 3 经典控制理论在主动队列管理中的应用 2 3 1 基于网络模型的a q m 系统 经典控制理论对t c p 拥塞控制机制和中间节点( 路由器) 进行建模，在此 基础上进行a q m 研究。假设t c p 流的丢包事件服从泊松分布，同时不考虑 传输超时等因素，可以得至f t c p 拥塞控制机制系统微分方程 2 6 1 。 降= 丽1 d t一氅铲以删l脚) 2 球) ” 降d t = 鬻咻c ( 2 - 1 ) 式中，矿为预期的t c p 拥塞窗口大小，g 为预期的队列长度，r 为往返时 间l m ，c 为链路容量，瓦为传输时延，为负载因子( t c p 连接数) ，p 为 分组的丢失概率。 记矿和口为该系统状态，p 为时延反馈输入，系统的平衡点( ，q o ，p 。) 满足如下条件。 吩胪2 ，r v o = 等舻詈+ 乙( 2 - 2 ) 则系统在该平衡点的线性化方程如式( 2 - 3 ) 所示。 a 方一茄删一等嘶一r o ) ( 2 3 ) a e c f ) = 罢a ( f ) 一去向( ，) 茎生盔兰三兰堡圭兰垡丝苎 记p 印p 一屿和p ，。分别为从印到却和从跏到印的传递函数，如式 ( 2 - 4 ) 所示。 小) = 焉篇 。：哪 p g ) = 箍 整个线性时延反馈控制系统结构如图2 2 所示。 图2 - 2a q m 控制方框图 f i g 2 - 2a q m c o n t r o lb l o c kd i a g r a m 不同的a q m 策略对应不同的控制器c o ) 。例如，r e d 的传递函数为式 ( 2 5 ) 所示【2 j 7 】。 c m o o ) 。丽l r e d ( 2 - 5 ) 式中，工艇d = p 一( m a x m n f i n m ) ，置= l o g ? 一, s ，6 为采样频率。 2 3 2 对r e d 算法的控制理论分析 根据控制理论，r e d 算法实质为一阶滤波加非线性比例控制，存在着 稳定性方面的问题。我们注意到系统的稳态增益为露c 3 4 n 2 ，它是t c p 连接数目和往返传输时间r 的函数。当凡增大或者减小时，系统的 稳态增益增大，抗干扰性的能力下降。因此调节r e d 参数的目标，就是要 让系统在凰和有扰动的操作条件下保持稳定。c h o l l o t 等人运用古典控 制理论中线性理论的频率分析法，分析了负载和网络状态的变化对系统稳 定性的影响，给出并证明了r e d 能够稳定运行的参数范围。对于某个民上 限r + 和下限一，当满足式( 2 6 ) 时，对所有n n 一和r o r + ，系统都 是稳定的。 第2 章主动队列管理 料辱 丽r 3 可” ( 2 6 ) 式中，。= o 1 m i n 2 n 一( r + r c ，1 r + 。 但是通过实验与仿真发现，不稳定的队列总是在m i n 。和m a x 。之间呈 现近似等幅震荡。任丰原等人针对队列的自激震荡，运用非线性控制理论 解释了队列的等幅震荡行为，采用描述函数分析方法，分析了r e d 的工作 特性，认为分组丢弃概率曲线中的非线性结构诱发的自激震荡是队列呈现 周期运动的根本原因，并给出了在r e d 算法的控制下，a q m 系统的稳定运 行判定依据，即r e d 控制队列时，需符合式( 2 7 ) ，才能保持队列稳定1 2 蚋。 g 魄) 搿硒- 1j j 2 月，vij ( 2 - 7 ) 规艰方程呻+ 玺躺啦高，爿上的 根。 2 3 3 比例和比例积分控制器 r e d 算法的一个重要缺陷是，系统响应时间太长。事实上，i m d 对队 列长度的采样值进行的平滑处理是系统响应时间变大的原因：当非突发性 的拥塞已经发生时，平滑后的平均队列长度没有反映出来。低通滤波器的 目的是平滑突发数据流，但是从控制理论的角度看，这样处理会导致系统 的不稳定和拥塞窗口的低频振荡。减小系统响应时间的一个办法是去掉低 通滤波器，取而代之的是经典的比例p 控制器。在p 控制器中，反馈信号就 是瞬时队列长度乘上一个比例系数，如式( 2 8 ) 所示。 pj=|吼(2-8) 式中，j 是计算使用的比例系数。 p 控制器可以通过调整r e d 算法的队列长度加权系数来得到。实际上， 若r e d 直接根据瞬时队列长度来计算丢包率，则r e d 可看作是一个分段连 续的p 控制器。p 控制器实现简单，并且在反应速度上具有很好的性能。文 燕山大学工学硕士学位论文 献 2 9 】在n s 一2 中对其性能进行了仿真，从得到的队列曲线可以看出该系统 是稳定的，并且它的响应速度比r e d 算法要快的多，但稳态误差太大。分 析一下p 控制器和r e d 的队列响应曲线，可以看出两种情况下都存在稳态 误差。这是由于队列长度口和丢弃概率p 之间的直接耦合造成的。这种稳 态误差依赖于网络的有关参数。尽管从网络的角度而言，误差不是一个很 重要的因素，但如果误差大到超过路由器缓冲的范围，就会导致系统的振 荡从而影响网络性能。 积分i ( i n t e g r a l ) 控制器有一个很重要的属性：能够使稳态误差为0 。如 果在a o m 中引入积分控制器，就可以消除队列长度和丢弃概率之间的直接 藕合，从而消除稳态误差，为此文献【3 0 引入积分作用，设计了p i 控制器。 p i 控制器是目前最具竞争力的算法之一，也是本文的一个重要研究点，将 在3 1 节详细介绍。 2 3 4 随机早期标记 随机早期标记r e m t 3 1 1 的特点是：“汇聚速率与带宽匹配”和“稳定队 列长度”。由于网络多源点和多连接，很难证明一般算法的收敛性和稳定 性，但是r e m 算法的收敛性是可以证明的，其宏观行为特征也容易理解和 描述成：源点和中间各结点分布式的执行一个梯度下降法寻优计算，以解 决一个对偶问题。 由于r e m 算法适用于基于速率的拥塞控制，而本身不能提供与源端速 率控制算法进行合作的机制，当真正用到网络中去，相配合的是一般的t c p 拥塞控制算法的时候，它退化成一般的a q m 算法3 2 1 。 2 4 智能控制理论的研究和应用 经典控制理论对问题的解决在很大程度上依赖于被控对象的数学模型 精度，但要得到实际对象的精确模型较难，往往需要许多假设和限制。智 能控制是控制理论发展的高级阶段，它主要解决经典控制理论难以解决的 复杂系统的控制问题，研究对象是不确定的模型，呈高度的非线性，任务 1 4 第2 章主动队列管理 复杂。模糊控制和神经网络控制作为智能控制的两大分支，近年来在网络 拥塞控制中得到广泛应用【3 3 】。 2 4 1 模糊控制在a q m 中的应用 模糊控制不依赖于对象模型，对模型的不确定性具有很强的适应能力， 在工业控制领域得到了广泛应用。在实际网络中，r e d 算法存在不稳定性， 同时对参数的变化很敏感，而r e d 算法所依据的模型，也是忽略许多因素 后得到的模型，与实际系统之间仍有较大差距。对此类复杂、时变、不确 定性的网络，模糊控制则能解决这一问题。模糊控制利用专家经验建立模 糊集、隶属度函数和模糊推理规则，以实现复杂系统的控制。模糊控制器 设计的一般步骤为：模糊化，模糊规则推理，清晰化。模糊控制系统可以 采用图2 3 所示结构，其中输入变量是队列长度和队列长度的变化率，输出 变量为丢包概率。 图2 - 3 基于模糊控制的主动队列管理系统 f i g 2 - 3a q ms y s t e mb a s e do nf u z z yc o n t r o l 张孝林等人改变r e d 中传统的做法，采用模糊规则和优先级策略来决 定不同队列的丢包率【3 4 】。尹凤杰等人提出了基于模糊变结构控制设计一种 鲁棒主动队列管理算法【3 5 1 ，算法依据路由器中队列长度的变化情况，根据 一定的模糊自校正原则来调整数据包的丢包概率，从而使路由器中的队列 长度稳定在参考值附近。仿真结果表明，该算法对不同的网络状况具有很 强的适应能力。 模糊控制器实际效果成功的关键在于针对网络实际特性，得到全面准 确的模糊控制规则，使模糊推理更合乎实际情况。在第3 章将给出一个基于 模糊控制理论的a q m 设计方法，此设计方法不同于以往的以队列长度和队 列长度的变化率为输入变量，丢包概率为输出变量，而是一种更有效的设 燕山大学工学硕士学位论文 计方法。 2 4 2 神经网络控制在a q m 中的应用 神经网络具有模拟人的部分智能的特性，因此神经网络控制具有学习 能力，对环境的变化具有自适应性，且神经网络也具有任意逼近非线性函 数的能力，所以比较适用于那些具有不确定性或高度非线性的控制对象。 目前神经网络广泛应用于控制领域，尤其是非线性系统领域。舒朝海等人 用神经网络应用于a t m 拥塞控制，神经网络输入为缓冲区队列状态，实时 观测流量情况，输出信号来调节信源发射速度p 。 考虑到对网络流量进行建模的复杂性，可以在主动队列管理中引入神 经网络的方法。陈潇等利用神经网络对各种流进行了鉴别和分类 3 7 1 ，根据 流特征赋予了不同的丢弃优先级，然后根据流的丢弃优先级和历史丢弃记 录，动态地调整丢弃概率，达到了避免和解除网络拥塞的目的，保证了网 络q o s 。仿真结果表明，此队列管理机制取得了很好的控制效果。 再励学习i 也( 又称强化学习) ，是模拟人适应环境学习过程的一种机器 学习模型，在神经网络与神经控制中得到了广泛的应用( 3 引。在第4 章将给 出一个基于再励学习的a q m 设计方法，该算法使得路由器队列长度能够很 快收敛到参考值，且保持稳定。 2 5 本章小结 本章首先对路由器管理缓存的传统方法队尾丢弃算法进行了简短分 析，然后着重介绍了经典的a q m 算法r e d ，并用经典控制理论对其进行 深入剖析。其次对p 控制器从控制理论角度进行了分析和总结，在认同控 制器优点的同时，又提出了更高的要求，以便适应复杂多变的网络环境。 最后简要概括了模糊控制和神经网络这两个智能控制理论的两大分支在 a q m 中的应用，从而为后继章节研究的展开起到一定的铺垫作用。 1 6 第3 章基于模糊控制的主动队列管理算法研究 第3 章基于模糊控制的主动队列管理算法研究 近年来，随着计算机和网络技术的迅猛发展以及多媒体应用的急剧增 加，人们对i n t e r n c t 的服务质量提出了更高的要求。如前面章节所述，主动 队列管理技术作为高速路由器中一个重要技术近年来越来越受到关注【3 9 】。 在a q m 的发展过程中，引人注目的是，h o l l o t 等人对a q m 的非线性模型进 行了局部线性化处理，然后将其等效为带时滞的二阶系统，设计了用于主 动队列管理的p 控制器和比例积分p i 控制器 4 0 l ，增强了系统的稳定性和适 应能力。 3 1p i 控制器 由于在p i 控制器中引入了积分项，相比p 控制器而言，p i 控制器可以有 效地消除p 控制器中出现的稳态误差，从而保证队列长度的稳定。但p i 将网 络视为定常线性系统和时不变非线性系统，而实际网络的状态参数却随着 新连接的建立和旧连接的拆除等诸多因素而瞬息万变，p i 算法静态的、定 常系统的处理方法使得当网络中的流量发生很大变化时，需要的收敛时间 大大增加。从前面章节得知，不同的a q m 算法，它的不同之处关键在于对 应于不同的控制器c ( j ) ，下面就介绍一下p i 控制器使用的传递函数。 3 1 1 连续p i 控制器 对于一个连续p i 控制器，其传递函数形式如式( 3 1 ) 。 c g ) ：垒幽( 3 - 1 ) 另外，p i 控制器也具有如下等价形式h ”。 c ( s ) = 七。+ 生( 3 2 ) 1 7 燕山大学工学硕士学位论文 式中，i ，为比例系数；t 为积分系数。 为了便于用经典控制理论去分析拥塞控制，我们进一步将第2 章中的 t c p 拥塞控制的线性化控制方框图2 2