（信号与信息处理专业论文）tcp拥塞控制算法及其性能评估.pdf

北京邮电大学硕士学位论文 t c p 拥塞控制算法及其性能评估 摘要 网络拥塞问题一直困扰着因特网，随着信息技术的发展，新的网络 应用对网络拥塞控制策略提出了更高的要求。目前，t c p 协议承载着因 特网超过7 0 的传输流量，t c p 拥塞控制算法研究对于改善网络的拥塞 问题十分重要。人们先后提出了多种卓有成效的算法，但如何全面的评 价这些算法的有效性却没有统一的标准。在这样的背景下，通过对t c p 拥塞控制算法研究，建立合理的机制完成t c p 拥塞控制算法的评估，并 针对评估过程中暴露出的问题进行研究以改善t c p 性能，是科研工作者 必须面对的问题。本文致力于t c p 拥塞控制算法及其性能评估方面的研 究。 本文在第一章首先介绍了t c p 拥塞控制算法及其性能评估的必要 性，其次，阐述了t c p 拥塞控制算法的相关基础知识，包括网络拥塞的 成因、拥塞控制算法需要解决的问题，以及t c p 拥塞控制算法的概述。 论文的第二章首先介绍了五种t c p 实现的拥塞控制机制，它们分别 为t a h o e ，r e n o ，n e w r e n o ，s a c k 和v e g a st c p ，并对这些t c p 实现 所采用的拥塞控制算法进行了详细的分析，算法包括慢启动，拥塞避免， 快速重传，快速恢复和加入了p a c k ( p a r t i a l4 c 匿) 和s a c k ( s e l e c t i v e a c k ) 的快速恢复算法。在此基础上，我们运用n s 对t a h o e ，r e n o ， n e w r e n o ，s a c k 四种以数据包丢失作为网络拥塞信号的t c p 实现进行 仿真对比，并对仿真结果进行了详尽的说明，结果证明加入了p a c k 和 s a c k 的快速恢复算法可以使t c p 更快的从网络拥塞中恢复。最后，文 章概述了其他的t c p 拥塞控制改善算法以及t c p 拥塞控制算法的发展 方向。 论文第三章对t c p 拥塞控制算法的评估进行了阐述。这一部分的内 容包括t c p 特征测度的定义与测量和t c p 拥塞控制算法性能的评估。 首先，论文对t c p 拥塞控制算法测度的制定进行了介绍，并建立了测度 与高层业务需求之间的对应关系。其次，论文对t c p 测度的具体测量方 法进行探讨，并引入了适于在流量测量设备中部署的被动式t c p 环回时 间测量算法p r e ( p a s s i v e r t t e s t i m a t e ) 。该算法通过选择轮次间隙的方 北京邮电大学硕士学位论文 摘要 法获得发送轮次的时长，进而完成t c p 环回时间的测量。再次，论文对 t c p 的拥塞控制算法的性能评估工作做了详细介绍，并且，为了在主观 评价与客观测度样值之间建立联系，论文引入了层次分析法( a h p ) 对 t c p 拥塞控制算法性能进行评估。最后，论文在n s 中加入p r e 算法进 行仿真，获得了r t t 等测度值，并运用层次分析法对t c p 拥塞控制算 法性能进行了评估。 论文的最后对t c p 拥塞控制算法及其性能评估工作做了总结，并对 将来的工作做出了展望。 关键词：网络拥塞t c p 拥塞控制算法t c p 性能评估层次分析法 北京邮电大学硕士学位论文a b s w a e t t c pc o n g e s t i o nc o n t r o la l g o r i t m a n dt h eq u a l i t ye v a l u a t i o n a b s t r a c t t h ei n t e m e th a ss u f f e r e df r o mt h el o n g - t e r mp r o b l e mo fc o n g e s t i o na t a l lt i m e s w i t ht h er a p i dd e v e l o p m e n to fi n f o r m a t i o nt e c h n o l o g y , m o r e c a r e f u l ，d e s i g n e d n e t w o r k c o n g e s t i o n c o n t r o l a l g o r i t h m i s r e q u i r e d a c c o r d i n gt ot h es t a t i s t i cc o l l e c t e di nr e c e n ty e a r s t c pc a r r i e so v e r7 0 i n t e m e tt r a f f i c s oas t u d yo ft h et 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 s n e c e s s a r yt os o l v et h ec o n g e s t i o np r o b l e mi nt h ei n t e m e t a l t h o u g hv a r i o u s s u c c e s s f u l l ya l g o r i t t m a sh a v eb e e np r e s e n t e d , b u tt h e r eh a sb e e nn os t a n d a r d t oe v a l u a t eq u a l i t yo f t h e s ea l g o r i t h m s i ti sab i gc h a l l e n g ef o rr e s e a r c h e r st o c o n s t r u c tt h et c pq u a l i t ye v a l u a t i o na r c h i t e c t u r ea n dt oi m p r o v et h et c p c o n g e s t i o nc o n t r o la l g o r i t h mb a s e do nt h ef o r m e ra n a l y s i s r e s e a r c ho nt h e 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 ma n di t sq u a l i t ye v a l u a t i o ni sd i s c u s s e di n t 1 1 i st h e s i s i nt h ef i r s tc h a p t e r , t h i st h e s i sf i r s ti n t r o d u c e st h en e c e s s i t y a n d i m p o r t a n c eo ft h en e t w o r kc o n g e s t i o nc o n t r 0 1 a n dt h e n , t h et h e s i sg i v e st h e b a s i cc o n c e p t so fn e t w o r kc o n g e s t i o n i nt h es e c o n dc h a p t e r , f i r s t l y ，t h et h e s i si n t r o d u c e sf i v et c p i m p l e m e n t a i o n s ：t a h o e ，r e n o ，n e w r e n o ，s a c k a n dv e g a st c p , a n d d i s c u s s e st h ec o n g e s t i o nc o n t r o la l g o r i t h m su s e di nt h e m t h ea l g o r i t h m sa r e s l o w s 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 , f a s tr e c o v e r y w i t hp a c ka n ds a c k s e c o n d l y , t h ep a p e ru s e ss i m u l a t i o n st oe x p l o r et h e b e n e f i t so fa d d i n gp a c k s a c ka n ds e l e c t i v er e p e a tt ot c ew ec o n c l u d e t h a ts a c ka n dn e w r e n ot c pp e r f o r mb e t t e rt h a nr e n oa n dt a h o et c p , e s p e c i a l l yw h e nm u l t i p l ep a c k e t sa r ed r o p p e df r o maw i n d o wo fd a t a l a s t l y , t h et h e s i ss u m m a r i z e so t h e rt c pc o n g e s t i o nc o n t r o la l g o r i t h m s t h et h e s i sr e s e a r c h e st h ee v a l u a t i o n so ft h et c pc o n g e s t i o nc o n t r o l 北京邮电大学硕士学位论文 a b s t r a c t a l g o r i t h mi nc h a p t e rt h r e e m e u i c so ft 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 s d e f m e di nt h eb e g i n n i n go ft h i sc h a p t e r t h e n ，t h em e t h o dt or e f i n em e t r i c s f r o mt h et r a f f i cs a m p l e si sd i s c u s s e d f u r t h e r m o r e ，ap a s s i v er o u n dt r i p t h n ee s t i m a t ea l g o r i t h m ( f r e ) i si n t r o d u c e di nt h et h e s i st om e a s u r er t to f t c ep r ea l g o r i t h mc a nm e a s u r et h el e n g t ho ft h er o u n d , w h i c h a p p r o x i m a t e l ye q u a l st or t t , a n de s t i m a t ei u ti nap a s s i v em o d e a f t e r t h a t a no v e r v i e wi sg i v e nt ot h ee v a l u a t i o n so ft h et c pc o n g e s t i o nc o n t r o l a l g o r i t h m a l s o ，t ob u i l dac o m p r e h e n s i v et c pc o n g e s t i o nc o n t r o la l g o r i t h m q u a l i t y e v a l u a t i o na r c h i t e c t u r e ，a 唧口n a l y t i ch i e r a r c h yp r o c e s s ) i s i n t r o d u c e di n t ot h ee v a l u a t i o np r o c e d u r e a n df i n a l l y , w eg i v ea l le x a m p l eo f e v a l u a t i n gt c pc o n g e s t i o nc o n t r o la l g o r i t h mw i t ha h 暖u s i n gt h ed a t ag o t f r o mt h es i m u l a t i o n t h et h e s i sg i v e st h ec o n c l u s i o na n dp r o s p e c ta tt h el a s t k e yw o r d s ：i n t e m e tc o n g e s i o nt c pc o n g e s t i o nc o n t r o la l g o r i t h m q u a l i t ye v a l u a t i o no f 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 m a h p 北京邮电大学硕士学位论文 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究成果。尽我所知， 除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的 研究成果，也不包含为获得北京邮电大学或其他教育机构的学位或证书而使用过的材料。与我 一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处， 本人签名：盈狴皇 本人承担一切相关责任。 日期：型兰：! 、! ! 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即：研 究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保留并 向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借阅；学 校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段 保存、汇编学位论文。t ( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密论文 注释：本学位论文不属于保密范围，适用本授权书。 本人签名：监叠皇日期： 导师签名： 护r 、- j - j o r 北京邮电大学硬士学位论文 第1 章绪论 1 1 t c p 拥塞控制算法研究的意义 1 1 1互联网现状 因特网最初源于美国国防部的a r p a n e t ，其最大特点是采用无连接的端到端 的包交换服务。在过去的十年中，因特网逐步发展成为互联全球的网络，它使得用 户在世界范围内进行通信成为可能。随着因特网的迅猛发展，它给人类社会带来了 巨大的变革。但就在因特网深刻影响人类历史发展进程的同时，因特网自身的发展 却面临着种种困难，其中之一就是网络拥塞。从因特网诞生起网络拥塞就与其如 影随形。虽然因特网的相关技术日渐成熟，但网络拥塞却仍未很好解决，反而随着 因特网的规模、用户和应用的急剧增加，网络拥塞问题日益突出。 据统计因特网上9 5 的数据流使用的是t c p i p 协议【2 j ，并通过传输层协议保障 通信双方数据传输的可靠性，t c p i p 传输层最主要的协议是t c p 和u d p 。t c p 是一 种通过累积确认判断报文传输成功与否，并以此为依据调整发送行为( 调节发送速 率或进行重传) ，保障通信数据完整性的协议。t c p 为通信双方提供可靠的数据连接， t c p 协议包括端到端的流量控制和错误检测机制，使它能够自动适应网上的各种变 化，保证了传输的有效性、可靠性和稳定性。u d p 贝i j 是一种简单的，不进行接收确 认和流控的协议。这两种传输协议具有不同的特性，在网络中承载不同的业务，前 者多用于数据的可靠传输，后者则主要应用于实时业务的承载。 t c p i p 传输层协议虽然可以简单高效地完成通信数据的传输，但由于端到端控 制策略自身的局限性以及i p 层路由的不确定性，无论t c p 协议还是u d p 协议，都会 给网络带来难以预期的拥塞，无法单独提供服务质量保障( q o s ) ，因而限制了新兴 业务与网络自身的发展。为了使现有网络可以提供一定程度的质量保障，业界开展 了大量研究工作，在网络的不同层面上提出了多种方案，以改善互联网的性能。 在网络层中，诸虫【i r e d ( r a n d o m e a r l y d i s c a r d ) 之类的队列管理策略被用来提高 网络利用率并降低排队迟延，w f q ( w e i g h t e df a i rq u e u i n g ) 等调度策略用于保证 数据流之间的公平性并提高链路带宽使用的效率；i s ( i n t e g r a t e ds e r v i c e s ) 和d s ( d i f f e r e n t i a t e d s e r v i c e s ) 模型提出了业务分类的概念，通过对业务区分处理，网络 可以在一定程度上满足业务对服务质量的需求。 在传输层上，基于现有的t c p 协议，人们进行了多种改进，用来缓解网络拥塞 北京邮电大学硕士学位论文 的发生或者在网络拥塞发生后，缩短网络恢复的时间，从而提高网络传输性能。在 u d p 、_ i k 务方面，为了使传输层不具备流控能力的u d p 业务适合在网络上进行传输， 一些基于端到端的流控策略应运而生，这些方案大多使用r t c p 协议的反馈信息作为 发端调整信息速率的依据。 从总体上来看，尽管网络层的解决方案能够在宏观上对于资源进行调配管理、 保障传输质量，但是受限于设备的复杂度，无法做到逐连接管理，因而无法保障端 到端的服务质量。基于终端的传输层解决方案虽然可以精细地控制每一个连接甚至 每一次会话，但是由于缺乏对网络总体状态的了解，其控制策略具有局限性和盲目 性，在较大规模的应用环境中并不能满足业务对传输质量的需求。 综上所述，因特网技术的各个研究领域虽然有了较大的发展，但是由于网络复 杂性和业务需求的多样性，目前尚没有统一的构架将各个领域的技术结合起来，在 实际网络中提供满意的服务质量保障。 1 i 2 t c p 拥塞控制算法研究与改善的必要性 从1 9 8 6 年1 0 月，因特网出现了第一次的严重“拥塞崩溃”，网络拥塞问题一直困 扰着因特网。尤其是近几年，光通信的发展大大提高了因特网的速度，但因特网的 部分子网的带宽还非常有限，中继路由器的缓存容量也十分有限，那么这个地方就 有可能成为网络瓶颈处，很容易因为缓存容量的不足而导致数据包的丢失，从而产 生网络拥塞。网络拥塞会导致网络吞吐量的急剧下降，从而影响整个网络的性能。 随着信息传送量的逐渐增大和网络组成的日益复杂，网络发生拥塞的可能性也 越来越大，网络拥塞问题正逐渐成为影响网络性能的重要因素之一，如果不对网络 拥塞进行有效的控制和在网络发生拥塞时使网络能即使恢复到正常状态，就会造成 严重的网络拥塞。网络发生拥塞时，大量用户数据得不到出来，甚至出现丢失，网 络的吞吐量下降，用户信息传送的对延加长，甚至导致网络崩溃。因此，网络拥塞 的避免和控制成为越来越重要和急待解决的问题，其相应的拥塞避免及控制算法的 研究与改进也变得更加重要和急迫。 因特网的拥塞问题的研究主要集中于t c p r p 拥塞控制，因为在因特网中，拥塞 控制的大部分工作是由t c p 来完成的。拥塞发生的主要原因在于网络能够提供的资 源不足以满足用户的需求，这些资源包括缓存空间、链路带宽容量和中间节点的处 理能力。因特网“尽力而为”的服务在网络资源不足时不能限制用户数量，而只能 靠降低服务质量来继续为用户服务，并且早期的t c p 协议也只有基于窗口的流控制 机制而没有拥塞控制机制，因而很容易导致网络拥塞。 北京邮电大学硕士学位论文 目前，标准的t c p 协议实现都包含了一些避免和控制网络拥塞的算法。可以说， 今天因特网的成功很大程度上得益于t c p 拥塞控制算法的引进，但是，现有的标准 的拥塞控制算法都存在一定的局限性。特别是在网络环境日益变化的今天，网络的 发展要求不再仅仅是规模的扩大，更重要的是如何在现有的网络中增加更多的增值 业务，同时对这些业务提供必要的q o s 保障，而其中的关键是进行拥塞控制。在大 量的数据报文传送时如何提高网络的传输速率，在网络拥塞时如何有效利用网络带 宽，这些都是拥塞控制机制应该解决的问题。实践表明因特网的飞速发展也得益于 t c p i p 的拥塞控制机制。t c p i p 中使用的拥塞控制算法已经成为保证因特网稳定性 的重要因素【3 1 。因此，对t c p 拥塞控制算法进行进一步的研究具有重要的理论和应 用价值。 1 2网络拥塞的基本概念 1 2 1拥塞的基本概念 拥塞崩溃最先在1 9 8 0 年中叶提出 4 ，当网络中存的数据包超过了网络的处理能 力时，会使得网络的性能下降，这种现象称为拥塞。在网络发生拥塞时，会导致吞 吐量减小，如果用户仍不断的提出对网络资源的需求，更增加了网络的负担，严重 时会发生“拥塞崩溃”( c o n g e s t i o nc o l l a p s e ) 现象，这主要是由于t c p 不必要地重传 那些正在传送或己经被接收方接收了的数据包。 删 型 雌 图i - i 网络吞吐量和响应时间与网络负载的关系 我们可以进一步用图1 1 来描述拥塞现象。当网络负载较小时，吞吐量基本上随 着负载的增长而增长，呈线性关系，响应时间增长缓慢。当负载达到网络容量时， 北京船电大学硕士学位论文 吞吐量呈现出缓慢增长，而响应时间急剧增加，这点称为k n e e 。如果负载继续增 加，路由器开始丢包，当负载超过一定量时，吞吐量开始急剧下降，这一点称为c l i f f 拥塞控制机制实际上包含拥塞避免( c o n g e s f i o na v o i d a n c e ) 和拥塞控制( c o n g e s t i d h c o n t r o d 两种策略。前者的目的是使网络运行在k n e e 附近，避免拥塞的发生；而后 者则是使得网络运行在c l i f r 的左侧区域。前者是一种“预防”措施，维持网络的高 吞吐量、低延迟状态，避免进入拥塞；后者是一种“漩复”措施，使网络从拥塞中 恢复过来，进入正常的运行状态。 1 2 2拥塞产生的原因 拥塞产生的直接原因有以下3 点1 5 1 ： 存储空间不足。几个输入数据流共同需要同一个输出端i s i ，在这个端口就会建 立排队。如果没有足够的存储空间存储，数据包就会丢弃。对突发数据流更是如此。 增加存储空间在某种程度上可以缓解这一矛盾，但如果路由器有无限存储量时，拥 塞只会变得更坏，而不是更好，因为在网络里数据包经过长时间排队完成转发时， 它们早己超时，源端认为它们己经被丢弃，而这些数据包还会继续向下一路由器转 发，从而浪费网络资源，加重网络拥塞。 带宽容量不足。低速链路对高速数据流的输入也会产生拥塞。根据仙农信息理 论，任何信道带宽最大值即信道容i c = b l 0 9 2 ( 1 十s i n ) 斟为信道白噪声的平均功率， s 为信源的平均功率，b 为信道带宽) 。所有信源发送的速率r 必须小于或等于信道容 量c 。如果r c ，则在理论上无差错传输就是不可能的，所以在网络低速链路处就会 形成带宽瓶颈，当其满足不了通过它的所有源端带宽要求时，网络就会发生拥塞。 处理器处理能力弱、速度慢也能引起拥塞。如果路由器的c p u 在执行排队缓存， 更新路由表等功能时，处理速度跟不上高速链路，也会产生拥塞。同样，低速链路 对商速c p u 也会产生拥塞。 要避免拥塞的发生，对以上3 点原因需综合考虑。例如，提高链路速率而不改变 处理器，只会转移网络瓶颈，而不能避免拥塞。所以拥塞往往也是系统各部分不匹 配的结果。拥塞一旦发生往往会形成一个不断加重的过程。如果路由器没有空余的 缓存，它就必须丢弃新到的数据包。当数据包丢弃时，源端会超时，重传该包。由 于没有得到确认，源端只能保留数据包，结果缓存会进一步消耗，加重拥塞。目前 在因特网( i p v 4 ) _ e 实际使用的拥塞控制基本上是建立在t c p 的窗口控制基础之上的。 4 北京邮电大学硕士学位论文 1 2 3 t c p 拥塞控制需要解决的主要问题 要改善t c p 传输的稳定性，减少拥塞的发生，或者要与非标准t c p 应用在同一 网络中共存需要采取一定的拥塞控制机制，拥塞控制机制需要解决的主要问题有： 第一、满足低的报文丢弃率的要求，提高带宽利用率。 第二、高t c p 传输的稳定性，减少网络状态的振荡。 第三、保证t c p 公平，l i 【i t c p 友好特性。 1 3t c p 拥塞控制算法研究背景知识介绍 1 3 1t c p 协议简介 t c p ( t r a n s m i s s i o nc o n t r o lp r o t o c 0 1 ) 协议是完成端到端信息传输的传输层协议， 是t c p i p 家族的重要成员。t c p 协议主要由差错控制机制和拥塞控制机制组成，它 能够自动适应网络状况的变化。 t c p 协议引入差错控制机制的目的是保障端到端传输的可靠性，为无连接的i p 网络提供基于连接的传输服务。事实上，口网络本身不能保证将数据报文无损地传 输到信宿，网络中的误码和拥塞都会导致报文在传输过程中被丢弃。为了解决这一 问题，t c p 协议通过累积确认( c u m u l a t i v e a c k n o w l e d g e m e n t ) 的方式对于报文接收 情况进行监督：t c p 的发送端采用报文序列号( s e q u e n c en u m b e r ) 对发送的报文进 行标识，接收端采用发送确认序列号( a c k n o w l e d g e m e n tn u m b e r ) 对于接收到的报 文进行确认( 此报文被称为应答报文，以下简称a c k 报文) ；如果某一个t c p 报文在 规定时间内未被接收方确认则说明此报文在传输过程中丢失；t c p 发端一旦认定某 报文已经丢失就会尝试重传该报文，直到此报文正确地传输到接收端为止。 t c p 拥塞控制机制的意义更为重大，它可以根据网络状况对发送速率迸行调节， 避免拥塞的扩大，这使得互联网络的正常运行成为可能。早期的t c p 协议缺少必要 的拥塞控制机制，因而由过量数据引发的拥塞极容易导致整个网络的瘫痪。为了解 决这一问题，科研工作者进行了不懈的努力：1 9 8 8 年j a c o b s o n 针对t c p 在控制网络拥 塞方面的不足，提出了慢启动( s l o ws t a r t ) 和拥塞避免( c o n g e s t i o n a v o i d a n c e ) 算 法：1 9 9 0 年出现的r e n ot c p 版本则增加了快速重传( f a s tr e t r a n s m i t ) 和快速恢复 ( f a s tr e c o v e r y ) 以提高t c p 传输的顽健性；n e w r e n ot c p 增加了恢复应答( r e c o v e r y a c k ) 以提高t c p 带宽恢复能力等等。经过十余年的发展，t c p 拥塞控制算法已经 拥有了多个改进版本，t c p 协议的传输性能也因此得到了不断的提高。 北京邮电大学硕士学位论文 由于t c p 和i p 报头相加后的总长度大于4 0 字节，为了提高传输效率，t c p 终端 把待发送数据收集至缓冲区中，使之汇聚成较大的片断( s e g m e n t ) ，然后逐片断进 行发送。这样，实际当中t c p 连接所传输的报文长度往往是相等的，其长度被称为 最大报文发送长度( s e n d e rm a x i m u ms e g m e n ts i z e ) 。当然，t c p 发端的缓冲处理在 提高传输效率的同时也会引入附加时延，这对于某些对传输时延敏感的数据业务来 讲是不可接受的。为了解决这一问题，t c p 协议添加了p u s h 操作，该操作会强制 t c p 终端在缓冲区未满的情况下直接发送报文，从而提高了t c p 协议的实时性能。 1 3 2 t c p 拥星控制算法概述 t c p 协议所采用的拥塞控制算法本质上是一种窗口上限可变的滑窗 ( s l i d i n g - w i n d o w ) 式流量控制方法，是对滑窗流控算法的继承和发展。 传统的滑窗式流控算法的窗口上限是固定的，发端每发送一个报文其发送窗口 减小一个单位，而每接收到一个报文的确认发送窗口增加一个单位，这样终端一个 轮次中能够发送报文的最大个数是确定的，因此，在链路带宽充足的情况下，发端 的传输能力将受到发送窗口上限的限制。t c p 流控算法对滑窗算法进行扩展，根据 网络状况对窗口上限进行调节。在t c p 算法中，窗口上限由发送端的发送窗口和接 收端的广播窗口共同决定( 取两者中的最小值) 。这样，在网络正常工作时，t c p 发端可以通过增大窗口上限尽可能多地占用网络空闲带宽；而当网络发生拥塞时， t c p 发端可以通过减小发送窗口上限的方式降低发送速率从而起到缓解拥塞的作 用。 t c p 协议采用滑动窗口( 单位为字节) 对于流量进行控制。由于滑动窗口大小 的设定与网络传输情况和接收端缓冲区的大小有关，因此t c p 拥塞控制算法的特点 就在于滑动窗口上限的设定方式和修正策略。不同版本的t c p 拥塞算法具有不同的 窗1 ：3 调整策略，但绝大多数版本的t c p 算法都采用了加增长乘减d a i m d ( a d d i t i v e n e r e o s em u l n p l i c a t i v ed e c r e a s e ) 的思想对窗口进行调整。一般来说，t c p 算法在通 信建立之初采用倍增发送窗口的方式迅速占用空闲带宽，这一过程被称为“慢启动” 阶段；在慢启动完成后，t c p 算法通过线性增加发送窗1 2 1 的方式( 加增长) 在充分 利用带宽的同时避免拥塞发生，此阶段被称为“拥塞避免”；当网络拥塞引起报文丢 失时，t c p 终端将把发送窗口减半( 乘减小) ，并重传被网络丢弃的报文，这被称为 “恢复”阶段。第二章将对被广泛应用的几种t c p 拥塞控制算法和t c p 的实现 ( i m p l e m e n t a t i o n ) 进行详细的介绍。 北京邮电大学硕士学位论文 第2 章t c p 的拥塞控制 2 1 t o p 拥塞控制算法介绍 t c p 协议经过多年的发展，有了多种具体的实现。其中包括t a h o et c p , r e n ot c p , n e w r e n ot c p , s a c kt c p 和v e g a st c p 。运行在主机中的这些实现使得t c p 连接在 网络发生拥塞时回退，并对网络中的拥塞信号进行响应，正是这些改进的t c p 实现 的拥塞避免和拥塞控制的算法防止了今天网络的拥塞崩溃。下面详细介绍这些t c p 实现以及运用于这些实现中的拥塞避免和拥塞控制算法。 2 1 1 t a h o e t c p t a h o et c p 的主要内容包括：引入了指数阶回退( e x p o n e n t i a lb a c k o f f ) 的传输 超时时长估计方法：规范了慢启动( s l o w s t a r t ) 和拥塞避免( c o n g e s t i o n a v o i d a n c e ) 算法；提出了快速重传( f a s t r e t r a n s m i s s i o n ) 机制以有效地检测报文丢失并合理地 调整拥塞窗口。 指数阶回退的重传超时时长估计( e x p o n e n t i a lr e t r a n s m i tt i m e r b a c k o f f ) 对重传超时时长( r t o - r e t r a n s m i s s i o nl i m eo u t ) 的有效估计可以使t c p 终端在 及时发现报文丢失的同时减少超时误判的发生。一般来说，t c p 发端在发出数据报 文后会启动一个计时时长为r t o 的定时器，若在定时器超时后仍没有接收蛩j a c k 报 文，则触发超时事件：t c p 发端认为报文在传输过程中被丢弃，需要对其进行重新 传输。 t a h o et c p 中引入了基于指数避退的超时时长估计方法：有别于r f c 7 9 3 ，t a h o e t c p 采用( 2 1 ) 和( 2 2 ) 对环回时间r t t 的统计特性进行估计，并根据( 2 3 ) 计算r t o 。这里r i t z 是环回时间的估计值，玎是环回时间的标准偏差( s t a n d a r d d e v i a t i o n ) 。 1 r 珥卜音尽珥+ 言r t t u ( 2 - - 1 ) 卜昙+ 丢( 忸砜一r 珥i - 。) r t o = 卢( 月暖+ 4 咏。) ( 2 - 2 ) ( 2 3 ) 需要说明的是式( 2 - - 3 ) 中的因子鼻并非常量，它根据通信的实际情况变化。 我们知道，在t c p 传输过程中，接连发生的传输超时事件说明网络拥塞严重。为了 缓解拥塞，t a h o et c p 终端在连续的超时发生时，将芦值加倍( 即将r t o 倍增) ， 北京邮电大学硕士学位论文 直到卢达到6 4 ；一旦t c p 发端接收到a c k 报文，则说明网络拥塞情况缓解，此时 p 被设置为l 恢复到拥塞发生之前的水平。 慢启动( 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 ) t a h o et c p 加入慢启动算法以使t c p 终端在通信发起之初迅速占有带宽；在t c p 占有一定带宽后，采用“拥塞避免”算法对于t c p 流量进行进一步的控制以避免拥 塞的发生。 慢启动算法是指发端每接收到一个a c k 报文，就将拥塞窗口增大最大报文发送 长度( s m s s ) 字节的行为。在不发生报文丢失且实际发送窗口不受广播窗口抑止的 情况下，每经历一个发送轮次发端的拥塞窗口就增加一倍，也就是说t c p 终端的发 送速率增加一倍。这样慢启动阶段t c p 的发送速率将以指数速度增长，可以有效的 占用网络的空闲带宽。 拥塞避免算法的窗口控制策略是：每经历一个发送轮次，发端将拥塞窗口增大 一个最大报文发送长度( 鼬z 婚) 。在这种情况下，t c p 发端的拥塞窗口将呈线性增 长。这种增长方式在有效利用带宽资源的同时可以降低t c p 终端发送数据对网络的 冲击。 最后说明慢启动算法与拥塞避免算法的切换问题。t a h o et c p 算法为此规定了慢 启动门限( s l o ws t a r tt h r e s h o l d ) 。t c p 发端在拥塞窗口小于慢启动门限时采用慢启 动算法调整拥塞窗口，当拥塞窗口大于慢启动门限时则使用拥塞避免算法调整拥塞 窗口。此外，t a h o e t c p 对于慢启动门限也进行调整，在t c p 通信之初，慢启动门限 被设置成为一个较大的数值以保障此时发端处于慢启动状态；一旦出现报文丢失， 慢启动门限将被设置成为报文丢失前拥塞窗口的一半，这样当t c p 的拥塞窗口再次 恢复并且超过慢启动门限时，t c p 终端将进入拥塞避免阶段。 快速重传( f a s tr e t r a n s m i s s i o n ) 首先介绍重复应答报文( d u p l i c a t e d a c k ) 的概念。如果t c p 发端接收到的某个 应答报文a c k l 中所包含的确认序列号( 且) 与此前接收到应答报文包含的确认序 列号相同，则此应答报文a c k l 是一个重复应答报文d u pa c k 。根据t c p 协议的工 作方式我们知道，当接收到报文的序列号( s ，) 大于收方所期待的序列号时，t c p 收端会向发端返回d u p a c k 报文。 、 进一步分析可知，导致d u p a c k 产生的原因有两个：其一是网络传输路径的不 同导致了报文接收乱序，发端后发送出的报文先到达了接收方( 如i p 网络的路由切 换或者负载均衡会导致报文接收乱序) ；其二是接收方期待的报文在网络传输过程中 被丢弃。因此，如果发端能够从接收到的d u p a c k 中分析出其产生原因，就可以判 北京邮屯大学硕士学位论文 断出已经发送的报文是否在传输过程中被丢弃。 t a h o et c p 规定，如果发端连续接收到一定数量的d u p a c k ( 通常为3 个) 则认 为有报文在传输中被丢弃。此时t c p 终端可以不等待传输超时计时器超时就重传 d u p a c k 所确认报文的下一个报文1 。在t a h o et c p 终端通过快速重传发现报文丢失 并重传丢失报文后，t c p 终端将慢启动门限设置为当前拥塞窗口的一半，并将拥塞 窗口减小到初始窗口c w ) 大小。 快速重传算法大大加快了t c p 终端检测报文丢失的速度，由于它具有简便有 效的特点，因此被广泛应用到以后的各个改进的t c p 算法中2 。 2 1 2r e n dt c p 由于t a h o et c p 算法在重传丢失报文后要将拥塞窗口重新设置为初始窗口大小， 这样，t c p 发端需要若干轮次才能恢复到报文丢失前的发送速率。这种特性造成网 络发生拥塞后多个t c p 之间出现“呼吸”效应，而这一过程中网络资源无法被充分 利用。为了提高拥塞发生后t c p 算法的吞吐量，j a c o b s o n 等人在t a h o et c p 算法的基 础上加入了快速恢复( f a s tr e c o v e r y ) 形成了r e n ot c p 算法。快速恢复算法的目的 是在快速重传之后提高t c p 算法的吞吐量。 快速恢复( f a s tr e c o v e r y ) 快速恢复算法的描述如下： 1 首先定义名词“恢复阶段”：我们把从快速重传算法发现丢失报文到重 传报文的a c k 报文返回发端的对段称为恢复阶段。 2 r e n ot c p 终端在发现报文丢失并重传报文之后，依据式( 2 4 ) 设置慢启 动门限，其中n r z o 氏表由t c p 终端发出的未被确认的数据报文所包含的净荷长度 ( o nf l i g h t ) 3 ，t h s s 为慢启动门限。 = m a x r “，2 s m s s 、 7 ( 2 4 ) 3 快速恢复算法在系统进入恢复阶段时，将拥塞窗口设置为慢启动门限 t h s s j ? t l 上3 倍的s m s s ，并在整个恢复阶段内每接收到一个重复确认d u pa c k 就 。“下一个报文”的详细解释，若报文b 为报文a 的下一个报文，则有跚= s n a + l e n a 其中巩代袭a 报 文中净荷的长度( 单位为字节) 。 2 并非所有的t c p 拥塞控制算法都必须使用基于d u p a c k 的快速重传算法发现报文丢失某些改进算法( 诸如 f a c k ) 可以通过分析已经接收到的a c k 报文的确认序列号之间的关系来发现报文丢失。 3 此名词在r f c 2 8 5 1 中被称为o nf 1 i o a t 。计算该长度其目的是为了衡量在网络发生拥塞时估计t c p 终端注入网 络的数据量。t c p 拥塞控制算法依据此数据长度对的慢启动门限进行设置，以防止因网络频繁拥塞而出现严重 的呼吸效应。 北京邮屯大学碗士学位论文 将拥塞窗口增 3 n s m s s 。这样若记恢复阶段的拥塞窗c i 为盎，恢复阶段接收到 的重复应答报文个数为n d u p ，则有式( 2 - 5 ) ： 彤豢= 死l 嚣+ d s m s s ( d 口3 ) 门一钔 、-o ， 4 在接收到重传报文的应答报文之后( 第一个非d u p a c k 的应答报文) ， 快速恢复算法将拥塞窗口设置为慢启动门限的大小4 ，然后退出恢复阶段。 快速恢复算法增加了t c p 终端在发现报文丢失后的发送能力，式但- 5 ) 的设定使 得t c p 终端在恢复阶段的发送速率能够保持在原发送速率一半左右。这样在适度减 少t c p 终端发送速率的同时，快速恢复算法有效地利用了网络的带宽，从而提高了 t c p 的吞吐量。 2 i 3n e w r e n ot c p r e n ot c p 提出的快速恢复算法提高了报文丢失后t c p 的吞吐量和顽健性，但是 它仅考虑了每次拥塞发生时只丢失一个报文的情形。然而在实际网络中，一旦发生 拥塞，路由器会丢弃太量的报文( 对于采用d r o pt a i l 的路由器而言，丢弃尤为严重) ， t c p 在一次拥塞中丢失多个报文的情形非常普遍。在这种情况下，采用r e n ot c p 算 法的终端会多次将拥塞窗口和慢启动门限减半，其结果是t c p 的发送速率呈指数降 低，系统吞吐量急剧下降；更有甚者，当发送窗口小于3 时无法有效地触发快速重传， r e n ot c p 终端会陷入仅遥过传输超时来发现报文丢失的困境中。 分析r e n ot c p 性能恶化的原因后可以知道：网络在一次拥塞中丢弃了多个报 文，而这一隋况却被r e n ot c p 终端错误地分析为传输中发生了多次拥塞( r e n ot c p 在恢复阶段一旦接收到非d u pa c k 报文后即认为经历了一次拥塞) ，进而过度的窗 口减小导致了传