（计算机应用技术专业论文）internet拥塞控制机制的研究.pdf

南京邮电大学 硕士学位论文摘要 学科、专业：工学计算机应用技术 研究方向：计算机在通信中的应用 作 者：j 翌堕级研究生 高猛 指导教师王熊莲 题目：i n t e m e t 拥塞控制机制的研究 英文题目： r e s e a r c ho ni n t e r n e tc o n g e s t i o nc o n t r o l 主题词：t c p 拥塞控制慢启动 k e y w o r d s ：t c p c o n g e s t i o nc o n t r o l c o n g e s t i o na v o i d a n c e 拥塞避免 s l o ws t a r t 南京邮电大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特另0 加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 研究生签名：垂亟垂日期：立，! 女。i ! ! ? 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留 本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其 他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一 致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权 南京邮电大学研究生部办理。 研究生签名：盘超导师签名：羔! 蔓! i 日期：。达旦壶：i ：些 南京邮电大学硕士研究生毕业论文 摘要 摘要 网络拥塞一直是长期困扰i n t e r n e t 的难题，近年来虽然人们先后提出了多种卓有成效 的算法，但网络拥塞问题仍未得到很好的解决，使得拥塞控制一直是网络研究领域的热点 之一。 本文首先分析了拥塞产生的原因以及拥塞控制的目前研究概况，并指出拥塞现象的发 生和t c p i p 网络的设计机制有着密切的联系。随后详细介绍了已有t c p 源算法和与之相 结合的i p 链路算法，并简单介绍了t c p 友好的拥塞控制。其次，本文深入分析了t c p 源 算法的各个阶段，并对各个阶段的改进进行了认真研究。最后，针对现有t c p 拥塞控制 机制的研究状况，本文对t c p 源算法中的拥塞避免阶段提出了改进，在此算法中引入一 个比例因子p ，使得传输过程尽可能保持在拥塞避免阶段，从而减少拥塞发生的次数，提 高吞吐量。为了便于性能对比评测，本文最后采用了t c p i p 研究领域的主流仿真软件n s 作为实验工具，使得实验结果更为客观、真实。 南京邮电大学硕士研究生毕业论文 a b s t r a c t a b s t r a c t t h ei n t e r n 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 ta l lt i m e s i nt h el a s t y e a r sa l t h o u g hv a r i o u ss u c c e s s f u la l g o r i t h m sh a v eb e e np r e s e n t e d ，t h ep r o b l e mo fc o n g e s t i o n s t i l lf a rf r o mb er e s o l v e d c o n g e s t i o nc o n t r o lh a sb e e nt h eh o t s p o t si nt h en e t w o r kr e s e a r c h r e a l i n f i r s t ，t h i sp a p e ra n a l y z e st h er e a s o nt h a tl e a dt oc o n g e s t i o na n dt h ec u n e n ts u r v e yo ft h e r e s e a r c ho nc o n g e s t i o nc o n t r o l ，p o i n t st h a tc o n g e s t i o ni sr e l a t i v ew i t ht h ed e s i g nm e c h a n i s mo f t c p i pn e t w o r k i tt h e ni n t r o d u c e st h ee x i s tt c ps o u r c ea l g o r i t h m ，t h ei pl i n ka l g o r i t h m a s s o c i a t e dw i t hi t ，a n dt h et c p f r i e n d l yc o n g e s t i o nc o n t r 0 1 a l s o ，t h i sp a p e ra n a l y z e st h ee v e r y p h a s eo f t h et c ps o u r c ea l g o r i t h md e e p l y , a n dd o e sc a r e f u lr e s e a r c ho nt h e s ep h a s e s i nt h ee n d ， t h ep a p e rt a k e sap r o p o s a lo nt h ec o n g e s t i o na v o i d a n c eo ft h et c ps o u r c ea l g o r i t h m i t i n t r o d u c e sap r o p o r t i o n a li t e m ( p ) i n t ot h ea l g o r i t h mo f t h i sp h a s et om a k et h et r a n s m i s s i o nb e k e p ti nt h ec o n g e s t i o na v o i d a n c ea sl i k e l ya sp o s s i b l e ，t h e r e b yr e d u c e st h et i m e st h a tc o n g e s t i o n h a p p e n sa n di m p r o v e st h et h r o u g h p u t t oc o m p a r et h ep e r f o r m a n c eo fa l g o r i t h m se a s i l y , t h e l e a d i n gt o o lo fn e t w o r ks i m u l a t i o ni nt c p i pr e s e a r c hr e a l m ，n s ，i si n t r o d u c e di nt h i sp a p e rt o m a k ee x p e r i m e n tr e s u l tm o r eo b j e c t i v ea n dt r u e 南京邮电大学硕士研究生毕业论文 第一章前言 第一章前言 近年来，网络技术的发展日新月异，网络规模迅速扩大，特别是进入九十年代后，以 i p 为基础的i n t e r n e t 呈爆炸式增长，已经逐渐发展成为全球性的信息基础设施，随着新型 网络应用的不断涌现和用户数量的迅速增加，使得i n t e r n e t 的流量急剧增长，其中除了传 统的w w w 、f t p 、t e l n e t 等数据流外，还出现了大量的实时多媒体数据流，由于网络中 不同的数据流在路由器处交汇，因而给网络的路由节点造成很大的负担，越来越严重的网 络拥塞问题逐渐暴露出来。 在网络通信中，拥塞容易造成延迟和吞吐量等q o s ( q u a l i t yo f s e r v i c e ) 性能指标下降， 是影响带宽、缓存等网络资源利用率的关键因素，因此有效解决拥塞问题对于提高网络性 能具有重要意义。网络产生拥塞的根本原因是终端提供给网络的负载大于网络资源容量和 处理能力，在i n t e r n e t 中，存储空间不足、通信信道带宽容量不足、处理机处理能力较弱 等都是产生拥塞现象的直接原因【l 】，但是无论增加缓存容量或是提高处理器及链路的速度 都不能从根本上解决问题，相反，某些情况下甚至可能会进一步加剧拥塞。网络中发生拥 塞后如果不加以控制，往往会导致恶性循环，这时如果路由器没有空余的缓存空间，它就 必须丢掉新到的数据包，当数据包丢弃时，源端可能会因为超时而重传此包，由于源端在 未收到确认之前不能丢弃数据包，相应的缓存不能释放，使缓存进一步消耗，导致拥塞加 重，在网络流量非常高的情况下，网络甚至会完全瘫痪，几乎没有数据包能够送达接收方。 网络拥塞己经成为制约网络发展和应用的一个瓶颈，如何更好地预防和控制拥塞一直是近 年来网络研究的热点问题。 拥塞控制的主要目标是控制进入网络的数据流量，保证通信予网不会被用户发送的数 据流淹没，合理地使用瓶颈资源。直观上，解决网络拥塞可以从两方面入手，一是拥塞避 免，即尽量避免拥塞的发生，使网络运行在最佳状态；二是在拥塞发生后采取补救措施消 除拥塞。完全避免网络拥塞是不可能的，因此，采用拥塞避免与拥塞控制相结合的方法更 为合理。拥塞控制策略主要由反馈机制和控制机制两个部分组成，网络通过反馈机制向源 端或目的端通告它的当前状态，端系统则根据接收到的反馈信息，利用控制机制完成对负 载的调整，从而达到消除拥塞的目的。 拥塞控制可以在网络协议的各个层次上实施。由于数据链路层靠近拥塞的发生点，所 以在数据链路层进行控制可以快速响应拥塞，但它只能对短期的拥塞现象进行控制。一般 1 南京邮电大学硕士研究生毕业论文第一章前言 来说，不同网络层次中的控制机制具有不同的目标，拥塞现象持续的时间越长，实现控制 的层次也应该越高，明确的拥塞控制主要在网络层和传输层实现。 多年来，人们已经对拥塞控制进行了大量研究，提出或改进了多种多样的拥塞控制算 法，致使现在的t c p 实现版本不少于2 0 0 多种。这一方面表明t c p 拥塞控制是网络研究 领域的一个热点问题，另一方面也说明t c p 拥塞控制仍然没有得到很好的解决。 本文在研究了t c p i p 拥塞控制各种版本以及t c p 拥塞控制的过程之后，以t c p 源算 法为基础，对拥塞控制中的拥塞避免阶段的算法进行了一些改进，该算法主要加入了一个 比例因子p ，用于减少拥塞窗口的增长速度，延缓拥塞情况的发生。最后通过网络仿真软 件n s 对新算法进行了仿真，结果表明新算法能使t c p 拥塞控制算法的性能得到明显改善。 2 南京邮电大学硕士研究生毕业论文 第二章拥寨与拥塞控制 2 1 拥塞产生的原因 第二章拥塞与拥塞控制 当网络中存在过多的数据包时，网络的性能就会下降，这种现象称为拥塞。在网络发 生拥塞时，会导致吞吐量下降，严重时会发生“拥塞崩溃”( c o n g e s t i o n c o l l a p s e ) 现象。当 网络处于拥塞崩溃状态时，微小的负载增量都会使网络的有效吞吐量( t h r o u g h p u t ) 急剧下 降。1 9 8 4 年，n a g e l 报告了由于t c p 连接中不必要的重传所诱发的拥塞崩溃。1 9 8 6 到1 9 8 7 年间，这种现象曾多次发生，严重时一度使l b l 到u c b e r k e l e y 之间的数据吞吐量从3 2 k b p s 跌落到4 0 b p s 。 幺 芒ec l醯 一一 | k 重 e 毒k ，li 驳 陟 f 一 i l o a d 图2 - t 网络负载与吞吐量及响应时间的关系 使用图2 - 1 来描述拥塞发生的情况。当负载较小时，吞吐量基本上随着负载的增长而 线性增长，而此过程中的响应时间增长缓慢。当负载达到网络容量时，吞吐量呈现出缓慢 增长，而相应时间急剧增加，这一点称为k n e e 。如果负载继续增加，则路由器开始丢包， 当负载超过一定量时，吞吐量急剧下降，而延迟急剧上升，这一点称为c l i f f 。可以看出， 负载在k n e e 附近时网络的使用效率最高。 拥塞现象的发生和t c p i p 网络的设计机制有着密切都联系。t c p i p 网络具有如下几个 特点： ( 1 ) 分组交换( p a c k e t s w i t c h e d ) 网络。与电路交换( c i r c u i t s w i t c h e d ) 相比，分组交 换通过共享提高了资源的利用效率，但这会引起分组在网络中滞留，造成分组数据可能出 现“乱序”现象，增加了端系统处理乱序分组的复杂性。 ( 2 ) 无连接( c o n n e c t i o n l e s s ) 网络。t c p i p 网络中，从网络层的角度来看，节点之间 在发送数据之前不需要建立连接。无连接模型简化了网络的设计，在网络的中间节点上不 3 如i：墨。甜瓣i尊蠡蚺掣一 南京邮电大学顶士i 跚究生毕业论义 帮二章拥采与拥采控制 2 1 拥塞产生的原因 第二章拥塞与拥塞控制 当网络中存在过多的数据包时，网络的性能就会下降，这种现象称为拥塞。在网络发 牛拥塞时，会导致吞吐量下降，严重时会发生“拥塞崩溃”( c o n g e s t i o n c o l l a p s e ) 现象。当 网络处于拥塞崩溃状态时，微小的负载增量都会使网络的有效吞吐量( t h r o u g h p u t ) 急剧下 降。1 9 8 4 年，n a g e l 报告了由于t c p 连接中不必要的重传所诱发的拥塞崩溃。1 9 8 6 到1 9 8 7 年间，这种现象曾多次发生，严重时一度使l b l 到u c b e r k e l e y 之间的数据吞吐量从3 2 k b p s 跌落到4 0 b v s 。 兰 弩 誊 霪 蠹 融- e ec ii 攫 一一 | 图2 一l 网络负载与吞吐量及响应时间的关系 使用图2 - 1 来描述拥塞发生的情况。当负载较小时，吞吐量基本上随着负载的增长而 线性增长，而此过程中的响应时间增长缓慢。当负载达到网络容量时，吞吐量呈现出缓慢 增长，而相应时间急剧增加，这一点称为k n e e 。如果负载继续增加，则路由器开始丢包， 当负载超过一定量时，吞吐量急剧下降，而延迟急剧上升，这一点称为c l i f f 。可以看出， 负载在k n e e 附近时网络的使用效率最高。 拥塞现象的发生和t c p ，i p 网络的设计机制有着密切都联系。t c p f i p 网络具有如下几个 特点： ( 1 ) 分组交换( p a c k e t s “t c h e d ) 网络。与电路交换( c i r c u i t - s w i t c h e d ) 相比，分组交 换通过共享提高了资源的利用效率，但这会引起分组在网络中滞留，造成分组数据可能出 现“乱序”现象，增加了端系统处理乱序分组的复杂性。 ( 2 ) 无连接( c o r m e c t i o n l e s s ) 网络。t c p f i p 网络中，从网络层的角度来看，节点之间 在发送数据之前不需要建立连接。无连接模型简化了网络的设计，在网络的中间节点上不 在发送数据之前不需要建立连接。无连接模型简化了网络的设计，在网络的中间节点上不 3 _。莲o*掣一 立塞业皇查堂堡主! ! ! 茎皇兰些望壅塑三皇塑垩皇塑鲞丝型 需要保存与连接到有关信息。但是无连接模型难以引入“接纳控制”( a d m i s s i o nc o n t r 0 1 ) 机制，在终端输入流量大于网络资源时，难以保证服务质量( q o s ) ；无连接也是网络中出 现分组乱序的一个主要原因。 ( 3 ) “尽力而为”的服务模型。所谓“尽力而为”的服务，是指网络不对数据传输的 服务质量提供保证。这与网络早期的应用有关，传统的网络应用主要是数据业务，它们对 网络性能( 带宽、延迟、丢失率等) 的变化不敏感，“尽力而为”服务能够满足需要。但 “尽力而为”服务不能很好地满足新出现的多媒体应用的要求，这些应用对延迟、速率等 性能的变化比较敏感。 虽然随着科技的发展，网络设备的处理速度不断加快、网络带宽持续增长，但是硬件 的建设的速度有时赶不上应用需求的增长。而且，很多时候，即使局部的网络资源很充足， 仍然会出现网络拥塞、分组数据丢失，从而导致性能下降。这是因为由于互连网络是一个 及其复杂的分散系统，网络中总是存在资源“相对”短缺的位置，成为网络性能提高的瓶 颈。 网络中有限的资源由多个用户共享使用。由于没有“接纳控制”策略，网络无法根据 资源的情况限制用户的数量；同时，互连网络是一个分散控制系统，由于缺乏中央集成控 制，网络无法控制用户使用资源的数量。目前，因特网上不断增长的用户和应用的数量， 必然会导致网络发生拥塞。但有些人可能会认为“只要增加足够多的资源，如将节点缓存 的存储空间扩大、或者将链路更换为更高速的链路、或者将结点处理机的运算速度提高， 就可以解决网络拥塞问题。”其实不然，网络拥塞是一个非常复杂的问题，简单地采用上 述做法在许多情况下非但不能解决拥塞问题，而且还可能使网络的性能更坏。例如，当某 个结点缓存的容量太小时，到达该结点的分组因无空间而暂时被丢弃。现在假设将该结点 的缓冲区容量扩展到非常大，到达该结点的分组均可以在缓冲区的队列中排队，由于输出 链路的容量和处理机的速度并未提高，队列中的分组有可能因等待时间长而导致重传，可 能还要重传多次，从而d r l , 目l 网络的负担，而且发送端在未收到确认之前必须保留所发分组 的副本以便重传，从而引起发送端缓冲区的拥塞。所以，简单地增加网络资源只会把“瓶 颈”转移到其他地方，并不能解决网络拥塞的问题。 上述问题的关键是整个系统的各部分资源不匹配。因为拥塞总是发生在网络中资源 “相对”短缺的地方，这反映了互连网络的不均衡性。这种不均衡性一方面表现在资源的 不均衡，如图2 2 ( a ) 中带宽分布不均衡：当s 以1 m b p s 的速率向d 发送数据时，在路 出器r 处会发生拥塞。另一方面是由于流量的不均衡，如图2 2 ( b ) 中带宽分布是均衡的， 但当s 1 和s 2 都以lm b p s 的速率向d l 发送数据时，在路由器r 也会发生拥塞。因特网 4 南京邮电大学硕士研究生毕业论文第二章拥塞与拥塞控制 中资源和流量分布的不均衡是广泛存在的，由此导致的拥塞不能通过增加资源的方法解 决。 ( a ) 带宽分布不均衡( b ) 流量分布不均衡 图2 - 2 网络负载与吞吐量及响应时间的关系 那么如果系统的各部分都平衡了，问题是否就能得到完全解决呢? 事实上，且不说更 换所有设备的经济可行性，网络数据传输的突发性和网络传输中许多的不确定性因素都需 要一个管理控制机制来加以约束，才有可能使网络发挥其最大功效。拥塞控制就是一个全 局性的过程，涉及到所有与网络传输性能相关的因素。“瓶颈”是永远都存在的，因此拥 塞控制必不可少。 在计算机网络中，如果网络用户提供给网络的负载大于网络资源容量和处理能力，那 么拥塞就会发生。此时会发生数据包丢失、传输延迟增大、网络吞吐量下降等现象。可以 说，在任何网络中，只要网络负载超过网络的处理能力，拥塞就会发生。i n t e m e t 也不例外， 而且作为一个复杂的互连网络，其发生网络拥塞的可能性也要比一般网络大得多。 拥塞产生的主要直接原因有如下几个方面： l 、存储空间不足。当一个端口收到几个输入端的报文时，接收的报文就会在这个端 口的缓冲区中排队。如果没有足够的存储空间存储，当缓冲区占满时，报文就会被丢弃。 适当增加存储空间可以缓解拥塞，如果过于增加存储空间，报文会因在缓冲区中排队时间 过长而超时，被源端重发，从而进一步加重了网络拥塞。 2 、带宽容量不足。根据仙龙信息理论c = b i c l 9 2 ( 1 + s n ) ( c 为信道容量) ，所以 结点接收数据流的速率必须小于或等于信道容量，否则，接收的报文在结点的缓冲区中排 队，当缓冲区占满时，报文被丢弃，导致网络拥塞。 3 、c p u 处理速度慢。如果结点的c p u 在执行缓存区排队、路由选择时，处理速度 跟不上链路速度，也会导致拥塞。同样，低速链路对高速c p u 也会产生拥塞。 4 、不合理的网络拓扑结构及路由选择也会导致网络拥塞。 既然在目前的i n t e m e t 中网络拥塞是无法避免的，那么就必须采取积极主动的策略去 堕塞塑皇查堂堡土婴塞圭兰些丝壅 笙三童塑窒兰塑墨篓型 控制和避免拥塞，把拥塞发生的可能性降至最低，即使在发生拥塞后也能及时恢复到正常 状态，同时拥塞控制也必须要保证网络效率。这也是拥塞控制研究的主要内容和目的。 2 2 拥塞控制的研究概况 拥塞控制就是指通过积极的措施来避免拥塞的发生或者在拥塞发生以后能尽快恢复 到平稳状态。拥塞控制算法实际上包含拥塞避免( c a ，c o n g e s t i o n a v o i d a n c e ) 和拥塞控制 ( c c ，c o n g e s t i o nc o n t r 0 1 ) 两种不同的机制。前者是一种“预防”措施，使网络运行在 k n e e 附近( 图2 一1 ) ，维持网络的高吞吐量、低延迟状态，避免拥塞的发生；后者是一种“恢 复”措施，保持网络运行在c l i f 的左侧区域( 图2 1 ) ，使网络从拥塞中恢复过来，进入正 常的运行状态。 从控制理论的角度，拥塞控制算法可以分为开环控制和闭环控制两大类。当流量特征 可以准确规定、性能要求可以事先获得时，适于使用开环控制；当流量特征不能准确描述 或者当系统不提供资源预留时，适于使用闭环控制。i n t e r n e t 中主要采用闭环控制方式。 闭环的拥塞控制分为以下3 个阶段：检测网络中拥塞的发生；将拥塞信息报告到拥塞 控制点；拥塞控制点根据拥塞信息进行调整以消除拥塞。闭环的拥塞控制可以动态地适应 网络的变化，但它的一个缺陷是算法性能受到反馈延迟的严重影响。当拥塞发生点和控制 点之间的延迟很大时，算法性能会严重下降。 根据算法的实现位置，可以将拥塞控制算法分为两大类：链路算法( 1 i n ka l g o r i t h m ) 和源算法( s o u r c ea l g o r i t h m ) 。链路算法在网络设备( 如路由器和交换机) 中执行，作用是 检测网络拥塞的发生，产生拥塞反馈信息。源算法在主机和网络边缘设备中执行，作用是 根据反馈信息调整发送速率。拥塞控制算法设计的关键问题是如何生成反馈信息和如何对 反馈信息进行响应。 源算法中使用最广泛的是t c p 协议中的拥塞控制算法。t c p 是目前在i n t e r n e t 中使用 最广泛的传输协议。根据m c i 的统计总字节数的9 5 和总报文数的9 0 都使用t c p 传 输协议。近年来，t c p 中采用了很多新的算法，包括慢启动( s s ，s l o ws t a r t ) 、拥塞避免 ( c a ，c o n g e s t i o n a v o i d a n c e ) 、快速重传( f r t ，f a s tr e t r a n s m i t ) 、快速恢复( f r c ，f a s t r e c o v e r y ) 、选择性应答( s a c k ) 等，大大提高了网络传输的性能。t c p 中使用的拥塞控 制算法已经成为保证i n t e m e t 稳定性的重要因素。 链路算法的研究目前集中在主动队列管理( a c t i v eq u e u em a n a g e m e n t ，简称a q m ) 算法方面。和传统的队尾丢弃( d r o pt a i l ) 相比，a q m 在网络设备的缓冲溢出之前就丢弃 6 南京邮电大学硕士研究生毕业论文 第二章拥塞与拥塞控制 或标记报文。a q m 的主要优点是： ( 1 ) 减少网关的报文丢失。使用a q m 可以保持较小的队列长度，从两增强网关容纳 突发流量的能力。 ( 2 ) 减小报文通过网关的延迟。减小平均队列长度可以有效地减小报文在网络设备 中的排队延迟。 ( 3 ) 避免l o c k o u t 行为的发生。 a q m 的一个代表是r e d ( r a n d o me a r l yd e t e c t i o n ，随机早期检测) 。研究表明，r e d 比d r o p t a i l 具有更好的性能。但是，r e d 的性能对算法的参数设置十分敏感，至今没有在 i n t e m e t 中得到广泛的使用。 对于a q m 的研究，大多采用依赖于直觉的启发式设计加上仿真试验验证的模式来进 行。不可否认，这种模式为网络设计积累了不少经验，发掘了不少新的方法与策略。在体 系结构、协议和机制的研究中无疑是一种最为理想的方式，但在有关算法的研究中，我们 有理由怀疑这种设计模式的有效性，因为启发式的设计不免带有盲目性和片面性。r e d 算 法两次修正设计参数的事实充分说明了这一点。 2 3 拥塞控制的研究意义 拥塞是不可避免的，这是因为：为了提高链路的利用效率，网络传输采用分组交换， 这样路由器的缓存经常被占：如果路由器缓存总是空的，虽然传输时延低，但是网络的利 用效率也低；如果路由器缓存总是被占用，传输时延高，但是网络利用效率也高。因此， 拥塞控制的研究目的不是要完全避免拥塞，而是研究怎样的拥塞程度是合适的。一种形象 的指标是：效率= 网络负载传输时延。虽然，拥塞控制的研究并非由q o s 保证而起，它从 分组交换网络的诞生时就一直倍受关注，但是在强调业务模型的新网络体系结构中，研究 如何通过增强的拥塞控制来帮助增强q o s 保证，也是拥塞控制研究的意义所在。 南京邮电大学硕士研究生毕业论文笫三章t c p i p 拥塞控制 第三章t c p i p 拥塞控制 t c p i p 作为当今i n t e r n e t 的主要协议，使得世界上不同体系结构的计算机网络互连在 一起形成一个全球性的广域网络i n t e m e t ，为各种信息的共享提供了便捷的途径，在i n t e r n e t 中的每一台计算机可以访问i n t e m e t 上的其他任意一台计算机。现在t c p i p 协议已经非常 流行并己经成为计算机网络通信协议的事实上的标准。之所以会这样，关键在于t c p i p 能够适应不同的网络体系结构和不同的传输链路，并且为客户端服务器模式提供了很好的 支持，这已经成为网络应用的标准模式。t c p 协议的广泛应用同时也对t c p 协议的设计提 出了更高的要求。网络自身并不对通信源端注入网络的业务流负载进行严格的控制。因而， 如果每一个连接都不加限制的向网络中注入业务流，那么大量涌入的通信业务流会超过网 络的负载能力，耗尽网络中有限和宝贵的资源，引起网络性能的下降，严重的情况下会导 致网络的拥塞崩溃。由于当前基于t c p 的业务在i n t e m e t 中占主导地位，为了避免拥塞的 发生，利用t c p 协议中对注入网络中的业务流负载进行有效的拥塞控制就显得极为迫切和 重要。同时，网络结点的支持和参与对拥塞控制也起着重要的作用。 本章就现有的t c p 拥塞控制协议以及i p 层拥塞控制机制予以描述和分析。 3 1t c p 拥塞控制机制的发展 1 9 8 8 年v a nj a c o b s o n 在文献 2 】中指出了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 ) 算法，算是最早的t c p 拥 塞控制协议，经过1 0 多年的发展己经出现了多个版本的t c p 拥塞控制协议【3 ，4 ，5 ，6 ，7 ，8 ，9 ， 1 0 ，1 l ，1 2 ，1 3 ，这些协议都采用是基于窗口的控制方式。以下将对主要的t c p 协议进行描 述和分析。 首先对分析过程中使用的基本变量进行说明： ( 1 ) r e c e i v e rw i n d o w ( r w n d ) ，接收端最近通告的接收窗口。 ( 2 ) c o n g e s t i o nw i n d o w ( c w n d ) ，发送端的拥塞控制窗口，用来控制可以发送 的数据报个数。 ( 3 ) i n i t i a lw i n d o w ( i w ) ，发送端c w n d 的初始值，这个值用来设置在t c p 连 接建立后的c w n d 的大小。 南京邮电大学硕士研究生毕业论文 第三章t c p i p 拥塞控制 ( 4 ) l o s sw i n d o w ( l w ) ，表示当发送端通过重传定时检测到丢包后拥塞窗口的 大小。 ( 5 ) r e s t a r t w i n d o w ( r w ) ，用来设置发送端经过长时间的空闲重新开始发送数 据时拥塞控制窗1 2 1 的大小。 ( 6 ) f l i g h ts i z e ( f t i g h t s i z e ) ，表示已经发送但是没有确认的数据包的总数。 3 1 1t a h o e t a h o e 5 是最初的t c p 协议，该协议主要包括陧启动和拥塞避免两个部分。这两个阶 段分别描述如下： 1 慢启动 在新的t c p 连接开始的时候，发送端并不知道网络状况，所以它不能太具侵略性的去 占有网络带宽，所以慢启动使得发送端能够逐渐增大自己发送到网络的数据包的速度以探 测网络的拥塞情况。利用状态变量c w n d 来表示发送端的拥塞窗口大小，初始值设置为1 ， 当发送端每收到一个a c k 时，将e w n d 增加l 。实际上这样的增长速率也很快，所以设置 慢启动的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 2 。 2 拥塞避免 在c w n d s s t h r e s h 的时候，发送端从慢启动进入拥塞避免阶段，其间在每个r t t ( r o u n d t r i pt i m e ，回路响应时间) 中，c w n d 理论上增加1 。当发生重传超时的时候，发送端重新 进入慢启动阶段，并且将s s t h r e s h 设置为c w n d 2 。 3 1 2r e n o r e n o 6 】是在t a h o e 基础上提出的，由于t a h o e 中一旦发生丢包将重新开始慢启动，发 送速度会急剧减小，产生发送速率的抖动，因此增加了快速重传和快速恢复算法。快速恢 复使得发送窗口不至于减小太多，而快速重传则实现丢失数据包的迅速恢复。具体协议描 述如下： 第一步，当发送端收到三个重复的a c k 时，设置s s t h r e s h 不超过m a x ( f l i g h t s i z e 2 ，2 ) ； 第二步，重传丢失的数据包，设置c w n d = s s t h e r e s h + 3 ，其中3 表示接收到的三个a c k 已经确认了三个数据包离开了网络： 第三步，在其后收到每个同样的重复a c k 时将c w n d 加1 ，因为每个a c k 表明己经 9 堕塞塑皇查兰堡圭堕壅生兰些堡苎 有一个数据包离开了网络； 第三章t c p i p 拥塞控制 第四步，在当前发送窗口和接收端通告窗口允许的情况下，发送一个数据包； 第五步，当收到新的a c k ，则将c w n d 设置为s s t h r e s h 的大小，并进入拥塞避免阶段。 3 1 3n e wr e n o n e wr e n o 3 1 是对r e n o 的改进，在r e n o 算法的基础上在第一步增加新的变量r e c o v e r ， 用于在第5 步中收到局部确认( p a r t i a la c k ) 或者新的a c k 时执行不同的操作。具体步 骤如下： 第一步，如果收到3 个重复的a c k ，并且发送端没有处在快速恢复阶段时，将s s t h r e s h 的值设置成不超过m a x ( f l i g h t s i z e 2 ，2 ) ，并用变量r e c o v e r 记录最大已发送数据包的序列 号： 第二步，重传丢失的数据包，设置c w n d = s s t h e r e s h + 3 ，其中3 表示接收到的三个a c k 已经确认了三个数据包离开了网络； 第三步，在其后收到每个同样的重复a c k 时，将c w n d 加l ，因为每个a c k 表明己 经有一个数据包离开了网络； 第四步，在当前发送窗口和接收端通告窗口允许的情况下，发送一个数据包； 第五步，当一个a c k 包含了新的数据包序列号，这个a c k 确认了在第2 步中重传的 数据包或者随后的重传数据包。如果这个a c k 足以确认所有包括序号为r e c o v e r 的数据包， 则可以将c w n d 设置成m i n ( f ii g h t s i z e + l ，s s t h e r e s h ) 或者在第一步中计算的s s t h r e s h 的值， 注意此处的f l i g h t s i z e 和第一步中的f l i g h t s i z e 可能不同。如果此a c k 确认的数据包序号 小于r e c o v e r ，则表明这是一个p a r t i a la c k ，重传其序号后第一个没有得到确认的数据包， 如果用s u m 表示此a c k 可以确认接收端收到的数据包的个数，将c w n d 减小s h m ，反映此 s t l m 个数据包离开了网络，通过这种方法确保在退出快速恢复的时候有s s t h r e s h 个数据包 在网络中。快速恢复过程将持续到没有重复的a c k 收到。 3 1 4s a c k 和d - s a c k 1 s a c k 当在同一个拥塞窗口内发生多个丢包时，t c pr e n o 多次进入和退出快速恢复阶段，这 样拥塞窗口有可能经过多次快速恢复阶段后变得很小。发送端每收到一个p a r t i a l a c k 时， 退出快速重传之后，重新进入快速重传时c w n d 将减半，当存在多个p a r t i a la c k 时，发送 端有可能会发生重传超时，导致不必要的进入慢启动。为了解决这个问题，研究人员提出 1 0 里蔓些璺盔兰堡主竺塾生兰些堡兰兰三雯! 里! ! ! 塑墨笙型 了s a c k 7 协议。通过修改t c p 协议中的部分设定，在a c k 中加入一定的接收端接收到 的数据包信息，有利于发送端选择性的重传。在t c p 连接建立阶段通过s y n 消息进行 s a c k 协议的协商，之后，在数据发送阶段，接收端在t c p 消息的选项域增加s a c k 选项， 以向发送端提供必要的确认信息。下表是t c ps a c k 选项的格式： 选项类型5 ( 1 字节) 陡度( 1 字节) 第1 块的左边界( 4 字节) 第1 块的右边界( 4 字节) 第n 块的左边界( 4 字节) 第r l 块的右边界( 4 字节) 因为选项域最大长度限制为4 0 字节，所以最多能容纳4 个块的信息( 8 * 4 十2 = 3 4 b y t e s 。i f f 赤 伽肝d ( r ) 一1 ，i fd i f f b a s 旦e r t t 2 慢启动 在r e n o 中，每个r t t 后c w n d 都会增加一倍，如果很不巧在前一个r t t 没有丢包， 此时发送速率刚好适合可用带宽，但是下一个r t t 发送速率会加倍，这可能会造成至少一 半拥塞窗口的数据丢失。v e g a s 采用完全不同的方式慢启动，它在每隔一个r t t 允许c w n d 指数增长，在两次增长之间则不变，以减少这种突发的大量的丢包。v e g a s 选择门限v ， 通常取1 ，当d i f y b a s e r t 时结束慢启动，这样做的好处是使网络中的队列有时间“排 空”，而不至于丢包，发送端就可以测量r t t 的变化，采取相应的措施。 3 丢包重传 准确的r 1 t 估计对于t c p 非常重要，它直接影响到重传超时时长的设定。文献 7 】在 l3 堕室堂皇查兰堡主堕窒皇兰些笙兰兰三皇! ! ! ! ! 塑墨丝型 一次仿真中发现，从发送一个数据包到因为超时判断它丢失再到重传此数据包，r e n o 平均 需要1 1 0 0 m s ，而实际的超时间隔只有不到3 0 0 m s ，这个问题是由于采用了比较粗的定时粒 度。 v e g a s 读取系统时钟来测量r t t ，分四种情况重传：发送端收到三个重复的a c k ：粗 粒度的重传定时超时；当收到一个重复a c k 时，v e g a s 检查第一个未确认包的r t t 是否 大于精细粒度的超时值，如果是，则重传此数据包，不用等到三个重复的a c k ；当收到一 个非重复的a c k 时，如果它是重发后收到的第一或第二个确认，v e g a s 检查是否所发送的 未确认包的时间间隔超时，如果是，则重传该包。前两种情况是采用其他拥塞控制算法的 t c p 发送端就可以做到的，面后两种，需要v e g a s 精确的定时来完成，特别是最后一种可 以弥补r e n o 对于p a r t i a la c k 处理的不足。 3 2i p 与t c p 拥塞控制机制的结合 t c p 基于窗口的端到端拥塞控制对于i n t e r n e t 的鲁棒性起到了关键作用。然而，随 着i n t e r n e t 本身的迅速发展，其网络规模越来越庞大，结构日趋复杂，仅仅依靠端到端 的拥塞控制是不够的，事实上i n t e r n e t 在这样复杂的异构系统中，不能指望所有用户在 i n t e r n e t 应用中兼容这种端到端的拥塞控制。网络现在必须参与资源的控制工作。 由于带宽、缓存等资源相对需求日益缺乏，i n t e r n e t 还会继续变得拥塞。这种情况 导致了几种解决拥塞的方法，第一种方法是继续改进已有的端到端拥塞控制并将其作为 i n t e r n e t 上的主要拥塞控制机制，稍后将会深入研究；第二种方法是利用价格等经济因 素限制用户对网络资源的需求，减少拥塞的发生。文献 1 5 提出另外建立网络收费论的方 法，但仅限于理论分析。文献【1 6 用经济学理论分析了具有拥塞特性网络资源的计费问题。 第三种方法是在路由器中采用排队算法和数据包丢弃策略，也就是这里要讨论的i p 拥塞控 制问题。排队算法通过决定哪些包可以传输来分配带宽，而丢弃策略通过决定哪些包被丢 弃来分配缓存。这些也直接影响数据包的延时特性。 以下分析了一些与t c p 相结合的i p 拥塞控制协议，这些协议能帮助t c p 有更好的性 能表现。 3 2 1 传统的先进先出( f i f 0 ) 它的最大优点在于实施起来简单，f i f o 又叫“先到先服务”( f c f s ) ，即第一个到达 路由器的数据包首先被传输，由于每个路由器的缓存总是有限的，如果包到达时缓存己满， 南京邮电大学硕士研究生毕业论文第二章t c p f l p 拥塞控制 那么路由器就不得不丢弃该包。这种做法没有考虑被丢弃包的重要程度。由于f i f o 总是 丢弃到达队尾的包，所以有时又称为“去尾”( d r o p t a i l ) 算法。但“去尾”和f i f o 是两 个不同的概念。f i f o 是一种包调度策略一决定包传送的顺序；“去尾”是一种丢弃策略， 决定哪些包被丢弃。因为f i f o 和“去尾”分别是最简单的包调度和丢弃策略，所以两者 有时被视为一体，甚至有时就简单称为f i f o 排队。 “去尾”的f i f o 是目前i n t e r n e t 使用最广泛的对数据包排队和丢弃方式。这种方 式将拥塞控制的所有责任都推给网络边缘。所以t c p 假定网络中的路由器对拥塞控制不起 任何作用，而独自承担检测和响应拥塞的全部责任。 基本f i f o 排队的一种简单改进是优先级排队。基本思路是将每个数据包分配一个优 先级标志。这个标志可以放在i p 数据包内。例如i p 包头的t o s ( t y p eo f s e r v i c e ) 域，路 由器则执行多个f i f o 排队，一个队列对应一个优先级，路由器总是优先传输非空的最高 优先级队列。在同一优先级队列中，数据包仍按f i f o 方式管理。这与b e s t e f o n 传输方式 稍有不同。但这种方式也没有对某一特定优先级数据流做担保，只是允许高优先级数据包 先被发送。优先级排队的主要问题是高优先级队列能“抢占”所有其它的队列。只要高优 先级队列中有数据，低优先级队列就得不到服务。所以不能允许用户用不受控制的方式指 定高优先级。为了保证i n t e r n e t 上最重要的数据包的传输，例如路由表更新信息，往往 采用优先级排队。这些数据包往往由i p 包头的t o s 域定义，并由一个特殊的队列保存， 实际上这就是区分服务思想的一个实例。另外，由于f i f o 无法“识别”面向连接的连续 t c p 数据流，所以在发生突发性包丢失的情况下其连接公平1 生较差 1 7 1 ，对上层t c p 的快 速恢复效率也较低。 3 2 2 随机早期检测算法( r a n d o me a riyd e t e c t io n r e d ) 这种算法在每个路由器上监控数据包排队长度，一旦发现拥塞迫近，就通知源端高速 拥塞窗口。这种算法也是通过丢弃数据包，使源端发现超时或重复a c k 的方式隐式地通 知源端拥