（计算机科学与技术专业论文）fast+tcp拥塞控制公平性改进研究.pdf

r e s e a r c ha n di m p r o v e m e n to nf a i r n e s so f c o n g e s t i o nc o n t r o lm e c h a n i s mo ff a s t t c p s p e c i a l t y ： q 耻坠! 曼! = 苎堡i 曼堕堡曼垒旦亟墅堡h 垒q ! q g y m a s t e rd e g r e ec a n d i d a t e ： l i 翌选i 丕i 望g s u p e r v i s o r ： v i c ep r o f y a nh u i c o l l e g eo fi n f o r m a t i o ns c i e n c e & e n g i n e e r i n g c e n t r a ls o u t hu n i v e r s i t y c h a n g s h ah u n a np r c 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 ，rt ， 作者签名：逖日期： 幽竺年工月笪日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 作者签名：查垫 导师签名径日期：丝【里年月丛日 摘要 当前，随着计算机和通信技术的飞速发展，互联网已经成为人们 日常生活中不可或缺的一部分。互联网的应用由以前简单的数据传 输、到实时通信、再到现在的远程协作和控制，它的应用领域不断拓 宽，速度越来越快、规模也越来越庞大。然而，一定时期内的网络资 源是有限的，网络拥塞不可避免。因此，怎样设计更高效、更合理的 拥塞控制机制对现有网络的顺畅运行发挥着至关重要的作用。面对复 杂的网络环境和不断膨胀的客户需求，拥塞问题至今还没有一个完美 的解决方案，网络拥塞控制依然是当前计算机网络和通信技术研究的 一个热门话题。 拥塞控制算法根据实现的位置不同，主要分为链路算法( 1 i n k a l g o r i t h m ) 矛l 源端算法( s o u r c ea l g o r i t h m ) 两种：链路算法在路由器和交 换机中执行，作用是检测网络拥塞，并产生拥塞反馈信息；源端算法 在主机和网络边缘设备中执行，作用是根据拥塞反馈信息实时调整数 据的发送速率。衡量拥塞控制算法有许多标准，如效率、公平性、稳 定性、友好性和收敛性等，其中公平性是最重要的标准之一。 本文分析了目前应用最广泛的源端拥塞控制算法叫c p 协议， 重点研究了针对高带宽长延时网络而出现的f a s tt c p 协议，通过 n s 2 仿真实验平台，我们比较了f a s tt c p 以及其它一些主流拥塞控 制算法的优缺点，并选择公平性作为主要研究方向。 本文研究了f a s tt c p 模型及其算法，针对其在公平性方面存在 的不足，提出了改进的拥塞控制算法f f a s tt c p ，通过在原有算法 中添加一个公平因子，达到显著改善其性能的目的。并对传统的t c p 拥塞控制算法、f a s tt c p 及f f a s tt c p 进行了模拟仿真，通过理 论分析和实验证明，在公平性和相对友好性方面f f a s tt c p 确实能 比原算法获得更好的性能。最后，提出了新算法的设计模型和公平因 子的选取方案。 关键词f a s tt c p ，拥塞控制，公平性，高速网络 a b s t r a c t w i t ht h ed e v e l o p m e n to fc o m p u t e ra n dc o m m u n i c a t i o nt e c h n o l o g y , p e o p l e sd e m a n df o ri n t e m e th a se x c e e d e do u re x p e c t a t i o n s ，t h er e s u l ti s b r o u g h ta b o u tt h er a p i de x p a n s i o no fn e t w o r ks i z ea n dt h ei n c r e m e n to f a p p l i c a t i o nf i e l d s t h e r e f o r e m o r ee f f e c t i v ea n dr e a s o n a b l ec o n t r o l m e c h a n i s m sf o rt h es m o o t ho p e r a t i o no fe x i s t i n gn e t w o r k sp l a yav i t a l r o l e i nw h i c ht h em o s tb a s i ca n dc r i t i c a le l e m e n ti st h ec o n g e s t i o n c o n t r o l ，n a m e l y , h o wt oe f f e c t i v e l yp r e v e n to re l i m i n a t et h ec o n g e s t i o ni n t h en e t w o r ka v a i l a b i l i t y h o w e v e r , f a c et ot h em u l t i f a r i o u se n v i r o n m e n t o ft h en e t w o r k ，c o n g e s t i o np r o b l e m sh a v en o ty e tap e r f e c ts o l u t i o n ，t h e r e s e a r c ha b o u tn e t w o r kc 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 n b o t hc o m p u t e rn e t w o r ka n dc o n t r o lt h e o r y 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 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 re d g ed e v i c e s ； t h eo t h e ri 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 s r o u t e r so rs w i t c h e s t h e r ea r em a n ys t a n d a r d st om e a s u r et h ec o n g e s t i o n c o n t r o la l g o r i t h m a n df a i m e s si so n eo ft h em o s ti m p o r t a n to n e f a s tt c pi san e wv a r i a n to ft c p p r o p o s e db yn e t l a b w r ea n a l y s i s t h e c o n g e s t i o nc o n t r o lm e c h a n i s ma n df a i m e s so ff a s t t c p 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 mb y a d d i n gaf a i rf a c t o r t h r o u g hs i m u l m 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 g t c pr e n o 、f a s tt c pa n df f a s tt c p f 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 si nf a i m e s s a tl a s t w es t u d yt h em e t h o do f s e l e c t i n gf a c t o r k e yw o r d sf a s tt c p , c o n g e s t i o nc o n t r o l ，f a i m e s s ，h i g h - s p e e d n e t w o r k s i i 目录 摘要i 目录i i i 第一章绪论1 1 1 课题研究背景和意义1 1 2 拥塞控制算法研究现状2 1 3 本文的主要研究内容和组织结构4 第二章t c p 拥塞控制机制5 2 1 拥塞控制概述5 2 1 1 拥塞产生的原因和危害7 2 1 2t c p 拥塞控制实现9 2 2t c p 拥塞控制主要算法1 2 2 3 拥塞控制的评价标准15 第三章f a s tt c p 拥塞控制机制研究1 9 3 1f a s tt c p 模型及特征1 9 3 2f a s tt c p 仿真方案设计2 1 3 3f a s tt c p 拥塞控制性能分析2 3 第四章f a s tt c p 公平性改进研究2 7 4 1f a s tt c p 算法公平性分析及存在的问题2 7 4 2f a s tt c p 算法公平性实验及数学分析2 8 4 3f f a s tt c p 公平性改进的f a s tt c p 算法3 0 第五章f f a s tt c p 拥塞控制算法设计3 2 5 1f f a s tt c p 模型设计3 2 5 2f f a s tt c p 公平因子的选取方案3 3 5 3f f a s tt c p 有效性实验3 5 第六章总结与展望- 3 8 6 1 论文总结一3 8 6 2 研究展望3 8 参考文献4 0 致谢4 4 攻读硕士期间主要的研究成果4 5 i i i 硕士学位论文第一章绪论 第一章绪论 纵观计算机网络的发展，其实是一部由简单到复杂，由低级到高级，由军用 到商用，由局域到全球的，不断响应人们需求，不断升级换代，不断高速发展的 进化史。 同时，这也是一部不断突破发展瓶颈，不断应对用户膨胀，不断提高带宽速 度，不断解决网络拥塞的奋斗史。 拥塞问题并不是自从网络出现就有的。传统的网络采用的是电路交换，电路 交换包括三个阶段：电路建立、数据传输和电路拆除。传统电话网就是电路交换 的典型例子。电路交换是一种直接的交换方式，它为一对需要通信的装置之间提 供一条临时的专用通道，这条传输通道既是物理通道又是逻辑通道( 使用时分或 频分复用技术) 。由于这条通道是独占的，一旦连接建立，即使通道空闲，别的 用户也不能使用。虽然它不会造成网络的拥塞，却会极大地浪费网络资源。 1 9 6 9 年，a r p a 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 影响人类历史发展进程的同时，其本身的发展也面临着种种困难，其中最重要的 就是网络拥塞( n e t w o r kc o n g e s t i o n ) 【l 】。1 9 8 8 年j a c o b s o n 在文献 2 中首次提出 了网络拥塞避免( n e t w o r kc o n g e s ti o na v o i d a n c e ) 和网络拥塞控制( n e t w o r k c o n g e s t i o nc o n t r 0 1 ) 理论，它为此后的网络拥塞研究【3 】奠定了基础。在当今网 络趋于大规模、高速和应用多元化的今天，网络拥塞控制已成为确保i n t e r n e t 高效运行的关键因素。 1 1 课题研究背景和意义 随着第三代计算机网络的发展，网络访问、网络服务、网络管理和安全等技 术的逐步完善以及标准化工作的不断进行，计算机网络的应用几乎遍及人类活动 硕l ：学位论文 第一章绪论 的一切领域。各种管理信息自动化系统、办公自动化系统、智能决策系统、军事 指挥系统、情报资料检索系统都是在客观分布情况下，以计算机网络为基础的信 息网络上完成的。计算机网络已经将“语言、图像、视频、音乐、统计数据”等 各种形式的多媒体信息的实时通讯带入了全新的时代，这也对网络的性能提出了 更高的要求，未来的网络必定是高速、大规模和应用多元化的。正是由于高速网 络具有极大的应用前景，而现有的t c p 拥塞控制算法仅适用于普通网络，于是 针对高速网络设计的f a s tt c p 4 】拥塞控制机制应运而生，并成为当f j 的研究热 点。 t c p 捌塞控制协议在低速网络中曾经占有重要地位，一度成为影响人们工作 学习的最伟大发明。但随着网络技术的发展和客户规模的不断膨胀，拥塞问题变 得越来越严重。这主要有两个方面的原因。一方面，在t c p 拥塞控制机制中， 源端只能获得低比特的拥塞信息，信息的不完整和不确定性导致源端对拥塞程度 做出了错误的估计和判断。另一方面，t c p 协议的丌放性，使用户可以轻易地修 改t c p 的实现代码，这种修改后的协议是否还具有拥塞控制功能，我们是无法 确定的。以上两种情况的发生，直接导致源端无法正确估计发送窗口的大小，如 果这个时候用户继续发送数据报，就会导致网络拥塞加重以及带宽享用不公平的 产生。此外，由于t c p 协议在窗口控制算法中的缺陷，当两条流处于相同链路 中，拥有较长r 盯的流与较小r 1 陌的流无法获得相同的带宽，这也是导致不公 平产生的一个原因。 根据经典控制理论，可以把网络拥塞控制看成一个复杂的控制系统，拥塞控 制算法设计的有效性、复杂性对研究者提出了前所未有的挑战。对网络拥塞控制 的研究，虽然已经持续了很长时间，但到目前为止，这个问题就像悬在科学家头 上的一片乌云，始终没有散去。因此，对目前应用最广泛的源端拥塞控制算法一 - t c p 协议，特别是f a s tt c p 协议版本进行公平性研究，不仅具有重要的理论 价值，同时具有广泛的应用研究价值【5 】。 1 2 拥塞控制算法研究现状 拥塞控制算法主要有两个实现目标：一、避免网络拥塞的发生以及在拥塞发 生后快速解除拥塞；二、为每个网络连接提供尽可能公平的服务。 对于i n t e m e t 网络，从控制系统的角度来看实际上是一个复杂的闭环系统。 这样，拥塞控制算法的研究主要涉及以下三个问题：( 1 ) 用什么方法检测网络拥 塞的发生；( 2 ) 女1 1 何将拥塞反馈信息传送到拥塞控制点；( 3 ) 捌塞控制点怎样根据 拥塞信息对发送速率和发送窗口进行调整。在早期的t c p 传输协议实现中，只 有流量控锘1 ( f l o wc o n t r 0 1 ) 而没有拥塞控制( c o n g e s t i o nc o n t r 0 1 ) 。流量控制利用t c p 2 硕士学位论文 第一章绪论 报头的通告窗口，让接收端可以通告发送端它能够接受的流量，它减轻了高速发 送端因发送速度过快从而淹没接收端的问题。但流量控制并没有考虑网络的实际 传输能力，这也为网络拥塞埋下了隐患。互联网历史上第一次由拥塞引起的网络 崩溃( c o n g e s t i o nc o l l a p s e ) 6 发生在1 9 8 6 年的美国，这引起了人们对网络拥塞的高 度关注，并开始对拥塞控制领域进行大量研究。 当前拥塞控制算法的研究热点主要包括： ( 1 ) “慢启动”过程的改进【_ 7 ，8 】。“慢启动 算法使t c p 协议在慢速启动阶段 不能很好地利用网络带宽，尤其是对于那些带宽时延积较小和i m 较大的链路。 实验证明，t c p 的延迟响应算法影响t c p 的性能，因为慢速启动算法是以大量 的报文段丢失而终止的。目前业界公认的较好的初始化窗口为( m i n ( 4 x m s s ， m a x ( 2 m s s ，43 8 0 b y t e s ) ) ，其中m s s ( m a x i m u ms e g m e n ts i z e ，最大报文尺寸) 代表网络能够传输的最大数据单元的字节数。通过改进初始窗口大小，达到减少 到达接收方报告的窗口尺寸所需要的必要时间的目的。 ( 2 ) 基于速率的控制策吲9 lo 】改进。t c p 协议在使用窗口控制策略时存在一 些缺陷：容易导致报文的突发；发送速率受到窗口初始大小的限制；一个窗口内 多个报文的丢失要很长时间才能恢复等。于是一些研究者提出r b p ( r a t e b a s e d p a c i n g ) ，原理是将窗口控制和速率控制结合起来一起考虑以克服以上缺陷。但文 献 1 1 对r b p 的有效性提出了质疑，指出当拥塞发生时，r b p 会造成多个连接 同时丢失报文，进而出现“全局同步 ( 酉o b a ls y n c h r o n i z a t i o n ) 现象，并严重降低 网络吞吐量。另一方面，r b p 的实现要依赖大量高精度的时钟，这必将消耗大 量资源。 ( 3 ) a c k 过滤( a c kf l i t e r ) 机制。它的主要目的是保持t c p 的“自时钟”( s e l f c l o c k i n g ) 1 1 2 机制。“自时钟 机制能够减轻突发报文对网络的破坏性冲击。 ( 4 ) 减少非必要的“超时重传 和“快速重传 。当这些重传发生时，t c p 协议都会相应减小拥塞窗口，从而降低传输速率。另外r 1 r r 测量的准确性以及 乱序报文都会影响t c p 做出正确的判断和反应。 ( 5 ) e c n ( e x p l i c i tc o n g e s t i o nn o t i f i c a t i o n ) 的使用【1 3 1 4 1 。端系统通过对比报文中 网关设定的标志位来检测拥塞的发生，而不仅仅依赖报文丢失为依据来判断是否 发生拥塞。在无线应用网络环境中，e c n 的使用可以将由报文损坏造成的报文 丢失和网络拥塞导致的报文丢失这两种情况区分开。 ( 6 ) 特殊网络环境中的拥塞控制研列1 5 , 1 6 】。它包括t c p 的无线链路网络【17 1 、 卫星链路网络 1 8 】、“非对称”链路【1 9 】网络上的拥塞控制等。 传统的t c p 拥塞控制协议由于自身缺陷已经成为高速网络传输的瓶颈，迫 切需要一种新的拥塞控制机制来代替。本文研究了一种适用于高带宽长延时网络 硕i ：学位论文 第一章绪论 的拥塞控制机制f a s tt c p ，并在此基础上提出在该算法中增加一个公平因 子，得到可显著改善其公平性和相对友好性的改进算法f f a s tt c p 。 1 3 本文的主要研究内容和组织结构 本文首先对f a s tt c p 协议进行了分析研究，通过理论分析及模拟实验相结 合的方式，对f a s tt c p 协议和现有的r e n o 【2 0 1 、s t c p 2 1 1 、b i c t c p 2 2 】和h s t c p 2 3 】 协议进行了对比分析，研究表明，在各种性能方面，f a s tt c p 协议都具有较好 的表现。同时，对f a s tt c p 协议的协议内公平性进行了分析，通过数学方法和 仿真实验分析了f a s tt c p 产生r 盯不公平性的原因，提出在该算法中添加一 个公平因子，不但可以显著改善其公平性，还可以增加其相对友好性。最后，本 文提出了新算法的设计模型和公平性因子的选取办法。 本文的具体章节内容安排如下： 第一章为绪论部分，介绍了本课题的研究背景和意义，对国内外有关于拥 塞控制算法的研究现状进行了分析，并指出了本文的研究内容和组织结构。 第二章介绍了t c p 拥塞控制协议的基础知识和实现方法，分析了拥塞产生 的原因和危害。并讨论了当前主流的拥塞控制算法，最后给出了拥塞控制算法的 主要评价标准。 第三章重点分析了f a s tt c p 的原理和拥塞控制模型，并详细介绍了研究 拥塞控制的模拟仿真环境n s 2 ，通过该仿真平台对f a s tt c p 、h s t c p 、s t c p 、 b i c t c p 和t c pr e n o 进行了性能比较，并选取综合性能较好的f a s tt c p 作为 主要研究对象。 第四章对f a s tt c p 协议的协议内公平性进行了分析，找出其产生r t t 不 公平性的原因，指出在f a s tt c p 算法中添加一个公平因子，以改善其公平性， 并将改进算法命名为f f a s tt c p 。 第五章提出新算法的设计模型和公平性因子的选取方案，并采用实验证明 了该改进算法不但可以显著改善其公平性，还可以增强其相对友好性。 第六章对全文内容进行了总结，并对当前工作中仍存在的问题进行了分析， 提出了下一步研究工作的设想。 4 硕士学位论文 第二章t c p 拥塞控制机制 2 1 拥塞控制概述 第二章t 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 ) 2 4 】是目前最著名的传输协议，也是 i n t e m e t 的t c p i p 协议家族中的重要协议，在单个网络中也可以使用。t c p 提供 可靠地端到端的数据流传输协议，t c p 协议主要有以下几个特点： ( 1 ) 提供面向连接的服务。发送方和接收方分别利用s o c k e t 原语创建一个 套接字的连接端点。套接字中包含主机的i p 地址及1 6 位端e l 号( t s a p ) 。为了进 行数据传输，必须首先在发送方和接收方的套接字之间建立连接。 ( 2 ) 面向数据流。t c p 实体将从高层接收的数据视为无结构的字节流，在接 收方向高层送交的也是字节流。 ( 3 ) 缓冲传输。当应用程序将数据送给t c p 实体时，t c p 可能将其缓存起来， 累加到一定量后作为数据片发送出去，这样可以提高传输效率。 ( 4 ) 提供可靠性。t c p 采用带重传的肯定确认来进行差错控制和流量控制。 t c p 对那些不按顺序到达的数据包，进行整理，组装成原报文。 ( 5 ) 全双工连接。t c p 允许在两个方向上同时进行传送。数据流服务允许在 一个方向结束数据流动，在另一个方向上数据继续流动。 t c p 的这些特性使得它在低速网络中能够很好的运行，但是，在高速网络中 的性能却不尽如人意，会产生拥塞现象。拥塞的发生和互联网的设计机制有着密 切关系，网络可看作由一个具有确定能力值a 的资源集合组成的，这些资源可 以是传输链路或源端主机。我们将这些资源在模型里定义为链路资源 三= 1 ，2 朋 ，每条链路带宽为a 。这些链路被一个单播数据流的集合共享 i = 1 ，2 n ，流平衡点的发送速率为x = k ；f = l n 。 则对经过链路i 的流i 具有路由矩阵尺 d 一! o ；当源_ 不经过链路， l x l i 一【l ；当源经过链路，( 2 一1 ) 图2 1 给出了一个具体例子： 5 硕i j 学位论文第二章t c p 拥采控制机制 图2 - 1 网络模型 对于以上3 条路径可以分别用路由矩阵表示： r 1 = 1o l 1 o 1 r 2 = ( 1 ，1 ，1 ) t ( 2 2 ) 网络根据服务的特征总体可以分为以下3 类： 1 分组( p a c k e t ) 交换网络 分组交换即包交换，用户想要传送的数据被划分成一定长度的数据段，每个 数据段组成一个分组。为了标示该分组的目的地址，需要在每个分组前加上一个 头部，然后交换机通过每个分组的地址标志，将其转发至目的地。这个过程通常 称为分组交换。进行分组交换的通信网称为分组交换网。分组交换网络是在“存 储一转发”的基础上建立起来的，这种网络结构同时具有电路交换和报文交换的 优点。和电路交换网络相比，分组交换网络提高了资源的利用率，并且可以对传 送的信息进行管理。和报文交换网络相比，分组交换网络具有更好的可靠性和交 互性。另外，分组交换具有很强的信息纠错能力，传输质量高，比较经济实用。 2 无连接( c o n n e c t i o n l e s s ) 网络 顾名思义，无连接的网络【2 5 】是指网络中的节点在数据传输前不需要建立连 接。由于在网络的中间节点上不需要保存和连接相关的信息，这种连接模式可以 简化网络的设计。另外，无连接的网络打破了空间和时间的限制，可以使人们随 时随地享受快捷方便的网络服务。但是该模型也有许多缺点：首先，当许多用户 共享网络时，网络速度会变慢，甚至出现连接中断；其次，无连接的网络没有采 用存储转发机制，没有信息纠错功能，从而造成乱序报文的产生；另外，该模型 对发送源的追踪能力较差，会给网络带来安全隐患。也就是说无连接网络是不保 证服务质量的网络。 3 尽力而为m e s t e 仃o n ) 的服务模型 尽力而为网络由于重视传输速率和结果，它也不对数据传输的服务质量提供 保证。于是最近几年提出了很多新的方案，如集成服务、区分服务等服务模型来 保证网络服务的质量，由于尽力而为网络的服务模型简单实用，在当前和未来的 6 硕：卜学位论文第一二章t c p 拥塞控制机制 网络中，该模型仍占有一席之地。 2 1 1 拥塞产生的原因和危害 拥塞产生的根本原因可以用一个比喻形容。在一条高速公路上，正常的车流 量是每分钟5 0 0 辆，当处于上下班高峰期时，车辆陡然增多，超过了高速公路设 计的最大容量，达到1 0 0 0 辆每分钟，这必然会导致车辆行驶缓慢甚至堵车的发 生。同样的道理，当对网络的需求大于网络的实际承载能力，如果没有相关的机 s u ( 交通警察) 来控制流入网络中的数据量，也必然会导致网络拥塞甚至网络崩溃 的发生。 图2 2 给出了数据吞吐量与给定负载之间的关系。从图中可知，当网络负载 较小的时候，吞吐量的增长和负载呈正比例关系，吞吐量增长迅速；当负载继续 增大，超过最佳操作点之后，网络吞吐量的增长速度慢于输入负载的增长速度， 这是因为网络进入了中等拥塞状态。在这个区域，网络可以继续应付负载，但是 从图2 3 中看出，延迟增加了。 吞 吐 量 z 迳 。 响 应 时 问 o 负载 ( b i t s s ) 图2 - 2 数据吞吐量与给定负载的关系 取i j f tri 厂 i i l c c i 拥塞崩溃区 负载 ( b i t s s ) 图2 - 3 响应时间与给定负载的关系 硕l ：学位论文 第二二章t c p 拥粜控, n l j l , n 这种情况下的吞吐量与理想情况的差别是由许多因素引起的。原因之一是负 载不可能均匀的分布在网络中，因此，当一些节点遇到中等程度的拥塞时，其他 节点则可能要经受严重的拥塞，以至于必须丢弃一些流量。另外，当负载增加时， 网络将试图通过选择穿过低拥塞区的分组路由来平衡负载。为了完成路由选择的 功能，更多数量的路由选择分组必须在节点之间交换以互相提醒要避丌拥塞区， 这种额外开销降低了可用于数据分组的容量。 当网络上的负载继续增加时，各个节点的队列长度也继续增加，直至进入拥 塞崩溃区。其原因是在每个节点中的缓存是有限的，当一个节点的缓存饱和时， 它会丢弃一些分组。这样信源除了传送新的分组外一定会重传被丢弃的分组，而 这只会加剧下列情况：随着越来越多的分组被重传，系统负载增加，越来越多的 缓存变得饱和，这个时候，网络有效容量几乎为0 。 拥塞是一种复杂现象，在网络的各个层次都有可能发生，因此，拥塞控制也 是一个复杂的课题。按照排队理论中的结果，网络是由队列组成的。在一个节点 ( 如交换机、路由器) ，每一个输出信道上都有一个分组队列。如果分组到达和排 队的速率超出分组能够传输的速率，队列大小和延迟都会不停增长。即使分组到 达的速率小于分组传输的速率，如果到达的速率接近传输的速率，队列长度也会 急剧增长。作为一个经验规则，当接受分组排队的线路利用率超过8 0 时，队列 长度的增长就值得警惕了。 有许多原因可以导致拥塞，一种典型的情况是：路由器瞬间在多条输入线路 上有分组流到达，而且这些流都需要同样的输出线路。此时，路由器将建立一个 队列，如果路由器没有足够的内存来存放所有的分组，那么有的分组将被丢弃。 虽然增加一定数量的缓存可以有助于路由器性能的提升，但是正如前面看到的， 如果路由器的缓存无限大，拥塞现在不是好转而是更差。因为当分组到达队列前 端的时候，这些分组可能已经超时，重复分组也已经被发送出来；而且所有这些 分组都将被尽职地转发给下一台路由器，从而增加了到达目标机的整条路径的负 载。在交换机中也存在同样的问题，比如可能有几个端口同时向一个端口转发数 据。 同样，单纯提高网络带宽也不能解决拥塞问题。因为源端不可避免地需要经 过一段时间才能收到关于拥塞的反馈，当传输速度较高时，源端在此之前就已经 发送了大量的数据。因而，如果出现拥塞，发送了更多的数据将会使拥塞变得更 严重。在高速网络流量中，尖峰可能很大，特别是如果流量具有自相似特征时， 捐j 塞可能出现得很快并持续一段时间，以至于在源端做出反应之前网络已经丢弃 了许多分组。 另外，路由器c p u 的处理能力不足以及i n t e r n o t 上网络分布的不均衡性都是 8 硕一l ：学位论文 第二章t c p 拥寒控制机制 产生拥塞问题的原因。首先是资源分布的不均衡，网络在组建之前并没有经过良 好的规划和设计，而是在各种不同容量、不同形式的网络都已经运行起来后才设 法将它们统一连接起来，这样就必然大量存在网络带宽分布不均的情况。其次是 网络流量的不均衡，在某些时刻，各种需求往往导致一些节点上的资源受到大量 的访问和冲击，甚至有些网络攻击行为就是利用这种方法进行对主机和网络的破 坏。 如果对网络拥塞不加以控制，将会产生严重的后果： ( 1 ) 包丢失率增大。由于拥塞，路由器不得不丢弃一些分组，在路由器缓存 溢出的情况下，后到达路由器的分组甚至会被全部丢弃，路由器采用的丢弃策略 直接影响着系统的性能。一般有去尾策略和随机检测丢弃策略。 ( 2 ) 资源利用率降低。拥塞会导致资源利用率的降低，例如路由器缓存被输 入到链路的分组占满后，通过其它链路的分组都会被丢弃，造成这些链路得不到 充分利用。 ( 3 ) 延迟增加。拥塞发生后，路由器缓冲队列长度增加，分组等待发送的时 间变长，糟糕的是随着延迟的增加还会引起超时重传，无休止的重传绝对是网络 的噩梦，这会造成网络资源的极大浪费。 ( 4 ) 导致拥塞崩溃。拥塞的持续恶化会导致拥塞崩溃发生，这是最为严重的 后果，此时几乎没有任何有效的数据传输，网络进入死锁状态。 ( 5 ) 资源无效利用率增加。由于在拥塞节点处分组被丢弃，此前消耗的网络 资源成为无用消耗，这必将造成时间的网络成本的增加。 2 1 2t c p 拥塞控制实现 按照控制论的观点，可以将拥塞控制策略分为两类：开环策略和闭环策略。 开环策吲2 6 】的本质是从一开始就保证问题不会发生，一旦系统启动并运行 起来了，就不需要中途修正，而试图用去良好的设计来解决问题。完成开环控制 的手段有：确定何时接收新的流量、确定何时丢弃分组及丢弃哪些分组，以及在 网络的不同点上执行调度策略。所以这些手段的共同之处是，它们在做出决定的 时候不考虑网络的当前状态。 与开环相对，闭环策吲2 7 】的控制过程主要有拥塞检测、信息反馈和调整系 统运行三个步骤组成。在监视子网的拥塞情况时可以使用多种度量标准，比如被 丢弃分组所占的比例、平均队列长度、超时重传分组的数量、平均分组延迟，以 及分组延迟的标准方差。对于这些度量值，数值越大，表示拥塞的可能性也越大。 t c p 拥塞控制采用的是基于端到端的闭环控制方式。图2 4 是对拥塞控制机 制的一种形象描述。 9 硕十学位论文 第_ 二章t c p 拥寒控制机制 图2 - 4 拥塞控制机制 根据图2 4 所示的闭坏控制系统，如果在时刻t ，某个用户的传送负载为 x 如) ，那么输入网络的总负载应为x 心) 。系统状态用n 为向量 x ( f ) = 肛。( f ) ，x ：( f ) ，x 。( f ) 表示。如果x ，( f ) 不大于网络承受能力x g o a l ， 那么网络运行流畅，如果一旦超过，则网络出现拥塞，需要使用控制策略来减轻 或避免拥塞。 基本的t c p 拥塞控制算法都是通过控制一些重要参数的改变实现的。t c p 用于拥塞控制的主要参数有【2 8 】： ( 1 ) 拥塞窗1 3 ( c w n d ) ：这是拥塞控制的关键参数。它描述发送端在拥塞控制 情况下一次最多能发送数据包的数量。 ( 2 ) 通告窗e l ( a w i n ) ：是接收端给源端预设的发送窗口大小，它只在t c p 连 接建立的初始阶段使用。 ( 3 ) 慢启动阈值( s s t h r e s h ) ：是慢启动阶段和拥塞避免阶段的分界点。一般情 况下，初始值设为6 5 5 3 5 个字节。 ( 4 ) 发送窗i ( w i n ) ：表示发送端实际发送数据的窗1 3 大小。 ( 5 ) 重传定时器( r t o ) ：描述数据包从发送到失效的时间间隔，是判断数据 包丢失与否、网络是否拥塞的重要参数。一般情况下设为2 r t t 或5 r t t 。 ( 6 ) 往返响应时间( r t t ) ：从发送端发送一个数据包开始，到发送端收到接 收端确认该数据包的时i 、日j l 日j 隔。 ( 7 ) 快速重传阈值( t c p r e x m t t h r e s h ) ：能触发快速重传的源端收到重复确认包 a c k 的个数。当此个数超过t c p r e x m a h r e s h 时，网络就进入快速重传阶段。 t c p r e x m t t h r e s h 缺省值为3 。 t c p 协议在i n t e r n e t 中仍然是占主导地位的传输协议。它在应用和网络设备 之间提供了一个接口，应用可以通过这个接口请求一种所需的服务质量。t c p 使用了序列号、校验和、确认以及超时重传等机制，为用户提供了可靠的数据传 输，t c p 拥塞控制的实现主要分为四个阶段： 1 慢启动阶段 1 0 硕上学位论文第二章t c p 拥塞控制机制 当建立一个连接时，t c p 为了充分利用网络带宽，会一次性发送许多数据包， 当超过网络的传输极限，路由器便对后到来的包进行排队，以先来先服务的原则 逐个发送，这自然造成了网络性能的降低。为了处理这种情况就需要慢启动。 开始时发送端将拥塞窗口设置为一个分组，当收到确认后就将拥塞窗口翻倍，直 到其达到慢启动阈值。当拥塞窗口超过慢启动阈值或者当观察到拥塞时，慢启动 结束，进入拥塞避免，如图2 5 所示。 2 拥塞避免阶段 从慢启动可以看到，c w n d 可以很快的增长上来，从而最大程度利用网络带 宽资源，但是c w n d 不能一直这样无限增长下去，一定需要某个限制。t c p 使用 了一个叫慢启动门5 曼( s s t h r e s h ) 的变量，当c w n d 超过该值后，慢启动过程结束， 进入拥塞避免阶段。拥塞避免的主要思想是拥塞窗口加性增加，也就是c w n d 的 值不再呈指数级增长。此时当窗口中所有的报文段都被确认时，c w n d 的大小加 1 ，c w n d 的值就随着i 册丌始线性增加。 拥塞 窗口 c w n d s s t h r e s h = g w n d 2 时间 图2 - 5 慢启动和拥塞避免阶段 3 快速重传阶段 t c p 发送端使用快速重传算法来探测或者修复数据丢失。快速重传算法以三 个重复a c k 的到达( 收到4 个一样的a c k ，其问没有任何其他包到达) 为一个数 据段已经丢失得标志。当收到三个重复的a c k 之后，t c p 不等重传定时器超时 就重传开来已经丢失的数据段，如图2 - 6 所示。 4 快速恢复阶段 在快速重传算法发送了看来已经丢失的数据段之后，快速恢复算法支配新的 数据的传送，直到非重复的a c k 到达。重传了丢失的数据包后，执行的拥塞避 免算法而不是“慢启动”算法，这样可以在中等程度拥塞的情况下缩短到达最佳 传输状态的时间。快速恢复是基于“管道模型( p i p em o d e ) 的“数据包守恒” 原贝l j ( c o n s e r v a t i o no fp a c k e t sp r i n c i p l e ) t 2 9 1 ，即同一时刻在网络中传输的数据包 硕+ 1 j 学位论文第二章t c p 拥塞控制机制 数量是恒定的，只有当“旧”的数据包离开网络后，才能发送“新”的数据包进 入网络。快速重传和快速恢复算法通常结合在一起实施。 拥塞 窗口 图2 - 6 快速重传和快速恢复阶段 2 2t c p 拥塞控制主要算法 时间 根据算法的实现位置，可以将拥塞控制算法分为两大类【3 0 】：链路算法( 1 i n k a 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 m e t 中使用最广泛的传输协议。根据m c i 的统计，总字节数的9 5 和总报 文数的9 0 使用t c p 传输。 链路算法的研究目前集中在主动队列管理( a c t i v eq u e u em a n a g e m e n t ，简称 a q m ) t 3 1 1 算法方面。和传统的队尾丢弃( d r o pt a i l ) 3 2 】相比，a q m 在网络设备的缓 冲溢出之前就丢弃或标记报文。a q m 的主要优点是：( 1 ) 减少网关的报文丢失。 使用a q m 可以保持较小的队列长度，从而增强网关容纳突发流