（通信与信息系统专业论文）模糊控制在主动队列管理中的应用研究.pdf

重庆邮电大学硕士论文摘要 摘要 随着互联网规模的增长，拥塞己经成为一个十分重要的问题。近年来。 主动队列管理( a q m ) 已成为网络拥塞控制领域的一个研究热点。a o m 通过评估网络状态、预测拥塞的出现，对分组进行有目的的丢弃，可以使 源发送端更及时地了解到网络状况并调整发送速率。现有算法在响应速 度、稳定性及环境敏感性等方面仍有缺陷。对于网络模型的复杂性难题， 模糊控制可以发挥相应的优点实现拥塞控制的智能化；而且模糊控制不严 格依赖于对象模型，对模型的不确定性具有很强的适应能力。因此，把模 糊控制技术引入到a q m 中有望能够较好地解决实际网络中的拥塞问题。 目前，关于此方面的研究已引起人们广泛的兴趣，亦取得了一些初步的研 究成果。不过现有的一些研究成果离实际应用尚有一定的距离，还需要作 进一步地探索。 本论文的主要工作如下： 分析了网络拥塞的固有特性，讨论了模糊控制理论在a q m 中的应 用； 分祈了具有代表性的基于模糊控制技术的a q m 方案，讨论了它们各 自的优缺点； 在具有代表性的算法“随机指数标记”( r e m ) 的基础上提出一种基 于模糊控制的改进r e m 算法，取名f u z z yr e m ，对其进行了理论分析和 仿真实验。仿真结果表明，即使网络动态变化，该算法也能够快速地稳定 队列长度，达到良好的控制性能，也较现有其它方案在网络拥塞控制的有 效性上有较好的改善。 在具有代表性的算法“模糊显示标记”( f e m ) 的基础上提出一种自 适应目标队列算法，取名a t q l f e m ，对其进行了仿真分析。仿真结果表 明这种自适应机制能有效提高应对突发流量时的适应性，很好地适合网络 模型的非线性。 关键词：拥塞控制，主动队列管理，模糊控制 重庆邮电火学硕士论文摘要 a b s t r a c t c o n g e s t i o nh a sb e e nav e r yi m p o r t a n tp r o b l e mw i t ht h eg r o w t hu po f n e t w o r ks c a l e i nr e c e n ty e a r s ，a c t i v eq u e u em a n a g e m e n t ( a q m ) h a sb e e na r e s e a r c hh i g h l i g h ti nn e t w o r kc o n g e s t i o nc o n t r o lf i e l d e v a l u a t i n go nn e t w o r k s t a t ea n df o r e c a s t i n gt h eo c c u r r e n c eo fc o n g e s t i o n ，i tc a na b a n d o ns e l e c t i v e l y t ot h o s eg r o u p s ，s oa st om a k es e n d i n gs o u r c ek n o w st h en e t w o r ks t a t ei nt i m e a n da d j u s tt h ed i s p a t c hs p e e d b u tm e c h a n i s mn o wh a sd e f e c ti nr e s p o n d s p e e d ，s t a b i l i t ya n de n v i r o n m e n ts e n s i t i v i t y a st ot h ec o m p l e x i t yp r o b l e mo f n e t w o r km o d e l ，f u z z yc o n t r o lc a nb r i n gr e l a t i v e a d v a n t a g e s i n t o p l a y , a c t u a l i z et h ei n t e l l e c t u a l i z i n go fc o n t r o ls y s t e m f u r t h e r m o r ef u z z yc o n t r o l d o e sn o td e p e n do no b je c tm o d e l ，a n da d a p t st ot h eu n s t a b l es t a t eo fm o d e l h e n c ei n t r o d u c i n gf u z z yc o n t r o li n t oa q mc a ns e t t l et h ec o n g e s t i o np r o b l e m i nr e a lt i m en e t w o r k ，a n dh a se x t e n s i v ea p p l i c a t i o na n dr e s e a r c hv a l u e s o m e r e s e a r c h e sn o ws h o wt h a tf u z z yc o n t r o lc a na p p l yt ot h ec o n t r o lo fn e t w o r k c o n g e s t i o ne f f i c i e n t l y b u tt h e r ei sd i s t a n c eb e t w e e nt h er e s e a r c h a c h i e v e m e n t sn o wa n dt h er e a lt i m ea p p l i c a t i o n ，f u r t h e re x p l o r a t i o no nt h i s a r e ai sn e e d t h ec o n t r i b u t i o n so ft h i st h e s i sa r ea sf o l l o w s ： a n a l y z i n gt h ec h a r a c t e r i s t i c so w n e db yn e t w o r kc o n g e s t i o n ，d i s c u s s i n g t h ea p p l i c a t i o no ff u z z yc o n t r o lt h e o r yo na q m a n a l y z i n gt h er e p r e s e n t a t i v ea q ms c e n a r i ob a s e do nf u z z yc o n t r o l t e c h n i q u e ，d i s c u s s i n gt h e i rs u p e r i o r i t i e sa n ds h o r t c o m i n g ss e p a r a t e l y b a s e do nt h ee x i s t e da q ma l g o r i t h m r e m 。t h i st h e s i se x p l o r e sf u z z y r e m o n ek i n d o fr e f i n e m e n ta l g o r i t h mo ff u z z yc o n t r o l ，s h o w st h e o r y a n a l y s i sa n ds i m u l a t i o nt e s t t h et e s ts h o w st h a tt h i sa l g o r i t h mc a ns t a b l e q u e u el e n g t hr a p i d l ya n da c h i e v ep e r f e c tc o n t r o lp r o p e r t i e si nt h ee v e n to f n e t w o r kd y n a m i cc h a n g e c o m p a r i n gt oo t h e rs c e n a r i o sa v a i l a b l en o w ，t h i s a l g o r i t h mi m p r o v e so nt h ee f f i c i e n c yo fn e t w o r kc o n g e s t i o nc o n t r 0 1 b a s e do nt h ee x i s t e df u z z yc o n t r o la q ma l g o r i t h m f e m ，t h i st h e s i s e x p l o r e sa t q l - f e m ，o n ek i n do fa d a p t i v et a r g e t 。q u e u el e n g t hf u z z y c o n t r o l a l g o r i t h m ，s h o w ss i m u l a t i o na n a l y s i s s i m u l a t i o nt e s ts h o w st h a tt h i sk i n do f n 重庆邮电大学硕士论文 摘要 a d a p t i v es y s t e m c a r le f f i c i e n t l yr a i s et h ea d a p t a t i o nt ob u r s t i n gf l o w , f u r t h e r m o r e ，t h eg u a r a n t e eo fp r o p e r t yp r o v e st h a tt h i sa l g o r i t h mc a na d a p tt o t h en e t w o r km o d e ln o n l i n e a r i t yp e r f e c t l y k e yw 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 t t a g e m e n t ( a q m ) ，f u z z y c o n t r o l n l 重庆邮电大学硕士论文 缩略语索引表 a a m a q m a 廷e d a t q l f e m a v q d i f l s e r v f c m f e m f i e f l c f t p f u z r e m h t t p i e t f l a n p i p d p q o s r e m i 汀t s r e d t c p t d t q l t c p ，i p u d p v o i p w a n 缩略语索引表 a d a p t i v ea d j u s tm o d u l e a c t i v eq u e u em a n a g e m e n t a d a p t i v er a n d o me a r l yd e t e c t i o n a d a p t i v et a r g e tq u e u el e n g t h - f u z z ye x p l i c i tm a r k i n g a d a p t i v ev i r t u a lq u e u e d i f f e r e n t i a t i o ns e r v i c e f u z z yc e n t r e lm o d u l e f u z z ye x p l i c i tm a r k i n g f u z z yi n f e r e n c ee n g i n e f u z z yl o g i cc o n t r o l l e r f i l et r a n s f e rp r o t o c o l f u z z yr e m h y p e r t e x tt r a n s f e rp r o t o c o l i n t e r n e te n g i n e e r i n gt a s kf o r c e l o c a la r e an e t w o r k p r o p o r t i o n a li n t e g r a l p a c k e td r o pp r o b a b i l i t y q u a l i t yo fs e r v i c e r a n d o me x p o n e n t i a lm a r k i n g r o u n dt r i pt i m e s t a b i l i z e dr a n d o me a r l yd e t e c t i o n t r a n s f e rc o n g e s t i o np r o t o c o l t a i ld r o p t a r g e tq u e u el e n g t h t r a n s m i s s i o nc o n t r o lp f o t o c o l ，i n t e r n e tp r o t o c o l u s e rd a t a g r a mp r o t o c o l v o i c eo fi n t e r n e tp r o t o c o l w i d ea r e an e t w o r k v l 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及 取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论 文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得重庆 整虫太堂或其他教育机构的学位或证书而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 意。 学位论文作者签名：“幸包可兮 签字日期： 学位论文作者签名：卅孢彤了 签字日期： 协1 年，月舯 | 学位论文版权使用授权书 本学位论文作者完全了解重庆邮电友堂有关保留、使用学位论 文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘， 允许论文被查阅和借阅。本人授权重鏖邮电太堂可以将学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等 复制手段保存、汇编学位论文 ( 保密的学位论文在解密后适用本授权书) 虢删令铷躲万匀 签字日期：呵年多月7 s 日签字日期：莎叫年f i i 重庆邮电大学硕士论文 第一章绪论 1 1 研究背景 第一章绪论 i n t e r n e t 是覆盖全球的信息基础设施之一。现有的i n t e r n e t 包括成几十 万个全球范围内的局域网。这些局域网通过主干广域网进行互联。随着互 联网网络规模不断扩大，互联网用户和新应用业务都在快速的增长。人们 逐渐习惯将i n t e r n e t 作为获取重要信息的途径，以及工作、生活和休闲娱 乐方式。目前，越来越多的高速数字业务在现有的互联网上传输。据统计， 6 0 的互联网总带宽有5 被沉迷于文件共享网站的用户所占用，而他们多 是传递一些大型文件或进行大量实时数据传输；新业务的涌现对网络提出 更高的质量要求，例如对延迟敏感的应用如v o i p 业务。这些各种各样的 应用使网络带宽资源变得十分紧张，由此引发的网络拥塞问题已成为制约 网络发展和应用的瓶颈，因此实施拥塞控制是保障网络良好性能的关键因 素，对保证互联网的稳定具有十分重要的意义。 网络拥塞控制根掘实现的物理位置，可以将拥塞控制算法分为两大类： 源算法( s o u r c ea l g o r i t h m ) 和链路算法( l i n ka l g o r i t h m t l l 。源算法工 作在主机( e n d h o s t ) 和网络边缘( n e t w o r ke d g e ) 设备上，其作用是根 据反馈信息调整发送速率。链路算法工作在网络设备( 如路由器和交换机) 上，其作用是检测子网传输路径端口上转发队列的累积，产生拥塞的反馈 信息。拥塞控制算法设计中的关键问题是如何在网络交换设备上生成反馈 信息和边缘主机如何对反馈信息进行响应。 在拥塞控制的源算法方面，主要集中在对t c p 协议的研究上。t c p 通 过动态调整发送窗口的大小达到拥塞避免和快速恢复，为应用提供可靠的 数据传输服务，在保障网络通信性能方面起着非常重要的作用。在过去的 十年内，学术界对t c p 拥塞控制做了大量的研究，提出了许多优异的t c p 拥塞控制算法，如：t c pt a h o e ，t c pr e n o ，t c pv e g a s ，t c ps a c k 等不 过，在i n t e r n e t 这样复杂的网络系统中不能期望源算法良好地控制端到端 的所有链路，因此，采用结合链路算法的控制方式对网络拥塞控制也起到 很重要的作用。 目前，链路算法的研究主要集中在“主动队列管理”( a q m ：a c t i v eq u e u e 重庆邮电大学硕士论文第一章绪论 m a n a g e m e n t ) 算法方面1 2 - 5 1 。它能够通过早期分组丢弃检测到初始拥塞并 避免拥塞的发生，缓解t c p 流的同步，并能够提供某种程度上的服务质 量( q o s ) 保证。a q m 的主要优点是：减少网关的报文丢失；减少报文 通过网关的延迟；避免l o c k o u t 行为的发生。a q m 的一个代表是r e d ( r a n d o me a r l y d e t e c t i o n ) 算法f 2 】r e d 比传统的“尾部丢弃”( t a i l d r o p ) 具有更好的性能，但是存在对算法的参数设置十分敏感，没有充分考虑 链路中复用的活动连接数，不能很好地适应网络负荷的变化和公平性欠缺 等问题【3 i ，至今还没有在互联网中得到广泛的使用。这促使人们希望研究 出更好的a q m 算法，目前已有诸多有价值的结论。然而，许多现有的 a q m 算法在设计上研究缺乏系统的理论，很大程度依赖于直觉和启发性， 使得最终在稳定性和强健性方面存在不少问题。 另外，从网络拥塞控制整个系统来看，仍存在下列困难因素：网络 控制系统本身的分布性。网络中各个节点需要使用不完整的信息独立决 策，解决拥塞：并且各个节点之间还要协作，适应不正常的节点。复杂 的网络环境。i n t e r n e t 结构复杂，规模庞大，是多种网络体系结构拼凑的 综合体。业务种类繁多，网络需求各不相同。网络用户数目随机变化，并 且要应付随时产生的通信故障。各种性能指标的权衡。q o s 要求拥塞控 制根据不同的业务流需求提供相应的通信保障，例如通信效率，网络稳定 性、公平性和算法收敛性等；一种特定拥塞控制算法不可能面面俱到，必 然有它特定的适用场合。 1 1 1 模糊控制在主动队列管理中的研究意义 近年来，非线性规划理论【6 】和系统控制理论被引入到拥塞控制的研究 中来，一些研究者尝试使用严格的数学模型来描述由端系统和网关共同组 成的系统。这对拥塞控制的研究有很大的推动作用。然而，目前t c p a q m 拥塞控制算法所依据的模型【7 1 ，是忽略许多因素后得到的模型，与实际系 统之间仍有较大差距 智能控制主要是针对被控对象、环境、控制目标或任务的复杂性而提 出的。被控对象的复杂性表现在模型的不确定性，高度非线性，时变性和 不完全性等，一般无法获得精确的数学模型。在这样复杂对象的控制问题 面前，将人工智能方法引入控制系统，实现控制系统的智能化，即采用仿 人智能控制决策，迫使控制系统向期望目标逼近基于当前智能控制系统 研究现状，可把智能控制系统分为：分级递阶智能控制系统、专家控制系 2 重庆邮电大学硕士论文 第一章绪论 统、模糊控制系统、神经网络控制系统、基于规则的仿人智能控制、集成 智能控制系统、组合智能控制系统等。基于多学科背景的智能控制目前仍 处于快速发展期，还有待进一步研究应用。 模糊控制作为智能控制系统的一种，为控制系统提供了一个良好的控 制方法。与传统控制方法集中于用系统模型构建控制器相比，模糊控制集 中于对如何控制系统的直觉理解。这允许模糊控制器对模型的不确定性， 非线性和噪音相对于传统控制来说少敏感性，因而可以控制更复杂的系 统。 对于网络模型的复杂性难题。模糊控制也可以发挥相应的优点进行解 决，实现控制系统的智能化，即采用仿人脑模糊控制决策，迫使控制系统 向期望目标逼近；而且模糊控制不严格依赖于对象模型，对模型的不确定 性具有很强的适应能力。因此，把模糊控制技术引入到主动管理机制中有 望能够较好地解决实际网络中的拥塞问题，具有广泛的应用前景和研究价 值。 近年来许多学者纷纷借助于模糊和预测控制技术，通过检测队列长度 的变化速率或变化趋势来获得网络拥塞的前期信息，从而可以避免拥塞的 实际发生。然而现有的一些研究成果离实际应用尚有一定的距离，而且国 内从事这方面的研究起步较晚、力度不够。本课题的研究将带来重要的技 术积累和学术创新，为模糊控制在主动管理中的应用提供重要的参考，同 时也可以为模糊控制在整个拥塞控制系统中的应用提供借鉴。 1 1 。2 国内外研究现状 a q m 作为一种主动的而非响应性的分组丢弃策略，它能够较好地适应 队列长度的快速变化。a q m 的管理目标是：减小队列长度，以降低端 到端的延时；当队列长度溢出时，减少数据包或丢弃数据包以保证网络 资源的有效性。基于a q m 管理策略，刚开始只有r e d 算法能够实现其目 标，随后围绕r e d 和a q m 的研究逐渐增多，逐步形成了a r e d i s l 、 b l u e t 9 1 、r e m 3 l 、p l 1 0 1 控制器和a v q t 5 l 等多种算法。 分析这些a q m 算法，除了p i 控制器和a v q 算法、r e m 算法外，大 多数算法都沿用了r e d 分组概率丢弃机制，它的有效性毋庸置疑。但由 于分组概率丢弃机制中随机数的生成需要大量的计算，不利于优化网络设 备的性能于是文献【l l 】提出了改善动态队列管理的( f u z z yl o g i c c o n t r o l l e r , f l c ) 算法，使系统的实时性、鲁棒性和系统的抗噪声和抗干 重庆邮电大学硕士论文 第一章绪论 扰能力有所增强。 针对同样的问题，文献 1 2 】提出一种利用模糊逻辑决定是否丢包的方 法，然后通过离线的合成推理使得分组丢弃判定仅需要简单查表和比较运 算即可完成，为优化路由器的性能提供了便利。不过其门限值的合理设定 存在一定的困难，即设定门限值为多少时才能恰当地表示网络处于轻度拥 塞状态文献【1 2 】中认为把门限值设为0 具有一定的物理意义，但缺乏论 证；而且“0 ”代表网络处于轻载和拥塞的临界状态，并。不表明此时网络 工作在轻度拥塞状态。 文献【l3 】针对t c p i p 网络的特点提出了基于d i f f - s e r v 的算法f u z z y r e d 1 。该算法取消了r e d 队列的固定上下限值，取而代之的是根据网 络当前状态由f l c 计算得出的动态值。因为在网络状态发生变化之后，传 统的r e d 算法已不能提供理想的计算结果，而f u z z yr e d 算法则根据网 络队列实际长度及其变化速率来计算丢包率。f l c 的实现采用d i f f - s e r v 算法，对不同的队列设置了不同的服务级别。 文献f 1 5 1 研究了在t c p i p 网络中实现的方法，指出其难度主要在于确 定非直觉的控制参数和动态检测网络流量变化，以及控制器对队列调整的 响应速度过慢。为此引入模糊显式标记f e m ( f u z z ye x p l i c i tm a r k i n g ) 和 e c n ( e x p l i c i tc o n g e s t i o nn o t i f i c a t i o n ) ，以路由队列长度、队列长度变化 率等要素来构造模糊推理规刚，运用模糊推理，为t c p i p 网络提供了拥 塞控制的新算法和队列管理的新方案。f e m 这类以t q l 为参考，使缓冲 器的队列长度围绕t q l 小幅震荡的方法，虽然可以实现较高的网络吞吐 量，较小的丢包率以及时间延迟，但同时也给a q m 设计带来一定的问题。 如果t q l 设置太小，则大量缓冲区空间被闲置，利用率得不到提高：如果 t q l 设置过高，一旦突发性流量出现，在t q l 影响下的a q m 因为瞬时的 队列累积将造成丢弃概率激增，带来的后果是分组被大量丢弃，服务质量 得不到保障。 文献【1 6 】首先从l y a p u n o v 的稳定性分析和检验中得出稳定性准则，这 种方法有利于保证一个稳定的控制器。然后。用该稳定性准则设计了一个 基于m a m d a n i 的控制模型( 该控制模型能够很好地抓住网络的非线性特 性) ，提出利用平移全部隶属函数的方式构建自适应模糊控制规则去平滑 分组丢弃概率，从而保证了动态网络环境下的性能 近年来，许多进化计算领域的智能优化算法( 如：遗传算法( g e n e t i c a l g o r i t h m ) 、人工神经网络( n e u r a ln e t w o r k ) 、蚁群优化( a n tc o l o n y o p t i m i z a t i o n ) 、粒子群优化算法( p a r t i c l es w a r mo p t i m i z a t i o n ，p s o 算法) 4 重庆邮电大学硕士论文第一章绪论 等) 通过模拟或揭示某些自然现象和过程而发展起来，为优化理论提供了 新的思路和手段，现己广泛应用于函数优化、模糊系统控制、模式识别等 多个领域【l “”1 。它们的主要特点是收敛速度较快、自学习和自适应能力强， 没有很多参数需要调整，且不需要梯度信息。目前，也有少量研究把智能 优化算法引入到模糊控制理论中应用于主动队列管理算法【2 卜23 1 ，但这些方 法仍处于进步地观察和研究探索中，也建立在基于模糊控制的主动队列 管理的应用研究的基础上。 当然，把模糊控制用于主动队列管理还有许多问题需要迸一步地研究， 譬如：控制系统的稳定性、公平性、复杂性和可测性( s e a l a b i l i t y ) ，异构 网络环境下的强健性。另一个值得研究的问题是怎样更好地利用已有的模 糊经验知识和一些已设计出的模糊控制规则库组成的模糊规则集合。 1 ，2 论文的研究目标及结构安排 本论文研究的目的一方面在于分析基于模糊控制的主动队列管理这一 技术领域的前期成果，另一方面则是试图分析已有的模糊控制a q m 算法 中相关参数对网络性能的影响，然后提出改进方案，使得改进方案在网络 中达到良好的控制性能，也较现有其它方案在网络拥塞控制的有效性上有 较好的改善。 本论文分以下六个章节进行介绍： 第一章：简述拥塞控制研究的重要性和必要性，以及本论文研究课题 的意义及主要内容； 第二章：概述网络流量特性，阐述a q m 主要技术，并对a q m 算法设 计方面进行了探讨；集中研究和讨论了被i e t f 推荐使用的r e d 及几种变 体算法和其他几种a q m 算法。最后介绍模糊控制技术及其在a q m 中的 应用，分析了具有代表性的基于模糊控制技术的a q m 方案，并讨论了它 们各自的优点和不足。 第三章：在代表性算法r e m 的基础上，介绍了本章提出的一种基于模 糊控制的改进算法f u z z y r e m ，对其进行了理论分析和仿真实验。该算法 能够很好地控制到预期目标队列长度，从而达到低排队时延和高链路利用 率，对于变化的网络环境和突发的网络流量也都具有良好的鲁棒性 第四章：针对模糊控制f e m 算法存在的问题，介绍了本章提出的一种 自适应目标队列长度的f e m 改进算法a t q l f e m ，对其进行了仿真分析。 该算法能够根据网络实际流量调整其目标队列长度，使得算法在高吞吐 5 重鏖塑皇盔堂堡堡塞 ：j 蔓l 鳖望一 量、低延迟、低丢失率中达到一定程度上的平衡。 第五章：总结全文，并探讨了进一步的研究方向。 6 重庆邮电大学硕士论文 第二章主动队列管理机制 第二章主动队列管理机制 尽管t c p 拥塞控制机制是必须的而且是有效的，然而仅仅依靠t c p 来 进行拥塞控制己经远远不够了，网络的其他部分，比如路由器也应该参与 进行拥塞控制，并对源端节点的拥塞控制机制进行补充。随着主动队列管 理( a q m ) 算法，特别是随机早期检测( r e d ) 的提出对路由器处的拥 塞控制的研究己经成为一个研究热点 2 1 网络流量特性 通过对各种实际网络( l a n ，w a n 乃至高速数据网) 中业务流量的探 测和统计表明：目前的计算机网络流量，特别是以太网流量，在很长的时 间尺度上体现出一种自相关性和自相似性。具有自相似性的网络流量，突 发性更加明显，缓冲队列的拥塞行为更容易累积。自相似业务量在较大时 间尺度上仍保留较强突发性，这意味着网络系统不仅仅要解决网络流量的 暂时性突发拥塞，还要能保证在整个通信流量持续期间流量的平稳性。 传统的p o i s s o n 统计流量模型对于以突发性流量为基本特征的i n t e r n c t 网络不再适应，然而，采用更接近i n t e r n e t 网络流量特征的自相似模型会 具有复杂的建模过程和繁杂的计算。为此，从数据缓冲区占用情况的实时 状态出发，运用模糊理论对网络流量动态变化这一模糊性问题进行描述。 建立起模糊拥塞控制模型，从而能实现对拥塞的模糊控制。 2 2 主动队列管理技术( a q m ) 队列管理技术一般可分为“拥塞恢复”和“拥塞避免”两类机制。 传统的队列管理技术是在队列满时丢弃随后到达的分组，这种方法称 为“尾部丢弃( t a i l d r o p ) ”。虽然这个方法在当兹i n t e r n c t 上得到了广泛的 使用，但其存在几个重大缺陷【2 4 l ： 死锁( 1 0 c k o u t ) 问题：在某些情况下，“尾部丢弃”算法会让某个 流或者少部分流垄断队列空间，阻止其他流的分组进入队列。 满队列( f u l lq u e u e s ) 问题：由于“尾部丢弃”算法只有在队列满时 才会发出拥塞信号，因此会使得队列在相当长时间内处于充满( 或几乎充 重庆邮电大学硕士论文第二章主动队列管理机制 满) 的状态。而队列管理最重要的目标之一就是降低稳定状态下队列的长 度，因为端到端的延迟主要就是由于在队列中排队等待造成的。另外，满 队列也易导致突发数据的丢弃。 全局同步( g l o b a ls y n c h r o n i z a t i o n ) 问题：由于i n t e r n e t 上数据的突 发本质，到达路由器的包也往往是突发的。如果队列是满的或者几乎是满 的，就会造成在短时间内连续大量分组丢弃。受此影响，大量t c p 数据源 将几乎同时降低自己的发送速率，在短期内造成网络负载过轻，降低了网 络资源利用率；然后，所有t c p 数据源又将同时逐步增加自己的发送速率， 导致下一轮网络拥塞的出现，周而复始地影响网络的运行效率。这被称为 “t c p 流全局同步”现象。 正是由于“尾部丢弃( t a i l d r o p ) ”算法存在上述问题，1 9 9 8 年b r a d e n 等人在i e t f ( i n t e r n e te n g i n e e r i n gt a s kf o r c e ) 上提出a 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 策略有 效地控制队列长度，从而实现了控制端到端的时延，保证了网络q o s 。 网络拥塞控制系统如图2 1 所示。a q m 模块根据队列长度q ( t ) 变化， 在缓存溢出之前对到达的数据包以概率p ( t ) 丢弃，这个概率经过一些时延 后被源端检测到，源端由此判断网络状态，然后源端的速率控制算法调整 发送速率，从而佼路由器缓存的队列长度得到控制。从这个角度看，a q m 是系统的控制器，输出p 为系统的控制信号，而源端的速率控制是系统的 执行器，它和路由器的队列长度以及链路延迟一起，成为系统的广义对象 p ( 广义对象p 为图2 1 虚线框所包含的范围) 2 5 1 。 广义对象p 反馈 图2 1 网络拥塞控制系统的团环控制模型 a q m 的主要技术目标是在减小排队时延的同时保证较高的吞吐量。 a q m 解决的问题主要包括以下4 个方面： 早期探测路由器可能发生的拥塞，并通过随机丢弃或标记分组来通 知源端采取措施避免可能发生的拥塞： 8 重庆邮电大学硕士论文第二章主动队列管理机制 公平地处理包括突发性、持久性和间隙性的各种t c p 业务流； 避免多个t c p 连接由于队列溢出而造成同步进入“慢启动”状态： 维持较小的队列长度，在高吞吐量和低时延之间作出合理平衡。 2 3 。1a q m 算法设计的困难 a q m 技术作为拥塞控制的一种关键技术，和t c p 端到端的拥塞控制相 结合，是解决目前i n t e r n e t 拥塞控制问题的一个主要途径。不仅如此，在 对i pq o s 呼声越来越高的今天，a q m 也是实现q o s 的重要机制。a q m 不仅可以通过减小丢包率、端到端延迟、提高吞吐量等支持q o s ，而且还 可通过对不同业务实施不同的a q m 机制来达到区分服务的目的。因此， a q m 已经成为目前的研究热点之一，但其在设计上仍然存在下面几个问 题： 网络流量特征对a q m 算法的影响 2 6 , 2 7 】 网络流量特征对a q m 算法的设计和有效性有很重要的意义。网络中的 “流”是网络资源的用户，拥塞控制算法负责在多个“流”之间分配资源。 在平衡状态下，如果网络中“流”的数量增加或者资源的数量减少，在“流” 之间必须重新进行资源分配，在重新分配完成之前会暂时出现“需求”大 于“供给”，从而发生拥塞。假设网络资源的数量是相对稳定的，如果“流” 的数量不断剧烈的变化，就会不断出现拥塞。这要求a q m 算法具有很好 的反应速度。目前，互联网中流量特征的研究还不够充分。r r y u 等人提 出互联网中“流”的到达比泊松分布更具有突发性和非关联性【拈i 这种流 量特征对a q m 算法的设计和有效性是一个很大的挑战。 a q m 算法的反馈方式 a q m 计算出反馈大小后，需要将反馈传递给端系统。网关可以采用的 反馈方式包括“丢弃”( d r o p p i n g ) 和“标记”( m a r k i n g ) 。“丢弃”是所有 网关都支持的操作，传统的t c p 算法只使用报文丢失作为拥塞发生的指 示。“标记”方式显式地通知端系统，可以避免t c p 发送端调用超时处理 然而，“标记”方式的缺点是需要网关提供特殊支持，但随着e c n 的标准 化和广泛采用，这个问题将得到解决。 聚集流量速率估算算法【2 9 】 为了实现拥塞避免，a q m 技术在拥塞产生之前对队列进行处理，对一 些分组选择性地丢弃或标记。这些队列的管理行为随着网络状态和应用环 境的变化而改变。a q m 技术通过精确地控制队列行为使拥塞得到避免： 9 重庆邮电大学硕士论文第二章主动队列管理机制 但同时还要保证一定的吞吐率，不因为过分的分组丢弃行为而降低网络利 用率。要达到所有这些目的，都建立在对当前网络状态和“每一流”的性 能数据的精确跟踪和测量的基础上。 a q m 技术要求算法对链路上的各个聚集的流量速率进行估算，以作为 当前网络状态的跟踪数据，并根据这些数据得到各个流的转发状态，作为 实施主动队列管理功能的依据。当某一聚集的流量速率估算值超过其应享 有的一定链路带宽时，主动队列管理算法可能会对这一聚集流进行限制， 或者对该聚集流中的部分分组进行丢弃或标记，以对该聚集流产生抑制作 用，促使流的源发送端做出响应，将流的发送速率降下来。直到恢复正常 水平为止：当某一聚集流量速率估算值过低，则算法可能对它的分组进行 保护，或者调整其优先级，通知源发送端可以增加流量的发送速率，以更 好利用网络链路带宽资源。 现在常用的速率估算算法都是根据对当前链路上的聚集流分组进行间 隔或连续统计，将在不同时间段的统计数据作为依据以反映最近段时间 内该流量速率的变化过程，并将其近似为当前的流量速率值。因此，流量 速率估算算法的优劣，不仅与测量值的准确与否相关，还依赖于不同的流 量特性，不会有一种完全适用于所有应用的速率估算算法。 2 3 2a q m 算法的评价方法 由于i n t e r n e t 数据本质上是突发的，因此允许传输突发的数据非常必 要，而路由器中队列的重要作用就是吸收( a b s o r b ) 突发的数据包。较大 的队列能够吸收更多的突发数据，提高吞吐量，但t c p 机制往往会保持较 高的队列占用，从而增加数据包的排队延迟。a q m 机制就是要维持网络 处于低延迟高吞吐量的状态。其总设计原则为： 管理队列，使之维持在较小的队列长度，因为维持较小的队列长度 除了降低排队延迟，提高吞吐量外，还能保持较大的队列空间来吸收突发 数据包； 兼颞公平，使链路中响应流与非响应流，t c p 友好流之间能够平等 占用带宽，而不是对某些流存有偏见； 能够有效地与端系统的拥塞控制配合。在这里需说明的是现今的主 动队列管理算法( a q m ) 都是基于t c p a q m 模型考虑的。重点考虑的是 a q m 与响应业务流量相互作用的反馈机制上的性能，而随着网络中非响 应业务流量的增加，一个好的队列管理算法必须也在非响应业务流量存在 1 0 重庆邮电大学硕士论文第二章主动队列管理机制 的环境下获得好的性能。 因此，a q m 算法的性能极其重要。评价一个队列管理算法的性能可以 通过以下几个方面考虑： 稳定性 有些a q m 算法的目的是控制路由器中的队列长度，因此算法稳定与否 直接关系到路由器中队列长度的变化情况，而队列长度的变化又直接影响 到网络的服务质量。一方面，对于一个特定的t c p 连接，由于其传播延迟 是固定的，因此该连接传输时延和时延抖动的大小主要是由路由器中的队 列长度所决定的；另方面，路由器中的队列长度直接关系到其输出链路 的资源利用率，只有当队列长度不为零时才能保证网络资源的有效利用。 可扩展性 i n t e r n e t 中各处的网络性能有很大的差异，对于不同的网络条件，如网 络的规模变化，带宽的变化，链路传输时延的变化。不同的端系统状况， 以及存在多种数据流时，a q m 算法都应该具有相对较好的性能指标。 性能要求 拥塞控制算法对性能有很高的要求，包括算法的公平性、效率、稳定 性、鲁棒性和收敛性。通常的拥塞控制策略只能达到部分的性能要求，需 要考虑这些性能指标的折衷。 易实现性 设计的算法的实现要尽可能简单，不仅要尽量减少附加的网络流量， 而且要减少反馈信号的复杂度。同时拥塞控制算法的设计还必须尽可能降 低该算法在网络节点的计算量和实现的复杂度。 2 3a o m 主要策略 2 3 1r e d 算法及其改进 r f c 2 3 0 9 推荐f l o y d 等人提出的随机早期检测r e d ( r a n d o me a r l y d e t e c t i o n ) 算法拉】作为a q m 镶珞的难一候选算法。该算法具有很多优点， 在业界得到路由器厂商的广泛支持，诸如c i s e o 。j u n i p e r 等公司。 r e d 算法在网关处采用指数加权平均的低通滤波方法计算队列的平均 长度，将平均队列长度与两个阀值m i n 。h 和t n a x t h 比较，当平均队列长度小 于m i n t h ，所有数据包都被接收，当平均队列长度处于两个阀值之间，网关 重庆邮电大学硕士论文第二章主动队列管理机制 将以一定的概率随机丢弃数据包，当平均队列长度大于m a x 。h 时，所有数 据包都被丢弃。假设采样周期是s ，加权系数为，o 0 是很小的常数； z 】+ = m a x z ，o ，。在式2 3 中6 ，( f ) 为 t 时刻队列，缓存区的队列长度，b 0 是目标队列长度；而( f ) 是t 时刻进入 队列，的总流量速率，c l ( f ) 是t 时刻队列，的可利用带宽。而o ) 一e a t ) 度量速 重庆邮电大学硕士论文第二章主动队列管理机制 率的匹配情况，b a t ) 一b 度量队列的匹配情况。常数口，能根据每个队列单 独设置以权衡传输过程中的带宽的利用率与队列时延。常数t 控制在网络 条件变化时r e m 算法的响应速度。从式( 2 3 ) 可以看出，如果速率不匹 配与队列不匹配的加权和( 加权系数为口) 为正，则“价格”增加，反之 “价格”减小。 实际