（系统工程专业论文）高速网络拥塞控制算法研究.pdf

摘要 摘要 随着网络传输业务需求和科学研究应用的发展( 如远程登录、卫星传 播、超大规模数据库) ，出现了越来越多的带宽大于1 g b p s ，往返时延大于 l o o m s 的高带宽长时延网络( 简称高速网络) 。计算机、通信和存储技术的 迅猛发展为计算和科学研究提供了足够的容量和高速有效的硬件环境。发 展高速网络所面临的挑战在于现有的网络拥塞控制算法和资源共享算法不 能扩展到新一代的高速网络中。主要表现为在高速网络环境下，现有的协 议算法不能保证低的包丢失率和低的时延及时延抖动等服务质量需求。目 前，国内外对高速网络方向的研究处于起始阶段。出现了一些代表性的源 算法，如h s t c p 、f a s tt c p 、x c p 等。其中h s t c p 算法实现简单，具 有良好的可扩展性，已经被i e t f 所接受。拥塞控制算法由t c p 源算法和 i p 链路主动队列管理算法构成。从控制理论的角度，源算法和i p 链路算 法构成了一个闭环反馈控制系统。现有研究结果表明长的时延会导致整个 网络的不稳定运行。 首先，本文针对长时延对拥塞控制系统算法的性能影响，运用最小拍 控制器设计方法设计了适应于长时延网络的主动队列管理算法d b c 。该算 法能够使路由器中的队列长度快速零误差地跟踪上参考队列长度，并且在 长时延网络环境和动态流量网络环境中均具有快速的响应性能。 其次，现有研究表明h s t c p 仍旧存在一些严重的性能缺陷。h s t c p 在拥塞点时会产生大量的数据包丢失，同时当队列管理为去尾算法时，存 在着严重的r t t 不公平性问题。针对h s t c p 算法的性能缺陷，本文提出 一种在拥塞避免阶段进行拥塞避免模式切换的改进算法，称为e h s t c p 。 提出一种新的基于窗口历史值的端到端的可用带宽预测方法，利用窗口历 史信息来判断拥塞避免切换点。同时引入r t t 公平因子，消除了h s t c p 的r t t 不公平性问题。 再次，本文对h s t c p a q m 闭环系统的性能进行了解析分析，分析结 果表明主动队列管理算法可以改善h s t c p 算法在去尾队列管理算法下的 性能缺陷。但现有主动队列管理算法不能直接移植到高速网络中。 燕山大学工学硕士学位论文 最后，本文提出了适应于高速t c p 网络的主动队列管理算法s p i 。该 算法能够保证在高带宽网络环境下h s t c p 算法具有高的链路利用率的同 时，还能克服上述h s t c p 算法在去尾算法管理下的性能缺陷。 关键词i n t e m e t ；拥塞控制；t c p ；h s t c p , 主动队列管理 a b s t r a c t a b s t r a c t w i t ht h e d e v e l o p m e n to ft h e n e t w o r kt r a n s m i s s i o ns e r v i c ea n d s c i e n c er e s e a r c h i n ga p p l i c a t i o n ( f o re x a m p l e ，t e l n e t ，s a t e l l i t et r a n s m i s s i o n , l a r g es c a l ed a t a b a s e ) ，t h e r ea r em o r ea n dm o r en e t w o r k s ( h i g hs p e e d n e t w o r k ) ，w h o s eb a n d w i d t hi sl a r g e rt h a n1g b p s ，a n dr t ti sl o n g e rt h a n 10 0 m s t h ed e v e l o p m e n to fc o m p u t e r , c o m m u n i c a t i o n sa n dt e c h n o l o g yo f s t o r a g ep r o v i d e se n o u g hc a p a c i t i e s a n df a s t - e f f e c t i v eh a r d w a r ef o r c a l c u l a t i n ga n ds c i e n t i f i cr e s e a r c h t h ec h a l l e n g eo fd e v e l o p i n gt h en e w g e n e r a t i o nn e t w o r k si st h a tc u r r e n tc o n g e s t i o nc o n t r o la l g o r i t h m sa n d r e s o u r c es h a r i n ga l g o r i t h mc a n tb ee x p a n d e dt ot h en e wg e n e r a t i o nh i g h s p e e dn e t w o r k s i ti sm a i n l ye x h i b i t e da si nt h eh i g hb a n d w i d t hn e t w o r k e n v i r o n m e n t ，t h ec u r r e n tp r o t o c o la l g o r i t h m sc a n tg u a r a n t e en i c e rs e r v i c e q u a l i f yo fl o wp a c k e tl o s sr a t e i u l ta n dd i t h e r i n go fr t c u r r e n t l y , i ti s i nt h eo r i g i n a t i v ep h a s e so fh i g hs p e e dn e t w o r k sr e s e a r c h i n g t h e r ea r e s o m er e p r e s e n t a t i v es o u r c ea l g o r i t h m s ，f o re x a m p l e ，h s t c p , f a s tt c p , x c pe t c b e c a u s eo fs i m p l i c i t ya n ds c a l a b i l i t yo ft h ei m p l e m e n t a t i o no f h s t c ei ti sa c c e p t e db yt h ei e t ec o n g e s t i o nc o n t r o la l g o r i t h m sa r e c o m p o s e do ft c ps o u r c ea l g o r i t h ma n di pl i n ka c t i v eq u e u em a n a g e m e n t a l g o r i t h m a c c o r d i n gt ot h ec o n t r o lt h e o r y , t h es o u r c ea l g o r i t h ma n di p l i n ka l g o r i t h mc o m p o s eac l o s e - l o o pf e e d b a c kc o n t r o ls y s t e m c u r r e n t r e s e a r c h i n gi n d i c a t e st h a tl o n gr t tw i l ll e a dt ou n s t a b l es t a t eo ft h e w h o l en e t w o r k f i r s t ，w ed e s i g nt h ed b ca 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 mu s i n g t h ed e a d b e a tt h e o r y , w h i c hi sa d a p t i v et ot h el o n gt i m e d e l a yn e t w o r k s a c c o r d i n gt ot h ep e r f o r m a n c eo fd e l a yt ot h ec o n g e s t i o nc o n t r o ls y s t e m i t c a nm a k et h eq u e u el e n g t hi nt h er o u t e rt r a c kt h er e f e r e n c eq u e u el e n g t h w i t hn o n e r r o la n da l s oh a sf a s tr e s p o n s ep e r f o r m a n c eb o t hi nl a r g ed e l a y n e t w o r k sa n dd y n a m i ct r a f f i cn e t w o r k s 燕山大学工学硕士学位论文 s e c o n d l y , t h ec u r r e n tr e s e a r c hi n d i c a t e st h a th s t c pa l s oh a ss o m e s e r i o u sd e f i c i e n c i e s t h e r ee x i s t s l a r g e n u m b e ro fp a c k e tl o s s u p o n c o n g e s t i o ne p o c ha n ds e r i o u sr t tu n f a i r n e s sw i t hd r o p t a i lg a t e w a y t o o v e r c o m et h ea b o v ed e f i c i e n c y , w ep r o p o s ea l li m p r o v e da l g o r i t h m , c a l l e d e h s t c ew h i c hs w i t c h e sb e t w e e nt w oc o n g e s t i o na v o i d a n c em o d e si n c o n g e s t i o na v o i d a n c ep h a s e t ol o c a t et h es w i t c hp o i n t ，w ep r e s e n tan e w p r e d i c t i v e m e t h o df o re n d t o - - e n da v a i l a b l eb a n d w i d t hu s i n g h i s t o r y c o n g e s t i o nw i n d o wd y n a m i c s s i m u l t a n e o u s l y , w ei n t r o d u c et h er t t f a i r n e s sf a c t o rt oe l i m i n a t et h es e r i o u sr t tu n f a i r n e s si nh s t c p t h i r d l y , w ea n a l y z et h ep e r f o r m a n c eo f t h eh s t c p a q mc l o s e - l o o p s y s t e m ，i ti n d i c a t e st h a tt h ea 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 mc a n o v e r c o m et h ed e f i c i e n c yo fh s t c pi nt h ed r o p t a i lg a t e w a y , b u tt h e e x i s t i n ga c t i v ec a n th eb r o u g h tt ot h eh i g hs p e e dn e t w o r k sd i r e c t l y f i n a l l y , w ep r o p o s ean e wa 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 mc a l l e d s p lw h i c hi se f f e c t i v ei nt h eh i g hs p e e dn e t w o r k s s p ic a ng u a r a n t e eh i g h l i n ku t i l i z a t i o n , a n da l s oc a no v e r c o m et h ea b o v ed e f i c i e n c i e so fh s t c p m a n a g e db yt h ed r o p t a i la l g o r i t h m k e y w o r d si n t e r n e t ；c o n g e s t i o nc o n t r o l ；t c p ；h s t c p ；a c t i v eq u e u e m a n a g e m e n t i v 燕山大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文高速网络拥塞控制算法 研究，是本人在导师指导下，在燕山大学攻读硕士学位期间独立进行研究 工作所取得的成果。据本人所知，论文中除已注明部分外不包含他人已发 表或撰写过的研究成果。对本文的研究工作做出重要贡献的个人和集体， 均已在文中以明确方式注明。本声明的法律结果将完全由本人承担。 作者签字彳易玺= 砭 日期：z 呻年乒月7 日 燕山大学硕士学位论文使用授权书 高速网络拥塞控制算法研究系本人在燕山大学攻读硕士学位期间 在导师指导下完成的硕士学位论文。本论文的研究成果归燕山大学所有， 本人如需发表将署名燕山大学为第一完成单位及相关人员。本人完全了解 燕山大学关于f q 专，使用学位论文的规定，同意学校保留4 向有关部门送 交讫殳的复印件和电子版本，允许论文被查阅和借阅。本人授权燕山大学， 可以采用影印、缩印或其他复制手段保存论文，可以公布论文的全部或部 分内容。 保密口，在年解密后适用本授权书。 本学位论文属于 不保密 ( 请在以上相应方框内打“寸) 作者签名： 导师签名： 锅焱花 泛拶彳 日期：2 岬醉月厂日 日期：1 7 年辱月7 日 第1 章绪论 第1 章绪论 1 1 研究背景及意义 随着i n t e r n e t 的迅猛发展，i m e m e t 给人类社会带来了巨大的变革。 但就在i m e m e t 深刻影响人类历史发展进程的同时，其t l 身的发展却 面临着种种困难，其中之一就是网络拥塞( n e t w o r kc o n g e s t i o n ) 。从 i n t e r n e t 诞生起，网络拥塞就与其如影随形。虽然经过二十多年的飞速 发展，i m e m e t 克服了其前进道路上的一个又一个技术障碍，而网络拥 塞却至今难以很好解决。而且随着现今i n t e r n e t 的规模，用户和应用 急剧增加，网络拥塞问题不仅没有得到缓解反而日益突出。为了解决 网络拥塞问题，1 9 8 8 年j a c o b s o n 在文献【2 】中首次提出了网络拥塞避 免( n e t w o r kc o n g e s t i o na v o i d a n c e ) 和网络拥塞控s o ( n e t w o r kc o n g e s t i o n c o m r 0 1 ) 理论，为此后网络拥塞控制的研究奠定了基础。现在，网络拥 塞控制已经成为确保i n t e r n 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 协议【卜5 1 ，因此对i n t e r n e t 拥塞问题的研究主 要集中于t c p h p 拥塞控制。实践表明i n t e r n e t 的飞速发展也得益于 t c p h p 的拥塞控制机制。t c p h p 中使用的拥塞控制算法已经成为保 证i m e m e t 稳定性的重要因素【6 j 。 然而，由于网络拥塞控制是一个复杂控制系统，拥塞控制算法的 分布性、复杂性使得拥塞控制算法的设计具有极高的难度。因此网络 拥塞控制的研究虽然已经有十多年的历史，但是到目前为止，网络拥 塞问题仍然没有得到很好的解决，依旧是当前国内外网络研究领域的 一个热点课题。 未来的几十年，由于科学研究和应用的需求( 如超大科学计算和 千兆兆级数据库) ，急需发展新一代鲁棒稳定的超高速i n t e r n e t 网络 ( 1 0 0 g b p s 及1 0 0 g b p s 以上) 。随着计算、通信和存储技术的迅猛发 燕山大学工学硕士学位论文 展，全球网格系统为计算和科学研究提供了足够的容量和高速有效的 硬件环境。发展新一代网络所面临的挑战在于现有的网络拥塞控制算 法和资源共享算法不能扩展到新一代的高宽带通信网络中。主要表现 在宽带高速网络环境下，现有的协议算法不能保证低的包丢失率和低 的时延及时延抖动等业务服务质量需求，甚至会导致整个网络的不稳 定运行，显著降低网络的业务服务质量 7 - 1 0 】。因此建立系统的拥塞控 制协议算法设计理论，提出具有良好扩展性( 任意大的网络容量和用 户业务数量) 的新协议算法，为通信网络系统性能分析提供数学模型 和分析方法，为下一代高速宽带i n t e r n e t 网络的拥塞控制算法设计和 实现提供理论基础等均是亟待解决的问题。 1 2 国内外研究现状分析 从控制系统的观点来看，i n t e r n e t 网络是一个闭环的复杂系统。因 此，拥塞控制算法主要涉及如下三个问题：( 1 ) 女1 1 何检测网络的拥塞； ( 2 ) 如何将拥塞信息反馈到拥塞控制点；( 3 ) 拥塞控制点如何根据拥塞信 息进行调整。 在早期的t c p 传输协议实现中只有流量控制( f l o wc o n t r 0 1 ) 而无拥 塞控制，流量控制利用t c p 报头的通告窗口字段使接收端向发送端告 知它可以接受的流量，流量控制避免了高速发送端发送速度过快淹没 接收端的问题。但流量控制没有考虑网络的传输能力，这就为网络拥 塞埋下了伏笔。1 9 8 6 年1 0 月，互联网历史上第一次由拥塞引起的网 络崩溃( c o n g e s t i o nc o l l a p s e ) 发生。当时，从l b l 到v c b e r k e l e y 的一 段带宽为3 2 k b p s 的线路，由于拥塞导致实际数据传输速率降为4 0 b p s ， 近1 0 0 0 倍的性能下降使网络几乎瘫痪。此后，引起了人们对拥塞控制 的广泛关注。到1 9 8 8 年，j a c o b s o n t 2 1 首次将端到端的拥塞控制算法引 入到t c p 传输协议中。随后基于端到端的t c p 拥塞控制研究蓬勃发 展，致使现在t c p 有不低于2 0 0 个实现版本，而它们之间的主要区别 就在于拥有不同的拥塞控制算法。 虽然人们在t c p 拥塞控制方面展开了广泛的研究，并取得了一定 2 第1 章绪论 的研究成果，相继提出了一些如t a h o e 、r e n o 1 1 , 1 2 、n e w r e n o ”1 、 s a c k 1 4 】、v e g a s ”】等著名的算法。但是人们随后发现单纯依靠t c p 端到端的拥塞控制策略很难解决i n t e r n e t 拥塞问题，网络本身必须参 与到拥塞控制中来。1 9 9 8 年，b r a d e n 等人在i e t f 提出了“主动队列 管理”( a c t i v eq u e u em a n a g e m e n t ，a q m ) i 勺研究动议【1 6 】，期望a q m 能 改善队列管理性能，减少排队延迟提高系统吞吐量，为t c p 拥塞控制 提供支持。a q m 拥塞控制算法通常又称为i p 链路算法，它一般是通 过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 ) 1 7 - 1 9 1 来实现的。 对于低速低时延的局域网和广域网，t c p a q m 算法设计框架在 保留了端到端的设计原则的基础上加入了拥塞预警机制，提高了算法 性能和业务服务质量，保证了当前网络的鲁棒稳定运行【2 。随着网格 计算逐步走向应用和网络的长距离传输( 卫星传输) ，下一代因特网 将具有高带宽时延积的特性。现有的研究将受制于两个瓶颈。一是目 前的单比特反馈( 用于包丢失或包标记) 的设计思想将t c p 算法和 a q m 算法进行分离设计，这就使得即使在流量层次上非常完善的 a q m 设计，在包层次实现时网络也仅能给源端提供包是否包标记的 二值逻辑信息。这一限制在高带宽时延积因特网( h b d p i ，h i g h b a n d w i d t h d e l a yp r o d u c ti n t e m e t ) 环境下会显著降低拥塞控制算法性 能，如在拥塞避免阶段采用的a i m d 算法会带来过慢的响应速度和明 显的振荡；二是研究和仿真均表明长的传输时延可导致网络不稳定并 带来不公平性问题。最近一个令人震惊的研究结果是高的链路容量会 增大网络运行的不稳定【2 1 2 3 1 ，这使得高带宽时延积因特网的鲁棒镇定 设计成为一个难点。由高带宽时延积带来的这两个新的挑战性问题， 使得对现有拥塞控制算法和协议实现框架进行深入分析，提出能保证 下一代因特网鲁棒稳定运行的协议设计理论成为当务之急。由于高带 宽时延积因特网刚刚显现，因此对上述拥塞控制问题的研究国际上也 仅处于初始研究阶段。解决方法主要是采用多比特的反馈控制方案。 如c a l t e c h 的l o w 博士所带领的n e t l a b 课题组提出的f a s tt c p l 2 “， 网络将测量到的端到端队列时延信息反馈到源端，根据此信息，源端 燕山大学工学硕士学位论文 对拥塞窗口进行动态调整。该算法能实现高带宽时延积网络的快速镇 定。另外一个重要的研究成果是m i t 的k a t a b i 博士所发表的x c p l 2 5 1 ， 该算法设计思想来源于a t m 网络中的a b r 显示速率拥塞控制算法， 应用多比特e c n 将路由器所计算的显示速率反馈给t c p 源端。上述 两种算法都要求t c p 报文头中包含多比特的反馈信息( 即全信息反 馈) ，理论上来说可以实现更精确的拥塞控制，但是将增加更多的负 荷，浪费网络资源并增加了实现的复杂度，实际协议实现的难度很大。 另外，前一种算法往返时间r t t 和端到端的队列时延的精确估计也 是一个难以解决的问题。后一种算法更是改变了端到端的t c p 拥塞 控制设计原则，需要在现有的t c p 协议上作大量的改动，因此都不能 实际解决上述的瓶颈问题。 此外国内学者对t c p a q m 这一研究领域非常重视，目前取得了 一些初步的研究成果，如清华大学的任丰原博士【2 6 2 7 】和上海交通大学 的汪小帆教授2 8 ，2 9 1 ，浙江大学的潘雪增教授【7 0 】。 1 3 传统t c p 算法性能缺陷 因特网的发展方向表明下一代因特网由于具有高带宽时延积特 性，给现有的研究提出了新的挑战。目前国际上对该问题的研究刚刚 展开，研究水平处于初始阶段。具体而言，该问题的研究进展受如下 条件的制约。第一，现有的t c p a q m 协议框架在包层次上的算法性 能降低。主要原因在于高的带宽时延积会带来非常大的t c p 拥塞窗口 ( 数量级为1 0 4 1 0 5 ) 。现有的t c p 拥塞控制机制主要采用慢启动机 制和a i m d 形式的拥塞避免机制 3 0 , 3 1 ，代表性的算法有t c pr e n o ， t c pn e w r e n o ，t c ps a c k 。在a i m d ( 加式递增乘式递减) 调整过程 中，如此大的拥塞窗口必然会导致“过缓”或“过激”的效应。如加式提 升，每一往返时延( i h t ) 仅增加一个包，这使得用户达到稳态吞吐 量的时间过长。当可用带宽为1 g b p s 时，一个包长为1 5 0 0 字节，r 1 、t 为2 0 0 m s 的t c p 链接需要2 7 分钟才能从包丢失的状态重新获得可用 带宽【3 ”。当发生包丢失( t c p r e x m t t h r e s hd u p l i c a t ea c k s o rt i m e o u t ) 4 第1 章绪论 和e c n 标记时，将当前拥塞窗口( c w n d ) 减半，这种行为又显得过 激，带来大的网络流量振荡，同时会带来低的网络吞吐量。第二，在 流量层次上现有的算法的鲁棒性和稳定性难以保证。首先保持大的平 衡窗口需要极小的包丢失率( 数量级为1 0 - 8 1 0 - 1 0 ) ，它们的关系可由 式( 1 1 ) 反映 w 0 = 1 耸( 1 - 1 ) p o 其中w 。为用户的平衡窗口大小，风为端到端的包丢失概率的平衡值， a 为比例因子。很显然随着带宽时延积的增加，在实际网络中该平衡 状态将难以保证。另外如此小的包丢失概率的精确估计也是一个很难 的问题。 1 4 拥塞控制算法介绍及分析 1 4 1高速网络拥塞控制算法介绍及分析 当前国际上对于高带宽时延积网络拥塞控制算法的研究处于起步 阶段，出现了一些具有可扩展性的算法。本章主要介绍以下四种代表 性的算法： h s t c p 算法1 3 叫：s f l o y d 针对传统t c p 算法在高带宽时延积网络 环境下存在的扩展性问题和响应缓慢的缺点 3 4 , 3 5 j ，提出了一种基于包 丢失的a i m d 窗口调整算法h s t c p 。它与传统的算法设计思路相反， 首先从流量层次着手来设计合适的响应函数，然后根据所设计的响应 函数具体在包层次上设计窗口的调整量。具体而言，为了保持t c p 友 好性，h s t c p 首先确定出一窗口阈值，当c w n d 时，h s t c p 保留了传统的t c p 窗口调整机制，根据传统t c p 的响应函数可以计 算出当= 3 1 时p 。= o 0 0 1 5 。为了保证在传输媒介允许的包丢失率 的范围内维持大的平衡窗口，h s t c p 选取在包丢失概率为1 0 。时窗口 为8 30 0 0 。即w h 耐= 8 3 0 0 0 ，p 神= 1 0 - 7 。然后选取一个使l o g ( w ) 和l o g ( p ) 成线性关系的函数 燕山大学工学硕士学位论文 w = 1 0 5 0 0 9 ( p ) - 1 0 9 ( ) 卜l o g ( ) ( 1 2 ) 其中j = o o g w 啦一l o g w , o ) ( 1 0 9 p , 曲一l o g p h ) ，代入w h ，w h 神，p h ， p 础可得s = - 0 8 2 。由式( 1 2 ) 可得出h s t c p 的响应函数 w ：等( 1 - 3 ) w = = h s t c p 根据上述响应函数，设计包层次上的拥塞避免算法。它仍 采用a i m d 形式的窗口调整机制，但窗口的变化量a ( w ) ，b ( w ) 是随着 窗口的大小自适应变化的。该算法在包层次上窗口动态调整如下： o na c k ：w 卜w + a ( w ) w o nl o s s ：w 卜w b ( w 1 w 其中加式增加因子口( w ) 和乘式下降因子b ( w ) 如式( 1 - 4 ) 和( 1 - 5 ) 所示。 口( w ) = w 2x 1 2 0 石xb ( 矿w ) xp ( w )( 1 4 ) 6 ( w ) = p 卅嚣鬻+ o s ( 1 s ) 其中b = o 1 。h s t c p 通过在流量层次上设计合适的响应函数，在 包层次上设计自适应变化的窗1 2 1 调整量口( w ) 、6 ( w ) ，保证了该算法的 可扩展性、公平性和友好性。 s t c p 算法【3 2 1 ：s t c p 是另外一种具有代表性的基于包丢失的高 速t c p 算法。它与h s t c p 的主要区别在于它采用m i m d ( 乘式递增 乘式下降) 的控制机制。该算法的拥塞窗口动态调整如下： d 玎爿c 匿w 4 - - w + a o nl o s s w 4 - - - w b w 其中口，b 为( 0 ，1 ) 之间的常数，文献【5 】中选取4 = o 0 1 ，b = 0 1 2 5 。s t c p 的响应函数为 a0 0 8 w = = ( 1 6 ) b pp 、7 由式( 1 6 ) 可以看出s t c p 发生包丢失后的调整周期与可用带宽的 大小无关，这是该算法的一个重要的优点。它的另外一个优点是经过 包丢失后窗口的调整幅度小，仅为当前窗口1 2 5 。从而避免了过大 6 第1 章绪论 的窗口振荡，使得该算法能够获得高的吞吐量。 f a s t t c p 算法1 2 4 】：以上介绍的h s t c p 、s t c p 均是以包丢失为 信号来调整拥塞窗口的，而f a s t t c p 则是采用端到端的队列时延的 变化为信号来调整拥塞窗1 2 1 的i ”】。以下将简单介绍f a s tt c p 的设计 思路及优缺点。f a s t t c p 的窗口调整策略如下： w - - m i n 2 w , ( 1 - 7 ) w + y l b a r s e 刀r t t w + 咖，g 撕) ) ( 1 - 7 ) 其中b a s e r t t 为端到端的传输时延( p r o p a g a t i o nt i m e ) ，i t 为端到 端往返时延，g 蛳为端到端的队列时延。a ( w ，g 协) 的定义如下 a ( w , q d a 。r ) ： a ，扩，q li o0 - 8 ) l r o l l l e r w t s e 从该算法的窗口调整策略可知，f a s t t c p 源端需要估计端到端的 传输时延，这在实际网络中是难以实现的。因为若路由器中已经存在 数据包排队时，新加入的f a s tt c p 流是无法准确估计出端到端的传 输时延的。f a s tt c p 相对于h s t c p 、s t c p 来说最大的优点在于它 具有良好的稳态性能。 x c p 算法1 2 5 ：x c p 是一种基于多比特信息的网络拥塞控制协议。 x c p 最大的特点就是将拥塞控制和公平性控制分离开来。拥塞控制实 现的目标是高的吞吐量、小的队列长度、几乎接近于零的丢包率；公 平性控制采用的是一种灵活的带宽分配策略，来实现流与流之间的公 平性。x c p 打破了原有的t c p a q m 协议框架，重新定义了包头。其 源端的窗口调整机制可以描述为 o n a c k ：m a x ( c w n d + h f e e d b a c k * r t t ，s ) o n l o s s ：c w n d ：竺型 2 其中hf e e d b a c k 为初始化源端的期望速率，由路由器进行重写。 x c p 的接收端除了将收到的数据包的包头的反馈信息拷贝到 a c k 包头之外，其余功能与t c p 接收端一样。x c p 的关键算法全部 在路由器内实现。其路由器算法主要由有效性控制算法( e c ) 和公平 性控制算法( f c ) 构成。e c 的目标是最大化链路的利用率、最小化 7 燕山大学工学硕士学位论文 包丢失率和小的队列长度。e c 仅考虑链路的总的流量，不考虑单条 流的流量及公平性问题。f c 实现目标是将e c 计算出的总的反馈量在 包层次上公平地分配给每条流。f c 以包为单位来分配e c 计算出的总 的反馈量，通过重写包头hf e e d b a c k 反馈给源端。 x c p 应用多比特信息反馈机制，将路由器计算出的显式速率反馈 给源端，以达到其设计目标。文献 2 5 】通过仿真验证了x c p 能在高带 宽时延积网络环境下获得良好的性能。但x c p 的大部分功能均在路 由器内实现，这无疑增加了路由器的负荷p “，因此x c p 需要强大的 路由器支持。在实际网络中要建造如此强大功能的路由器的造价是十 分昂贵的。同时x c p 算法实现复杂，在实际网络中难以实现。另外 x c p 采取了t c p 的保守的窗口下降方式。当x c p 应用于有线无线异 构网络时，x c p 源端会将无线网络中的随机包丢失误认为拥塞丢失， 造成窗口的振荡和吞吐量的下降。 1 4 2 主动队列管理算法介绍 a q m 算法与简单的包丢弃策略的主要不同在于隐含“预测”机 理，路由器通过当前的路由信息( 队列，输入和输出速率) 对网络拥塞 进行预测标识，及时调整源端窗口大小，保证较小的包丢失率，从而 提高了整个网络带宽的利用率。根据拥塞检测机制的不同，许多学者 提出了不同的主动队列管理算法，主要有随机早期检测算法( r a m o m e a r l yd e t e c t i o n ，r e d ) ，b l u e 算法，随机指数标识算法( r a n d o m e x p o n e n t i a lm a r k i n g ，r e m ) 和自适应虚拟队列( a d a p t i v ev i r t u a lq u e u e ， a v q ) 算法等。 r e d 算法邛】：r e d 由f l o y d 提出，是目前a q m 算法事实上的标 准。它用平均队列作为拥塞标识，当平均队列小于设定的最小门限值 时，包不被丢弃，当平均队列大于设定的最大门限值时，所有包都被 丢弃，当平均队列在这两者之间时，包的丢弃概率是队列平均长度的 一个分段线性递增函数。其拥塞控制算法可以由式( 1 9 ) 表示： 第1 章绪论 彳= ( 1 一a 茸+ 叼 p = 0 0 彳q m 云- q 石b p 一。茎虿绌 1 - 9 ) 1 q 一虿 其中a 【o ，1 】为加权因子，q m ，q 。，p 一为r e d 可调整的参数。 但是r e d 很难提供一个可扩展的参数配置方法 3 7 , 3 5 1 ，主要原因有( 1 ) 平均队列长度对流量负载和r e d 设置参数非常敏感；( 2 ) 网络吞吐量 与流量负载和r e d 设计参数密切相关。这样使得基于r e d 主动队列 管理的网络拥塞指标和性能指标相耦合，高的网络利用率必然带来高 的包丢弃率和长的队列时延。针对r e d 参数配置的困难，提出了许多 改进算法，如a d a p t i v er e d 39 1 ，d r e d 4 0 ，4 1 1 ，b l u e l 4 2 1 ，f u z z yr e d 2 1 , 4 3 等。 b l u e 算法 1 0 , 4 2 ：b l u e 算法利用瞬态队列长度和链路利用率作 为流量负荷的标识，当瞬态队列长度值超过事先设定的门限值， b l u e 算法将包丢弃或标识概率提高一个常值幽妇( 其为事先设定的 系统参数值) 。为了避免包丢弃策略太“激进”，b l u e 算法给出了一 个最小更新区间f e e z et i m e 。如果链路空闲( 对列为0 ) ，则包丢弃概 率以周期为f e e z et i m e 降低如，幻。通过瞬态队列长度和链路利用率 ( 空闲事件) 来调整概率p ，b l u e 算法能够将瞬态队列值逼近到小 的稳态队列。 r e m 算法i 】：r e m 算法则是将网络性能测量和拥塞测量分离， 通过分布式运算“代价”对数据包进行标识。其代价的更新律如下： p t ( f + 1 ) = k ，o ) + y ，b ，【6 ，o ) 一岛) ) + y ，o ) 1 r ( 1 - 1 0 ) 其中y ，和a ，为小的正常数。由式( 1 1 0 ) 可以看出，当网络达到平衡态 时，r e m 算法能同时达到速率匹配和缓冲匹配，即能够保证在较小的 缓冲队列时网络仍具有很高的吞吐率。从控制理论角度来看，r e m 算 法是一个二阶p d 控制器，因此其能达到一个光滑的运算律，而r e d 9 燕山大学工学硕士学位论文 及其改进算法都是简单的一阶p 控制器，其控制律是个非线性切换控 制律。由于r e m 算法要进行指数运算，从而增大了算法的计算量。 a v q 算法4 5 q 7 1 ：自适应虚拟队列算法与上述算法不同，它仅以路 由器的输入速率x o ) 作为拥塞指示。当数据包到达路由器，虚拟队列 容量进行如下更新： 等= a 一x 其中 ，为期望的利用率。该设计方法的主要依据是当到达速率超过了 期望的带宽利用率时，包将被标识或丢弃。此算法在固定网络环境下， 仿真分析表明其在包丢弃概率、平均队列长度和带宽利用率方面均高 于r e m 算法。 目前这些队列算法各有优缺点，但是大部分算法的参数设计是根 据仿真分析得来，因此很难比较这些算法在一般网络环境下的可扩展 性和稳定性。要对网络系统进行定性的理论分析，则必须给出基于 a q m 的网络源端数学模型。目前的研究主要是两个方向，一个是e c n 作用的机制下，保持源端不变，对t c p 拥塞避免阶段进行数学建模， 然后将a q m 看成控制输入，组成一个闭环系统，进行闭环系统性能 分析和控制器设计。此方向的研究由于可以保持源端算法不变，只需 对a q m 进行设计，因此近两年来受到通信网络和控制理论研究领域 的学者和专家的广泛关注。研究设计框图如图1 - 1 所示。 其中前馈和反馈路由矩阵中包含了前向和反向传输时延。另一研 究方向则是基于效用函数优化模型，进行静态或动态a q m 参数进行 设计。基于上述控制框图，我们可以利用古典控制理论和现代控制理 论的控制分析与集成技术，提出系统的主动队列控制器设计方法。文 献 4 8 1 基于t c p 源端模型，分析了r e d 算法的稳定性，并提出了p 和p i 型主动队列管理控制器用以改善r e d 算法的性能。文献【4 9 】考 虑t c p 窗口在每个i h t 时间内只下降一次并且是突发性下降的性质 基础上，建立新的t c p 源端模型，并给出了状态反馈型的主动队列管 1 0 第1 章绪论 理。文献【5 0 】是在非线性源端模型上( 不考虑传输时延) ，基于非线性 变结构控制设计思想提出了一种新的鲁棒主动队列控制器设计。但是， 目前控制器参数的设计和稳定性分析大都是在简化的网络拓扑上进 行，即只考虑单瓶颈网络或者不同源在链路传输的时延是相等的。至 今为止，基于通用网络拓扑的可扩展性控制器设计还是一个尚未解决 的问题。另外，由于丢失概率或者标识值通过e c n 反馈路由传输会有 一定的时延，且其值要满足0 s p 瓜) 1 ，因此考虑输入具有饱和非线 性时滞因素是该控制器实现的关键 2 7 , 5 1 , 5 2 1 。 图1 - 1 典型的a q m 控制器设计框图 f i g 1 - 1t h eb l u ep r i n to f t y p i c a la q m c o n t r o l l e r 1 5 本文的研究工作 时延是影响t c p i p 网络拥塞控制系统稳定性的关键因素之一。本 文首先针对时延对拥塞控制系统算法的性能影响，从i p 链路角度出 发，设计了适应于长时延网络的主动队列管理算法d b c 。接下来针对 h s t c p 算法存在的性能缺陷【卯。6 】提出了相应的改进算法e h s t c p 。最 后在分析h s t c p a q m 算法性能的基础上，提出了适应于高速t c p 网络的主动队列管理算法s p i 。 燕山大学工学硕士学位论文 第2 章长时延网络的主动队列管理算法 2 1引言 现有的主动队列管理算法几乎都忽略了时延和动态流量的影响， 如r e d 、r e m 、p i 和b l u e 等。长的时延和动态流量会对系统的稳定 性造成不利影响，主要表现为缓冲区队列长度的不稳定。本章将重点 解决长时延和动态流量对系统造成的影响。从控制理论中，我们知道 最小拍控制器的设计方法具有使系统输出快速地镇定到某一给定的参 考输入的优点，系统输出在一拍或者几拍内便可跟踪上参考输入。对 于t c p a q m 闭环系统来说，表现为系统大约经过一个r t t ( r o u n dt r i v t i m e ) 的时间便可跟踪上参考输入。本章将推出d b c ( d e a db e a tc o n t r 0 1 ) 主动队列管理算法，该算法能够使路由器缓冲区的队列长度快速地跟 踪上参考队列长度，提高链路利用率，降低包丢失率。并且在动态流 量环境下具有快速的响应性能。 2 2d b c 主动队列管理算法 2 2 1模型描述 在文献【5 7 】里，作者给出了描述t c p a q m 系统的动态模型，仿 真实验结果表明该模型能够准确地描述t c p a q m