（通信与信息系统专业论文）因特网拥塞控制机制的研究.pdf

摘要 因特网的拥塞控制已成为当前网络发展面临的重要课题之一。论文详细研究 了基于窗口的t c p 拥塞控制算法，对各种算法的协议实现进行了较为深入的分 析，并通过仿真实验对各自的有效性和公平性进行了对比研究；分析了t c p 公平 的数据吞吐量模型，在此基础上研究了基于速率的t c p 公平的拥塞控制算法 t f r c 并进行了详细仿真。针对现有拥塞控制的机制和算法存在的问题和不足， 对t c p 拥塞控制算法以及基于速率的拥塞控制算法提出了改进并通过仿真实验 对其进行了验证。论文工作中建立了网络仿真平台并构建了试验模型。 关键词：t c p拥塞控制t f r c a b s t r a c t r e s e a r c ho nt h ei n t e r n e tc o n g e s t i o nc o n t r o li sb e c o m i n ga ni m p o r t a n tt a s ki nt h e p r e s e n tn e t w o r kd e v e l o p m e n t t h e p a p e rs t u d i e dv a r i o u sa l g o r i t h m so f w i n d o w b a s e d t c p c o n g e s t i o nc o n t r o li nd e p t h ，a n a l y z e d t h ea l g o r i t h m si nd e t a i l ，a n dc o m p a r e dt h e i r v a l i d i t y a n df a i r n e s sb a s e do ns i m u l a t i o ne x p e r i m e n t t h ep a p e ra l s o s t u d i e dt h e t h r o u g h l ： u tm o d e lo ft c pa n dr a t e - b a s e d ，t c p f r i e n d l yc o n g e s t i o nc o n t r o lp r o t o c o l t f r cw a ss t u d i e db a s e do nt h em o d e l s o m ea d v a n c e da l g o r i t h m sw e r ed e v i s e dt o a m e l i o r a t es o m ed e f e c t si nt c pc o n g e s t i o nc o n t r o la n dr a t e b a s e dc o n g e s t i o nc o n t r o l a n dt h e a l g o r i t h m sw e r e a t t e s t e d b ys i m u l a t i o n e x p e r i m e n t m o d e la n dn e t w o r k s i m u l a t i o np l a t f o r mw e r eb u i l ti nt h ew o r ko f t h ep a p e r 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 l t f r c 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果：也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名唐谁日期兰型三丝堇 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文( 与学位论文相关) 工作成果时署名单位仍然为 西安电子科技大学。学校有权保留送交论文的复印件，允许查阅和借阅论文；学 校可以公布论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保 存论文。( 保密的论文在解密后遵守此规定) 本大签名：垒丝 导师签名维y 澎f = | 期 堕竺! 第一章绪论 第一章绪论 1 1 前言 1 1 1 目前的网络技术 t c p i p 协议族是美国国防部高级研究计划署( d a r p a ) 在六十年代为分组交 换网络提出的系列标准，经过几十年的发展，这一协议族已成为当今i n t e m e t 的标 准，经过三十多年的发展，i n t e m c t 已由1 9 6 9 年包含不到几百个用户的试验网络发 展为至r 2 0 0 0 年4 月为止拥有4 亿用户的目前世界上最大和最成功的网络。i n t e m e t 的 成功发展和普及证明了分组交换网络的有效性，它给人类信息交流方式带来的巨 大变革不亚于印刷术的发明。 一- 应用层 表示层 会话层 传输层 罔络层 数据链路层 物理层 应用层 转输层 i p 屉 l阿培接口层 图1 1 0 s i 模型和t c p ，i p 模型对比 从基本功能上看，分组交换网络包括端结点( 如各种主机) 以及为端点之间 提供连接的中间结点( 如路由器) 。各种用户应用业务通常在端结点上运行并通 过中间结点进行相互之间的通信。在分组交换网络中，端点与中间结点之间以数 据包为单位进行数据传输，数据包有长度限制，过大的信息会被分段封装成多个 数据包在网络中进行传输。每一数据包中均包含信息目的地址并在网络中独立的 选择路由进行传输，同一通信进程中具有相同目的地址的不同数据包在网络中可 能会经历不同的路径到达目的端点。分组交换网络为端点提供b e s t e f f o r t 式的传输 服务，无法保证所有数据包都能准确无误的到达目的结点，有些数据包在网络传 输过程中可能发生丢失或差错。 网络( 如i n t e r n e t ) 的构建需要一系列协议规范的支持，协议( p r o t o c 0 1 ) 是指 用于描述结点间如何通信，数据包采用什么格式，以及结点如何对网络环境做出 圉特网拥塞控制机制的研究 反应等网络行为的规则。o s i 模型提供了清晰的分层网络体系结构，其结构过于复 杂也不适用，t c p i p 协议模型的到了全世界的承认，实际上它没有完整的体系结 构，图1 1 是o s i 模型和t c p i p 模型的对比。 1 1 2i n t e m e t 拥塞控制问题以及研究方向 目前i m e m e t 虽然取得了显著的发展，但是随着用户需求的日益增长以及越来 越多样化，以及各种网络基础设旋技术的发展，传统的i n t e m e t 已经不能满足人们 日益增长的对网络的需求。 首先，表现在网络中的应用需求的变化。i n t e m e t 发展运行其上的业务初期主 要以文件传输、电子邮件以及远程接入。1 9 9 0 年，这三种业务占到i n t e r a c t 骨干网 中总数量的7 0 ，1 9 9 5 年，这三种业务所占比重下降到了3 8 ，而w w w 服务所 占比重上升到2 4 ，到了1 9 9 8 年m c i n e t 骨干网中的数据统计 2 表明，w w w 应 用业务数据量已经上升到了7 0 左右，成为i n t e m e t 中主要的应用业务。当前很多 新业务比如流媒体( s t r e a mm e s a ，视频和音频数据) 业务，更是对传统的i n t e m e t 提出了全面的挑战。 其次，随着传输技术的发展，i n t e r a c t 可以采用各种新型的链路进行基本的数 据传输，这些新型的传输链路具备不同的特性( 例如在无线和卫星链路中，丢包 现象并非主要是由网络拥塞造成的) ，这些特性已远远超出了当初i n t e r a c t 协议设 计时对传输链路的认识和假设。 第三，随着芯片技术的迅猛发展，和各种路由器处理技术的革新，路由器处 理能力不断增强，由于大容量存储技术的应用，在路由器中进行数据运算处理的 性价比正在不断降低，路由器将对网络性能提升提供很大的发展空间。 最后，服务质量( q o s ) 已越来越成为当前i n t e m e t 上的“瓶颈”问题【3 1 ，这 一问题也成为近年来研究热点，i e t f ( i n t e m e t e n g i n e e r i n g t a s k f o r c e ) 提出了多 种业务模型和机制，用以满足各种q o s 的要求。其中主要包括：综合服务资源预 留( i n t e g r a t e ds e r v i c e s r s v p ) 模型，区分服务( d i f f e r e n t i a t e ds e r v i c e s ，d s ) 模 型，多协议标记交换1 4 “( m u l t i - p r o t o c o ll a b e ls w i t c h i n g ，m p l s ) ，流量工程( t r a f f i c e n g i n e e r i n g ) 和受限选路( c o n s t r a i n t b a s e dm u t i n g ) 等。这些模型和机制在下一代 i n t e m e t 中将会得到不同程度的应用，它们均要求网络结点具备符合各自要求的计 算处理能力。 i n t e r a c t 应用需求的不断变化给i n t e r a c t 技术提出了巨大的挑战，i n t e m e t 拥塞 控制问题就成为了当今i n t e m e t 技术需要研究的热点问题之一。作为i n t e m e t 技术 的一个重要组成部分，t c p i p 的捌塞控制( c o n g e s t i o nc o n t r 0 1 ) 也面临着巨大的 挑战。拥塞控制是确保i n t e m e t 健壮性( r o b u s t n e s s ) 的关键因素，i n t e m e t 主要互连 协议t c p i p 的拥塞控制机制对控制拥塞具有特别重要的意义。产生拥塞的原因是 第一章绪论 多方面的，一方面是网络带宽的增长速度远远落后于网络负载的增长速度，这直 接导致了全球范围的带宽资源紧张；另一方面是人们向i n t e r n e t 中引入了越来越多 的流媒体应用，如i p 电话、视频会议等等，为了给这些应用更好的实时服务，所 以它们多采用u d p 协议来传输：并且由于i n t e m e t 采用端到端的服务，个别端点 有可能会贪婪的抢占带宽。这些因素都可以导致i n t e m e t 的拥塞，而严重的拥塞甚 至会导致整个网络瘫痪。i n t e m e t 拥塞问题的根源就是网络带宽的需求大于供给， 所以最直接的解决办法是增加带宽。但是仅依靠提高网络带宽并不能完全解决搠 塞问题，即使带宽的性价比越来越高，但是应用的带宽需求增长速度仍然远大于 带宽的增长速度，并且由于i n t e m e t 的异构性和负载的不确定性，流量在时间空间 上的分布不均，也会导致局部或者暂时的拥塞。所以i n t e m e t 捌塞控制机制是实现 带宽资源有效分配的重要手段。 拥塞控制实现网络带宽资源的有效分配，而应用占用带宽资源的多少又决定 了它能获得的服务质量，因为拥塞控制、带宽资源分配和服务质量( q o s ) 三者之 间是密切相关的。i n t e m e t 采用端到端的拥塞控制机制为各种应用分配带宽，在此 机制中路由器通常提供分组调度和缓存管理办法，而端结点则采用t c p 协议等拥 塞控制协议进行流量调节。i n t c r n e t 服务模型的研究试图对i n t e m e t 体系结构做出 修改以提供区分服务质量的i n t e m e t 服务，这些服务模型和实际应用还有很大的距 离，这方面的研究还有待于深入的研究。从适用的角度出发，对现有i n t e m e t 体系 结构的修改和补充就成了解决i n t e m e t 拥塞问题的比较合适的途径。 现有i n t e m e t 拥塞控制机制包括端结点的拥塞控制以及路由器分组调度和缓 存管理。作为i n t e m e t 主要协议的t c p 拥塞控制协议以及基于速率的拥塞控制协 议的研究都是通过现有i n t e m e t 体系的改善达到有效控制拥塞的目的，如n e w r e n o 6 1 、s a c k 7 】和t f r c t 引。因为网络拥塞的直接感受者是路由器，所以在路由器 分组调度和缓存策略方面的研究也成为当前拥塞控制研究的一个主要方向，这些 控制机制很多时候也需要端结点的配合如e c n 1 4 1 。 1 2 本文的工作以及内容安排 本文详细研究了基于窗口的t c p 拥塞控制算法，对各种算法的协议实现进行 了较为深入的分析，并通过仿真实验对各自的有效性和公平性进行了对比研究； 分析了t c p 公平的数据吞吐量模型，研究了基于速率的t c p 公平的拥塞控制算法 t f r c 并进行了详细仿真。针对现有拥塞控制的机制和算法存在的问题和不足，对 t c p 捌塞控制算法以及基于速率的捐j 塞控制算法提出了一定改进。 本文采用的研究方法主要是仿真分析。本文采用的仿真平台是n s f 加1 ( n e t w o r k s i m u l a t o r ) ，它是u c b l b n l 实验室_ 丌发的离散事件驱动的多协议模拟工具，该平 因特网拥塞控制机制的研究 台原本设计运行于l i n u x 操作系统，经过一段时间对其研究和尝试，我们做了一些 修改，使得该平台已经完全能够运行于w i n d o w s2 0 0 0 x p 操作系统。n s 采用开放 源代码的方式，研究人员可以按照研究需求修改其代码，平台源代码是用c + + 语 言编写的，仿真是用t c l 语言来完成。 本文内容安排如下，第二和第三章对单播拥塞控制协议进行研究和分析，对 已经提出的各种拥塞控制协议进行仿真，对其做出性能分析和比较。第四章对基 于速率的拥塞控制协议进行了研究和分析，对t f r c 协议进行了比较详细的分析， 并对其优势和存在的缺陷做了验证，对其缺陷做出改善。 第二章t c p 拥塞控制机制 第二章t c p 拥塞控制机制 t c p i p 作为当今i n t e m e t 的主要协议，使得世界上不同体系结构的计算机网 络互连在一起形成一个全球性的广域网络i n t e r n e t ，为各种信息的共享提供了便捷 的途径，在i n t e m 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 协议的设计提出了更高的要求。网络自身并不 对通信源端注入网络的业务流负载进行严格的控制。因而，如果每一连接都不加 限制的向网络中注入业务流，那么大量涌入的通信业务流会超过网络的负载能力， 耗尽网络中有限和宝贵的资源，引起网络性能的下降，严重的情况下会导致网络 的拥塞崩溃( c o n g e s t i o nc o l l a p s e ) 。由于当前基于t c p 的业务在i n t e m e t 中占主导 地位，为了避免拥塞的发生，利用t c p 协议中对注入网络中的业务流负载进行有 效的拥塞控制( c o n g e s t i o nc o n t r 0 1 ) 就显得极为迫切和重要。同时，网络结点的支 持和参与对拥塞控制也起着重要的作用。 本章就现有的t c p 拥塞控制协议以及i p 层拥塞控制机制予以描述和分析。 2 1t c p 拥塞控制 1 9 8 8 年v a nj a c o b s o n 在 1 1 指出了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 拥塞 控制协议 6 ，7 ，1 1 ，1 2 ，1 4 , 2 6 , 3 0 , 3 3 3 4 , 3 5 , 3 6 1 ，这些协议都采用是基于窗口的控制方式。以下 将对主要的t c p 协议进行描述和分析。 基本变量说明： r e c e i v e r w i n d o w ( r w n d ) ，接收端最近通告的接收窗口。 c o n g e s t i o n w i n d o w ( c w n d ) ，发送端的拥塞控制窗口，用来控制可以 发送的数据报个数。 i n i t i a lw i n d o w ( ，) ，发送端c w n d 的初始值，这个值用来设置者在 t c p 连接建立后的c w n d 的大小。 l o s s w i n d o w ( l w ) ，表示当发送端通过重传定时检测到丢包后拥塞窗 因特网拥塞控制机制的研究 口的大小。 r e s t a r tw i n d o w ( r w ) ，用来设置发送端经过长时间的空闲重新丌始 发送数据时拥塞控制窗口的大小。 f l i g h t s i z e ( f l i g h t s i z e ) ，已经发送但是没有确认的数据包的总数。 2 1 1t ，山o e 凰m m ( a ) 懂启动 尹葡厅司 _ j ；出“斟。“” ( b ) 拥塞避免 7 i 】m o ( c ) 慢启动和拥塞避免时拥塞窗1 2 1 的变化 圈2 1 慢启动和拥塞避免 t a h o e 1 是最初的t c p 协议，协议主要包括慢启动( s l o ws t a r t ，s s ) 和拥塞避 免( c o n g e s t i o n a v o i d a n c e ，c a ) 两部分。分别描述如下： 1 慢启动 在新的t c p 连接开始的时候，发送端并不知道网络状况，所以它不能太具 侵占性的去占有网络带宽，所以慢启动使得发送端能够逐渐的增大自己发送到网 第二章t c p 拥塞控制机制 络的数据包的速度以探测网络j j 塞情况。利用状态变量c w n d1 来表示发送端的拥塞 窗口大小，初始值设置为1 ，当发送端每收到一个a c k ，将c w n d 增加1 。实际上 这样的增长速率也很快，所以设置慢启动的c w n d 增长的上限s st h r e s h ，当慢启动 中c w n d 增长到s s _ t h r e s h ，则停止慢启动，进入拥塞避免阶段。当还没有进入捎j 塞 避免阶段的时候发生重传超时，则发送端重新丌始慢启动，并设置s st h r e s h 为 c w n d 2 。 2 拥塞避免 毛：e c w n d 船一t h r e s h 的时候，发送端从慢启动进入拥塞避免阶段，其间每个 r 1 盯中c w n d 增加大约1 。当发生重传超时的时候，发送端重新进入慢启动阶段， 并且将s s _ t h r e s h 设置为c w n d 2 。 2 1 2r e n o r e n o 1 2 j 是在t a h o e 基础上提出的，由于t a h o e 中一旦发生丢包将重新开始慢 启动，发送速度会急剧减小，产生发送速率的抖动，因此增加了快速重传( f a s t r e t r a n s m i t ) 和快速恢复( f a s t r e c o v e r y ) 。快速恢复使得发送窗口不至于减小太 多，而快速重传实现丢失数据包的迅速恢复。具体协议描述如下： 第一步，当收发送端到三个重复的a c k ，设置s st h r e s h 不超过 m a x ( f l i g h t s i z e 2 ，2 ) ： 第二步，重传丢失的数据包，设置c w n d = 船一t h e r e s h + 3 ，其中3 表示接收到 的三个a c k 已经确认了三个数据包离开了网络； 第三步，在其后收到每个同样的重复a c k ，将c w n d j 口l ，因为每个a c k 表 明已经有一个数据包离开了网络； 第四步，在当前发送窗口和接收端通告窗口允许的情况下，发送一个数据包； 第五步，当收到新的a c k ，则将删以设置为s s _ t h r e s h 的大小，并进入拥塞 避免阶段。 2 1 3n e w r e n o n e w r e n o 【6 】是对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 ，并且发送端没有处在快速恢复阶段，将 1 n ：有砦文档中价议描述时伽门d 、s s t h r e s h 等变量都以1 ：节为单位，为拒一次连接中每个数据包人 尘兰釜粤煮t 所以呵以用所发送的数据包个数代替数据量，本史中所有的根窗u 有关的控制变量都足以数据 包数为单位。 。 。一 冈特网拥塞控制机制的研究 s st 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 st h e r e s h + 3 ，其中3 表示接收到 的三个a c k 已经确认了三个数据包离开了网络。 第三步，在其后收到每个同样的重复a c k ，将c w n d 加1 ，因为每个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 l i g h t s i z e + l ，s st 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 镧，反映此s u m 个数据包离开了网络， 通过这种方法确保在退出快速恢复的时候s s _ t h r e s h 个数据包在网络中。快速恢复 过程将持续到没有重复的a c k 收到。算法详细状态图如图2 2 所示。 2 ，1 4s a c k 和d s a c k 幽2 2 n e w r e n o 协议状态幽 箱二章t c p 拥塞控制机制 2 1 4 1s a c k 当在同个捌塞窗口内发生多个丢包，t c p r 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 时，发送端有可能会发生重传超时，导致不必要的进入慢启动。为 了解决这个问题，提出了s a c k 【7j 协议。通过修改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 选项的格式如表2 1 。 表2 ls a c k 选项 选项类型5 ( i 字节) 长度( 1 字仃) 第1 块的左边界( 4 字节) 第1 块的右边界( 4 字。协) 第n 块的左边界( 4 字节) 第n 块的右边界( 4 字。悼) 因为选项域最大长度限制为4 0 字节，所以最多能容纳4 个块的信息( 8 * 4 + 2 = 3 4 b y t e s 赤( 2 - 1 ) b d s e r 盯 删叫，) _ 1 ，i f d i f f 面赫 2 1 5 2 慢启动 在r e n o 中，每个r t t 后c w n d 都会增加一倍，如果很不巧在前个f 汀t 没有 丢包，此时发送速率刚好适合可用带宽，但是下一个r t t 发送速率会加倍，这可 能会造成至少一半拥塞窗口的数据丢失。v e g a s 采用完全不同的方式慢启动，它在 每隔一个r t t 允许e w n d 指数增长，在两次增长之间则不变，以减少这种突发的大 量的丢包。v e g a s 选择门限y ，通常取i ，当d 矽 y 脑出玎，结束谩启动。这 样做的好处是使网络中的队列有时间“排空”，而不至于丢包，发送端就可以测量 1 2 旦堑旦塑奎丝型塑型堕塑壅 _ 一一 r t t 的变化，采取相应的措施。 2 1 5 3 丢包重传 准确的r t t 估计对于t c p 非常重要，它直接影响到重传超时时长的设定。 1 4 】 在一次仿真中发现，从发送一个数据包到因为超时判断它丢失再到重传此数据包， 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 1 r r 是否大于精细粒度的超时值，如果是，则重传此数据包，不用等到三个 重复的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 l a c k 处理的 不足。 2 2i p 与t c p 拥塞控制机制的结合 t c p 拥塞控制对当前的i n t e m e t 的健壮性发挥了巨大的作用，但是随着i n t e r a c t 的迅猛发展，其结构也越来越复杂，仅仅依靠端到端的拥塞控制是不够的，事实 上在h l t e m e t 这样复杂的异构系统中，不能指望所有用户在i n t e m e t 应用中兼容这 种端到端的拥塞控制，网络必须参与资源的管理工作。近些年随着i n t e m e t 硬件和 软件技术的迅猛发展，使得网络能更有效地参与到搠塞控制中来，随之产生了一 些网络中间结点辅助的拥塞控制机制。因为本身拥塞是发生在网络当中的，拥塞 的最直接感受者就是网络中间结点，所以这些存在于网络中间结点的搁塞控制方 式能提供比端到端的拥塞控制方式更有效的控制机制。由于网络拥塞几乎都是由 于带宽和缓存等资源的限制引起的，和分组调度策略及缓存管理机制有很大的关 系，所以基于i p 层的拥塞控制机制就基于分组调度和缓存管理策略上。 本节介绍t c p 和i p 相结合的拥塞控制协议，这些协议能帮助t c p 有更好的 性能表现。 2 2 1 先进先出队列 传统的i n t e m e t 结点采用的是先进先出( f i r s ti nf i r s to u t ，f i f o ) 的排队方式， 这是现如今i n t e r n e t 中使用最广泛的方式，其最大的优点就是实现起来简单。但由 于f i f o 采用了弃尾法( d r o p t a i l ) 的丢弃算法，所以容易造成突发的丢包，对上 第二章t c p 拥塞控制机制 1 3 层的t c p 快速恢复的效率也较低。对于网络中不受控的数据流( 如u d p ) 和受控 的数据流竞争带宽时( 如t c p ) ，采用这种方式时，不受控的数据流会抢占到更多 的带宽和缓存。所以近年来相继产生一些新的队列管理算法。 2 2 2 随机早期检测算法 随机早期检测算法 1 ( r a n d o me a r l yd e t e c t i o n ，r e d ) 是按一定的概率丢弃进 入路由器的数据包。r e d 设计的早期思路是避免丢弃属于同连接的连续数据包， 从而提高连接的吞吐量。通过分摊包丢失率，r e d 可以在各连接之间获得较好的 公平性，对突发业务的适应性较强。图2 4 显示了r e d 算法的过程，其中包丢失 率p 为平均排队长度绒一的函数。可以用公式2 - 2 表达r e d 算法： p = 0 ，i f q m 一 t h r e s h r a i n j 五2 二生璺堕竺l ，i f 腩，e s ，u 伽 瓯。 t h r e s h m a x 其中t h r e s h m a x 与t h r e s h r a i n 是两个可调控制参数。 r e d 的问题在于会引起网络的不稳定( i n s t a b i l i t y ) 【1 6 】，选择合适的配置参数 也不是件容易的事。 j t h l i i t nt h r e r hn - a x， 图2 4 丢弃率和平均队列长度关系 2 2 3 公平排队法 公平排队法( f a i rq u e u i n g ，f q ) 算法中路由器对每个输出线路( o u t p u tl i n e ) 有一个排队队列。当一条线路闲时，路由器就来回扫描所有队列，依次将每个队 列第一个包发出。f q 的带宽分配独立于数据包大小，各种服务在队列中几乎是同 时开始的。所以它在没有牺牲统计复用的情况下提供公平惶，与端到端的拥塞控 制机制可以较好地协同。它的缺点在于实现起来很复杂，需要对每个数据流进行 排队处理，每流状态统计，数据包的分类( c t a s s i f y ) 以及包调度会产生额外的开 销等。 2 2 4 加权公平排队算法 冈特网拥塞控制机制的研究 加权公平排队算法( w e i g h t e d f a i rq u e u i n g ，w f q ) 是f q 的改进算法。根据 不同数据流应用对带宽的不同要求，对每个排队队列采用加权方法分配缓存资源， 从而增强f q 对不同应用的适应性。 2 2 5 显式拥塞指示法 以前的拥塞控制算法都是用包丢失作为告诉端系统网络发生拥塞的指示。这 种方式对一次性大批量数据传输的效果比较理想。但对于时延有较高要求的应用， 例如音频( a u d i o ) 、远程登录t e l n e t 等效果并不是很理想。显式拥塞指示算法【1 7 ，2 8 , 斟“3 2 1 ( e x p l i c i tc o n g e s t i o nn o t i f y ，e c n ) 从以前d e c b i t 算法得到启发，在源端 数据包中嵌入e c n 使能发送比特位，由路由器根据网络情况设置c e ( c o n g e s t i o n e x p e r i e n c e d ) 比特位，然后传递给目的端。目的端在反馈的t c p 确认包中向源端 反馈相应信息。源端接收到从目的端反馈信息，减慢发送速率以避免拥塞。e c n 的优势在于不需要重传超时，也不依赖于粗粒度的t c p 定时，所以对于时延有较 高要求的应用效果较好。e c n 需要源端和目的端系统共同协调，源端和目的端系 统如果有任意一个不支持，将无法发挥出e c n 的优势。 2 3 本章小结 本章对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 s 进行了描述，对i p 层拥塞控制机制进行了简单介绍，为下面的仿真分析 奠定一定的基础。 笙婴兰茎! 婆奎塑! ! 奎篓型堕壅婴窒 一旦 第三章t c p 拥塞控制协议仿真研究 基于对以上协议的描述，我们在这一章对现有的各种主要t c p 拥塞控制协议 算法进行仿真分析，其目的是通过详细的仿真分析，获得具体数据，验证各种t c p 协议算法性能，研究各种算法在多神情况下的有效性、彼此之间的公平性，主要 的特点以及存在的问题，为后续工作奠定基础。 3 1 协议有效性研究 本节将对目前t c p 拥塞控制算法几个主要版本的有效性进行比较分析研究。 禽1 叫虱。磊丽一 1 ”“s l ! ；罗 圈3 1 协议有效性仿真网络拓扑 3 1 1 特定丢包条件下协议有效性分析 这个测试中我们将对协议在特殊条件下的有效性迸行仿真分析。仿真采用图 3 i 的网络拓扑结构。数据包大小设定为1 0 0 0 字节1 。 我们在仿真过程中将特定的包在链路上丢弃，然后比较这些协议的操作，此 次仿真实验中我们将序号1 4 、2 6 、2 8 等三个数据包在发送端到路由器的链路上丢 弃。 从图3 2 中( a ) 看出，t a h o e 在遇到丢包时就将拥塞窗口减小到1 ，重新开始 慢启动过程，即使此时网络不再摺塞，但由于发送端速率很低，会造成较大的带 宽浪费，协议发送效率不高。 图b 中显示r e n o 的发送数据包序号和接收到的a c k 序号的变化，当第一次 丢包( 序号为1 4 ) 发生的时，发送端收到后续的三个重复的a c k ( 1 3 )( 注： n s 中，t c p 确认消息a c k 中返回的序号是当前已收到包中的最大序号) 重发此 数据包，并将拥塞窗1 2 1 大小减半( 原先为1 5 ，现降为7 ) 。之后每收到一个重复 a c k ( 1 3 ) ，拥塞窗口加1 ：当发送端收到a c k ( 2 5 ) 时表明对方收到了第1 4 包， 之后又连续收到3 个重复的a c k ( 2 5 ) ，于是发送端重发序号为2 6 的包，由于在 下一个r 1 盯中，2 6 、2 8 是在同一个搠塞窗口中发送的，当重发了2 6 以后，收到 对2 7 的a c k ，这是一个p a r t i a la c k ，按照r e n o 协议，发送端要等到3 个重复的 a c k 才会重发2 8 ，可惜，由于此时发送端已经减小了拥塞窗口，没有可用窗口发 l ：本文的所有仿真实验中除非特别括，发送端数据包人小都驶定为1 0 0 0 字节。 画| l吉 凰獬 一 因特网拥塞控制机制的研究 送新数据，发送端就只有等待重发定时超时了。由此可见，r e n o 协议在发生单个 丢包时，将拥塞窗口减半，并执行快速恢复，协议效率比t a h o e 高；但当一个r t t 内发生多个丢包时，r e n o 执行多次快速恢复，最终使拥塞窗口剧减，并可能导致 不必要的超时重发并进入慢启动，协议效率( 平均发送速率) 受到了很大影响。 在图( c ) 中，由于n e w r e n o 规定在同一个r t t 内不会将拥塞窗口减小两次， 当重发2 6 后，收到a c k ( 2 7 ) 即对数据包2 7 的确认时，由于2 7 小于已发送最大 序号3 2 ，发送端发现这是一个p a r t i a la c k ，立即重发数据包2 8 ，不用等到收到三 个重复的a c k ( 2 7 ) 后再重发2 8 。由于协议规定在处理一个r 1 r r 内出现的多个 丢包时，只迸入一次快速重发，拥塞窗口只减