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

摘要 随着计算机技术的发展，i n t e m e t 在过去十几年中迅速发展，其 网络规模的迅速膨胀和用户数量的急剧增长不仅对网络设备提出了 更高的要求，也对网络拥塞问题的研究提出了新的挑战。现有的网络 拥塞控制算法远远无法满足未来网络的需求。网络拥塞控制研究也成 为当前计算机网络和控制理论交叉领域研究的一个热点课题，不仅具 有重要的理论价值，同时具有广泛的应用研究背景和意义。 拥塞控制的算法可以根据位置不同分为两大类：在源端系统上使 用的源算法( s o u r c ea l g o r i t h m ) 以及在网络设备上使用的链路算法( 1 i n k a l g o r i t h m ) 。衡量拥塞控制算法的标准有效率、公平性、稳定性、收 敛性等，其中稳定性是最重要的标准之一。 本文分析了现今应用广泛的实现源端拥塞控制算法的t c p 协议， 重点研究了针对高速远距离网络的f a s tt c p 拥塞控制算法的拥塞 控制机制及其稳定性问题。 本文研究了f a s t t c p 模型及算法，针对其不足，提出了改进的 f a s tt c p 拥塞控制算法a w - f a s tt c p ，采用了自适用方式调整拥 塞控制窗口，使网络更容易达到稳定。并对传统的t c p 拥塞控制算 法、f a s tt c p 及a w - f a s tt c p 进行了模拟仿真，通过分析和比较， 在稳定性方面a w - f a s tt c p 均获得较好的性能。同时通过理论证明 了该算法在分离时间模型上拥有反馈延时时，t c p 流趋于稳定可以通 过调整协议参数口( 窗口缓存) 来解决，确定了使网络稳定的口值的 一个下界。 关键词：f a s tt c p ，拥塞控制，高带宽高延时，稳定性 a bs t r a c t i nr e c e n ty e a r s ，r a p i di n f l a t i o no fi n t e m e ts c a l ei sn o to n l yb r o u g h t f o r w a r dah i g h e rr e q u e s tt on e t w o r ke q u i p m e n t ，a l s oi m p e l l e de m b e d d e d r e s e a r c hi nc o n g e s t i o nc o n t r 0 1 i n d e x t h e r e f o r e i ti si m p o r t a n tt os o l v e t h e c o n g e s t i o n ，p r o b l e me f f e c t i v e l y t h e r e s e a r c ha b o u tn e t w o r k c o n g e s t i o np r o b l e mh a sa l s ob e e nah o ts u b j e c ti nb o t hc o m p u t e rn e t w o r k a n dc o n t r o lt h e o r y , w h i c hm a k e sg r e a ts e n s ei ns c i e n c ea sw e l la s p r a c t i c a la p p l i c a t i o n t h e r ea r et w op r i m a r yc o m p o n e n t si ne n d t o - e n dc o n g e s t i o nc o n t r o l ： o n ei st h el i n ka l g o r i t h me x e c u t e db yn e t w o r kd e v i c e s s u c ha sr o u t e r so r s w i t c h e s ；t h eo t h e ri st h es o u r c ea l g o r i t h me x e c u t e db yh o s tc o m p u t e r so r e d g ed e v i c e s a n ds t a b i l i t yi so n eo fm o s ti m p o r t a n tc r i t e r i o nt om e a s u r e c o n g e s t i o nc o n t r o lm e c h a n i s m f a s tt c pi st h en e wv a r i a n to ft c pp r o p o s e d b yn e t l a b w e a n a l y s i st h ec o n g e s t i o nc o n t r o lm e c h a n i s ma n ds t a b i l i t yo ff a s tt c e w ea n a l y z e do nc u r r e n tf a s tt c pm o d e li nd e t a i l a n dt e s t e di t s p e r f o r m a n c e w ei m p r o v e df a s tt c pa l g o r i t h m t h r o u g hs i m u l a t i o n ， w ea n a l y z e da n dc o m p a r e dt h et h r o u g h p u ta m o n ga w - f a s tt c p 、f a s t t c p 、h s t c p 、s t c pa n dt c pr e n o a w - f a s tt c pc o n s i s t e n t l y o u t p e r f o r m so t h e rp r o t o c o l s i n s t a b i l i t y a t t h es a m ew eu s ea d i s c r e t e - t i m em o d e lo ff a s tt c pt h a t f u l l yc a p t u r e st h ee f f e c to f s e l f - c l o c k i n ga n dp r o v et h ec o n d i t i o no ff a s tt c p ss t a b i l i t yo nt h e p r o t o c o lp a r a m e t e r sv a l u et ot h ec a s eo fan e t w o r kw i t ht h ef e e d b a c k d e l a y k e yw o r d s ：f a s t t c p , c o n g e s t i o nc o n t r o l ，h i g h s p e e dl o n g - l a t e n c y , s t a b i l i t y 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均己在论文中作了明确的说明。 作者签名： 日期：j 啤年月掣日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 作者签名：如虬导师签名单l 日期斗年上月必日 硕士学位论文第一章绪论 1 1 研究背景和意义 第一章绪论 拥塞控制算法是一种分布式的算法，它能够使相互竞争的用户共享网络资 源。资源的可用性对用户来说是不可预知的，因此需要一种高效的共享方法，使 数据源能够动态的调整发送速率以达到流量控制的目的。在i n t e m e t 上，这些任 务都是由t c p 协议来完成的。 纵观i n t e m e t 的发展，可以很清晰地看到如下几个特点： ( 1 ) 网络规模不断扩大。1 9 6 9 年的a r p a n e t 只有4 个节点，仅限于美国国 内，现在的i n t e m e t 已经覆盖全球。从1 9 8 1 年以来，加入i n t e m e t 的节点数几乎 保持着线性增长，t c p i p 发明是推动i n t e m e t 规模增长的最重要的动力。 ( 2 ) 网络带宽不断提高。早期的a r p a n e t 主干带宽只有5 6 k b ，而目前 i n t e r n e t 主干带宽己经达到1 0 g b 或者更高。 ( 3 ) 网络应用越来越复杂。早期i n t e m e t 上的主要网络应用为e m a i l 、t e l n e t 、 n e w s 和f t p ，用户主要集中在科研群体。目前，i n t e m e t 上网络应用种类繁多： 电子商务、远程医疗、远程教育、虚拟社区、网络游戏以及各类实时业务等功能 复杂的网络应用己深入普通人的日常生活。 目前，从传输的端口容量看，利用光纤通信技术，在一个波长上就可实现 1 0 至4 0 g b i t s s 的传输速度，而采用波分复用技术( w d m ) 后，又可以在一条光纤 上传送多达1 2 8 个光波的数据，即将来在一条光纤上就可传送高达数t b i t s s 的 速率。目前，能够商用的w d m 技术已能实现4 0 g b i t s s 的传送能力，还远未达 到光纤的传送潜力。在高速路由器或交换机的端口方面，已有厂家推出1 0 g b i t s s 速率的端口，而1 0 0 m b i t s s 至2 5 g b i t s s 范围的端口速率，己是目前网络设备的 常见端口类型。从网络高速化发展来看，2 5 g b i t s s 以下的端口速率将会在接入 层网络中普遍使用，骨干层网络将会普遍采用1 0 g b i t s s 以上的端口速率。虽然 目前商用化的交换路由器的交换能力还停留在数1 0 g b i t s s 的能，但从技术的发 展趋势来看，大容量、高速率的i p 交换将成为可能，而采用光换技术，则交换 能力将会达到数十t 甚至数百t 。 另一方面，多媒体应用近年来以更加迅猛的速度发展。从v o i p ( i p 电话) 到实 时的多方音视合作，如多媒体会议系统、远程医疗、电子商务等，都为终端用户 带来了全新的体验。和普通数据不同，多媒体数据具有实时特性，即数据之间必 须满足一定的时间要求。目前基于尽力而为( b e s t e f f o r t ) 的i n t e m e t 己经不能满足 多媒体应用和各种用户对网络传输质量的要求。因此，以提高网络资源利用率、 硕：b 学位论文 第一章绪论 为用户提供更高服务质量( q u a l i t yo fs e r v i c e ，q o s ) 1 3 为目标的研究领域目前极具 活力。 因此，基于当前网络带宽容量大、高时延、链路可靠性高、数据传输实时性 要求高等特点，有必要有适合该环境的网络协议。f a s tt c p 4 j 是基于该网络环 境而提出的网络协议。拥塞是网络协议的一个最重要的一个方面，因此，网络拥 塞控制【5 】研究成为当前国内外计算机网络和控制理论交叉领域研究的一个热点 课题，不仅具有重要的理论价值，同时具有广泛的应用研究背景和意义，于是 f a s t t c p 拥塞控制研究成为当前网络的一个研究热点【6 】。 1 2 国内外现状 f a s tt c p 是2 0 0 4 年提出的一个在高带宽网络中运行的协议，它是基于路 径延时反馈的协议，以排队延时作为反馈因子，利用源端侦测a c k 延时变化来 调整拥塞窗口，结合使用了延时和丢包来判断拥塞。 早期t c p 的实现只是使用累计确认、超时重传等机制，而没有拥塞控制。 接收端利用t c p 报头将接收能力通知发送端，这样的控制机制只考虑了接收端 的接收能力，而没有考虑网络的传输能力。 拥塞控制1 7 】的研究开始于8 0 年代中期，1 9 8 4 年，n a g l e 首次指出了复杂 t c p i p 网络中存在的拥塞问题，特别是在由路由器连接的带宽差异较大的网络 中，容易发生“拥塞崩溃”( c o n g e s t i o nc o l l a p s e ) 现象。1 9 8 8 年，v a nj a c o b s o n 在 著名的论文中指出了t c p 协议在拥塞控制上的不足，并提出“慢启动”、“拥塞 避免和“快速重传算法，并于1 9 9 0 年提出了“快速恢复”算法，奠定了拥 塞控制研究的基础。从8 0 年代至今，许多学者进行了更深入和细致的研究，不 断完善和改进t c p 拥塞控制存在的缺陷，相继提出几个版本的t c p 拥塞控制算 法：t a h o e 、r e n o 、n e wr e n o 、s a c k 8 9 1 、v e g a s 、x c p 、s t c p 、h i g hs p e e dt c p l l 们、 f a s tt c p 、b i c 1 1 - 1 2 。 由于稳定性是拥塞控制算法的重要特性之一，因此，针对f a s tt c p 拥塞控 制机制的稳定性研究也成为拥塞控制机制的研究热点之一。 1 2 1 拥塞控制的研究进展 拥塞控制算法可以分为两个主要部分：在源端系统上使用的源算法和在网络 设备上使用的链路算法。 源算法中使用最广泛的是t c p 协议中的拥塞控制算法。t c p 是目前在 i n t e m e t 中使用最广泛的传输协议。根据统计，总字节数的8 0 和总报文数的 硕士学位论文 第一章绪论 7 5 使用t c p 传输。近年来，t c p 中采用了很多新的算法，包括慢启动( s l o w s t a r t ) 、拥塞避免、快速重传( f a s tr e t r a n s m i t ) 、快速恢复( f a s tr 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 ) 算法【1 3 - 1 5 】方面和传统的“队尾丢弃( d r o p t a i l ) 相比，a q m 在网络设 备的缓冲溢出之前就丢弃或标记报文a q m 的主要优点是： ( 1 ) 减少网关的报文丢失，使用a q m 可以保持较小的队列长度，从而增强 网关容纳突发流量的能力。 ( 2 ) 减小报文通过网关的延迟，减小平均队列长度可以有效地减小报文在设 备中的排队延迟。 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 的性能对算法的参数设置十分敏感。a q m 能够公平的处理各种t c p 流，避免多个t c p 连接由于队列溢出而同时进入“慢 启动 状态，并能维持较小的队列长度，在高吞吐量和低时延之间做出合理的平 衡。 对于低速低时延的局域网和广域网，t c p a q m 算法设计框架在保留了端到 端的设计原则的基础上加入了拥塞预警机制，提高了算法性能和业务服务质量， 保证了当前i n t e m e t 网络的鲁棒稳定运行。随着网格计算逐步走向应用和网络的 长距离传输( 卫星传输) ，下一代i n t e m e t 将具有高带宽延迟积的特性，这一趋势 给现有的研究提出了新的挑战，目前国际上对该问题的研究刚刚开始，研究水平 处于初始阶段。具体而言，该问题的研究进展收到如下条件的制约： 第一，现有的t c p a q m 在包层次上的算法性能显著降低。主要原因是高的 带宽延迟积会带来大的t c p 拥塞窗口( 数量级为1 0 4 1 0 5 ) 在a i m d 调整过程中， 如此大的拥塞窗口必然会导致“过激 和“过缓”的效应。如加式提升，每一往 返时间( r t t ) 仅增加一个包，这使得用户到达稳定吞吐的时间过长，而当发生包 丢失和e c n 标记时，将当前拥塞窗口。w n d 减半，这种行为又显得过激，带来 大的网络流量振荡。很显然，这会同时带来极低的网络吞吐量和利用率。 第二，研究和仿真均表明长的传输延迟导致网络不稳定并带来不公平性问 题，同时最近的研究结果是高的链路容量会增大网络运行的不稳定。 而且，目前尚没有带宽时延积、网络拓扑参数和鲁棒稳定性这三者关系的解 析理论，因此具有可镇定性和鲁棒可扩展性的算法参数设计和协议实现也是一个 瓶颈问题。 在高带宽网络中，研究人员发现传统的t c p 协议主要存在下面几个方面的 硕：卜学位论文 第一章绪论 问题： ( 1 ) 传统t c p 的拥塞窗口机制造成网络带宽利用率很低。举例来说，一个包 长为1 5 0 0 字节和l o o m s 延时的标准t c p 流，要快速到1 0 g p s 的网速，至少需 要1 5 0 亿的低丢包率。但是一旦发生丢包，从拥塞避免阶段恢复到网络高利用 率的话，至少需要一个多小时的恢复时间，这是让人无发接受的。 ( 2 ) 往返传输时间( r o u n dt r i pt i m e ，r t t ) 差异所带来的吞吐量不公平性加 剧。传统t c p 协议就一直存在流与流之间i 汀t 不公平性的问题，高带宽网络上 表现更加厉害。 ( 3 ) t c p 流抖动频繁，网络不稳定性加剧。 由于高带宽时延积因特网刚刚显现，因此对上述拥塞控制问题的研究国际上 也仅处于初始研究阶段。解决方法主要是采用多比特的e c n 反馈控制方案。如 c a l t e c h 的l o w 博士所带领的n e t l a b 课题组最近刚刚提出的f a s tt c p ，网络将 测量到的端到端队列时延信息反馈到源端，根据此信息，源端对拥塞窗口进行动 态调整。该算法能够实现高带宽时延积网络的快速镇定。另外一个重要的研究成 果是m i t 的k a t a b i 博士多发表的x c p ，该算法设计思想来源于a tm 网络中的 a b r 显式速率拥塞控制算法，应用多比特e c n 将路由器所计算的显式速率反馈 给t c p 源端，两种算法都要求t c p 报文头包含多比特的反馈信息( 即全信息反 馈) ，理论上来说可以实现更精确的拥塞控制，但是将增加更多的负荷，浪费网 络资源并增加了实现的复杂度，实际协议实现的难度很大。另外，前一种算法往 返时间r t t 和端到端的队列时延的精确估计也是一个难以解决的问题，后一种 算法更是改变了端到端的t c p 拥塞控制设计原则，需要在现有的t c p 协议上做 大量的改动，因此在实际的应用中还存在很大的问题，不能从实际上解决目前存 在的问题。 在当前f a s tt c p 稳定性研究中，已经证明了f a s tt c p 没有反馈延时是全 局稳定的，证明了f a s t t c p 拥有反馈延时时是局部稳定的。 1 2 2f a s tt c p 概述 随着计算机网络的高速发展，高速网已经成为一种趋势，传统的拥塞控制策 略已经难以满足需求。传统协议( t c pr e n o ) 拥塞控制算法主要表现在以下四个方 面的问题： ( 1 ) 在包级，在每一个r t t ( 往返传输延时) 时间拥塞窗口增加一个包显得太 慢，每丢失一个包，窗口减半显得太剧烈。 ( 2 ) 在流级，维持巨大的拥塞窗e l 需要非常小的丢包率。 ( 3 ) 在包级，拥塞窗1 2 1 抖动不可避免，因为t c p 使用的是二进制的拥塞控制 4 硕士学位论文 第一章绪论 算法。 ( 4 ) 在流级，网络的动态性表现为不可预知性，只有精确估计包的丢失率和 对流动态性稳定性设计才能减少抖动。 f a s tt c p 的拥塞控制机制与传统的基于丢包率的拥塞控制机制不同，该机 制是一个基于平衡的算法，通过调整f a s t t c p 的窗口机制，使得使用f a s t t c p 协议的流能够逐步到达平衡状态，从而消除了数据包级的震荡问题。f a s tt c p 继承了v e g a s 的做法，使用队列延迟作为衡量网络拥塞的主要方法，由于在高速 长距离的网络中，队列延迟比丢包率提供了更准确地信息，使源端能够更准确的 判断拥塞的发生。 f a s t t c p 在平衡状态下，目标是在瓶颈路由的队列中维持一定数量的数据 包，从而避免拥塞的产生并持续获得高的链路利用率。f a s t t c p 通过测量已发 送数据包的r t t 来控制拥塞窗口大小。 f a s t t c p 是针对传统协议的问题而提出的，它是一种基于延时反馈的高速 网协议，而对拥塞控制算法的好坏的评价中，主要是对稳定性、公平性、收敛性 和吞吐量这4 个方面进行评价。 在f a s tt c p 性能分析中，稳定性分析尤为复杂，主要表现在网络环境的复 杂性，如不同的反馈延时、非窗口流，流的抖动等等，因此，对f a s t t c p 稳定 性研究显得非常重要。本文研究了f a s tt c p 模型，然后在分离时间模型基础上 分析和证明了f a s tt c p 在拥有反馈延时达到稳定性可以通过调整口。( 协议参 数) 来解决。 1 2 3f a s tt c p 拥塞控制存在的问题及研究热点 由于f a s tt c p 研究还处于起步阶段，它还存在一些问题，如快速恢复机制 还没有得到很好的实施，内存消耗太大，流与流之间的公平性等。目前，人们主 要从下面几个方面研究它。 ( 1 ) “慢启动”过程的改进，“慢启动”阶段对短数据传输更重要，“拥塞避 免”阶段对长数据传输更重要。目前i n t e m e t 上的一个主要应用h t t p 的流量主 要是短数据。这方面的研究包括增大拥塞窗口的初始值，推荐将初始拥塞窗口的 值由1 m s s ( m a x i m u ms e g m e n ts i z e ) 增加到4 m s s ，将“慢启动”过程分为多段，逐 步减小窗口增长的速度，平滑从们慢启动 到“拥塞避免 的过渡。 ( 2 ) 减少不必要的“超时重传”和“快速重传”。这些重传发生时，f a s tt c p 都会减小拥塞窗口，从而降低传输的速率。i 盯t 测量的准确性和乱序报文都会影 响t c p 做出正确的判断。 ( 3 ) 特殊网络环境中的拥塞控制。它包括在无线链路、卫星链路、“非对称” 硕。i ：学位论文第一章绪论 链路上的拥塞控制等。 近年来，高速率的网络如1g b p s 以上的网络己经从实验室转向实际应用。 在数据网格网络和存储网中，网络主机通常会有吉比特的网络接口直接连接到高 速网络上。为了移动程序数据，备份或同步数据库，通常会传输上g b 甚至是 t b 的数据。在这种情况下，如果用来做大量数据传输的话，现有的广泛应用的 普通t c p 实现己经不能获得足够的吞吐量去满足以上的应用，怎样提高高带宽 网络的吞吐量、公平性、带宽利用率是我们必须考虑的问题。 f a s tt c p 通过r r t 的变化进行判断能够及时的预测网络带宽的使用情况， 对小缓存的路由器适用性较强，效率也比较理想，因此f a s tt c p 被认为是能够 在高带宽网络最好的协议之一。 f a s tt c p 协议在提高网络带宽吞吐量的同时，结合了r t t 延时变化信息， 在网络近饱和状态表现出一定的保守型，近些年的研究表明，怎样通过提高测量 延时的准确性确定拥塞状况是我们最重要考虑的问题。因此，研究f a s tt c p 在 高带宽网络中对网络利用率、吞吐量提高等有重要的意义。 1 3 本文内容结构安排 本文针对t c p 协议的最新变种之一一f a s tt c p 协议进行分析研究，通过理 论分析及模拟实验相结合的方式，对f a s tt c p 的吞吐量、队列大小进行了分析， 并对f a s tt c p 协议和现有的r e n o 、s t c p 、h s t c p 进行了实验仿真，研究表明， 在以上各方面，f a s tt c p 协议都具有更好的性能表现。证明f a s tt c p 在分离 时间模型上可以通过调整参数来达到全局稳定，并研究它的下界。 本文的具体的章节内容安排如下： 第一章介绍本文的研究背景和拥塞控制的国内外研究现状以及f a s tt c p 拥塞控制存在问题及研究热点。 第二章介绍拥塞控制产生的原因和设计困难，当前拥塞的主要拥塞控制算 法，包括源算法和链路算法，介绍f a s tt c p 的模型，分析f a s tt c p 拥塞控制 算法的原理，对数据管理、窗口控制、突发控制和估计进行了较为详细的分析， 最后介绍拥塞控制算法的评价标准。 第三章详细介绍拥塞控制的仿真环境n s 2 ，并对f a s tt c p 的性能进行了分 析，主要是对静态模型和动态模型进行分析，并与其它的传统拥塞控制算法进行 比较。同时提出了改进的f a s tt c p 拥塞控制算法a w f a s tt c p ，并与f a s t t c p 进行比较，a w f a s tt c p 在稳定性获得了更好的性能。 第四章介绍f a s tt c p 的稳定性链路分析模型，并在分离时间模型上对 f a s tt c p 的稳定算法进行证明，通过实验和理论对f a s tt c p 拥塞控制算法的 6 硕士学位论文 第一章绪论 稳定性的研究，证明f a s tt c p 在单瓶颈链路中拥有的反馈延时可以通过调整参 数来达到稳定，并且分析的它的下界。 第五章为总结和展望，总结本文的工作，指出目前在研究中还存在的一些问 题和不足，并给出下一步可能的研究方向和相关设想。 硕士学位论文第二章t c p 拥采控制研究 第二章t c p 拥塞控制研究 2 1 拥塞控制产生原因和设计困难 当一个子网或者子网的一部分中出现太多分组的时候，网络的性能丌始下 降。这种情况称为拥塞( c o n g e s t i o n ) 。当主机发送到网络上的数据量低于网络的传 输容量时，除了在传输过程中因传输错误无法正确到达目的主机的数据包外，大 部分数据将被f 确发送至目的主机。然而随着通信量的增加，当用户发送的数据 量超出网络的传输容量时，网络就会产生拥塞。 图2 1 给出了数据吞吐量与给定负载之间的关系，显示出了最佳操作点k n e e 和拥塞崩溃区。开始时网络负载较轻，网络带宽未被完全利用，吞吐量与负载量 呈正比。当吞吐量继上升，最终会保持在一个稳定的值，该稳定值和链路带宽的 最大限制值相等，此时，数据包开始在链路中排队。当负载进一步加重，吞吐量 会出现“悬崖效应一在很短的时间内迅速下降最终接近于0 。 吞 吐 量 寸 们 区 负载( b i t s s ) 图2 - 1 数据吞吐量与给定负载的关系 拥塞控制机制试图减少和消除这种“悬崖效应一网络崩溃。一个好的拥塞 控制算法的目标是通过调整资源，从而提供最佳负载，使网络始终处于图中曲线 的左转折处。 拥塞控制算法可分为拥塞避免( 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 n c o n t r 0 1 ) 两种类型。拥塞避免算法是一种“预防”机制，用于众k n e e 点之前，目 标是为了使网络维持在高吞吐量、低延迟状态，避免网络拥塞的发生。拥塞控制 算法是一种“恢复”机制，用于k n e e 点之后，用于拥塞产生后将网络从拥塞状 态中快速恢复过来并重新进入拥塞避免阶段。 拥塞的发生和互联网的设计机制有着密切关系，互联网的网络模型可以用以 下几点进行抽象： 1 分组交换网络 8 硕：仁学位论文第二章t c p 拥塞控制研究 分组交换也称包交换，它将用户传送的数据划分成一定长度，每个部分成为 一个分组。在每个分组前加上一个头部，用来标示该分组的目的地址，然后交换 机通过每个分组的地址标志，将其转发至目的地。这一过程称为分组交换。进行 分组交换的通信网称为分组交换网。 分组交换网络是在“存储一转发”的基础上发展起来的，这种网络结构同时 具有电路交换和报文交换的优点。和电路交换网络相比，分组交换网络提高了资 源的利用率。和报文交换网络相比，分组交换网络具有较小的传输时延和更好的 交互性。 2 无连接( c o n n e c t i o n l e s s ) l 网络 无连接的网络指网络中的节点在传输数据前不需要建立连接。这种连接模式 简化了网络的设计，在网络的中间节点上不需要保存和连接有关的状态信息。但 该模型在用户需求大于网络资源时很难保证服务质量；由于该模型对发送源的追 踪能力较差，也给网络安全带来了隐患；无连接的网络模型也是造成乱序报文出 现的主要原因之一。 3 尽力交付( b e s t e f f o r t ) 的服务模型 尽力而为网络不对数据传输的服务质量提供保证。尽管最近几年提出了很多 的方案，如集成服务、区分服务等服务模型用于提供网络服务质量的保证，但是 尽力而为网络的服务模型简单实用，在当前和未来的网络中，该模型仍占有重要 的比重。 拥塞产生的原因是对网络的需求大于网络的实际承载能力。当网络中有限的 资源被多用户共享时，如果没有相关的机制控制流入网络中的数据量，则必然会 导致网络拥塞甚至网络崩溃的发生。 拥塞一般发生在网络资源相对短缺的位置。网络的拥塞表现在几个方面： ( 1 ) 存储空间不足。如果几个输入数据流共同需要同一个输出端口，那么在 这个端口就会建立排队。如果没有足够的存储空间，数据包则会被丢弃。 ( 2 ) 带宽容量不足。低速链路对高速数据流的输入也会产生拥塞。所有信源 发送的速率r 必须小于或等于信道容量c 。如果r c ，在理论上无差错传输则 是不可能的。所以在网络低速链路处就会形成带宽瓶颈，当其满足不了通过它的 所有源端带宽的要求时，网络就会发生拥塞。 ( 3 ) 处理器处理能力弱、速度慢。如果路由器的c p u 在执行排队缓存、更新 路由表等功能时，处理速度跟不上高速链路，也会产生拥塞。 ( 4 ) 网络带宽的不均衡性。由于网络设施的不同，在不同的路径中具有不同 的带宽，当数据从高带宽的链路进入低带宽的链路时，可能会发生拥塞。 ( 5 ) 流量分布的不均衡。不同的数据流以不同的速率进入网络，当主机发送 9 硕一 ：学位论文第二章t c p 拥寨控制研究 数据包至网络的速率过高，超过网络的承载能力时，会产生拥塞。在互联网中， 资源和流量分布的不均衡都是广泛存在的，因此，在前面3 个方面靠增加网络资 源的方式可以解决问题，但是由于后面2 个方面的问题，仅靠增加网络资源，远 不足以解决网络拥塞的问题。 拥塞总是发生在网络中资源“相对“短缺的位置。塞发生位置的不均衡反映 了i n t e r n e t 的不均衡性。首先是资源分布的不均衡。图2 2 ( a ) q h 带宽的分御是不均 衡的，当以1 m b s 的速率从s 向d 发送数据时，在网关r 会发生拥塞。其次是流量 分布的不均衡。图2 2 ( b ) 中带宽的分布是均衡的，当a 和b 都以1 m b s 的速率向c 发送数据时，在网关r 也会发生拥塞。i n t e m e t 中资源和流量分布的不均衡都是广 泛存在的，由此导致的拥塞不能使用增加资源的方法解决。 ( b ) 图2 - 2 带宽分布 拥塞控制算法的设计困难体现在以下几方面： ( 1 ) 算法的分布性。拥塞控制算法的实现分布在多个网络节点中，必须使用 不完整的信息完成控制，并使各节点协调工作，还必须考虑某些节点工作不正常 的情况。 ( 2 ) 网络环境的复杂性。i n t e m e t 中各处的网络性能有很大的差异，算法必须 具有很好的适应性。另外，由于i n t e m e t 对报文的正确传输不提供保证，算法必 须处理报文丢失、乱序到达等情况。 ( 3 ) 算法的性能要求。拥塞控制算法对性能有很高的要求，包括算法的公平 性、效率、稳定性和收敛性等。某些性能目标之间存在矛盾，在算法设计时需要 进行权衡。 ( 4 ) 算法的开销。拥塞控制算法必须尽量减少附加的网络流量，特别是在拥 塞发生时。在使用反馈式的控制机制时，这个要求增加了算法设计的困难，算法 还必须尽量降低在网络节点( 特别是网关) 上的计算复杂性。目前的策略是将大部 分计算放在端节点完成，在网关上只进行少量的操作，这符合i n t e m e t 的基本设 计思想。 2 2t c p 拥塞控制算法 前面介绍拥塞控制算法主要分为两个主要部分：在端系统上使用的源算法和 1 0 硕士学位论文第二章t c p 拥塞控制研究 在网络设备上使用的链路算法。 2 2 1 滑动窗口协议 t c p 使用滑动窗口协议来传输数据，所以在介绍t c p 拥塞控制算法之前， 先了解一下滑动窗口协议。 在所有的滑动窗口协议中，每一个要发出的帧都包含着一个序列号，范围 是从n 到某个最大值。最大值通常是2 n 1 ，因此序列号恰好能放入n 位的字段中。 t c p 发送窗口和接收窗口如图2 3 、图2 4 所示： 后沿 厌 、 、心 给 逻 沁 厌窟 泌 j 趸 岁 图2 - 3 发送窗口 发送窗口用来对发送端进行流量控制，而发送窗口的大小w 就代表还没有 收到对方确认的条件下发送端最多可以发送多少个数据帧。如图2 3 ，解释了发 送窗口的概念。假设用3 个比特来编码，即从0 到7 。又设发送窗口w = 5 ，即在 未收到对方确认的条件下，允许发送端最多发送出5 个数据帧。图2 - 3 ( a ) 是刚刚 开始发送时的情况。这时，在扇形的发送窗口内，共有5 个序号，从0 到4 。具 有这些序号的数据帧就是发送端现在可以发送的帧。若发送端发送完这5 个帧但 仍未收到确认信息，则由于发送窗口已填满，就必须停止发送而进入等待状态。 当0 号帧的确认信息收到后，发送窗口就沿顺时针方向旋转一个号，使窗口后沿 再次与一个未被确认的帧号相邻，如图2 - 3 ( b ) 。这时由于5 号帧已落入发送窗口 之内，因此发送端现在就可以发送这个5 号帧。之后假设又有3 个帧( 1 到3 号) 的确认帧达到发送端。于是发送窗口再沿顺时针方向向前旋转3 个号，而发送端 可以继续发送的数据帧序号是6 ，7 ，0 。 为了减少开销，接收端不一定要对每一个接收到的正确帧都发回一个确认， 而是可以在连续收到几个正确的数据帧后，才对最后一个确认，即是说，对某一 数据帧的确认，表明该帧和之前的所有帧都已经被正确无误地收到了。 同样，在接收端设置窗口是为了控制那些帧可以接收而哪些帧不可以接收。 如图2 4 所示，在接收端只有当收到的数据帧的发送序号落入接收窗口内才允许 硕卜学位论文 第二章t c p 拥寒控制研究 将该帧收下。若接收到的帧落在接收窗i z l 之外，则一律抛弃。图2 - 4 ( a ) ，表明一 开始接收窗口处于0 号帧处，接收端准备接收0 号帧。0 号帧一旦收到，接收窗 口就沿顺时针方向旋转一个号，准备接收1 号帧，同时向发送端发送l 号帧的确 认信息。 图2 - 4 ( b ) 中，若收到l 号帧，接收窗口旋转l 格，并发出确认。但若收到的 不是1 号帧，比如收到的帧号落入接收窗口之前， f f d ! z n 收到了2 号帧，这时接收 端抛弃它，并发出对2 号帧的否认信息。但若收到了落在接收窗口之后，f f d ! z i j 收 到了0 号帧，而0 号帧已经正确收到，并确认了。此时就表明0 号帧的确认帧没 有被收到，因此现在要重发0 号帧的确认，但是0 号帧不能接收，否则就重复了。 这两种情况，接收窗口都不旋转。 后辩 - r 袋 、 确 汐 r 礤f八 汐 厌分 辽汐 1 t o ) 图2 4 接受窗口 从以上讨论可以看出，当接收窗口保持不动时，发送窗口无论如何也不会旋 转。只好有在接收窗口发生旋转后，发送窗口才有旋转的可能。 2 2 2t c p 协议的拥塞控制源算法 在各种源端的拥塞控制算法中，t c p 的拥塞控制算法是使用的最为普遍和成 功的拥塞控制算法。它使用了序列号、校验和、确认以及超时重传等机制，为用 户提供了可靠的数据传输。t c p 的拥塞控制由慢启动1 1 8 。19 】、拥塞避免、快速重传 和快速恢复四个核心部分组成，下面分别介绍这四种算法： 1 慢启动 早期开发的t c p 应用在启动一个连接时会向网络中发送大量的数据包，这 样容易导致路由器缓存空间耗尽，使网络产生拥塞，从而导致t c p 连接吞吐量 的急剧下降。由于t c p 源端无法得知网络资源当前的利用状况，因此新建立的 t c p 连接不能一次发送大量数据，而只能采用逐步增加发送数据量的方法，从而 避免拥塞的发生。 当建立新的t c p 连接时，拥塞窗1 2 1 ( c o n g e s t i o nw i n d o w ，c w n d ) 初始化为一个 1 2 硕士学位论文第二章t c p 拥塞控制研究 数据包大小源端按照拥塞窗口的大小发送数据报，当每次收到一个a c k 确认时， 拥塞窗口的大小增一，这时c w n d 随着回路响应时f i l l ( r o u n dt r i p t i m e ，r t t ) 呈指 数增长。使用慢启动方法，要达到每个i 汀t 发送w 个数据包的量仅需时 r 1 v r 木l o g w 。 2 拥塞避免 由于传输引起数据包丢失的概率很小( s s t h r e s h 时，t c p 协议启动 拥塞避免算法。在拥塞避免阶段，c w n d 每次收到一个a c k 时只增加一个l c w n d 个数据报，在一个r 1 r t 内，c w n d 仅增加1 。因此在拥塞避免阶段，c w n d 不是呈 指数增长，而是线性增长。 3 快速重传 j a c o b s o n 提出了对拥塞避免算法的改进，实现了当收到一个乱序包时，接收 端可以发送一个复制a c k 。这个a c k 的目的是告诉发送端有乱序包并且通告该 包的序号。 t c p 并不知道复制a c k 是由于包的丢失引起的，还是由于包乱序引起的。 但如果认为是乱序包引起的，在乱序包处理前应当只有1 个或者2 个a c k 。如 果有3 个或者超过3 个复制a c k 收到，则认为是由于丢包引起的，因此重传包 而不等重传计时器超时。这种机制就是快速重传机制。 4 快速恢复 重传了丢失的数据包后，执行拥塞避免算法而不是慢启动算法，这就是快速 恢复【2 0 】算法，这样可以在中等程度拥塞的情况下支持高输出。快速恢复是基于 “管道 模型( p i p em o d e ) l 拘“数据包守恒”原贝, l j ( 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 ) ， 即同一时刻在网络中传输的数据包数量是恒定的，只有当“旧”的数据包离开网 络后，才能发送“新”的数据包进入网络。 快速重传和快速恢复算法通常结合在一起实施。 ( 1 ) 当收到第三个复制a c k 时，s s t h r e s h 设为当前窗口拥塞的一半，但不小 于2 。重传丢失的数据段。设置c w n d 为s s t h r e s h + 3 * s e g m e n t 。这就实现了根据离 开网络的数据段和接收端缓存的数据段来扩大c w n d 。 ( 2 ) 每次当另外一个复制a c k 到达时，将c w n d 增加l ，这就为已经离 开网络的数据段扩大了拥塞窗口。 ( 3 ) 当下一个对新数据认可的a c k 到达时，将c w n d 设为s s t h r e s h ，这个a c k 是对第一步中重传的数据段的认可。 硕：l 学位论文 第二章t c p 拥寨控制研究 拥塞 室口 o _ 州 鳓t h r e 曲 善伽n 囟，2 拥霎 w n 图2 5 慢启动和拥塞避免 i 斓 图2 - 6 快速重传和快速恢复 2 2 3t c p 协议的拥塞控制链路算法 b 寸f i l 在当前的i n t e m e t 上，丢包是对发送端节点进行拥塞通知的重要信号，解决 拥塞队列溢出的方法便是在队列充满之前丢包，这样发送端节点便能在队列溢出 前对拥塞做出反应，这种方法便称为主动式队列管理( a c t i v eq u e u e m a n a g e m e n to 因此，a q m 算法是一种基于f i f o 调度策略的队列管理机制，使 得路由器能够控制在什么时候丢多少包，以配合端到端的拥塞控制。a q m 有以 下优点： ( 1 ) 减少了路由器中丢弃的包的数量，由于网络中数据包的突发本质是不可 避免的，a q m 通过保持较小的平均队列长度( a v e r a g eq u e u es l z e ) 昵提供更大的容 量吸收突发数据包，从而大大减少了丢包数。 ( 2 ) 对需要持续交换大量数据的服务提供了更低的延迟。a q m 通过保持较小 的平均队列长度，因此降低了端对端连接的排队时延。对需要持续交换大量数据 的服务是非常重要。 ( 3 ) 降低了“死锁的概率。a q m 算法设法主队列保持较短的队长，使大多 数到来的数据包都有可用的队列空间，从而降低了“死锁”现象的概率，也防止 1 4 硕士学位论文第二章t c p 拥塞控制研究 了对低带宽高突发的流的偏见。 随机早期检测算法( r a n d o me a r l yd e t e c t i o n ，r e d ) 是著名的a q m 算法，该 算法于1 9 9 3 年由s f l o y d