（计算机应用技术专业论文）高速网拥塞控制算法研究.pdf

摘要 随着计算机网络技术的迅速发展，出现了带宽大于1 0 g b p s 的高速网络，而且带宽 还有不断增加的趋势。一些应用如科学协作、远程诊断和实时检测利用高速网络从远 程探测器如卫星、雷达传输高带宽实时数据、图像和录像。目前，国内外对高速网络 拥塞控制的研究尚处于初始阶段，出现了一些代表性的算法，如：h s t c p 、s t c p 、b i c t c p 、c u b i ct c p 、f a s tt c p 等，这些新算法通过调整拥塞窗口的增加减少机制，大 大提高了在高速网络中的性能。其中h s t c p 算法实现简单，具有良好的可扩展性，已 经被i e t f 接纳。h s t c p 虽然在高速网络中能获取相当高的吞吐量，但是仍存在一些 严重的性能缺陷。 首先，论文在分析传统t c pr e n o 算法应用于高速网络的局限性的基础上，简要地 介绍了目前出现的几种适用于高速网络的拥塞控制算及拥塞控制算法的评价标准。通 过建立o p n e t 仿真模型，对几种常见的高速t c p 拥塞控制算法的性能进行仿真分析。 接着，论文系统地研究了h s t c p 拥塞控制算法，通过理论和仿真实验分析了 h s t c p 算法性能上的不足。当队列管理为丢尾算法时，i 玎t 小的流能获得非常大的带 宽资源，r t t 大的流只能获得相当少的网络资源，使得h s t c p 算法存在严重的i 玎t 不公平性。另外，当h s t c p 和传统t c p 共享同一瓶颈带宽且丢包率不是很大的情况 下，它会夺取本该由传统t c p 获得的网络资源，因此具有很差的t c p 友好性。 最后，论文在前面分析的基础上对现有的h s t c p 算法进行了改进，提出了 w - h s t c p 算法。该算法针对h s t c p 和t c pr e n o 共存时的友好性及l 玎t 公平性等问 题进行了改进。改进的w - h s t c p 拥塞控制算法在拥塞避免阶段增加了公平性因子， 消除了窗口增加和i 玎t 之间的比例关系来增强算法的i 玎t 公平性。通过估计当前的网 络带宽，调整w - h s t c p 和传统t c pr e n o 的转换模式，避免w h s t c p 流过多的占用 网络资源，给传统t c p 流留出更多的资源，提高算法的友好性。通过一系列仿真实验， 结果表明改进的w - h s t c p 算法具有良好的性能。 关键词：高速网络；拥塞控制；h s t c p ；公平性；t c p 友好性 a b s t r a c t t h ed e v e l o p m e n to fc o m p u t e rn e t w o r kt e c h n o l o g yl e a d st ot h ea p p e a r a n c eo fm a n y h i g hs p e e dn e t w o r k sw h i c hb a n d w i d t hl a r g e rt h a n10 g b p s t h r o u g hh i g hs p e e dn e t w o r k s a p p l i c a t i o n sl i k es c i e n t i f i cc o u a b o r a t i o n ，t e l e m e d i c i n ea n dr e a lt i m ee n v i r o n m e n tm o n i t o r i n g c a nt r a n s f e rh i g hb a n d w i d t hr e a lt i m ed a t a , i m a g e sa n dv i d e oc a p t u r e df r o mr e m o t es e n s o r s s u c ha ss a t e l l i t e sa n dr a d a r s a tp r e s e n t ，w h i l et h er e s e a r c ho fc o n g e s t i o nc o n t r o lo fh i g h s p e e dn e t w o r k si s s t i l li nt h ei n i t i a ls t a g ea th o m ea n da b r o a d ，t h e r eh a v eb e e ns o m e r e p r e s e n t a t i v eh i g hs p e e dc o n g e s t i o nc o n t r o la l g o r i t h m s ，n a m e l yh s t c p , s t c p , b i ct c p , c u b i ct c p , f a s tt c pe t c t h e s en e wa l g o r i t h m sg r e a t l yi n c r e a s et h ep e r f o r m a n c eo fh i g h s p e e dn e t w o r k sb ya d j u s t i n gt h ei n c r e a s ea n dd e c r e a s em e c h a n i s mo fc o n g e s t i o nw i n d o w f o rt h es 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 fh s t c ei ti sa c c e p t e db yt h ei e t f h s t c pc a no b t a i nv e r yh i g ht h r o u g h p u ti nt h ec u r r e n th i i g hs p e e dn e t w o r k s ，b u tt h e r es t i l l s o m es e r i o u sp e r f o r m a n c ed e f i c i e n c i e s f i r s to fa l l ，o nt h eb a s i so fa n a l y z i n gt h el i m i t a t i o n so ft c pr e n oa p p l y i n gi nh i g h s p e e dn e t w o r k ，s e v e r a lc o n g e s t i o nc o n t r o la l g o r i t h m sw h i c ha r ec u r r e n t l yu s e di nh i g hs p e e d n e t w o r k sa n dt h ee v a l u a t i o nc r i t e r i o na r eb r i e f l yi n t r o d u c e d t h r o u g ht h ee s t a b l i s h m e n to f o p n e ts i m u l a t i o nm o d e l ，t h ee f f i c i e n c yo fs e v e r a lh i g hs p e e dt c pa l g o r i t h m si sa n a l y z e d s e c o n d l y , h s t c pc o n g e s t i o nc o n t r o la l g o r i t h mi si n v e s t i g a t e ds y s t e m a t i c a l l y , f o c u so n i t sp e r f o r m a n c e sa n di m p e r f e c t w h e nd r o pt a i lq u e u em a n a g e m e n ti sa d o p t ，t h ef l o ww i t h s m a l li 盯tc a no b t a i nv e r yl a r g eb a n d w i d t hr e s o u r c ea n dc o n v e r s e l yt h ef l o ww i t hl a r g ei 订t c a no b t a i nv e r yl i t t l en e t w o r k sr e s o u r c e s oh s t c pa l g o r i t h mi sl a c ko fr t tf a i r n e s s w h e n t h es a m eb a n d w i d t hi ss h a r e db yh s t c pa n dt r a d i t i o n a lt c pa n dt h ep a c k e tl o s sr a t ei s s m a l l ，h s t c pw i l ls e i z el a r g en u m b e ro f b a n d w i d t h ，r e s u l t i n gi nv e r yp o o rt c p f r i e n d l i n e s s f i n a l l y , b a s e do n t h ea b o v ea n a l y s i s ，h s t c pa l g o r i t h mi si m p r o v e da n dan e w a l g o r i t h m ，w - h s t c pi sp u tf o r w a r d i nt h ee n v i r o n m e n to fh i g hs p e e dn e t w o r k s ，t h e w - h s t c pm a k e ss o m ei m p r o v e m e n ta b o u tt h ef r i e n d l i n e s sw i t hr e g u l a rt c pr e n o i t si h t f a i r n e s si sa l s oe n h a n c e d w - h s t c pe l i m i n a t e st h er e l a t i o no fp r o p o r t i o nb e t w e e nt h e i n c r e a s i n gw i n d o wa n dr t tb ya d d i n gaf a i m e s sf a c t o r b ye s t i m a t i n gt h ec u r r e n tn e t w o r k b a n d w i d t h ，t h et r a n s f e rm o d eb e t w e e nt h et r a d i t i o n a lt c pa n dw - h s t c pi sa d j u s t e d ， a v o i d i n gw - h s t c pf l o we x c e s s i v e l yo c c u p i e sn e t w o r kr e s o u r c e sa n dr e s e r v i n gm o r e r e s o u r c e st ot r a d i t i o n a lt c p , s oa st oi m p r o v et h et c pf r i e n d l i n e s s t h ep e r f o r m a n c et e s ti s c a r r i e do u t , a n dt h es i m u l a t i o nr e s u l t ss h o wt h a tt h ei m p r o v e da l g o r i t h mh a sg o o d p e r f o r m a n c e k e yw o r d s ：h i g hs p e e dn e t w o r k ；c o n g e s t i o nc o n t r o l ；h s t c p ；f a i r n e s s ；t c p f r i e n d l i n e s s 西南交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并 向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借闼。本人授 权西南交通大学可以将本论文的全部或部分内容编入有关数据库进行检索，可以采用 影印、缩印或扫描等复印手段保存和汇编本学位论文。 本学位论文属于 1 保密口，在年解密后适用本授权书； 2 不保密使用本授权书。 ( 请在以上方框内打“v ”) 学位论文作者签名： 日期： 王磊 加j 口茸6 同翻日 指导老师签名：谭扒 日期： 历1f 垮 西南交通大学硕士学位论文主要工作( 贡献) 声明 本人在学位论文中所做的主要工作或贡献如下： ( 1 ) 首先对目前适用于高速网络的几种拥塞控制算法进行了分析，然后根据拥塞控 制算法的评价标准，通过建立o p n e t 仿真模型对几种常见的拥塞控制算法的性能进行 了仿真分析。 ( 2 ) 对h s t c p 算法的原理及性能优缺点分别进行了理论和仿真分析，并针对其r t t 不公平性和t c p 非友好性这两点缺陷，提出了一种基于h s t c p 的改进算法w - h s t c p ， 通过添加公平因子减轻了i 玎t 不公平现象；通过进行带宽估计调整高速t c p 模式和传 统t c p 模式之间的转换，提高了算法的t c p 友好性。仿真分析结果表明，w - h s t c p 算法的公平性和t c p 友好性较原算法都有了一定的提高。 本人郑重声明：所呈交的学位论文，是在导师指导下独立进行研究工作所得的成 果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体己经发表或撰 写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中作了明确的说明。 本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 五磊 日期：z , , o 辱6 日硝日 1 1 研究背景及研究意义 第1 章绪论 随着i n t e r n e t 的飞速发展，i n t c r n c t 给人类社会带来了巨大的变革。如今，以互联 网为代表的信息网络已经渗透到当今社会的各个领域，逐渐成为了国家进步和社会发 展的重要支柱，它的重要性就像铁路和高速公路的蓬勃发展给工业社会带来的深远影 响一般，必将成为2 1 世纪全世界最重要的设施之一。但是，就在1 1 1 t c m e t 深刻影响人 类历史发展的同时，其自身发展也面临着许许多多的困难，其中最主要的就是日益严 重的网络拥塞【1 1 ( n e t w o r kc o n g e s t i o n ) i f i j 题。目前，i n t e r n e t 上绝大部分数据流使用的是 t c p i p ( t r a n s f e rc o n t r o lp r o t o c o l i n t e r n e tp r o t o c 0 1 ) 协议【z j 。最初的t c p 协议中只有流量 控制而没有拥塞控制，接收端利用t c p 报头将其接收能力通知给发送端，这样的拥塞 控制机制只考虑到了接收端的接收能力，并没有考虑到网络的传输能力，结果导致了 网络崩溃( c o n g e s t i o nc o l l a p s e ) 的发生。最早发现拥塞崩溃现象是在1 9 8 6 年1 0 月，美国 劳伦斯一伯克利国立实验室( l b l ) 与伯克利加州大学( u cb e r k e l e y ) 之间链路的数据吞 吐量从3 2 k b i t s 跌落到4 0 b i t s 。网络的吞吐能力降至原来的1 1 0 0 0 。此后，人们开始 在拥塞控制领域进行了大量的研究工作。 为了解决日益严重的网络拥塞问题，1 9 8 8 年，j a c o b s o n 在文献 3 】中首次提出了拥 塞避免( c o n g e s t i o na v o i d a n c e ) 和拥塞控带l j ( c o n g e s t i o nc o n t r 0 1 ) 理论，为以后进行网络拥塞 控制的深入研究奠定了基础。现在，拥塞控制已经成为了确保i n t e r n e t 鲁棒性( r o b u s t n e s s ) 的关键因素，也是各种管理控制和应用的基础。由于t c p i p 协议在i n t e m e t 上的广泛 使用，所以目前对i n t e r n e t 拥塞问题的研究主要针对于t c p i p 拥塞控制。多年实践表 明i n t e r n e t 的飞速发展也得益于t c p i p 的拥塞控制机制。t c p i p 拥塞控制算法也已经 成为保证i n t e m e t 稳定性的重要因素【4 1 。 然而，由于网络拥塞控制机制是一个比较复杂的控制系统，拥塞控制算法的分布 性、复杂性也使得算法在设计上具有较高的难度。因此，网络拥塞控制机制的研究虽 然已有很多年的历史，但是迄今为止，网络拥塞问题仍然没有一个很好的解决方案， 依旧是目前国内外网络研究领域的一个热点课题。 未来的几十年，计算、通信和存储技术将得到更加迅猛地发展，全球的网格系统 为计算和科学研究提供了足够容量和高速有效的硬件环境。因此，发展新一代网络所 面临的挑战在于现有的拥塞控制算法和资源共享算法不能扩展到新一代的超高速网络 ( 1 0 0 g b p s 及1 0 0 g b p s 以上) 中，其表现在高速网络环境下，现有的拥塞控制算法不能保 证低的包丢失率和低的时延以及时延抖动等业务服务质量需求，甚至会导致整个网络 的不稳定，显著降低网络的业务服务质量q o s ( q u a l i t y o f s e r v i c e ) 5 。因此建立系统的 拥塞控制算法理论，提出具有良好的扩展性( 任意大的网络容量和用户业务数量) 的 新算法，为网络系统性能分析提供数学模型和分析方法，为下一代高速网络拥塞控制 算法的设计和实现提供理论基础等均是亟待解决的问题。 1 2 国内外研究现状、 目前的t c p 拥塞控制算法主要包含有4 个版本：t c pt a h o e 、t c pr e n o 、t c p n e w r e n o 8 和t c ps a c k 9 , 1 0 】。t c pt a h o e 是早期的t c p 版本，它包括了3 个最基本的 拥塞控制算法“慢启动( 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 ) 。t c pr e n o 在t c pt a h o e 的基础上增加了“快速恢复( f a s t r e c o v e r y ) 算法。t c pn e w r e n o 对t c pr e n o 中的“快速恢复”算法进行了改进，它考 虑了一个发送窗口内多个数据包丢失的情况。在r e n o 版本中，发送端收到一个新的 a c k 确认后就退出“快速恢复”阶段，而在n e w r e n o 版本中，只有当所有数据包都 被确认后才退出“快速恢复”阶段。t c ps a c k 算法对数据包进行有选择的确认和重 传，避免不必要的重传，减少时延，但是s a c k 需要修改t c p 协议，提出了一种快速重 传的改进算法，可以不必等待重传超时就能够从多包丢失中恢复。文献 1 1 建议在发生 拥塞时，使用一种动态恢复机制代替快速恢复算法从丢包中恢复。一些研究人员发现， 当发送方的拥塞窗口较小时，t c p 的丢失恢复策略不能很好地工作。例如，由于发送 的数据量有限，或受到接收方通告窗口的限制等，对此，文献 1 2 提出了相应的解决方 案，指出可以在快速恢复阶段发送方接收到两个连续的重复a c k 时发送一个新的数据 包。 1 9 9 4 年，l s b r a k m o 等人提出了一种新的拥塞控制算法t c pv e g a s 1 3 , 1 4 。t c p v e g a s 通过观察t c p 连接中i 玎t 值的改变来判断网络中是否发生拥塞，从而改变拥塞 窗口的大小。如果发现i 盯t 值显著增加，就认为网络正在发生拥塞，于是开始减小拥 塞窗口；如果发现i 盯t 值变小，就认为网络拥塞正在解除，可以增加拥塞窗口。这样 一来，拥塞窗口在理想的情况下就会稳定在一个适当的值上。t c pv e g a s 的优点在于拥 塞控制机制的触发只与r t t 的改变有关，而与包的具体传输时延无关。t c pv e g a s 不 是利用丢包来判断网络的可用带宽，而是以r t t 的变化来判断，所以能更精确地预测 网络目前的可利用带宽，其效率很高。但是t c pv e g a s 之所以没有在i n t e r n c t 上广泛使 用，是因为使用t c pv e g a s 的流在竞争带宽能力方面不如未使用t c pv e g a s 的流，从 而会导致网络资源享用的不公平。 为了适应高速网络的发展，2 0 0 3 年，s f l o y d 针对传统t c p 算法在高带宽时延积 网络环境下存在的扩展性问题和响应缓慢的缺点 1 5 1 6 ，提出了h s t c p ( h i g h s p e e d t c p ) 1 7 】算法。h s t c p 修改了t c p 的响应函数，使得能够拥有很大的拥塞窗口，并提 高了效率。该协议根据丢包率的范围而使用分段函数来实现拥塞控制的目的，当拥塞 事件发生率十分低的情况下，使用修改后的协议，而当丢包率至少为1 0 - 3 时，使用传 统t c p 。h s t c p 算法解决了在高速网络中标准t c p 算法的主要性能缺陷，并且实现简 单，便于在实际网络中推广且在高速网络中具有良好的可扩展性。但是其无法满足公 平性要求，而且存在着r t t 不公平性。为了更好的适应高速网络，替代的高速网络传 输协议以简单和鲁棒的方式与标准的t c p 传输流共存， 2 0 0 3 年，t k e l l y 提出了s t c p ( s c a l a b l et c p ) t 埔】拥塞控制算法。s t c p 的基本思想 是在一个拥塞事件后，令丢包恢复时间和丢包前窗口大小无关，减少了丢包恢复时间， 包丢失后，窗口调整幅度小，仅为当前窗口的1 2 5 ，从而避免了过大的窗口震荡， 提高了网络吞吐量。通过修改t c p 的窗口增加和减少参数来调整发送窗口大小，以适 应高速网络的环境，并且能够高效的利用带宽，使系统保持稳定。但是s t c p 也存在 不同r t t 的公平性( 在面临同步丢失时是不公平的) ，其t c p 的友好性和收敛性相对较 差 1 9 2 0 】也是一个不容忽视的问题。 2 0 0 4 年，s h l o w 在t c pv e g a s 的基础上提出了f a s tt c p 2 1 】拥塞控制算法。f a s t t c p 算法以队列延时为主要拥塞信号，队列延时比丢包概率的估计更为精确。f a s t t c p 通过估计部分对当前状态与稳定状态差距的精确计算，能够使拥塞窗口快速平稳 的过渡到平稳状态。有研究表明，f a s tt c p 在吞吐量、公平性和稳定性等方面比以往 的t c p 拥塞控制算法有了很大的提高，但是其公平性不稳定，而且其吞吐量与队列缓 冲区大小的配置有关。在大的队列缓冲区时，f a s tt c p 获得较高的吞吐量。但是大的 队列缓冲势必使得路由器的造价增加。 同年，针对高速协议的高吞吐量、r t t 公平性、t c p 友好性等方面，国外学者提 出了b i ct c p 2 2 协议。b i ct c p 解决了传输流之间的i 盯t 不公平性问题。2 0 0 5 年提出 的c u b i ct c p 2 3 】是b i ct c p 协议的改进版本。它简化了b i c 的窗口控制机制，并且 提高了t c p 友好性和i 玎t 公平性，同时保持了可扩展性和稳定性。它主要的特点是具 有一个实时的拥塞窗口增加的函数，并且与i 玎t 无关。但是，b i c 和c u b i c 协议的慢 的收敛速度又导致了协议的不公平性。 近几年来，在高速网络拥塞控制的研究过程中，研究人员从最初单纯解决t c p 的 低效问题，到围绕公平性和t c p 友好性等特性开展了一系列更深入的研究。针对h s t c p 算法存在的r t t 不公平性和t c p 非友好性问题，国内外学者提出了一些改进算法。 文献 2 4 采用了b l o c k p a c i n g 机制来解决产生突发流时在拥塞点造成大量的数据 包丢失的问题。b l o c k 机制将窗口的增长部分划分为快速增长阶段和线性增长阶段，即 当h s t c p 流没有获得可用带宽时采用快速的窗口增长方式，当接近可用带宽时转换为 传统t c p 的增长方式，这样可以避免过多的包丢失，同时也提高了t c p 友好性。文献 f 2 5 提出的t c p a f r i c a 算法同样采用了双模态的窗口增长方式，该文献指出采用两种 模式相互转换的增长方式可以降低包丢失事件的发生频率，从而降低包丢失率。该机 制运用于与传统t c p 共存的混合网络中能提高传统t c p 的吞吐量，改善h s t c p 的t c p 友好性，类似的工作还有文献 2 6 。但上述方法都是根据队列时延的变化来预测网络拥 塞的。b i a z 在文献 2 7 】中指出运用往返时延的测量信息不能充分地反映路由器队列长度 的变化，不能被用来作为拥塞发生的指示。因此运用队列时延难以准确地判断窗口增 长模式的切换点，此外类似的工作还有文献 2 8 等。 虽然国内外学者针对h s t c p 算法的不足提出了一些改进，但是也都存在着一些问 题，到目前为止仍然没有一个统一的解决方案。 1 3 本文主要研究工作及内容安排 本文首先对目前几种常见的高速网络t c p 拥塞控制算法性能进行理论分析，然后 利用o p n e tm o d e l e r 建立仿真模型，对高速t c p 拥塞控制算法的性能分析结果进行仿 真验证。接下来，针对h s t c p 算法的i 玎t 不公平性和t c p 非友好性，提出了一种基 于h s t c p 的改进算法，最后通过仿真实验分析了改进算法的性能。仿真结果表明，改 进算法确实比原算法的性能有了一定的提高。 本文的组织结构安排如下： 第一章为绪论，主要介绍了研究背景与意义、国内外研究现状、以及本论文的研究 内容及组织结构。 第二章首先简要地介绍了目前适用于高速网络下的几种t c p 拥塞控制算法的工作 原理，然后对拥塞控制算法的评价标准进行说明。 第三章介绍了本文选用的仿真工具o p n e tm o d e l e r 的基本原理，比较详细地介绍 了本文所用仿真模型的建立过程，并利用所建仿真模型对前面介绍的几种高速t c p 拥 塞控制算法的性能进行仿真分析。 第四章首先详细地介绍了h s t c p 算法的原理，接着从理论上分析了该算法的优点 与不足。最后通过仿真，来验证前面理论分析结果的正确性。 第五章针对h s t c p 性能上的缺陷进行了改进，提出了一种基于h s t c p 算法的改 进算法w - h s t c p 。最后通过仿真实验对改进算法和原算法的性能进行分析，给出了实 验结果。 论文的最后为总结与展望，对全文作了总结，并提出了下一步研究工作的设想。 第2 章高速网络t c p 拥塞控制算法 在计算机业日益发展的信息时代，互联网给人类社会带来了巨大的革新。虽然传统 t c p 拥塞控制算法在低速网络中性能尚可，但是，随着高速网络的出现，网络拥塞问 题也日益严重，传统t c p 拥塞控制算法中的a i m d ( a d d i t i v ei l l c r e a s em u l t i p l i c a t i v e d e l e t e ，和式增加积式减少) 机制使得拥塞窗口增加太慢而又减少太慢，不仅会最终 导致队列溢出，还会使往返时间较长的数据流收到不公平的待遇，从而降低了网络利 用率。随着对拥塞控制算法研究地不断深入，高带宽时延乘积网络的拥塞控制研究已 经引起了越来越多国内外学者的关注。研究方法也从单纯的模拟来验证到借助多个领 域的知识，从理论和模拟上来证明新的算法在各个方面的性能，近几年来这方面做了 大量的工作，并取得了良好的开端。 2 1 传统t c p 拥塞控制算法及其缺陷 2 1 1 网络拥塞的基本概念 网络拥塞现象指的是在分组交换网络中，当需要传送的分组数目太多时，由于存储 转发节点的资源有限而导致网络传输性能下降的情况。当网络中发生拥塞时，会出现 数据丢失，时延增大，网络吞吐量下降，严重时会导致“拥塞崩溃 现象。f l o y d 总结 出拥塞崩溃主要包括以下几种情况：传统的崩溃、未传送数据包导致的崩溃、由于数 据包分段造成的崩溃、日益增长的控制信息流造成的崩溃等。一般来说，网络拥塞发 生在网络负载增加导致网络效率降低的时候。 网络产生拥塞的根本原因在于用户( 即端系统) 提供给网络的负载( 1 0 a d ) 大于网络的 资源容量和处理能力( o v e r l o a d ) ，其典型表现就是数据包时延增加，丢包概率增大，上层 应用系统性能显著下降等。网络拥塞是一种持续的网络超负荷状态。 网络出现拥塞的主要原因有以下几个方面： ( 1 ) 路由器缓存不足。当多条线路上有多个数据包到达时，并且这些数据包都需要 相同的输出线路，路由器就建立一个队列。如果路由器没有足够的缓存空间来存放这 些到达的数据包，那么数据包就会被丢弃。增加路由器缓存空间可以在一定程度上缓 解这个矛盾。但是文献 2 9 指出如果无限制地增加路由器缓存，当数据包到达队列前端 的时候就已经超时，而发送端则认为它们已经被丢弃，所有数据包都被转发给下一台 路由器，从而浪费了资源，同时加重了拥塞。 ( 2 ) 带宽容量不足。高速的数据流通过低速链路时也会产生拥塞。根据香农信息理 论，节点接收数据流的速率必须小于或等于信道容量( 即信道带宽的最大值) ，才有可 能避免拥塞。否则，接收的报文在节点的缓冲区中排队，在缓冲区占满时，报文被丢 弃，导致网络拥塞。所以，网络中的低速链路将成为带宽的瓶颈和拥塞产生的重要原 因之一。 ( 3 ) c p u 处理速度慢。如果c p u 处理能力弱，难以完成必要的维护工作( 缓冲区排 队、更新路由表等) ，处理速度跟不上高速链路，也会产生拥塞。 ( 4 ) 不合理的网络拓扑结构和路由选择，也会导致网络拥塞的发生。 要避免拥塞的发生，必须对以上几个方面综合考虑。拥塞虽然是因为网络资源不足 造成的，但是单纯的增加资源并不能避免拥塞的发生。这是因为拥塞本身就是个动态 的问题，它不能只靠静态的方案来解决。这需要协议能够在网络未出现拥塞时，避免 拥塞事件的发生，一旦网络中出现拥塞现象要尽快解决拥塞，恢复网络的正常通信。 拥塞控制的结果是在拥塞期间各数据流实现资源共享。 2 1 2 传统t c p 拥塞控制算法 1 9 8 8 年，v a nj a c o b s o n 针对t c p 在网络拥塞控制方面的缺陷，提出了“慢启动” 和“拥塞避免”这两个算法p j ，1 9 9 0 年出现的t c pr e n o 版本又在其基础上增加了“快 速重传 和“快速恢复”算法，避免了在网络拥塞不够严重时采用“慢启动”算法而 造成的过大地减小发送窗口大小的现象。目前广泛应用的t c p 拥塞控制算法主要由这 4 个核心算法组成，即t c pr e n o 算法 3 0 ”】。 下面将简要介绍这几个核心算法( 如图2 1 ( a ) 和) 所示) ： ( 1 ) 慢启动阶段：在早期，当启动一个t c p 连接时，发送端会向网络中发送大量的 数据包，这样会导致路由器缓存空间很容易被耗尽，网络发生拥塞，使得网络吞吐量 急剧下降。因为t c p 发送端无法知道当前网络资源的利用情况，所以，新建立的t c p 连接不能从一开始就发送大量的数据，只能逐步地增加每次发送的数据量，来避免上 述现象的发生。具体来说，当建立一个新的t c p 连接时，拥塞窗口( c o n g e s t i o nw i n d o w , c w n d ) 会初始化为一个数据包的大小。以后，发送端会按照c w n d 的大小发送数据，每 收到一个a c k 确认，c w n d 就会增加一个数据包的大小，这样一来，c w n d 就会随着回 路响应时间( r o u n dt r i pt i m e ，r t t ，也叫做往返时延) 呈指数增加，发送端向网络发送 的数据量将剧烈增加。这种方式虽然称为“慢肩动”，但事实上，慢启动一点也不慢， 要达到每l 玎t 发送w 个数据包所需的时间仅为r t t l o g ，w 。当网络发生拥塞时，拥 塞窗口会减半甚至会降到1 ，因此，慢启动确保了t c p 发送端的发送速率最多是链路 带宽的两倍。 ( 2 ) 拥塞避免阶段：如果t c p 发送端发现分组在传输过程中超时或收到3 个相同的 a c k 确认时，就会认定网络中发生了拥塞，( 主要是因为由传输所引起的数据包损坏 的概率很小( s s t h r e s h ，t c p 就将执行拥塞 避免算法，这时，c w n d 在每次收到一个a c k 确认时只增加1 c w n d 个数据包，这样一 来，在一个r t t 内，c w n d 将增加1 个数据包大小。所以说，在拥塞避免阶段，c w n d 是呈线性增长，而不是呈指数增长。若c w n d s s t h r e s h ，t c p 就会执行慢启动算法。 捅毒 亩日 o w n d 5 5 h t h r e s h = o n c 矿2 ( a ) 慢扁动和拥摩避免 畦同 嚣彳f 亏 ( b ，挟连点传千l j 快速恢复 图2 - it c p 拥塞控制的4 个阶段【3 司 ( 3 ) 快速重传阶段：快速重传是指当t c p 发送端收到三个相同的a c k 确认时，就 会认为有数据包丢失。然后发送端就会重传丢失的数据包，而不用等待重传定时器( r t o ) 超时，同时将s s t h r e s h 设置成当前c w n d 值的一半，并且将c w n d 减为原先的一半。 ( 4 ) 快速恢复阶段：快速恢复是基于管道模型( p i p e m o d e l ) 的数据包守恒原则 ( c o n s e r v a t i o no f p a c k e t sp r i n c i p l e ) ，即同一时刻在网络中传输的数据包的数量是恒定的， 只有当原先的旧数据包离开网络后，才能发送新的数据包进入网络。如果发送端收到 一个重复的a c k 确认，则会认为已经有一个数据包离开了网络，于是，拥塞窗口就会 增加一个数据包的大小。 2 1 3 传统t c p 拥塞控制算法性能缺陷 i n t e r n c t 的发展方向表明下一代i n t e r n e t 具有高带宽时延积特性，给现有的研究提出 了新的挑战。t c p 拥塞控制算法虽然在当前的i n t e r n e t 网络中获得了很大的成功，但是 近些年来，学者们越来越清晰地认识到传统的t c p 拥塞控制机制主要采用了慢肩动机 制和a i m d 的拥塞避免机制在高速长距离网络中的性能已经达到瓶颈【3 3 1 。经过多年研 究分析，得出了传统t c p 在高速长距离网络环境下不能达到高吞吐量主要有以下几个 方面的原因： ( 1 ) 传统的t c p 拥塞控制机制对拥塞的反应性比较差。 t c p 在高速长距离网络中对包丢失的敏感度远远高于普通的广域网或者局域网， 这主要是因为它本身的拥塞避免算法，基于a i m d 的窗口增加或减少的原则。每一个 i 玎t 内，至多增加一个数据包的大小来增加拥塞窗口( 这叫做和式增加) ，而在高速网 络中单个数据包丢失对传输过程的影响是很严重的：一个t c p 连接一旦被检测到有数 据包丢失，就立刻将它当前的拥塞窗口减少一半( 这叫做积式减少) ，这可能要花去大 量的时间才能重新恢复到原来拥塞窗口的大小。这就意味着大量的网络带宽在这一段 时间之内都是被闲置的。拥塞窗口增加过于缓慢直接导致吞吐率不高，无法充分利用 带宽。而窗口减小又显得过于剧烈，这造成了网络流量的巨大震荡，同时也会降低网 络的吞吐量。慢启动阶段也会造成t c p 在网络中的性能下降，但是相比拥塞避免阶段， 它的影响要小很多。因为通过收到三个重复的a c k 比超时更容易检测丢包。所以，t c p 连接在拥塞避免阶段要比在慢启动阶段花费更多的时间。 ( 2 ) 拥塞窗口和丢包率之间约束关系的制约。 文献 3 4 指出：根据t c p 的拥塞窗口大小w 与丢包率p 之间的约束关系， w = 1 2 2 p0 。5 3 5 3 6 ，要使拥塞窗口稳定在8 3 3 3 3 个分组大小，丢包率必须为2 1 0 - 1 0 ， 这意味着每5 1 0 9 个分组中只允许1 个分组丢失，也就是说，在将近1 7 个小时内只允 许一个丢包事件发生，即使是当前误码率最低的光通信技术也很难达到这样的要求。 ( 3 ) t c p 拥塞控制机制中的慢启动算法在高带宽情况下也能给网络传输带来一些负 面影响。 由于慢启动算法会造成拥塞窗口的过快增长，很容易使得发送端进入拥塞避免阶 段，因此，并不能真正缓解传统t c p 在高速网络中效率地下的问题。假如在链路带宽 为1 0 g b p s 的网络中只存在一个t c p 连接，当发送端通过慢启动算法使得发送端吞吐 量很快的达到1 0 g b p s 以后，在下一个l 玎t 时间，发送端的吞吐量将直接变为2 0 g b p s ， 从而导致路由器缓存空间马上耗尽，网络发生严重拥塞，会有大量分组被丢弃，并开 始进入漫长的拥塞避免阶段。在整个过程中，慢启动算法只是在一个很短的时间暂时 提高了利用率，而从较长的时间尺度上看，它不能真正解决t c p 的低效问题，而且还 容易造成网络流量的突发和较高的网络丢包率。这些问题在文献 3 7 ，3 8 1 中有提及。 ( 4 ) 传统t c p 拥塞控制算法在连续收到3 个重复a c k 后才开始重传并且减少慢启 动阈值和拥塞窗口大小。但是，在拥塞严重的情况下，第二个或者第三个重复a c k 很 可能不会到达发送端。这一方面增加了网络重传丢失数据包的时间，另一方面会造成 不必要的重传，而被迫转入不必要的慢肩动阶段，从而降低了网络吞吐量、增加了时 延、严重影响了系统的性能。 2 2 高速网络t c p 拥塞控制算法 为了更高效率地利用网络带宽，提高吞吐量，近些年来国内外学者一直都在研究适 合于高速网络的t c p 拥塞控制算法，已经研究出来的成果包括h s t c p 、s t c p 、f a s t t c p 、b i ct c p 、c u b i ct c p 等，这一节将对这些算法的原理进行介绍。 2 2 1h s t c p ( h i g hs p e e dt c p ) 2 0 0 3 年，s f l o y d 等人提出了一种基于包丢失的a i m d 窗口调整算法h s t c p ( h i g h s p e e dt c p ) 。h s t c p 虽然和传统t c pr e n o 算法的i d ( i n c r e a s i n g d e c r e a s i n g ) 策略都是 基于a i m d 模型，不同的是两者在拥塞避免阶段每个i 玎t 选用的i d 参数不同，t c p r e n o 对其拥塞窗口的调整与当前的窗口大小无关，而h s t c p 则根据当前窗口大小相 应调整其拥塞窗口。h s t c p 通过对t c pr e n o 中拥塞避免算法的增加参数和减少参数 进行了修改，从而实现了窗口的快速增长和慢速减少，使拥塞窗口保持在一个足够大 的范围，以充分利用带宽。 为了保持与传统t c p 的兼容性，h s t c p 根据当前拥塞窗口与高速t c p 阈值的关系， 采用不同的i d 策略：如果当前的拥塞窗口小于高速t c p 阈值，h s t c p 采用和传统 t c p 相同的拥塞窗口i d 策略( 此时h s t c p 算法和t c pr e n o 算法完全一致) ：如果当 前的拥塞窗口大于高速t c p 阈值，h s t c p 就采用更快捷的拥塞窗口递增策略和更缓和 的拥塞窗口递减策略。由于t c p 拥塞控制工作在自时钟( s e l f - c l o c k i n g ) 方式下，每个事 件( 比如发送数据包或计算超时) 都完全由过去决定，即系统的未来可以由过去描述。所 以拥塞窗口的i d 程度可以取决于当前的拥塞窗口值：如果拥塞窗口的值较大，h s t c p 窗口增加地就较快，递减地也更慢。所以，h s t c p 可以达到更高的拥塞窗口值，因此 能够获得较传统t c p 更高的吞吐量。 2 2 2s t c p ( s c a l a b l et c p ) 2 0 0 3 年，t k e l l y 等人提出了s t c p ( s c a l a b l et c p ) 拥塞控制算法。s t c p 是一种以稳 定性著称的面向高带宽时延乘积网络的新算法。和h s t c p 一样，s t c p 也是一种基于 包丢失的高速t c p 算法，但是它是采用m i m d ( m u l t i p l i c a t i v ei n c r e