（计算机应用技术专业论文）高速网络中拥塞控制算法的分析及其改进.pdf

南京邮电大学硕士研究生学位论文摘要 摘要 随着互联网规模的增长，网络拥塞已经成为一个十分重要的问题。本文从拥塞控制 算法的必要性入手，从两方面介绍并分析了拥塞控制算法：拥塞控制源算法和拥塞控制 链路算法。在源算法中以t c p 算法为主，在链路算法中以路由器队列管理算法为主。本 文首先介绍了现有的t c p 机制t c pr e n o 。由于住高带宽大时延的网络中使用现有的 t c p 机制，网络得不到有效的利用，于是引出了适应高速网络的高速t c p 算法一一i l s t c p 。 论文在介绍i t s t c p 在吞吐量和带宽利用率上带来巨大改善的同时，也分析了h s t c p 在公 平性上的缺陷，并提出了改进方案。通过逝一步的观察，发现改进的t t s t c p 的性能受到 d r o p t a i l 和r e d a r e d 路由器的限制，所以接着本文就讨论了路m 器管理算法。近年来， 主动队列管理算法己成为端到端拥塞控制的一个研究热点。它通过评估网络状态、预测 拥塞出现，对分组进行有目的的丢弃，从而可以使发送端更及时地了解到网络状况并调 整发送速率。但是现有算法在响应速度、稳定性及环境敏感性等方面仍有缺陷。通过分 析及仿真，本文提出了一个改进的适应性r e d 来解决在多流中数据包同时丢失的问题， 这个改进的适应性r e d 称为p a r e d 。p a r e d 在改变最大丢失概率的时候考虑了平均队列 长度的变化趋势，它比a r e d 表现出了更有效的主动式队列管理性能。最后本文利用n s 2 对这些算法及其改进方案做出了详尽的仿真和分析。仿真表明改进的h s t c p 同p a r e d 结 合在起能够得到更好的带宽利用率和更好的公平性。 关键词：拥塞控制，高速t c p ，h s t c p ，主动队列管理，r e d ，a r e d 南京邮电大学硕士研究生学位论文摘要 a bs t r a c t c o nl 1 n u o u sa n de x p o s i v eg r o w t ho ft h ei n t e r n e th a ss h o w nt h a i ，c o n g e s t i o n c o n t r o lh a sb e c o m eav e r yi m p o r t a n tp r o b l e m 。b e g i n n i n gw i t ht h en e c e s s a r yo f c o n g e s t i o nc o n t r 0 1 t h i sp a p e ra n a l y s i s a n di n t r o d u c ec o n g e s t o nc o n t r o l a l g o r i t h m si nt w oa s p e c t s ：c o n g e s t i o nc e n t r e ls o u r c ea l g o r i t h ma n dc o n g e s t i o n c o n t r o ll i n ka l g e r i t h m t c pc o n g e s t i o nc o n t r o lm e c h a n is mi st h em a j as o u r c e a l g o r i t h ma n dq u e u em a n a g e m e n ti st h em a i ni i n ka l g o rit h m t h ep a p e ri n t r e d u c e s c u f f e n tt c pa l g o t i t b m r e n ot c pf i r s t l y 。 h e n ；ti sa n a l y z e dt h a tc u r r e n tt c p m e c h a n i s m se a n q o ta c h i e v ee f f i c i e n tu t 1i z a t i o no fn e t w o ￥k sw i t h 1 a r g e b a n d w i d t h d e l a yp r o d u c t s s oh i g h s p e e dt c pisi n t r o d u e e d h i g h s p e e dt c ph a si t s a d v a n t a g ei nt h r o u g h p u ta n du n d e r t i t i l i z a t i o no fn e t w o r k b u ti ta 1 s oh a s d i s a d v a n t a g ei nt h i r n e s s 。t h e nt h i sp a p e rp r o p o s e sat r a n s p o r t - l a y e rp r o t o c o l ， w h ic hjsb a s e do nh i g h s p e e dt c p f u r t h e r m o r e ，i ti so b s e r v e dt h a tt h ed e r f o r m a n e e o fi m p r o v e dh s t c pi s1 i m i t e db yb o t hd r o p r a i1a n dr e d a r e dr o u t e r s ， h u s c o n g e sl i o nc o n t r o la 】g o t i t h mf o rl i n k i si n t r o d u c e d a c t i v eq u e u em a n a g e m e n t ( a q m ) a l g o r i t h md r o p sp a c k e t sp u r p o s e f u l l yb ye v a l u a t i n gs t a t eo fn e t w o r ka n d f o r e c a s t i n gc o n g e s t i o f i s 。s o t h es e n d e r sc a t ) b ei n f o r m e d w i t hs i t a a t i o no l n e t w o r k a n dt h e nc a r la d a p tt h es p e e d b u tc u t r e n ta l g o r it h m sh a v ed i s a d v a n t a g e si ns o m e a s p e c t s ，s u c ha sr e s p o n d i n gs p e e d ，s t a b i l i t ya n ds e n s i t i v i t yt on e t w o r k t h e n am o d i f i e da d s p t i v er e dc a l l e dp a r e di sp r o p o s e dt oa d d r e s st h e ) ! 、o b l e mo f s i m mt a n e o u sp a c k e td r o p sa m o n gm u l t i p l ef l o w s 。8 ya d a p ti n gt ot h et r e n di n v a r i a t i o no ft h ea v e r a g eq u e u el e n g t h 。p a r e dp e r f o r m sa c t i r eq u e u em a n a g e m e n t m o r ee e c t i v e l yt h a na r e d s i m u l a t i o n ss h o wt h a tc o m b i n i n g m p r o v e dh s t c p t o g e t h e rw i t hp a r e dl e a d st oe f f e c tu t i liz a t i o no fn e t w o r kb a n d w i d t ha n dg o o d f a jr n e s s k e yw o r d s ：c o n g e s t io r ：o r l t t o l ，h i g h s p e e d + i c p ，h s r p ，a q m ，r e d ，a r e d i 南京邮电大学 硕士学位论文摘要 学科专业：工学计算机应用 研究方向：盐簋垫堕焦生圈间墨堡垫盔 作 者：业堕级研究生鲞丝麴 指导教师：鲎堕 题目：高速圈垫主塑塞蕉型笠选曲盆堑丛甚丛鲨 笔文足亟 习：旦! ! z ! i ! ! 堡旦! 坐p ! ! ! ! 坐曼些! q 望g ! ! ! i ! 旦g 旦望! ! ! ! 垒! g ! ! i ! ! 盟 i 旦垫i g 垒二! 卫星星垦垫旦堕! 垫! g 曼二壁星! 垒z 盟星! 塑q ! 蔓! 主题词：t c p 拥塞控制算法，a i m d ，r e n o ，h s t c p ，h ig h s p e e dt c p ， a q m ，队列管理算法，r e d ，a r e d k e y w o r d s ：t c pc o n g e s t i o nc o n t r o la 1 9 0 r i t h m ，a i m d ，r e n o ，h s t c p h i g h s p e e dt c p ，a q m ，q u e u em a n a g ea l g o r it h m ，r e d ，a r e d 南京都电大学学彼论文独创健声鹤 y 8 5 1 0 7 2 本人声蝴所璺交羽学位论文是我个a 在导炳指导下进行的研究工 乍及取锝灼研究祟。 尽我掰船，豫了文中特涮加以标注鞠熬谢静堍方磐，论文中不鬯含其 遣入已经发表或撰写 过酌磷究成聚，遣不包含为获褥南衷郎奄大学或其它激鸯极栋瓣学位域涯书嚣缓瘸过蕊枣耋 料。与我一同工作的问志对本研究所做的任何贡献均已在论文中作了明确的说确并表示了 谢意。 骖究生签名：专墓舀；盎。秘期：幽f 南京邮电大学学位论文便精授权声鞠 辫寨郯电大学、巾謦秘学投零售息研究所、国家麴书镕胄权僳翻本人所送交学位论文 的复印件和电子文稻，可良采焉影印、缩印或其他羹翻手段傈存论文。本人电子文糖鹣内 容和纸旗论文的内容褶致。豫在保密期肉静绦密论文井，兔诲论文藏查圈鞠缮阕+ i 以 公布( 包括刊登) 沦文的全部蜮部分内容。论文的公布( 包括邗登) 授权南京邮电大学研究生 部办理。 研究宅躲敞燃名滥朗：碰钽f 南京邮电大学硕士研究生学位论文绪论 1 拥塞控制算法的必要性 绪论 随着计算机网络的急速发展，拥塞问题也接踵而来。例如，在一段采用t c p 作为 传输鼷协议昀黼络中，经常会发现菜一台路由瑟西秀本魏亟的缓冲区溢嗡蔼产生1 0 左右 的丢包率，因此发端会根据n a c k 戏超时机制发觉i 叟端并未收到数据包，于是重传该 数据戗并循环往复。如果网络上每一台终端都存做这样的事情，那么网络将不堪重负从 面严整影响藜髂靛网络性能。 ，卜述例子充分说明了网络中使用拥塞控制算法的必要性。根据f l o y d 的定义，拥黎 控算法是+ 令基予潮终 二豹其有专嚣互竞争关系f | 皇用p 上运露数分匆式算法，凌算法用 于在竞争用户之间台艘分配网络资源。由于网络中可用资源和竞争情况的随机性，如何 育效穗分配资源菲鬻蘩要。捅馨控翻嚣法正楚各个网络用户蠲寒依据掰络环壤变忧提供 的反馈信息而自适应地调整其网络行为，以达到整个网络系统的最佳运行性能的分布式 算法。 此外，网络系统中的一些网络节点( 如路由器) 也参与到这种调节行为中来。为了 解决网络拥塞，提高网络服务的质量，实现网络的优化管理，近年来对拥塞控制算法进 牙大鬃薹 究工作，可将其分为在媸系绞上使用鞠源算法葶拜在列终漫墨上使用的链臻算法 两种。源算法中使用鼹广泛的是t c p 协议中的拥塞控制算法，链路算法的研究主要集 中在队列管理舞法豹毳井究上，该方法爱在路囊器中采掰寇潺爱磐法秘缓存管壤援末。实 现链路算法的队列管理多种多样，主疆分被动式队列管理和动式队列管理两种。 所以可隧澄整个弊法体系包含两部分，发送方和接收寿一匕懿t c p 算法，以及链髓 上( 如路出器) 的a q m ( a c t i v eq u e u em a n a g e m e n t ) 算法，在本沦文将把这两方面结 合起来研究讨论。 传统拥塞控制算法的局限性 网络中的拥塞来源于网络资源和网络流量分布的不均衡狂。搪塞不会随着黼络处璀 能力嬲提高丽消除。拥塞控制箨法的分布性、网络的复杂性和对拥塞控制算法的性能要 求又使拥塞控制算法的设计具有很高的难度。 塑塞些鱼查堂塑主篮塞尘兰篁笙壅 竺兰 蘧羲t n t e m e t 瓣发震，萁糖塞浚麓橇翻毽应该不灏改遴以遥应穗络鹣发袋。菠零静 发展趋势预示辫未来的网络将包含了极多的高带宽的饺路，同时还会出现越来越多的卫 星及无线通信蒋高延迟的网络。传统的t c p 拥塞控制算法在商带宽的网络j 二不仅会不 稳定，而且其性能也会下降。由下浆_ 嗣加性增氏机制，传统的t c p 拥塞控制算法在每 拿r t t 中增热发送靛包过于缓慢，这在裹带竟兹网络坏凌下会浪费若下戤_ 方糍充分 利露阏络带宽。努外，当在里星通信和无线 , v a n 中静流数目增加时，公乎经也会上齐 为一个严重的问题。 而且，随潜网络规模的扩大和网络应用的拓宽，并不是每个用户都实现了基于窗口 的端到端的搠爨控制，单纯的端到端的搦塞控制已经难以保持网络豹高效和公平地运 行，必缳谴l p 溪参与瓣终懿援塞羧糕。 本文将从两方面来讨论网络拥糕控制算法：( 1 ) t c p 算法的性能以及对h s t c p 算 法的改进方案；( 2 ) 路由器队列管理算法性能及对a r e j ) 算法的改进方案。最后把这两 方面结合在一起讨论，通过两方面的改进，使得最后的拥塞控制算法的性能强进一步地 提高。 3 本论文安排 本论文主裳研究高速链路下t c p 1 勺拥塞控制算法以及路南器队列管理算法，并展 努广泛丽涤入戆磺究和仿真工 蕈。涂文营先奔缨捌塞控锻葵法静一些基本槭念和燕量指 标，然后介绍穗箭应用最为j “泛的t c pr e n o 算法，在贪缁t c pr e n o 算法瓣嗣时指l 出 其在高速键路下的算法缺陷；接着本文介绍2 0 0 3 年术f l o y d 针对高速大时延环境| i 的 t c p 拥塞控制算法一- - h i g h s p e e dt c p ，随后介绍对该算法的改进意见；通过仿真和分 毒厅，发现改进的h s t c p 算法的性能受爨现有的路由嚣队捌管理葵法的影响，所以接着 本文讨论了路态嚣队歹l 管理算法，分缓了最零嗣懿隈捌鸶瑾算法r e d ，蕊霹爨出r e d 算法的缺陷，引出a r e d 算法并提出埘a r e d 算法的改进，最后结合仿真结果讨论其 有效性及可行性。 全文内容组织如下： 第一章壤遴穗塞控霉l 算法熬凡个纂本摄念，劳绘塌了簿董算法控憨静凡个搔栎。 第一二章简单介绍t c p r e n o 算演，证分析了r e n o 的缺陷基础上引入h s f c p 算法。 在介绍h s t c p 算法的优越性的同时池指出h s t c p 的缺陷，特别是存与t c p r e n o 并存 时的公、f 性问题，并介绍了对h s t c p 算法的改进。然后提出由于路由器队列管理算法 妻室塑皇查堂堡主篓蒸生兰竺笙奎 茎望 采嗣了d r o p t a i l 绒者r e d 雾法霹霹整令捐塞控裁葵法豹瞧麓骞羹莓影镳，著弓l l 屯跨隆由 器队列管理算法的讨论。 第三章介绍了拥塞控制键路算法，简单介绍了被动式管理算法及其缺陷之后重点分 析了现在常使用的队列管理算法r e d 算法，在r e d 的撼础上 i 出a r e d 算法，并通过 分褥a r e d 熬缺点撼出鑫己对a r e d 豹改遘意见，霪翻凝的箕法p a r e d 棼泫。 第圈章利丽n s 仿真对所实现的h s t c p 良及a r e d 算法进行一系列的祷景仿真实 验，利用仿真结果验证h s t c p 相对于t c pr e n o 的优越性，a r e d 相对于r e d 的优越 性以及改进的h s t c p 同改进的a r e d 算法一一p a r e d 结合的有效性。 第五章总络全文。 南京船电大学碗士研究啦学位论文第一章拥塞控制的j l 个基本概念 第一章拥塞控制的几个基本概念 在i n t e r n e t 设计的初期，对于拥塞的控制是通过t c p 协议中端到端基于滑动窗口的 涟量控制完成豹。遗蓑应塌需求的f l 蕊丰富强技术的不凝发展，研究太爨开始将部分萋拜 究注意力转惫隧缭中的路由器等中阚节点设备，翳鋈逶遥增强它翻的功来实现主辊薅 无法达到的技术目标。就拥塞控制而言，网络中阳j 节点有可能更及时，甚至提前准确了 解网络的拥塞状态，并依此实施有数的资源管理策略，使网络能避免拥塞，娥尽早从严 重的拥塞状态中恢复过来。 本章穗分绥瓣络纛塞控截戆蕊本理论，夯绥鞠塞控潮豹蓥奉魏裁，在陵磊懿，遣章终 对在发送端实现的拥塞控制t g p 算法帮在网络中问节点处实现的路由器队列管理算法一 一进行介绍。 1 。l拥塞 在网络中，当数据到达一个大的管道并向一个较小的管道发送时便会发牛獭塞。当 多个输入流到达一个路由器，而路( = j 器的输出流小于这热输入流的总和时也会发卜拥塞 ( 见图1 1 ) 。具体到实际场景，当某个路山器的包到达率犊近链路极限时边会发q i “排 队”臻露产，圭延逡。出子路由器的缀冲区大小有限，不可避免产生包的丢失。手是传送 此包的所有上游潞由嚣所作兹转发王作以及重传该包对带宽静占用使成为誊| 塞豹代徐。 墨爨 酾m b p s 增 圈 刨1 il 叫络拥器发屯场景研例 当拥塞发生时，若缺乏一个很好的控制机制，则很容弱发生网络崩溃现象( c o n g e s t i o n c 。l l a p s e ) ，所谓斓络渍溃现象鄹多个发端由于拥塞的出璐丽丢包，他嚣j 共同蕊传该包从 蔼产生了更为严鬟黪穗塞。穰撂不鬻辨阚络协议实褒，网络稿溃瑷蒙还r 虿麓有以下舔个 原因引起： 1 ) 重传机制：当仅丢失某一个数据分片时，若发端将簟发整个人的报文段时，刚络 崩溃将更为严重。 童塞塑塑查堂堡生篓塞墨堂些鎏塞 苎二童塑塞茎型墼! i 2 苎查堡查 2 ) 反馕瓤铡：当发臻不支持或鸯暴露不台瑾豹反缓穰凝霹，霹络蘩溃 楚毂豸黟藏。 当网络崩溃发生时，网络的吞畦率和延迟将发生明强的变化，如图1 2 所示。 吞吐掇 延遮 栽 强1 2 媾络勰溃聍粒吞睦枣翥 廷避焚纯强 1 2 拥塞控制v s 流控制 徼裁 在最初的t c p 协议中只有流控制( n o wc o n t r 0 1 ) 而没有拥塞控制，接收端利用t c p 报 头将接收能力遐镪发送端。这抒的控毒椒割只考虑了接收漆鲸接收能力，藤没有考虑礴 络敕俦输髓力，这将导致瓣络壤演装发生。t 9 8 6 年1 0 嚣，由于发生了圈络麓溃，美邕 l b l 到u cb e r k e l e y 的数据吞吐量从3 2k b p s 跌落到4 0b p s 。住1 1 2 _ 后，在拥塞控制领 域开展了大量的研究工作，拥寒控制算法的提出对保诚i n t e m e t 的稳定具有十分重要的 作用。 穰塞控涮露浚控潮主要有以下舞令虿阉点： n 流控制的手要目的是为避免趱岛接收端的接收熊力，i ! i i i 更关心镣收端的缓存； 而拥塞控制主要目的足为了避免使路由器缓存溢出而引起网络拥塞，卡要是着眼 于网络的商吞吐量和低延迟。 2 ) 弱者采趱不嗣熬窗口规刳：漉控铡采用的窗口一般记为w n d ，撩塞羧镥有自己的 掬塞窑翻c w n d ，最终发端魏发送密目太曩、为两者的最小德m i n ( w n d ，c w n d ) 。 1 3拥塞控制机制 飙控到理论躲穗发，参| l 塞控铡群渡可以分为开环控涮鞠闼环擦裁两大类；11 ，当渡量 特鬣可以准确爆宠、性链要求i l j i 以事先获得时，逶予佼瓣开环控裁；当滚_ 蠹特征不能准 确描述或者当系统不提供资源预图时，适于使用闭环控制a i n t e r n e t 中主要采用闭环控制方式，以动态的适应网络的变化，其设计关键是如何 塑塞坚皂查堂婴主塑壅兰堂缝鎏兰 璺：童塑塞蝗型塑! ! 尘墨查塑垒 生戏爱镶蕊惑稠按俺对反馈谈息送行峨应。趣环醵撼塞控制分为三个羚段：检测鼹终中 捌塞的发生；将拥塞信息报告到拥塞控制点；拥塞控制点根据拥塞信息进行调艇以消除 攘塞1 2 1 。溺环静謇蒜塞控裁可以动态懿遥应网臻的交纯，僵算法洼戆受翻反镶廷运静严 重影响【l ，刘。当拥塞发生点和控制点之间的延迟很大时，算法性能会严重下降。 穰据算法的实现位簧，可以将拥寨控制算法分为两大类：滁算法( 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 c p 搀议中的拥塞控制算法a t c p 是目前在i n t e r n e t 中使用嫩广泛的传输协议。根据m c i 的统计，总字节数的9 5 和总 攫文数装9 麟缓嚣t c p 馋辕f d 3 。近年寒，善e p 中采瑶了缓多耨懿麴塞挖铡算法，包括漫启 动( s o ws t a r t ) 、拥寨避免、快速重传( 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 ) 5 j 簿，大夫提赢了潮络传徐的性蘸。l c p 中侵瑁麓骞替塞控制算法已经 成为保证i nl e r n e t 稳滗性的璧要因素。 链路算法的研究酲前集中在“主动队列管理”( a c t i v eq u e u em a n a g e m e n t ，简称 a o m ：) 算法方藏。和传统的“队尾丢弃”( d r o p t a i l ) 柏比，a q m 在网络没罄的缓冲滋 出之前就丢弃或标记报文，a o m 的主耍优点是： ( 1 ) 减少剩关载投文丢失。使曩a 娜可以保持较小豹队列长整，从两增强斓终中闷萤 点容纳突发流攮的能力。 ( 2 ) 减枣缀文逶过麓关酶延迟。藏小平均酞列长瘦露以有效建减小搬文在嘲络漫蚕中 的排队延迟。 ( 3 ) 避免l o c k - o u t # 亍为的箴生1 7 】。 a 娜的一个代表是r e d f 8 ( r a n d o me a r l yd e t e c t i o n ) 。研究表明，r e d e g d r o p t a il 具 有更好的性能，这在第四章的中将通过仿真束表示出来。在r f c 2 3 0 9 中，强烈推荐使弼 r e 0 传为今后灼标准。但是进步谤究发现，r 鞠鸵性糍对算法灼参数设置十分敏感，至 今没有在i n t e r n e t d 0 得到广泛的使用。 1 4拥塞控制算法性能指标 在设计和比较拥塞控制算法时，需要一定的1 平价方法。从用户的角度出发，可以比 较臻系统豹吞睦率、丢戋率和延迟等援糠，这些是臻户辑关心瓣。由于参囊塞控裂算法对 整个网络系统都有影响，在评价算法时更应该从整个系统的角度出发进行考虑。 6 壅塞塑塞查兰篓圭璧塞兰蹩垫鎏苎璺= 童塑鐾楚! ! 塑墨全蔓查壁垒 对算法褴能秘分褥主溪在满令方溪：乎缀性能( e q u i l i b r i “m ) 积动态性能 ( d y n a m i c s ) 。平衡绺熊主要讨沧斡怒系绞在乎德点处瓣器秘运行牲艇及袭瑷，这包挺泰 吐鬟( t h r o u g h p u t ) ，萎失( 1 0 s s ) ，延迟( d e l a y ) ，公乎穗( f a i r n e s s ) ，司扩艘褴 ( s e a l a b i l i t y ) 箨簿。动态性能鳓体现在系统的稳定椎s t a b i l i t y ) 积 | 禽应嶷 ( r e s p o n s i v e n e s s ) 一垃。 i 4 。i 吞畦量 器i 鞋= 量蹲予每个滋溃来说也藏魑传输速率，指酌是个源端在单经时澜内淀网络中 发送的数据墩，单位一般最k b p s 。在流层的模爱中，定义每个源墒，在时刻t 的传输速 率为并，( f ) 。内于这个发送逶率x ，( f ) 葙发送方麓搁塞密口大小嗽( # ) 存在这撵钓关系： x i ( 0 = 1 8 ) 霉，e ( o 为寐嘲时鼷( 邸r t t ) ，一般受潮绦环境交纯衡决定所以，掰苏 通过这个关系式就可以籁肇的来理解复杂的网络行为：方谳发送方通过调憝的稍塞窗 口太小 孵) 来调节发送速率t ( ) ，另方面黼臻环境盼变彳墓又逶过t o ) | 爹确了这释发送 速率。 吞吐爨常被用寐汁算疆源刹用的“效率”。这坦瞧顺便介绸下“效率”的概念： 嶷源分配鹣效率可以耀p o w e r 黼数9 ，l o j 米浮份。p o w e r 灏数定更为： p o w e r = t h + o u g h p u t 。r e s p o n s e t i m e 在上式中，一般敬a = l ，魏架评价绱重眷避鲞，翼l 敬a i ；魏暴评徐镛麓反应时瓣， 烈敬a 0 1 ) ( 1 5 ) x 网络系统总的响应度指数r ：m a x r ：) 。显然r 越小响应度越高，网络系统的汇聚速度 越快。 1 5本章小结 本章从拥塞控制的必要性出发，首先介绍了拥塞，拥塞控制与流控制、拥塞控制机 制等概念，在介绍拥塞控制机制的过程中分别从源算法和链路算法两方面进行展开；最 后介绍了一一下衡量算法平衡性能的几个指标：吞吐量、丢失、延迟、公平性、稳定性和 响应度。 南京鳏电夫学碗 ：趣拜究生学位论空 纂黎t c p 算法 第二章t c p 算法 2 1t c p 拥塞控制的发展 i 9 8 8 年j a c o b s o n 针对k j ) 在阐络搁塞控蠲方筒瀚不足，疆鹅了“漤启动” ( s l o w s t a r t ) 帮“黼褰避免”( c o n g e s d o na v o i d a n c e ) 算法。j a c o b s e n 奠定t t c p x 童 流羹控黼的蒸本框檠，函为其在】n t e r n e t 上举足轻蘩豹作用，矮涞翡学者辩磷究入员继 续对它邀行了燮为绥敲蕊深入豹磷究，不断完善和改避了算法巾存镬敬黪，袒缝产生 了5 个圭蘩舨本憋t c p 溅量控制算法，它们分别是t a h o e ，r e n o ，n e w r e n o ，s a c k 哥h v e g a s 。 其中以r e n o 冀法疲粼熬浸为广泛，掰以在本文主要介缁t r e n o 簿法。1 9 9 0 零搿域的t c p r e n o 舨本增加了“快速羹传”( f a s tr e t r a n s m i s s i o n ) 莉“快速恢复”( f a s t r e c o v e r y ) 冀法，遮免了凰终绷塞不严麓时象髑“瞧穗动”嚣法丽造缄过度藏小发送整 门尺寸的飙豫。此螽掰形成的阮p 稍熬控制靛主黉由这4 个核心冀法缎或：镬璃动、桶黪 避免、抉遮鬣传鄹快速後复。这黧舞法楚在论文 l 、】5 巾液设计出来，并在：l 夔巾被 标港讫。 2 2r e n o 算法介缓 2 。2 。1 慢癌动拥塞避免 t c p 发送端采用缀唐动和捅褰避免算法来控箭囱黼络输送麓鼗捺爨。为了实现这些 算法，必须向t c p 每连接状态加入三个参羹： 一个楚黼褰簿强( c w n d ) ，它是对发送端牧瓣确认( a c k ) 之裁滟淘瓣络传送 的最大数裕蹙的个发送端瀚隧耩； 一个蹙攘板端遗稚窝醴( r w n d ) ，它蹩黠未完蔽数攒餐静搂羧灞勰隈制，( c w n d 和雌饼矗熬瀑夺 壹决定了数撰传送) 。 慑崩韵溺氆( s s t h r e s h ) ，被鲻来确定是鼹慢舞动还避角捌塞避免算法来控剃 数撂佟遴，具体恩法搦下：警c w n d s s t h r e s h 时使熙| | _ 曼感动箕法； 刚群菇 s s t h r e s h 酵馒援穰塞避免冀法；当c w n d = s w t h r e s h 时，发送溃溉可以使 题褪囊动也可以搜掰麴戆遴纨。s s t h r e s h 的初始值可以任意大( 比如，一些实 南京邮电大学硕士研究生学位论文 第章t c p 算法 现中使用接收端通知鬻口的尺寸) ，但是一旦对拥塞嫡应之羼，其大小可能会 被减小，详细情况将在下面描述。 在不涛楚瓣络繇瓷兹漕凝f 巍爨终传送数撂，要求t c p 缓瀣逸探测翘终以凌定可用 带宽，以避免突然传送大量数据而使刚络拥塞。为达此目的，在传送开始时，采用了慢 启动帮t 翩，这个橇涮在修复了整重袭定时器探溅到懿数据丢失之螽也被采蠲。 荫先要确定的是c w n d 的初始值i w ( 初始窗口大小) ，这里规定它必须小于或等1 二 2 s m s s 字节而且不熊大子两个数据段。但怒在一些非标准的，实验性的t c p 的扩充允 许t c p 使用一个更大黝i w ，在等式( 2 。1 ) 中绘予定义【1 7 ： ，彤= m i n ( 4 s m s s ，m a x ( 2 s m s s ，4 3 8 0 b y t e s ) ) ( 2 i ) 有了这个扩充，t c p 发送端可良经溺一令3 或4 数据段静初始容暖，只要这些数瓣 段的总尺寸不超过4 3 8 0 字节。 在慢启动期间，每收到一个新的a c k ，e w n d 最多蹭长l ( 郾l x s m s s 个字节) 。蛮矧 c w n d 超过s s t h r e s h 或者检测剿期塞时，婷止执行慢启动算法，转入捌塞避免阶毁。 1 谯拥塞避免期间，c w n d 在每个a c k 以一- ( 或每个r t t 增加s m s s 个字节) 的速 c w n d 度遂遴。稍爨避免算法壹保持直到裣灞出翔塞。等式( 2 2 ) 给出了一个在耪| 塞逮免麓 问用来修正c w n d 值的公式： c w n d + = l ，c w n d( 2 2 ) 撼收到一一个非重艇的a c k 都采用等式( 2 2 ) 来调髌c w n d 。等式( 2 2 ) 用于近似拥耩 避免弹法的增长。 在实现中，在拥囊避免期闻鬻用公式：c w n d + = s m s s x s m s s c w n d 来修正c w n c l 的 值，当s m 路s m s s c w n d 1 时，c w n d + = l 。 另一静改进稳方鬃是每当凝终a c k 妥寒时记f 鞍麟雅认瓣字萤数，然瑟# w 臻d 竣可 增加相应字节数，这个增加的数目最多可达到s m s s 字节。 一照t c p 发送端使用重传定时嚣检测戮龟丢失时，s s t h r e s h 藏设戒等式( 2 。3 ) 所给鑫奄 值： s s t h r e s h = m a x ( f l i g h t s i z e 2 ，2 s m s s ) ( 2 ，3 ) 囊如上瑟所提到的，f l i g h t s i z e 惫已发送但未收到a e k 懿数据熬大小。 茔重发了丢失的数据段之后，c q n d 必须被设置成l w ( 丢失窗口) ，它等于一个 满尺寸数据段的大小。再发丢失的数据段之后，发送端起用慢启动算法增长窗口，直到 1 2 南京蛳电大学硕士研究生学位论文 第二罐t c p 弊涟 该蜜鞠太小袭长翻等予瑟没鬻豹s s t h r e s h 篷之焉，叉采麓灏塞避免篓渡了+ 2 2 2 快速重传快速恢复 当接收端收到一个失序魏数掇撤对，会立即发回个重复a c k ，这个a ( ：k 的强的是 告甄发送溅浚戮拿失旁夔数疆缀并巍爨萁嚣藕望蕊渡受净譬。簌发送壤黪楚菠看，瀵 复a e k 可驻楚诲多蕊络润嚣g | 趣镳。首先，它们有可怒怒邋为毫丢失瓣引怒。在此搪撼 下，在此数粥段之后的所有数据段都会触发熬复a c k 。其次，重复a c k 可能溉由丁二网络 对数据羧豹瀵糖裁 廖引莛静。装盾，逐复a c k 畜可戆怒a c k 袋数握段羧掰终艇鞠辑零l 起 静。姥羚，萼渡牧端黎分或完蘩媳壤蛰了浮号窒绞瘟意郄发送，一令a c k ，这搀可以受及 时建遭躲发送漆，菠其迅速麸薰菠敞态中恢笺过来。 t c p 发遴端成该使用快速重传算法来探测或赣修缀数据丢失，在收到兰个重复 a c k ( 即连续的姻个相间的a c k ，标志港一个数据段已妥失) 时，t c p 不答重传定时器超时 裁立翔菱传器寒琶丢失兹数据段。此后起用j 妖速恢复簿法来避行掰的数据传辘，直烈一 令j 蓬复a c k 黧这。 f 嚣是捷逋抟送馁速恢复葜法灏实臻： 当第三个重复a c k 收到时，s s t h r e s h 根据等式( 2 3 ) 设值。 重僚篆失懿数据段并将。w n d 靛 萱设蓬力s s t h r e s h 十3 繇秣，稼之舞给糖窭客 鞫“兖气”。 此蜃封簿拿接收菇一个重楚a c k ，滋c w n d 激大s m s s 字节，这褥人为遗扩充撼 塞窗口用以反映已经离开网络的刚加数掘段。 如暴c w n d 和接收端的通知衡口值允许的话，发送一个数据段。 当下个确认赣数掇豹a c k 捌达酵，没囊c w n d 缓为s s t h r e s h ( 步骤l 浚藿溜煎) ， 这称俸绘窑疆“藏气”。这令a c k 爨矮蹩步囊l 舷笈豹蘧发雩l 起豹凑歆，j 鬟笈之磊一个 r t t ( 在接牧溅有次序紊乱豹数据敬瀚涪凝下，宅可髓会j l 靛到达) 。 另外，此a c k 应该确认丢失数掀段和第三个重复a c k 期间的数掘段，如粜它们个 也没有丢失鹩话。 2 2 3r e n o 算法豹性鼹分耩 麸酌r e n o 运行税翻中德容器溪建，为了维持一m 令动态平簿，崮须蠲翔魏抟产生 定量的丢失，辩加卜a i m d l8 ，1 9 3 机制碱少快，增长慢，尤其是在丈窗口环境下， 3 南京邮电人学硕士研究生学位论文 第一章t c p 算法 由予个数掇搬的丢失所带柬的窗口缡小要花费很长的时间来恢复，这样， 不可能很高，而且随潜网络的链路带宽不断掇升，这种弊端将越来越明显。 公乎蛙方嚣，攫掇绫 手数握，r e n o 黪公乎性还跫爨到了姻当的肯定， 大的网络范围内理想地维持公平性原则。 2 3 h i g h s p e e dt c p ( h s t c p ) 简介 2 3 1t l i g h s p e e dt c p 的引入 带宽利用攀 它越够在较 可以看到，传统t c p 拥寒控制算珐已经被广泛地应用。实践证明，当其虑用于低带 宽环辘下貔数据传输时，g 够潺是应翊对吞睦釜鹭纛求。然舔，当它应翅子在麓蒂突嚣 境下的数据传输时，由于传缆t c p 仂、议自身的问题，吞吐鬣往往不能达到应用的实际 需求。s f l o y d 对r e n ot c p 瓣撩塞控制舅法进行了研究 2 0 1 ，褥出了吞睦鬟，包丢失 时间间隔，乎均拥塞窗口大小，包丢失率阃的关系： l = b r ( 1 2 d ) ( 1 ) w 2 b r j ( 8 d ) ( 2 ) p = l ，5 w 2( 3 ) 其中， 表示丢包事馋满疆静糊露个数；b 表示吞吐餐；r 表示网络延迟；d 表示包的 大小；w 表示平均拥塞窗口；p 表示稳定状态的包暑失率。 檄据上述3 个公式，可l 盖褥委吞睦量、雹丢失淹隔、平均撵塞鬻 l 和鼋丢失率约缒 关系，如表2 1 ( 此时包的大小为1 5 0 0 字节，往返时问为1 0 0 m s ) 所示。 袭2 1r e n o t c p 吞吐量包丢失阀隔，平均拥塞密醋大l 、，包丢失率阀的关系 v t c p ：瓣吐量4 錾罴拳同雕。警姆聱囔l 簿；豢誉 一 包爱失率 ( m b p s “，一1 i = 鞘漆枣羧羚；i 攥鬟簿鹫装e 。j ， 15 58 30 0 2 1 05 5 。58 3 3 0 ，0 0 0 2 1 0 05 5 5 ，58 3 3 + 30 0 0 0 0 0 2 1 0 0 05 5 5 5 5 8 3 3 3 3 0 0 0 0 0 0 0 0 2 1 0 0 0 0 5 5 5 5 5 58 3 3 3 3 30 + 0 0 0 0 0 0 0 0 0 2 根据表2 i ，如累在l o g b p s 的在高速链路上，使用传统t c p ( r e n ot c p ) 进行通 讯，其每个包的大小为1 5 0 0 字节，往返时间r 1 t 为1 0 0 m s ，那么所需要的平均拥寒窗 日大小为8 3 3 3 3 个撤文段长发，其对应豹氇丢失率努须羝予2 一1 0 。，浚包丢失率丈大 低于目前路由水平和光纤所能达到的包丢失率。而且，网络上发丢包事件后，需要经过 | 塞塞簦塞鲞i 避圭鐾銎竺羔垒鲨苎 蔓三量坚! 茎笙 5 5 5 5 5 ，5 r t t ，电就是5 5 5 5 s 能恢复到拥塞前的释吐量。这样的恢复速度在实际使用过 程中是不可忍受的，且由于网络数据流量的突发性，要在5 5 5 5 s 内保持良好的网络状况 也是不现实的。因此，目前所采j e j 的标准t c pr e n o 无法在高速大时然环境下获得高的 吞吐量，焚主要原因在于在缀文段层，每个r t t 期耀仅增长一个数据段大小太馒了， 丽在丢失镣个缀文段拜雩倍数级瀚减小又太茯了。 基于传统t c pr e n o 在简带宽大时延环境下的局限性，s f l o y d 在2 0 0 3 年1 2 月正式 提出了h i g h s p e e d t c p 算法 2 1 ( r f c3 6 4 9 ) 。h i g h s p e e d t c p ( 下面箝称h s t c p ) 的目 的主要是通过对传统t c pr e n o 的修改，在赢带宽大融延网络环境下达列尽可能犬的吞 睦暴。 2 3 2h s t c p 的算法工作原理 h s t c p 的基本思想是在搠察避免阶段采用不阿的窗口控制机制。当拥塞窗口比较大 f 每露镔，燃t c p r e n o 糖魄，h s t c p 在磬 | 塞窑墨静臻女n 主委蘧逐速，蠢在巍口憝减少二蔓 为缓慢，并最终保持一个比较大的拥塞窗口以充分利用网络的带宽。 h s t c p 与传统t c pr e n o 的i d 策略( i n e r e a s i n g d e c r e a s i n g ) 都是基于加法增加 乘法递减模型( a i m d ) ，不同的是两者在拥塞避免阶段每个r t t ( r o u n dt r i pt i m e ) 选 羽熬 d 参数不同。 表2 ，2 高速豫p 参鼗判袭 参数搿称参数禽义 a ( w ) 拥塞避免阶段的拥塞窗口递增因子 b ( w ) 检测到包丢失后的掇塞蜜口递增因子 b h i g h在商带瓷环境f 的递减系数 p h d g h表示对应于拥塞窗口w h i g h 的丢包率 w j o w 进入高遵t c p 的闽值 w h i g 舞赢带宽联器求的平均拥塞密圈 s i t s ( i )第i 令，藤环周麓翁浸瘤动阑馕 与传统的t c p 拥塞控制算法相同，h s q 、c p 的棚戆控制也是由报文段丢失事件触发。 为了方便介绍，根据拥塞事件发生的频度，h s t c p 按下面的规定被划分为若于循环周期： 定义从第( i 一1 ) 个包丢失事件丌始到第i 个包丢失事件结束的这段时间为第i 个循环 周蘩。 1 5 南京邮电大学顽土研究生学位论文 第二章t c p 算法 h s t c p 孛l 舞薅静参数翅表2 2 所示。 为了保持与传统t c p 协议的兼容性，h s t c p 根据当前拥塞窗口与高速t c p 闽值之间 的关系，选确不同的i d 策略：如果鲞前的拥塞窗口小于高速t c p 阀僮， i s t c p 采用釉 传统t c p 相劂鲍拥塞窗口i d 策赡；如果当前的拥塞窗口大于高速t c p 闽值，h s t c p 就 采用聪快捷的拥塞窗口递增策略和更缓和的拥塞窗口递减策略。由于t c p 拥寒控制工作 在自懿镑( s e l f c l o c k i n g ) 方式，每个事件( 例如发送数据包或计努超时) 郄完全内 过去决定，即系统的未来可以由过去描述。所以拥塞窗口的1 d 程度可以取决于当前的 麴塞察口徨：魏鬃 舞l 塞塞曩浆毽较大，h s t c p 塞弱= 磺热遣载较浚，递渡遗氇凳漫。投撰 上述改进原则，h s t c p 可以达别更高的平均拥滤窗口德，因此能够获得较传统t c p 更随 的吞婚量。在每个胛t 中，h s t c p 的稍塞窗酣递增因予为g ( w ) ，递减掰子为6 ( w ) 。如果 当前翔塞窟口毽为w ，经过一个r t t ，袭没有丢包的情况下，h s t c p 把捌塞密f 1 趣值增加 为w + a ( w ) w ；当按蹙到拥寒事件，例如收到3 个重艇的a c k 后，i t s t c p 将拥塞窗口的 值递减为w ( 1 一b ( w ) 。 h s t c p 在镄寓动和绷塞避免阶段麴公式撼述如下： 当每个a c