（计算机应用技术专业论文）网络拥塞控制技术研究及其仿真实现.pdf

哈尔滨工程大学硕士学位论文 摘要 网络拥塞控制技术已经走过了2 0 多年的发展历程。它的每一次进步 都使人们能更有效的利用网络链路的带宽。从r f c l l 2 2 到t c pt a h o e 再 到现在应用最广泛的t c pr e n o ，每次改进都带来网络性能的较大提高。 然而，网络技术的应用的日新月异使得原有的网络拥塞控制技术总会不 断出现各种各样的的问题。于是不断对网络拥塞控制技术的研究者不断 提出新的挑战。 t c pv e g a s 是继t c pr e n o 之后提出的的拥塞控制机制，很有希望代 替当今网络上应用最广泛的t c pr e n o 的拥塞控制机制。但是t c pv e g a s 在混合网络环境中的性能表现不佳使得它现在仍未能广泛地应用。本文 在不改变其原有优点的前提下，对算法进行了改进。之后，对其建立了 数学模型。分析的结果表明改进的慢启动算法能够给后一阶段的拥塞避 免阶段提供更大的初始值，从而提高拥塞避免阶段的吞吐率，而且在慢 启动阶段的吞吐率也有所提高。 然后本文通过对服务请求加以一定的控制的思想用到网络应用层协 议，改进了w e b 服务器的性能。通过对其建立数学模型后证实了改进算 法的有效性。同时，本文为超时中断率也提供了一种计算方法。 对网络协议建立数学模型的方法虽然有自身的优点，比如有一定的 预见性，但是一种通常还要用实验来验证。于是本文对n s 一2 进行了初步 的研究，并且对其中的然后重要协议进行了一些仿真实验。 关键词：t c pv e g a s ：t c pr e n o ；拥塞控制；接纳控制；n s 一2 ：t c pt a h o e r f c1 1 2 2 ；带宽 哈尔滨工程大学硕士学位论文 a b s t r a c t t h ed e v e l o p m e n to fc o n g e s t i o nc o n t r o la l g o r i t h mh a sah i s t o r yo fm o r e t h a nt w e n t yy e a r s e v e r ys t e pm a k e sp o s s i b l eh i g h e rb a n d w i d t hu t i l i z a t i o n r a t e f r o mr f c112 2t ot c pt a h o ea n dt ot h em o s tw i d e l yu s e dt c pr e n o ， e a c hm o d i f i c a t i o nh a sm a d eab i ge n h a n c e m e n ti ni t sp e r f o r m a n c e h o w e v e r ， a st h ea p p l i c a t i o nf i e l do fn e t w o r kt e c h n o l o g yb e c o m e sw i d e r ，t h ec o n g e s t i o n c o n t r o l t e c h n o l o g yh a s t o a d a p t t o i t s o ，n e t w o r ki n v e s t i g a t o r sf a c e c h a l l e n g e so f t h i sf i e l da l lt h et i m e t c p v e g a si so n eo ft h em o s tp r o m i s i n gm e c h a n i s m st h a tm a ys u b s t i t u t e t c pr e n o ，w h i c hi sm o s tw i d e l yi m p l e m e n t e di nt h ec u r r e n ti n t e r n e t ， h o w e v e r ，t h ew e a k n e s st h a tt c pv e g a ss h o w si nc o m p e t i n gw i t ht c p r e n o o v e rm i x e dn e t w o r ks c e n a r i oh a sp r e v e n t e di tf r o mb e i n gw i d e l yi m p l e m e n t e d t h ew e a k n e s so ft c pv e g a si nm i x e dn e t w o r ks c e n a r i o si sa n a l y z e d ，a n da n e ws l o ws t a r ta l g o r i t h mi s p r e s e n t e d t h ea n a l y t i cr e s u l ts h o w st h a tt h e i m p r o v e d s l o ws t a r t a l g o r i t h m c a n g e n e r a t e ab e t t e ri n i t i a lv a l u ef o r c o n g e s t i o na v o i d a n c e ，s ot h a tt h et h r o u g h p u ti si m p r o v e d t h e nt h i sp a p e rs t u d i e sa d m i s s i o nc o n t r o la l g o r i t h mi nt h ea p p l i c a t i o n l e v e l ，a n di m p r o v e st h ep e r f o r m a n c eo fw e bs e r v e lb ye s t a b l i s h i n gi t s m a t h e m a t i c a lm o d e l ，w ec o n f i r mt h ev a l i d a t i o no ft h em o d i f i c a t i o n a tt h e s a m et i m e ，t h i sp a p e rp r o v i d e saw a yt oc o m p u t et or a t e a l t h o u g ha n a l y t i c a l m o d e lh a si t so w na d v a n t a g e s - - w h e nt h e a p p l i c a t i o nb a c k g r o u n dc h a n g e s ，i te a r lf o r e s e et h ee f f e c t s s i m u l a t i o nc a n f u r t h e rt e s ti t se f f e c t s o ，w ea l s os t u d yn s - 2i n t h i sp a p e ra n dd os o m e e x p e r i m e n t sb yu s i n gi t k e y w o r d s ：t c pv e g a s ；t c pr e n o ；c o n g e s t i o nc o n t r o l ；a d m i s s i o nc o n t r o l n s 一2 ：t c pt a h o e ；r f c1 1 2 2 ；b a n d w i d t h 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下， 由作者本人独立完成的。有关观点、方法、数据和文献的引 用已在文中指出，并与参考文献相对应。除文中已注明引用 的内容外，本论文不包含任何其他个人或集体已经公开发表 的作品成果。对本文的研究做出重要贡献的个人和集体，均 已在文中以明确方式标明。本人完全意识到本声明的法律结 果由本人承担。 作者( 签字) ： 日期：瓣罗月t - - - - n 举 哈尔滨工程大学硕士学位论文 第1 章绪论 1 1 概述 近些年来，有相当多的研究都试图扩展i n t e m e t 体系结构，为即将大量 出现的实时多媒体应用提供服务质量的保证。其中一个最基本和最重要的要 求就是防止网络出现拥塞崩溃，在现有的网络体系结构中采用适当的控制机 制，使网络运行在轻度拥塞的最佳状态，同时保证一定的公平性。 最初设计的i n t e r n e t 是非面向连接的分组交换网络，所有的业务分组被 不加区分地在网络中传输，网络能给出的唯一承诺就是尽自己最大的努力传 输进入网络的每一个分组。在这种所谓的存储转发网络中，它无法给出一个 定量的性能指标比如吞吐量、端到端时延和分组丢失率等参量的界。相应的 用户也无需进行业务许可请求，因此网络的性能不仅仅是其本身可以确定的， 还受到用户施加负载的影响。很显然，这种网络体系结构缺乏一定的隔离和 保护机制，但是建立在这种体系结构之上的传统网络应用于网络协议具有较 强的灵活性和适应性。 拥塞控制本质上是一个如何共享资源的问题。在包交换网络中，所有的 激活终端共享网络资源。这些资源包括节点处理能力、缓存空间和通信链路 带宽。这三者中的任何一个都可能成为潜在的瓶颈，从而导致网络拥塞。从 用户需求的角度来说，网络必须为所有用户的请求提供服务，然而用户的需 求在传输起始时间、需求速率、持续时间上变化很大，在很多情况下还是突 发的。从网络提供资源的角度来说，任何网络物力资源都有固定的上限能力。 因此，用有限的资源去适应波动很大的用户需求，一定会出现网络资源不能 满足用户需求的时候，此时就必须使用拥塞控制来管理用户流量对瓶颈资源 的共享。 1 1 1 拥塞定义 信道带宽的需求超出可用的网络带宽资源，网络就可能出现拥塞。当短 期的分组到达率超过路由器的最大分组处理速率时，分组储存在缓存中。 哈尔滨工程大学硕士学位论文 个路由器可以维持很高的分组到达率在短时间内，具体时间多长由缓存的大 小决定。然而当缓存满时，路由器就不得不丢弃分组。于是经过这个路由器 的连接就会发生分组丢失。对于可靠数据传输，丢失分组需要重传，于是进 一步加深了网络的负载。在某些情况下，即使最初引起网络拥塞的根源被消 除，网络拥塞仍然可能由于重传而继续。 下面几个因素可以导致网络拥塞： 1 ) 远程的高速连接增加了整个网络的流量。当分组数量超过网络的承载 能力，就存储在缓存中，缓存的利用率越大，分组丢失的概率也越大。 2 ) 即使网络的平均载荷并不高，突发的网络流量仍然可能导致暂时的拥 塞。 3 ) 不利的拓扑结构以及不匹配的链路速度同样会导致拥塞，例如如果一 个很慢的路有器却连接着几个流量很大的主机到网络中去，就有可能产生拥 塞。 4 ) 一些协议并不能合适的减小发送速率即使在网络拥塞将要发生的情况 下。这样实施的网络协议对网络旋加了一个很严重的问题，随着它们被广泛 采用，i n t e m e t 网络依赖于终端结点来防止拥塞崩溃。 5 ) 如果网络的基础结构不能适应网络流量持续增长，快速增长的i n t e m e t 将成为一个问题。在过去的2 0 多年中，用户的数量以及它们连接到网络中的 速度增加了好几个数量级。同时，i n t e r n e t 的使用也随着不断增长的电子业务 ( 如e m a i l ，电子商务等) 而增长。现存的应用升级为支持更高带宽的应用 随着这些带宽的可用。新的大容量的应用也从局域网转移到了i n t e r n e t 。 拥塞存在于不同的时间规模上，从瞬间的到长期的达数月甚至数年。短 期的拥塞可能在尚未做出反应时它已经被消除。长期的拥塞通常由网络的基 础结构引起的，通常持续直道基础结构的改变。本文研究的网络拥塞侧重于 中间时间长度规模。因为极短时间规模和大时间规模的拥塞不能通过端到端 的控制来消除。 1 1 2 拥塞控制 随由于拥塞引起的路由器中的分组丢失是一个很严重的问题。提供可靠 2 哈尔滨工程大学硕士学位论文 的数据传输的传输层协议重传丢失的分组将导致额外的网络流量。让网络从 拥塞中恢复过来，并且让分组有低时延和高有效吞吐率的拥塞管理是一个很 紧迫的任务。 t c p ( t r a n s m is sio nc o n t r o lp r o t o c 0 1 ) 是i n t e r n e t 上应用最广泛的协 议，大约有9 5 的流量都是t c p 流。在最初实施t c p 时，只有非常基本的拥 塞控制机制，不足以防止中间路由的拥塞。结果，网络在8 0 年代中期经历了 好几次崩溃。其中的一次拥塞崩溃只有很少量的带宽能被利用，而大部分的 流量都是由不能到达目标而丢弃的分组组成。 j a c o b s o n 在他的一个重要的文章“”中寻找了拥塞崩溃的起因。他为t c p 提出了一个改进的拥塞控制机制。很显然，t c p 仍然被广泛使用尽管2 0 多年 过去了。而t c p 的成功主要是由于他的健壮的拥塞控制机制。当遇到拥塞时， 这个机制要求t c p 减小发送速率。 t c p 能胜任今天的大部分任务，但仍然有一些应用t c p 不能符合其要求 的。也不是所有的应用都要求可靠的数据传输的。有些应用可能使用别的机 制来从传输错误中恢复过来，例如f e c 前向纠错。另外，t c p 发送速率的减 小太快虽然对于减小拥塞很有帮助，但是有些应用可能不能应付如此迅速的 速率减少，比如视频和声音传输。 典型的，u d p 应用到t c p 不适合的业务中。u d p 提供不可靠的数据传输服 务，它不会尝试从丢失分组中恢复过来。u d p 并不会因为发生了拥塞而减小 发送速率，拥塞对于它来说完全是不可见的。在拥塞时不减小发送速率会导 致网络浪费带宽，而且对能响应拥塞的协议也是很不公平的。有些应用使用 f e c 甚至会导致冗余层级的增加，从而他们的数据丢失率很高，这更加深了 网络的拥塞。f e c 可能严重的影响别的数据流如果不与拥塞控制机制结合。 到目前为止这些还没成为一个严重的问题是因为t c p 流组成了网络的 哈尔滨工程大学硕士学位论文 9 5 的网络流量。随着网络带宽的不断增长，视频会议工具以及网络游戏的应 用也增多，这些应用将增加网络中非t c p 流量的比率因为他们通常不能使用 t c p 协议。另外的，所有多播流“1 都是基于u d p 的，没有退避机制。 所有以前提到的使用拥塞控制的原因都有利于网络，但u d p 也有自己的 优势。例如，在大规模的多人参与的网络游戏以及仿真试验中，低时延和高 响应速率对角色的真实感或者试验的真实性很重要。 1 1 3 拥塞控制协议所考虑的因素 下面的一些特点是端到端的拥塞控制协议所期望的： 1 ) 平稳性：发送速率保持相对的稳定即使网络中的噪声增加。 2 ) 兼容性：能够维持其性能在各种网络状况下，以及在各种异质网络环 境中。 3 ) 公平性：协议应该与别的流尤其别的t c p 流公平的竞争。 4 ) 快速响应：对网络状况的改变能够快速及时地做出响应。 5 ) 性能：不能因为加上了拥塞控制机制之后资源的利用率就很大程度的 变低。 并不是所有这些特点都能同时获得；稳定性和快速响应之间就要做出某 种折中。当发送速率越平稳，它对网络状况的改变响应就越迟钝。同样的折 中存在于性能和公平性中。而另一方面，公平性和好的性能应该被协议同时 获得。 有以下几种可能的拥塞控制形式。首先是发送端驱动的拥塞控制，发送 端根据网络状况随时改变它的发送速率；其二是接受端驱动的拥塞控制。它 将责任转移到了接受端。接受端根据目前的网络拥塞状况来决定参与或者退 出某次会话。第三，路由器驱动的拥塞控制，路由器通过识别那些超额占用 带宽的流量并且优先丢弃。一个好的解决方案通常考虑发送端驱动和接受端 驱动方案同时辅以路由驱动的拥塞控制。 用户的应用能够比路由器更好的调整它们的发送速率，因为路由器只能 通过丢弃分组来达到调整发送速率。而目前并没有什么激励措施来让各种应 4 哈尔滨工程大学硕士学位论文 用在拥塞时调整他们的发送速率。那些获得超额带宽的应用能得到“奖励” 一更高的吞吐率。这导致别的与之竞争的数据流吞吐率的减小，以及网络的 进一步拥塞。为了施加某种激励措施，路由器必须对不加拥塞控制的流实施 一定的惩罚措旋。 1 2 本论文研究的方法、目的和意义 1 2 1 本论文的研究方法 进行网络协议的研究有很多研究方法，包括分析建模、实验测试和网络 模拟等。它们各有其优缺点和适用范围。本文采用先建立分析模型，然后进 行网络模拟的方法来研究网络协议。 分析方法：建立分析模型对所研究的对象( 例如w e b 应用) 和所依存的 网络系统( 例如i n t e r n e t ) 进行初步分析，根据一定的限定条件和合理假设， 对研究对象和系统进行描述，抽象出研究对象的数学分析模型。通过数学推 理证明，或与现实实例对照，或与模拟的结果比较等方法，来验证模型的有 效性和精确性，对模型进行校验修正。最后利用求指后的数学分析模型对问 题进行解答。这种方法的优点是具有灵活性，不受硬件或软件性能等物质资 源的限制，但模型的有效性和精确性受假设限制很大，当一个系统很复杂时， 无法用一些限制性假设来对系统进行详细描述。这种方法适用于网络节点协 议实现理论研究、简单的网络行为分析。 模拟方法：应用网络模拟软件对所研究的对象( 例如w e b 应用) 和所依存 的网络系统( 例如i n t e r n e t ) 进行初步分析，自己开发或选用一个网络模拟工 具，设计一个实际的或理论的网络系统的模拟模型，在计算机上运行这个模 型，并分析运行的输出结果。模拟法很灵活，可以根据需要设计所需的网络 模型，以用相对很少的时间和费用了解网络在不同条件下的各种特性获取 网络研究的丰富有效的数据。缺点是受软硬件资源的限制，无法同时展现现 实网络的全部特性。模拟方法适用于网络协议研究、网络性能研究、网络设 计。 哈尔滨工程大学硕士学位论文 1 2 2 本论文研究目的和意义 本论文研究的目的一方面在于详尽介绍网络拥塞控制这一技术领域的研 究现状，介绍该领域研究的前期成果，另一方面则是试图根据拥塞控制技术 的发展轨迹，发现原有算法的弱点进行改进，提出新的拥塞控制算法。 拥塞控制算法的研究，对提高网络性能是很有实用价值的。本论文在拥 塞控制算法的研究方面，以及如何在拥塞控制算法的新的设计思想方面，作 了一些有意义的探索。结合拥塞控制发展的各个不同阶段，对拥塞控制中所 包含的各个机制的功能进行了详细的分析，这对于了解拥塞控制技术的特点 和现有技术的缺点，以提出更好的拥塞控制机制是具有实际价值和启发意义 的。 1 3 本论文的章节安排 在本论文中，我们介绍了拥塞控制技术的起源以及其二十余年的发展历 史。探讨了t c p 各个版本的演进，以及较新的版本增加的机制对较前版本的 优缺点。介绍了建立网络数学模型的基础。并给出了两种不同版本的拥塞控 制技术的性能比较和试验结果。 具体章节安排如下：第一章为绪论部分，主要介绍拥塞控制技术的起源， 以及论文研究的方法，目的和意义；第二章详细介绍了拥塞控制的发展历史 以及研究现状，概述了拥塞控制的有关理论和模型，并详细介绍了拥塞控制 的各个理论与技术细节；第三章讨论了最新版本的t c pv e g a s 的优缺点，同 时将它与最广泛应用的t c pr e n o 版本的比较，在此基础之上，改进了v e g a s 的不足之处，对其建立了数学模型，并且证实了改进方法的可行性；第四章 给出了一个拥塞控制的仿真实验，并结合实验结果阐述了各自的优缺点，同 时介绍了这个国际上广泛用到的n s 一2 仿真软件；第五章将对连接加以控制 的思想扩展到应用层，提出了一个能改善服务器性能的接纳控制构架，最后 给出了论文研究的结论。 6 哈尔滨工程大学硕士学位论文 第2 章拥塞控制概述 在i n t e r a c t 设计初期，对于拥塞的控制是通过传输控制协议( t r a n s m i s s i o n c o n t r o lp r o t o c o l ，t c p ) 中端到端基于滑窗的流量控制完成的。1 9 8 8 年v a n 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 na v o i d a n c e ) 算法， 后来被所有的i n t e m e t 主机支持 1 9 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 中资源和流量分布的不均衡都是广泛存在的，由此导 致的拥塞不能使用增加资源的方法来解决。如下图2 1 ( a ) 就是一种资源分 布严重能够不均衡的例子，而2 1 ( b ) 则是分布均衡的例子。于是拥塞控制 的发展就成为必然。 临) 图2 1 资源分配示意图 7 一 哈尔滨工程大学硕士学位论文 2 1 t o p 的演进中的几个重要论文及演进 1 ) 1 9 7 4 年，k a h n 和c e r f 的文章1 2 0 】奠定了t c p 协议的基础，正是由于 这篇文章才会有t c p f l p 协议簇，也正是这篇文章才让一个全球化的i n t e m e t 成为可能。在这篇文章中k a h n 和c e r f 发现了一个很重要的技术问题，并且 提出了设计解决这个问题的思想。这个问题就是：如何将传送不同的分组网 络连接起来，以及如何透过不同网络的边界让资源共享变得可能? a r p a n e t 解决了构建一个分组交换网络连接不同计算机和不同操作系统。但是，要连 接不同分组交换网络却会带来新的问题，包括不同的格式、分组大小、寻址 机制以及别的约定。要互联有不同分组的网络，这个问题必须解决。文章 2 0 1 正是基于如何设计一个体系来解决这个问题的，当时引起这个领域的学术界 的震惊。 2 ) 1 9 8 8 年v a nj a c o b s o n 提出了慢启动、拥塞避免和快速重传算法，t c p t a h o e 指的就是1 9 8 8 年加入v a nj a c o b s o n 提出的慢启动、拥塞避免和快速重 传算法之后的4 3 b s d 或类似的t c p 实现版本。运行在主机中的这些机制使 得t c p 连接在拥塞时回退，象我们所说的t c p 流对网络中的拥塞信号进行 响应( 例如“丢弃包”) 。正是这些t c p 避免拥塞算法防止了今天网络的拥塞 崩溃。 3 ) t c pr e n o 在t a h o e 的基础上增加了“快速恢复”。“快速恢复”使 用“管子”模型的“报文守恒”特性。发送方每收到一个重复的应答，就认 为已经有一个报文离开网络，于是将发送方的拥塞窗口加一。 4 ) t c pn e w r e n o 对r e n o 中“快速恢复”算法进行了补充。它考虑了一 个发送窗口内多个报文丢失的情况。在“快速恢复”算法中，发送方收到一 个不重复的应答后就退出“快速恢复”状态。而在n e w r e n o 中，只有当所有报 文都被应答后才退出“快速恢复”状态。 5 ) t c ps a c k 也关注一个窗口内多个报文的丢失，它使用“选择重传”策 略。 6 ) 与网络相关的重要r f c 文档做成表格2 1 如下： 8 哈尔滨工程大学硕士学位论文 表2 1 重要r f c 文档 r f c 编号主题 2 0 1 8 关于选择确认( t c ps a c k ) 1 2 3 1 2 3 0 9 早期随机探测( r e d ) 2 4 1 4 - 2 4 1 6初始窗口增加策略嘲 2 4 8 1 显示拥塞通告( e c n ) t 2 6 1 2 4 8 8t c p 用于卫星网络【2 7 】 2 5 2 5t c p 实施中的问题t 2 8 1 2 5 8 l 收录了慢启动，拥塞避免，快速重传，快速恢复等机制【2 9 j 2 5 8 2n e wr e n o 3 0 1 2 7 5 7 无线网络相关”1 i 2 7 6 0t c p 在卫星网络中应用的进一步研究口2 l 2 9 8 8 r t o 的计算m 1 2 2 拥塞控制包含的各机制详述 t c p 的发展靠的是不断改进原先的机制或者增加新的机制，下面分别对 其介绍。 2 2 1 自同步机制 自同步机制是t c p 流量控制中的一个重要机制，v a nj a c o b s o n 在1 9 8 8 年的那篇著名的论文o ”中首次阐述了t c p 流量控制的自同步机制，如图2 2 中所示。它说明了瓶颈出现在互联网某处的情况。网络配置被抽象为一个连 接源端和目的端的管道。管道的粗细与数据速率成比率。源端和目的端都处 在高容量网络上并且可能以那么高的容量收发数据。较细的中间一段管道代 表了形成瓶颈的一条低速链路。每个报文都用一个矩形表示，其中矩形的面 积与报文段中所含比特数成比例。这样，当一个报文段被挤进一条较狭窄的 管道时，它就会在时间上扩展开来。时间p b 是最慢链路上的最小报文段间隔。 当报文段到达目的端时，即使数据速率增加这个间隔也会保持不变，因为到 达间隔时间并不变化。因此，接受方的报文段间隔p r 就等于p b 。如果目的 9 哈尔滨工程大学硕士学位论文 端在报文到达时就做出确认，那么a c k 报文段离开接收方的间隔就由报文段 到达间隔决定，所以有a r = p r 。最后由于时隙p b 对报文段足够大，它对a c k 报文段肯定也足够大。所以a b = a r 。返回的a c k 就起同步信号的作用。在最 初突发后的稳定状态发送方的报文段速率就会和a c k 的到达速率相匹配。因 此，发送方的报文段速率就等于其传送路径上最慢链路的报文段的速率。 】嘲一目 源端k与目的端 二：二盛壤酽一 源端苎型驾 图2 2 t c p 流量控制自同步示意图 目的端 这样一来，t c p 就能自动感知网络瓶颈，并对其流量作出调整。这就是t c p 流量控制的自同步行为。 从上面的分析以及图2 2 中我们可以看出一个问题：源端无法知道它接 受a c k 的同步速率是反映了目的端的状况还是网络中的状况。于是，虽然t c p 滑动窗口机制是为端到端流量控制设计的，但它必须在使用中考虑到拥塞控 制的需要。 哈尔滨工程大学硕士学位论文 2 2 2a i 帖( 加性增加倍乘减小) t c p 的拥塞控制中的加性增加倍乘减小和流量控制共同构成了t c p 拥塞 控制的基础。可以说拥塞控制的拥塞避免阶段( 如图2 3 ) 就是这种思想的一 个体现。 僻 古 临 度 曹 铡 蜃 载荷 图2 3 负载吞吐量关系曲线 下面我们详细讨论a i m d 。1 思想： 假设源端f 在时刻t 的发送速率为薯( k ) ，同时，得到网络拥塞状态的反 馈信息为： m ，= 霄慧 现只考虑发送速率随时间的变化：薯o + 1 ) = x i ( t ) + f ( x j ( t ) ，y ( f ) ) ，其中， 为控制函数，可为线性与非线性。现只考虑线性的四种情况： 1 ) 倍乘增加倍乘减小m t m d ( m u l t i p l i c a t i v ei n c r e a s e m u l t i p l i c a t i v e d e c r e a s e ) 哈尔滨工程大学硕士学位论文 啪删= 肿b o x , ( o 嚣嬲裟麓 其中岛 l ，0 。，故只需 刚。于是考。且 。：或者 。，。且嚣批再噼负性，删，得 至o ：a z 0 , b i 0 ；口。o ，o 6 。 s s h r e s h 时，每个往返时间对c w n d 增加1 下面的图2 7 可以比较明显的看出这个过程。 9 哈尔滨工程大学硕士学位论文 引 超时发生点 门限缨 一 lllllillill 1 2345 r 丌( 往返时间) 图2 7 只包含慢启动和拥塞避免算法的t c p 拥塞控制执行过程 2 2 4 3 快速重传 发送t c p 实体涌来确定什么时候对一个报文段进行重传的重传定时器 ( r t o ) 通常比该报文段a c k 到达发送方所花的往返时间要长许多。原来的 r f c 7 9 3 算法和j a c o b s o n 算法都把r t o 的值设置得比估计的往返时间s r t t 要 长一些。留这个余量是完全有必要的，因为我们必须考虑到下列一些因素： 1 ) r t o 的计算基于对下一个r t t 的预测，这个预测是以过去的r t t 值为 基础的。如果网络时延发生波动，则估计的r t t 可能比实际的小。 2 ) 类似地，如果目的端引入的时延发生波动，估计的r t t 也会变得不可 靠。 3 ) 目的系统可能并不对每个报文段都发送一个a c k ，而是对多个报文段 积累发送一个a c k ，同时在它有数据要发送时就发送a c k 。这种行为可以引起 r t t 波动。 这些因素的一个结果是如果一个报文段丢失了，t c p 可能不能及时重传。 如果目的t c p 用按序接受策略，那么就会导致许多报文段的丢失。即使在更 哈尔滨工程大学硕士学位论文 可能的情况下即目的t c p 使用按窗口接受策略，不及时重传也会引起问题。 为了理解这一点，设想a 传输了一系列的报文段，而头一个报文段丢失了。 只要其发送窗口不空而且r t o 没发生超时，a 就可以继续传输而不用等待收 到确认。b 除了第一报文段意外收到了所有其他报文段。但b 必须将所有这 些到来的报文段存储起来，直到收到重传的丢失报文段为止；他不能通过将 数据给应用而清除其缓存区，直到丢失的报文段到达为止。如果对丢失报文 段的重传被耽误太久，b 将不得不开始丢弃原来的报文段。 j a c o b s o n 提出了两种规程，分别叫快速重传和快速恢复。使用这两种规 程在某些情况下可以提高重传的性能。快速重传利用t c p 中的下列规则。如 果一个t c p 实体收到一个丢失报文段，它必须立即发出一个对于最后一个收 到的按序报文段的a c k 。对于每一个道来的报文段t c p 将继续重复发送这个 a c k ，直到丢失的报文段的到达填补了它的缓存中的空隙。当空隙填充之后， t c p 就对所有迄今为止按序收到的报文段发送一个积累a c k 。当源端t c p 收到 一个重复的a c k 时，这就意味着发生下列两种情况之一： 1 ) 被确认的报文段后面的报文段被延迟了以致于它最终失序到达； 2 ) 这个报文段丢失了。 在情形1 这个报文段最后确实到达了，因此t c p 不应该重传它。但在情 形2 ，一个重复的a c k 可以看作是一个预警系统，它告诉源端t c p 一个报文 段已经丢失了而必须重传，为了确保我们遇上的是情形2 而不是情形1 ， j a c o b s o n 建议t c p 发送方要等收到同一个报文段的3 个重复a c k ( 即一共收 到同一个报文段的4 个a c k ) 。在这种情况下，随后的报文段已被丢失的可能 性就很大，因此应该被立即重传，而不是等超时才重传。 快速恢复 当t c p 实体使用快速重传冲发一个报文段时，它知道( 确切地讲是假定) 一个报文段丢失了，即使它还没有在这个报文段上发生超时。因此，t c p 实 体应该采取拥塞避免措施。一种容易想到的策略是当发生超时时所用的慢启 动拥塞避免方法。这就是说，t c p 实体可以将s s t h r e s h 设置为c w n d 2 ，设置 c w n d = 1 并开始植树规律的慢启动过程直到c w n d = s s t h r e s h 为止。然后线性 增加c w n d 。j a c o b s o n 说这种方法过于保守。多个a c k 已经返回这个事实本 身说明数据报文段正相当经常地到达对方，所以他提出了快速恢复技术：重 哈尔滨工程大学硕士学位论文 传丢失的报文段，把c w n d 减半，然后继续以线性规律增加c w n d 。这个技术 避免了最初的指数慢启动过程。 精确地，快速恢复技术可以表述如下： 1 ) 当第三个重复a c k 到达时， a 设置s s t h r e s h = c w n d 2 。 b 重传丢失的报文段。 c 设置c w n d = s s t h r e s h + 3 。 给s s t h r e s h 加3 的理由是这考虑进了已经离开网络并且对端已经缓存起 来的报文段的个数。每次有一个更多的重复a c k ( 对同一报文段所发的) 到 达时，把c w n d 加1 并在可能情况下传输一个报文段。这考虑到已经离开网络 并触发了重复a c k 的又一个报文段。 2 ) 当确认新数据的下一个a c k ( 即丢失报文段及其后报文段的积累确认) 到达时，设置c w n d = s s t h r e s h 。 2 3t c p 各个版本的概述 t c p 从开始提出实施到现在已经经历了许多个版本。学术界研究得比较 多的主要由这么几个t c p 版本：t c pt a h o e 、t c pr e n o 、t c p n e w r e n o 、t c p s a c k 以及t c pv e g a s ，下面对其进行简要的概述。 2 3 1t c pt a h o e t c p 的各种应用都包含了一系列的算法用于控制网络拥塞，同时保持一 个较好的吞吐率。早期的t c p 应用都采用g o b a c k r l 模型、累积确认以及一 个超时重传时钟来实现。这些t c p 并不能有效的减小网络拥塞。 t c pt a h o e 应用增加了一系列的新算法到早期的t c p 应用中。这些算法 包括慢启动、拥塞避免和快速重传。同时对r t t 的估计也进行了修改，所有 的这些修改都在文章o ”中描述了。有了快速重传算法后，当收到小数量的重 复a c k 时，发送端就能快速知道分组已经丢失了，然后应该重传分组，而不 是等到重传计时器的超时信息。这样就能提高信道的利用率和连接的吞吐率。 哈尔滨工程大学硕士学位论文 2 3 2t o pr e n o t c pr e n o 应用包括了t c pt a h o e 中的所有机制，同时修改了快速重传， 把快速恢复加入到了协议中。新的算法防止通信链路在快速重传后的空闲， 从而避免了在发生某个分组丢失时要重新用慢启动来增加通信链路的占有 率。快速恢复假定每收到一个重复a c k 就代表一个分组成功发送。这样， 在快速恢复时，t c p 发送端能够较为准确的估算尚未完成的数据。 在收到定数量的重复a c k 时快速恢复就启动。这个数量通常设定为3 ， 称为t c p r e x m t t h r e s h 。一旦重复a c k 达到这个数量，发送端重传一个分组， 并且将拥塞窗口减小一半。在t c pr e n o 中发送端的可用窗口为m i n ( a w i n ， c w n d + n d u p ) ，其中a w i n 是接受端通知的窗口，c w n d 是发送端的拥塞窗1 2 1 ， n d u p 保持为0 ，除非重复a c k 数量达到t c p r e x m t t h r e s h 。于是，在快速恢复 阶段发送端通过接受到的充复a c k 来加大自己的窗口。在进入快速恢复和 重传了丢失分组之后，发送端等待剩余的重复a c k 的到达，并且对每个到 达的a c k 都发送一个新的数据。在接受到一个新的发送数据的a c k 之后， 退出快速恢复阶段，并且n d u p 设置为0 。 r e n o 的快速恢复算法在单个分组丢失的情况下是最优处理。每个r e n o 发送端重传最多一个丢失的分组在每个r t t 内。它很大程度上改进了t a h o e 的行为，在一个分组丢失的情况，但是当一个窗口中有多个分组丢失的时候 性能会很大程度上的受到影响。 2 3 3n e w - r e n ot o p 虽然n e w - r e n ot c p 对t c pr e n o 仅有一个很简单的改进，但却能在性能 上得到很大的提高在某些情况。在n e w - r e n ot c p 中，如果有多个分组丢失， 它不必等待重传时钟的超时。n e w - r e n ot c p 的改进主要是在快速恢复阶段。 哈尔滨工程大学硕士学位论文 它的修改考虑的是在收到p a r t i a la c k 的情况，p a r t i a la c k 是对某些分组确 认，而不是所有分组的确认。在r e n o 中，p a r t i a la c k 让t c p 退出快速恢复 阶段通过把可用的窗口退回到拥塞窗口。在n e w - r e n ot c p 中不会出现这种 情况。当收到p a r t i a la c k 时，它认为在p a r t i a la c k 后的一个分组丢失了而 应该重传。于是，当多个分组在一个窗口丢失的情况，n e w - r e n ot c p 仍然 能够从丢失中恢复，而不是等待超时重传。 2 3 4t c ps a c k 在拥塞控制算法中实施的s a c kt c p 是对r e n ot c p 拥塞控制算法的一个 保守的扩展，因为他们可以使用相同的算法增加或者减小拥塞窗口，而只是 作很小的修改对于别的拥塞控制算法。将s a c k 加入到t c p 中并不会改变拥塞 控制算法的基础。s a c kt c p 应用保存了t a h o e 和r e n ot c p 在收到失序分组 时的健壮性的特点，并且用超时重传作为最后的选择。s a c kt c p 和r e n ot c p 的主要不同是多个分组在同一个窗口中丢失的处理上。 正如在r e n ot c p ，s a c kt c p 进入快速恢复阶段。当收到t c ”e x m t t h r e s h 个重复a c k 时，发送端重传一个分组，并且对拥塞窗口减半。在快速恢复阶 段，s a c k 维护了一个称为“p i p e ”的变量，这个变量代表了估计的在网络中 的末被处理的分组数。当估计的分组数小于拥塞窗口大小时，发送端仅发送 新的数据或者需要重发的分组，并且将p i p e 变量加1 。当发送端接受了一个 带s a c k 选项的重复a c k ，表明新分组已经被接受端接受，p i p e 变量减1 。p i p e 变量的使用将何时发送与发送哪一个分组有效解耦。发送端维护了一个特殊 的数据结构。记忆前面s a c k 的确认信息。当发送端被许可发送分组时，一次 发送丢失列表中记录的分组。如果没有这样的分组，而接受端的通报窗口又 足够的大，则发送端将发送新的数据分组。 当重传分组本身被丢弃后，s a c k 用重传超时探测丢失，再次重传后进入 “慢启动”过程。在确认了所有出现在进入“快速恢复”阶段的分组后，发 送端将从“快速恢复”阶段退出。 对于“p a r t i a la c k ”，s a c k 有特殊的处理。每收到一个“p a t t i a la c k ”， 发送端将变量p i p e 减2 ，而非减1 。在启动“快速重传”时，当认定一个分 组已经被丢失时，将变量减l ；重传一个分组时，p i p e 加1 。因此，对于第 哈尔滨工程大学硕士学位论文 一个“p a r t i a la c k ”，将p i p e 减2 似乎有些不合理，因为一个“p a r t i a la c k ” 紧紧依偎着一个分组离开了网络。对于后续的“p a r t i a la c k ”而言，重传分 组进入网络时，p i p e 增加了1 ，但丢失在网络中的分组永远触发不了p i p e 的减小过程。因此，对于每一个持续到来的“p a r t i a la c k ”，实际上意味着 两个分组以经离开了网络：即最初认定丢失的分组和重传分组。 2 3 5i c pv e g a s 在1 9 9 4 年，l - s b r a k m o 等提出了一种新的拥塞控制策略- - t c pv e g a s 。 由于r t t 值与网络运行情况有密切关系，因此，t c pv e g a s 通过观察t c p 连 接中r t t 值改变感知网络是否发生拥塞，从而控制拥塞窗口大小。如果发现 r t t 值变大，v e g a s 就认为网络正在发生拥塞，于是开始减小拥塞窗口；另一 方面，如果r t t 变小，v e g a s 就认为网络拥塞正在解除，于是再次增加拥塞 窗口。这样，拥塞窗口在理想情况下就会稳定在一个合适的值上。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 之所以未能在互联网上大规模使用，主要是因为使用t c p v e g a s 的流在带宽竞争能力方面不及未使用t c pv e g a s 的流，从而导致网络 资源享用不公平，而不是算法本身的问题。 现在详细地介绍它的主要三