（计算机软件与理论专业论文）基于高速tcp的网络拥塞性能分析研究.pdf

摘要 摘要 近年来，随着计算机网络的普及和网络用户的急剧增加，网络拥塞控 制机制的研究变得越来越重要。t c p i p 是一项从实践中诞生的，并在实践 中不断得到发展和完善的网络技术，也是目前在i n t e m e t 中使用最广泛，占 主导地位的端到端传输协议。 但是，最近几年1 0 0 0m b p s 以上的高速网络逐渐从实验室转向实际应 用，传统t c p 在这样的网络中运行时，性能受到了限制。因此，f l o y d 提 出了一种高速t c p 算法( h i g h s p e e dt c p , h s t c p ) ，用于提高t c p 在高速网 络中传送数据时的性能。 为此，本文首先分析了i n t e m e t 的体系结构。同时就拥塞的成因，拥塞 控制算法设计的困难，拥塞控制算法的评价标准等相关问题进行了阐述。 其次，在深入分析传统t c p 源算法的基础上，对当前t c p 源算法研究 领域的热点慢启动进行了改进，提出了一种基于比例因子的慢启动策 略。本策略通过引入一个比例因子，使得拥塞窗口的增长能从慢启动阶段 平滑的过渡到拥塞避免阶段，解决了慢启动后期突发数据流和大量丢包的 问题。经仿真验证，改进算法能明显减少丢包和突发数据流量。 最后，由于传统t c p 在高速网络中的局限性，f l o y d 提出了一种解决 这一问题的可行方法h s t c p 。实验表明h s t c p 比标准t c p 能够更充 分的利用带宽，但存在着严重的r t t 不公平性。通过仿真验证和数学分析 对h s t c p 的r t t 不公平性进行研究，然后在原有算法的基础上添加一个 公平性因子来降低由于r t t 不同造成的窗口增长差异。实验表明改进算法 有效保证了h s t c p 流的带宽公平性、降低了丢包率。 关键词t p ；h s t c p , 高速网络；拥塞控制；公平性；慢启动 燕山大学工学硕士学位论文 a b s t r a c t i nt h e s ey e a r s ，w i t ht h ep o p u l a r i z a t i o no ft h ec o m p u t e rn e t w o r ka n dt h e r a p i d l yi n c r e a s i n go f n e t w o r ku s e r s ，t h er e s e a r c ho fn e t w o r kc o n g e s t i o nc o n t r o l a l g o r i t h mb e c o m e sm o r ea n dm o r ei m p o r t a n t t c p i pi san e t w o r kt e c h n o l o g y w h i c hc o m e sl i o mp r a c t i c e sa n di sd e v e l o p e di np r a c t i c e s t c p i pa l s oi st h e m o s tp o p u l a re n d - t o - e n dt r a n s m i s s i o np r o t o c o li nt h ei n t e r n e tn o w , a n dt h e s t a b i l i t yo ft h ei n t e m e th a st h ec l o s er e l a t i o n s h i pw i t ht c p ss u c c e s s f u l c o n g e s t i o nc o n t r o la l g o r i t h r a b u ta l o n gw i t ht h e1 0 0 0m b p sa b o v eh i g h - s p e e dn e t w o r k sg o i n go u to f t h e l a ba n dg o i n gi n t op r a c t i c e ，r e g u l a rt c pd on o ta c h i e v eg o o dp e r f o r m a n c ew h e n r u n n i n go ns u c hn e t w o r k s s of l o y dg i v e saa l g o r i t h mn a m e dh i g h s p e e dt c p 口s t c p ) a i m e dt oa c h i e v eb e t t e rp e r f o r m a n c ei nh i g h - s p e e dn e t w o r k f i r s t l y , t h i sp a p e ra n a l y z e dt h en e t w o r ka r c h i t e c t u r ea n dp o i n t e do u tt h a t n e t w o r kc o n g e s t i o nc l o s e l yr e l a t e dt oi n t e r n e td e s i g n a tt h es a m et i m es o m e r e l a t e ds u b j e c ts u c ha sc a u s eo fc o n g e s t i o n , d i f f i c u l to fa l g o r i t h md e s i g na n d e v a l u a t i o nc r i t e r i ah a v e b e e ni l l u s t r a t e d s e c o n d l y , b a s eo nt h o r o u g hs t u d yt h ec u r r e n tt c ps o u v 七a l g o r i t h m s ，t h i s p a p e ra n a l y z e st h es l o w - s t a r to ft c pc o n g e s t i o nc o n t r o lw h i c hh a sb e e no n eo f h o t s p o t s i nt c ps o l r c 君a l g o r i t h m s t u d ya n d i t s p r o b l e m an e wv a r i a n t s l o w - s t a r ts c h e m ei sp r e s e n t e dw h i c ha p p r o a c h e st h es l o w - s t a r tt h r e s h o l dm o r e g r a d u a l l ya n dr e s o l v et h ep r o b l e mo fb u r s t i n e s sb e t w e e nt h es l o w - s t a r ta n d c o n g e s t i o na v o i d a n c ep h a s e st h r o u g hi n t r o d u c i n gap r o p o r t i o n a lf a c t o r t h e c o m p a r i s o no fn ss i m u l a t i o nr e s u l t ss h o wt h a tt h i sn c 、) l rs l o w - s t a r ts c h e m ec a n s i g n i f i c a n t l yr e d u c eb o t hp a c k e tl o s s e sa n dt r a f f i cb u r s t i n e s s a tl a s t , c u r r e n tt c pc o n g e s t i o nc o n t r o lc a n n o ta c h i e v ee n o u g hb a n d w i d t h i nh i g h - s p e e dn e t w o r k s ，h s t c ph a sb e e np r o p o s e da so n eo ft h ep o s s i b l ew a y s a b s t r a c t t os o l v et h i sp r o b l e m e x p e r i m e n t sr e v e a l e dt h a th s t c pc a l ll l s et h eb a n d w i d t h m a r cs u f f i c i e n tt h a nc u r r e n tt c p b u ti th a ss e v e r er 丌u n f a i r n e s s i nt h i sp a p e r , w ef i r s ti n v e s t i g a t et h er t tu n f a i r n e s st h r o u g hm a t h e m a t i c a la n a l y s i sa n d s i m u l a t i o ns t u d i e s a n dt h e nw ea d daf a i rf a c t o rt ot h eh s t c pt od e c r e a s et h e d i f f e r e n c eo fw i n d o wi n c r e a s ec a u s e db yd i f f e r e n tr t t e x p e r i m e n t ss h o wt h a t t h em o d i f i e da l g o r i t h mc a l lg u a r a n t e et h eb a n d w i d t hf a i r n e s so fh s t c pf l o w s a n dr e d u c et h ep a c k e t sl o s sr a t e k e y w a r d st c p ；h s t c p ；h i g h - s p e e dn e t w o r k ；c o n g e s t i o nc o n t r o l ；f a i r n e s s ； s l o w - s t a r t 燕山大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文基于高速t c p 的网络拥 塞性能分析研究，是本人在导师指导下，在燕山大学攻读硕士学位期间独 立进行研究工作所取得的成果。据本人所知，论文中除己注明部分外不包 含他人已发表或撰写过的研究成果。对本文的研究工作做出重要贡献的个 人和集体，均已在文中以明确方式注明。本声明的法律结果将完全由本人 承担。 作者签字t 分脊裔日期：2 。0 7 年，月，日 燕山大学硕士学位论文使用授权书 基于高速t c p 的网络拥塞性能分析研究系本人在燕山大学攻读硕 士学位期间在导师指导下完成的硕士学位论文。本论文的研究成果归燕山 大学所有，本人如需发表将署名燕山大学为第一完成单位及相关人员。本 人完全了解燕山大学关于保存、使用学位论文的规定，同意学校保留并向 有关部门送交论文的复印件和电子版本，允许论文被查阅和借阅。本人授 权燕山大学，可以采用影印、缩印或其他复制手段保存论文，可以公布论 文的全部或部分内容。 保密口，在年解密后适用本授权书。 本学位论文属于 不保密囱。 ( 请在以上相应方框内打“4 ”) 作者签名：信香宦日期：7 0 7 年，月1 1 日 导师签名：猡卅j 边 日期：z 。7 年f 月，f 日 第1 章绪论 1 1 研究背景和意义 第1 章绪论 随着i n t e m e t 的迅猛发展和用户数量的剧增，互联网的规模日益增大， 网上业务变的日益繁忙。通信量的迅猛增长使得主干网日益拥塞，新业务 的涌现对网络提出更高的服务质量要求，承载的业务种类也在不断增加。 为了确保互联网能够正常运转，必须要考虑网络的拥塞控制【1 ( n e t w o r k c o n g e s t i o n ) f 司题。 端到端的拥塞控制是目前i n t e m e t 的一个研究热点。在最初的t c p 协 议中只有流控制而没有拥塞控制，接收端利用t c p 报头将接收能力通知发 送端。这样的控制机制只考虑了接收端的接收能力，而没有考虑网络的传 输能力，导致了网络崩溃的发生。1 9 8 6 年1 0 月，由于拥塞崩溃的发生，美 国l b l 到u cb e r k e l e y 的数据吞吐量从3 2k b p s 跌落到4 0b p s ，近1 0 0 0 倍 的性能下降使网络几乎瘫痪l l 】。为了解决网络拥塞问题，1 9 8 8 年j a c o b s o n 在文献【1 】中首次提出了网络拥塞避免和网络拥塞控制理论，为此后网络拥 塞控制的研究奠定基础。现在，网络拥塞控制已经成为确保i n t e r a c t 鲁棒性 的关键因素，也是各种管理控制机制和应用的基础。另一方面，据统计 i n t e m e t 上9 5 的数据流使用的是t c p i p 协议【2 卅，因此对i n t e m e t 拥塞问 题的研究主要集中于t c p i p 拥塞控制。实践表明i n t e m e t 的飞速发展也得 益于t c p f i p 拥塞控制机制。t c p i p 中使用的拥塞控制算法已经成为保证 i n t e m e t 稳定发展的重要因素p j 。 近年来，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 ) 、快速重传( f a s tr e t r a n s m i t ) 、快速恢复( f a s t r e c o v e r y ) 、选择性应答( s a c k ) 等，大大提高了网络传输的性能。t c p 解决 拥塞是采用基于窗口的端到端的算法，以前主要有两种：t a h o e 和r e n o ， 分别对通过重复应答所判断出的丢包现象进行不同的处理。t a h o e 在超时或 燕山大学工学硕士学位论文 者收到重复的应答时一律认为网络发生了拥塞。而r e n o 在收到重复的应答 时却认为网络可能是暂时的而不是持久的拥塞。r e n o 可能导致在同一窗口 中出现多包丢弃的现象，t a h o e 包括慢启动，拥塞避免和快速重传等几个主 要阶段。后来随着网络技术的发展在r e n o 算法的基础上出现了算法 n e w - r e n o 和s a c k 。 近年来，高速率的网络如lg b p s 以上的网络己经从实验室转向实际应 用1 7 , 8 】。在数据网格网络和存储网络( s a n ) 中，网络主机通常会有吉比特的 网络接口直接连接到高速网络上。为了移动程序数据，备份或同步数据库， 通常会传输上g b 甚至是t b 的数据。在这种情况下，如果用来做大量数据 传输的话，现有的广泛应用的普通t c p 实现( 如t c pr e n o 版本) 己经不能获 得足够的吞吐量去满足以上的应用。所以，出现了高速t c p ( 例如 h s t c p 。s t c p 。f a s t t c p 等1 眇“1 。 1 2 研究现状分析 为了更好的研究网络拥塞，本节首先对i n t e r n e t 网络模型以及拥塞控制 算法的分类进行介绍，并在此基础上进一步对拥塞控制算法的研究现状进 行介绍。 1 2 1i n t e m e t 网络模型 拥塞现象的发生和i n t e r a c t 的设计机制有着密切的关系，i n t e m e t 的网 络模型可以用以下几点来抽象1 1 2 1 。 ( 1 ) 数据包交换网络与电路交换网络相比，由于包交换网络对资源的 利用是基于统计复用的，因此提高了资源的利用效率。但在基于统计复用 的情况下，很难保证用户的服务质量( q u a l i t yo f s e r v i c e ，q o s ) ，并且很容易 出现数据包“乱序”的现象，对乱序数据包的处理会大大增加拥塞控制的 复杂性。 ( 2 ) 无连接网络互联网的节点之间在发送数据之前不需要建立连接， 从而简化了网络的设计，网络的中间节点上无需保留和连接有关的状态信 2 第1 章绪论 息。但无连接模型很难引入接纳控制，在用户需求大于网络资源时难以保 证服务质量；此外，由于对数据发送源的追踪能力很差，给网络安全带来 了隐患：无连接也是网络中出现乱序数据包的主要原因。 ( 3 ) “尽力而为”的服务模型不对网络中传输的数据提供服务质量保 证。在这种服务模型下，所有的业务流被“一视同仁”的公平的竞争网络 资源，它尽最大努力将数据包送达目的地。但对数据包传递的可靠性、延 迟等不能提供任何保证。这很适合e m a i l 、f t p 、w w w 等业务。但随着互 联网的飞速发展，口业务也得到了快速增长和多样化。特别是随着多媒体 业务的兴起，计算机已经不是单纯的处理数据的工具。这对互联网也就相 应地提出了更高的要求。对那些有带宽、延迟、延迟抖动等特殊要求的应 用来说，现有的“尽力而为”服务显然是不够的。 同时，在资源分配和拥塞控制中还用到以下网络模型。g ，s ) t b 】为所有 链路的集合，其中三= l ，2 ，工 ，对某一特定的链路，l ，其传输能力或带 宽为q 0 ；肛 l ，毋为网络中信源集合，信源s s 途径链路的集合为 工( s ) c 工；对任一链路j ，令s q ) = 扣e s lz 工( j ) ) 。假设某一时刻信源集合 s 是固定的，根据某一带宽分配原则分配给信源s 的带宽为葺 0 ，则带宽 分配应满足以下限制条件： 芝：t g ，z = l ，l ( 1 一1 ) 1 2 2 拥塞控制算法分类 拥塞控制算法虽然是多种多样，但一般可以从以下两个方面对其进行 分类【1 4 1 。 ( 1 ) 控制论的角度分为开环和闭环。当流量特征可以准确规定，性能 要求可以事先获得时，适于使用开环控制；当流量特征不能准确描述或者 当系统不提供资源预留时，适于使用闭环控制。开环的关键是通过事先良 好的设计来避免拥塞出现，确保问题已开始就不会发生。闭环的解决方案 是建立在反馈的基础之上。 ( 2 ) 算法的作用位置角度分为链路算法和源端算法【1 5 】。链路算法在网 燕山大学工学硕士学位论文 络设备( 如路由器和交换机) 中执行，作用是检测网络拥塞的发生，产生拥塞 反馈信息。源端算法在主机和网络边缘设备中执行，作用是根据反馈信息 调整发送速率。拥塞控制算法设计的关键问题是如何生产反馈信息和如何 对反馈信息进行响应。两种算法在网络中的分布如图1 - 1 所示。 图l - 1 算法分布 f i g 1 - 1l o c a t i o no f a l g o d t h m s 源端算法主要是指t c p 协议中基于端到端的拥塞控制算法；链路算法 主要集中在主动队列管理a q m 的研究。本文以下将主要依据第二类分类方 法，将拥塞控制算法分为p 链路算法和t c p 源端算法。 1 2 3 拥塞控制算法研究现状 自从1 9 8 6 年1 0 月，互联网历史上第一次由拥塞引起的网络崩溃发生。 1 9 8 8 年j a c o b s o n 首次将端到端的拥塞控制算法引入到t c p 传输协议中，此 后，许多科研人员致力于t c p 拥塞控制策略的研究。针对t c p 拥塞控制中 存在的问题进行了方方面面的改进【1 6 1 ，以便使它能够更好的符合各种网络 应用的需要、适应网络动态变化的特性，使网络运行在最佳状态。 1 9 9 0 年，j a c o b s o n 在t c pr c n o 算法中添加了快速重传及丢失恢复算法。 为了解决t c pr e n o 算法中存在的不足，n e w - r e n o 、s a c k 和f a c k 等算 法提出了相应的解决方案。n e w - r e n o 算法【l 不依赖于重传定时器，利用一 个a c k 确认部分发送窗口，立即重传余下的数据包，尽力避免在快速恢复 阶段的许多重传超时；s a c k 算澍埔】对数据包进行有选择的确认和重传， 4 第1 章绪论 避免不必要的重传，减少时延，但是s a c k 需要修改t c p 协议；提出了一 种快速重传的改进算法，可以不必等待重传超时就能够从多包丢失中恢复。 文献【1 9 】建议在发生拥塞时，使用一种动态恢复机制代替快速恢复算法从丢 包中恢复。一些研究人员发现，当发送方的拥塞窗口较小时，t c p 的丢失 恢复策略不能很好地工作。例如，由于发送的数据量有限，或受到接收方 通告窗口的限制等，对此，文献 2 0 1 提出了相应的解决方案，指出可以在快 速恢复阶段发送方接收到两个连续的重复a c k 时发送一个新的数据包。 1 9 9 5 年，l a w r e n c e 提出了不同于t c p 基于包丢失率的拥塞控制机制， t c p - v e g a s 算法【2 l j 通过在源端监测i u t 的改变来控制拥塞窗口c w n d ，如果 发现r t t 显著增加，便认为网络发生拥塞，减小c w n d ；如果尉丌变小， 就认为拥塞己经解除，再次增加c w n d 。v e g a s 的缺点是在竞争带宽时会导 致不公平性问题。 为了满足高速网络的发展，2 0 0 2 年，m a r kh a n d l e y 等人提出了x c p 拥 塞控制算法；2 0 0 3 年，s f l o y d 提出了h s t c p ( h i g h s p e e dt c p ) 拥塞控制算 法；同年，t k e l l y 提出了s c a l a b l et c p 拥塞控制算法；2 0 0 4 年，s h l o w 在t c p v e g a s 的基础上提出了f a s tt c p 拥塞控制算法。 1 3 研究内容 本文对l m t e m e t 中的t c p i p 拥塞控制机制进行了探讨，在深入分析已 有算法的基础上，基于n s 环境对高速t c p 源算法以及标准t c p 算法展开 了研究。首先，针对t c p 源端算法的研究热点之一慢启动，提出了一种基 于比例因子的t c p 慢启动策略；其次，在分析研究现有公平性算法的基础 上提出了一种基于h s t c p 改进的公平性算法。并且通过仿真实验来验证它 们的有效性。 1 4 论文结构 本文各章节的组织结构如下。 燕山大学工学硕士学位论文 第1 章为绪论，对课题研究的背景和现状做了介绍，提出拥塞研究的 必要性和迫切性，说明了拥塞研究的方法和途径，拥塞研究包括的主要方 面，还指出了使用网络仿真软件进行拥塞算法的仿真和研究非常的有效和 方便。 第2 章主要介绍t c p 进行拥塞控制的背景知识，分析了网络拥塞的成 因，拥塞控制算法设计的困难，评价拥塞控制算法的标准等基础知识，为 后继的研究打下基础。 第3 章是本文的主要研究内容之一，在介绍传统t c p 拥塞控制的基础 上，对已有t c p 源算法进行了深入分析之后，针对现有t c p 源算法存在的 问题之一慢启动，提出了一种基于比例因子的t c p 慢启动策略并进行了仿 真实验对比。 第4 章是本文的另一个研究重点，首先分析了传统t c p 在高速网络的 局限性和h s t c p 算法的原理，然后通过仿真实验验证h s t c p 确实存在严 重的r 1 盯不公平性并通过理论分析了产生r t t 不公平的原因，最后以新的 思想提出了一种基于h s t c p 改进的公平性算法，并通过编程实现仿真与已 有算法进行了大量对比。 最后总结全文并对未来的研究方向进行了展望。 6 第2 章拥塞控制 第2 章拥塞控制 2 1 开放系统互联模型( o s l l 开放系统互联参考模型o s i ( o p s y s t e mi u t e r c o n n e c t i o nb a s i c r e f e r e n c em o d e l ) ，是实现网络互联的基础。 2 1 1o s i 层次结构 成立于1 9 4 7 年的国际标准化组织i s o ( i n t e m a t i o n a ls t a n d a r d s o r g a n i z a t i o n ) 是个多国团体，专门就一些国际标准达成世界范围的一致。覆 盖网络的所有方面的i s o 标准就是开放系统互联参考模型o s i 的国际标准 i s o o s l 7 4 9 8 ，如图2 1 所示。开放系统是许多协议的集合，它使得两个不 同的系统能够通信，而不管它们底层体系结构是什么样子。 图2 一lo s l 模型 f i g 2 - 1o s lm o d e l 但是，o s i 模型仅仅表示了每层应该作什么，并没有对每一层的协议 进行确切的描述，因而o s i 模型并没有被真正实现，它只代表一个理想化 的网络结构，主要用于教学和网络协议设计的参考。o s i 模型是按层次划分 7 7 6 5 4 3 2 ， 燕山大学工学硕士学位论文 的【2 2 】，它包括七个分离的但又相关的层次。 2 1 2 服务、接口和协议 由于错误的时间、错误的技术、错误的实现和错误的政策，使得o s i 模型没有被实际网络设计所采用。但是o s i 提供了3 个有益的概念：服务、 接口和协议。它们的定义如下。 ( 1 ) 服务每一层都为其直接相邻上层提供相应的服务，每层的服务定 义该层能做什么，而不管上层如何访问它和该层如何工作和怎样实现。服 务是通过一些服务原语向上层提供的。 ( 2 ) 接口接口是相邻层之间相互通信的一个服务访问点。每一层的接 口告诉上层的进程如何访问它。它定义了调用的参数以及预期的返回结果。 同样，它也和该层如何工作无关。 ( 3 ) 协议协议是网络对等实体之间相互通信所遵循的一组规则和约 定。某一层中采用的协议是该层的内部事务，它可以采用任何协议，只要 能完成该层所提供的服务。也可以改变使用的协议而不影响到它上面的层。 o s i 模型中的协议具有很好的隐蔽性。 2 2 网络拥塞控制 网络拥塞指的是在包交换网络中由于传送的包数目太多，而存贮转发 节点的资源有限而造成网络传输性能下降的情况。 2 2 1 拥塞和拥塞控制 当网络中传输的数据包的数量过多时，网络的性能会下降，这种现象 称为拥塞【1 2 j ，即对网络资源的需求大于网络本身拥有的资源。在网络发生 拥塞时，会导致吞吐量下降，严重时会发生拥塞崩溃现象。f l o y d 总结出拥 塞崩溃主要包括以下几种：传统的崩溃、未传送数据包导致的崩溃、由于 数据包分段造成的崩溃、日益增长的控制信息流造成的崩溃等。 对于拥塞现象，可以进一步用图2 2 来描述。当网络负载较小时，吞吐 8 第2 章拥塞控制 量基本上随着负载的增长而增长，呈线性关系，响应时间增长缓慢。当负 载达到网络容量时，吞吐量呈现出缓慢增长，而响应时间急剧增加，这一 点称为k n e e 。如果负载继续增加，路由器开始丢包，当负载超过一定量时， 吞吐量开始急剧下降，这一点称为c l i f f o 拥塞控制机制实际上包含拥塞避 免和拥塞控制两种策略。前者的目的是使网络运行在k n e e 附近，避免拥塞 的发生；而后者则是使得网络运行在c l i f f 的左侧区域。前者是一种“预防” 措施，维持网络的高吞吐量、低延迟状态，避免进入拥塞；后者是一种“恢 复”措施，使网络从拥塞中恢复过来，进入正常的运行状态。 删 一 帕 网络负载网络负载 图2 - 2 网络负载与吞吐量及响应时间的关系图 f i g , 2 - 2n e t w o r kl o a da n dt h r o u g h p u ta n dr t tr e l a t i o n s 拥塞控制算法包含拥塞避免和拥塞控制这两种不同的机制。拥塞控制 是“恢复”机制，它用于把网络从拥塞状态中恢复出来；拥塞避免是“预 防”机制，它的目标是避免网络进入拥塞状态，使网络运行在高吞吐量、 低延迟的状态下。 2 2 2网络拥塞的原因 随着通信和计算机技术的成熟和发展，互联网规模的增长，网络用户 和网络应用都在快速地增长，人们对包括话音、文字、数据、图像等多种 媒体通信的需求不断增大。在计算机网络中有许多网络资源，如链路的容 量、交换节点中的缓冲区和处理机等。如果在某段时间，用户( 端系统) 加于 网络的负载大于网络资源容量和处理能力，就会产生拥塞，网络的性能就 要变坏。若网络中的许多资源同时产生拥塞，网络的性能就要明显变差， 9 燕山大学工学硕士学位论文 整个网络的吞吐量将随输入负载的增大而下降，表现为数据包时延增加、 丢弃概率增大、上层应用系统性能下降等。可以将出现资源拥塞的条件写 成如下公式： y 对资源的需求 可用资源 分析网络拥塞的种种现象，其产生的直接原因【2 3 】有以下3 点。 ( 1 ) 路由器的缓存不足当多个分组突然从不同的输入线路涌入路由器 时，这些分组就要在路由器进行排队，如果路由器没有足够的缓存存储分 组，就会使得一些分组被丢弃。虽然增加缓存对这一问题会有所帮助，但 n a g l e 在文献 2 4 1 q a 指出过大的缓存反而会导致拥塞的恶化，因为当分组最 终排到队头时，源端早己超时重发。实际上，太多的缓存远比较少的缓存 危害更大。 ( 2 ) 链路带宽不足高速链路和低速链路的不匹配或者多条输入带宽总 和大于输出带宽容量，都会使路由器中数据到达率远远大于离去率，从而 导致长队列，缓冲区填满，进而导致拥塞。 ( 3 ) 处理器速度慢如果路由器的c p u 在执行排队缓存，更新路由表等 功能时，处理速度跟不上高速链路，也会产生拥塞。同样，低速链路对高 速c p u 也会产生拥塞。 虽然拥塞是由于资源短缺引起的，但不幸的是，仅仅依靠增加资源却 无法解决拥塞问题，它只会转移网络瓶颈。所以如何有效的和公平的分配 好现有资源对拥塞控制就显得尤为重要。实质上拥塞控制和资源分配是同 一事物的两个方面1 2 5 1 。一方面，如果网络在资源分配方面采取了积极的措 施( 如严格的资源预定) ，就可以避免拥塞。另一方面，可以对资源分配不加 以限制，发送方想发多少就发多少，然后当拥塞发生时再恢复。这种方式 实现容易，但对网络有破坏性。折中的方法是即采取一些资源分配措施， 又允许一定的拥塞发生，结合资源分配和拥塞控制进行拥塞检测和恢复， 两者良好的结合对网络的良好运行起着十分重要的作用。 2 2 3网络拥塞的危害 如果对网络拥塞不加以控制，就会使得包丢失率增加、延迟增大、系 i o 第2 章拥塞控制 统吞吐量降低，严重的还会导致拥塞崩溃的发生。拥塞的危害具体表现为 以下几个方面。 ( 1 ) 延迟增加拥塞发生时，路由器缓冲队列长度增加，分组等待排队 输出的时间变长，进而导致延迟的增加。糟糕的是随着延迟的增加还会引 起超时重传，更多的分组进入网络，进一步加重拥塞程度。 ( 2 ) 包丢失率增大由于拥塞，路由器不得不丢弃一些分组，在路由器 缓存溢出的情况下，随后到达路由器的分组都会被丢弃。路由器采用的丢 弃策略，直接影响系统的性能。 ( 3 ) 资源利用率降低拥塞导致资源利用率降低，例如：路由器缓存被 输出到一条链路的分组占满，此后通往其他链路的分组都会被丢弃，造成 这些链路得不到充分利用。 ( 4 ) 资源无效利用率增加在拥塞节点处被丢弃的分组，此前消耗的网 络资源都成为无效资源被消耗，降低了资源的有效利用率。 ( 5 ) 导致拥塞崩溃拥塞的持续恶化，会导致拥塞崩溃的发生。这是最 为严重的后果。此时，几乎无任何有效的数据传输，网络进入死锁状态。 f l o y d 在文献 2 6 】中总结了拥塞崩溃的几种形式，分别为：负载崩溃、 为到达分组导致的崩溃、分段重装导致的拥塞崩溃、过时分组导致的拥塞 崩溃以及控制分组流量增加导致的拥塞崩溃。 2 3 拥塞控制算法的设计 下面简要介绍了拥塞控制算法设计中存在的困难及算法的评价标准。 2 3 1网络各层策略对算法设计的影响 拥塞控制不仅仅是网络单独某一层的问题，数据链路层、网络层和传 输层所采用的设计策略都直接或间接的影响着拥塞控制算法的设计，成为 拥塞控制算法设计困难的主要原因之一鲫。 ( 1 ) n 络层网络层采用的连接机制( 虚电路或数据报) 决定了只能使用 拥塞控制方式。路由算法同样影响着拥塞控制，好的路由算法能通过将负 燕山大学工学硕士学位论文 载分散到各条链路来避免拥塞，坏的路由算法会将过多的分组加载到本已 拥塞的链路上。 ( 2 ) 传输层往返时延的计算和超时的设定、采用的重传策略都会影响 基于超时的拥塞控制算法的稳定性如果采用累计确认，虽减少了负载，但 却增加了反馈延迟。传输层采用的流量控制策略影响着使用何种拥塞控制 ( 基于窗口或基于速率) 。 ( 3 ) 数据链路层数据链路层所采用的策略如：重传策略、确认策略、 流量控制策略等对拥塞的影响和传输层类似，只是数据链路层的机制只作 用于每个跳段之上。另一方面，拥塞控制机制必须满足低开销、公平性、 动态适应性、未定性和全局性等要求，使得很难设计出一个理想的拥塞控 制算法。 2 3 2 拥塞控制算法设计的困难 拥塞控制算法设计的困难体现在以下几个方面 2 5 1 。 ( 1 ) 算法的分布性拥塞控制算法的实现分布在多个网络节点中，必须 使用不完整的信息完成控制，并使各节点协调工作，还必须考虑某些节点 工作不正常的情况。 ( 2 ) 网络环境的复杂性i n t e h m c t 中各处的网络性能有很大的差异，算法 必须具有很好的适应性。另外，由于i n t e m e t 对报文的正确传输不提供保证， 算法必须处理报文丢失乱序等情况。 ( 3 ) 算法的性能要求拥塞控制算法对性能有很高的要求，包括算法的 公平性、效率、稳定性和收敛性等。某些性能目标之间存在矛盾，在算法 设计时需要进行权衡。 ( 4 ) 算法的开销拥塞控制算法必须尽量减少附加的网络流量，特别是 在拥塞发生时。在使用反馈式的控制机制时，这个要求增加了算法设计的 困难。算法还必须尽量降低在网络节点上的计算复杂性。 2 3 3 拥塞控制算法的评价标准 衡量拥塞控制算法的好坏，需要一定的评价标准。由于拥塞控制是与 第2 章拥塞控制 全局资源分配密切相关的问题，所以通常用以下四个指标来评价拥塞控制 算法。 ( 1 ) 效率主要考虑吞吐量和延迟。总希望获得尽可能大的吞吐量和尽 可能小的延迟。但两者很难兼得，要提高吞吐量就得允许尽可能多的分组 进入网络，只就会增加路由器队列的长度，从而导致延迟的加大。可以用 能力( p o w e r ) 函数来描述两者的关系： p o w e r = t h r o u g h p u t “d e l a y ，( 0 a s s t h r e s h ， t c p 就执行拥塞避免算法。此时，c w n d 在每次收到一个a c k 时只增加 1 c w n d 个数据包，这样，在一个r t t 内，c w n d 将增加1 ，所以在拥塞避免 阶段，c w n d 不是呈指数增长，而是线性增长。 ( 3 ) 快速重传和快速恢复阶段快速重传是当t c p 源端收到三个相同的 a c k 副本时，即认为有数据包丢失，则源端重传丢失的数据包，而不必等 待r 1 d 超时。同时将s s t h r e s h 设置为当前c w n d 值的一半，并且将c w n d 减 为原先的一半。快速恢复是基于“管道”模型的“数据包守恒”的原则， 1 9 燕山大学工学硕士学位论文 即同一时刻在网络中传输的数据包数量是恒定的，只有当“旧”数据包离 开网络后，才能发送“新”数据包进入网络。如果发送方收到一个重复的 a c k ，则认为已经有一个数据包离开了网络，于是将拥塞窗口加1 。如果“数 据包守恒”原则能够得到严格遵守，那么网络中将很少会发生拥塞；本质 上，拥塞控制的目的就是找到违反该原则的地方并进行修正。 口古 徊 豢 u 时间 图3 3 慢启动和拥塞避免 f i g 3 - 3s l o w - s t a r ta n dc o n g e s t i o na v o i d a n c e 丑 佃 蒜 霉 时同 图3 4 快速重传和快速恢复 f i g 3 - 4f a s tr e t r a m m i ta n df a s tr e c o v e r y t c p 使用下面的公式来调整自己拥塞窗口的大小。 ( 1 ) 慢启动阶段当算法进入慢启动阶段时【6 】，拥塞窗口洲，耐首先被设 置为一个分组大小。此后，源端每收到一个a c k ，c w n d 就增加一个分组。 一个r 丁丁后c w n d 变为原来的两倍，即在慢启动阶段c w n d 随r t t 呈指数增 长，直到大于s s t h r e s h 为止。慢启动算法可以简单的描述为： i n i t i a l ：o w n d = 1 ； f o re v e r ya c k 第3 章基于比例因子的t c p 慢启动研究 i f f c w n d s s t h r e s h ) t h e nn 州萨阡；) 在开始新建一个连接时，慢启动阶段c w n d 从1 个分组大小按照指数方式增 长，逐渐的搜索网络的可用带宽。标准慢启动算法拥塞窗口的增长如图3 5 所示。 2 i 盯t 图3 - 5 慢启动示意图 f i g 3 - 5f i g u r eo f s l o w - s t a r t ( 2 ) 拥塞避免阶段每收到一个a c k ： c w n d = c w n d 4 - 旦_( 3 1 ) c ，加 发生一次丢包： c w n d = e w n d - b c w n d ( 3 2 ) 式中a , b ，c 是以m s s ( m a x i m u ms e g m e n ts i z e ，最大分段大小) 为单位的，在传 统t c p 中a = 1 , b = 0 5 c = 1 。 3 2 3 几种传统t c p 的拥塞控制算法 经过十多年的发展，目前t c p 协议主要包含有四个版本【1 4 】：t c pt a h o e 、 t c pr e n o 、t c pn e w r e n o 和t c ps a c k 。下面分别介绍一下这几种主要的 燕山大学工学硕士学位论文 算法。 ( 1 ) t c pt a h o e t c pt a h o e 是在早期t c p 实现中为了减少拥塞现象，加 了很多新算法，作了改进而得到的，目的是在保持良好的用户通信的吞吐 量的同时，控制网络拥塞。新算法包括慢启动、拥塞避免，快速重传，另 外对往返时间的计算作了改进，以便更好地设定超时重发时间片大小，但 不包括快速恢复。 ( 2 ) t c pr e n ot c pr e n o 实现也具有t c pt a h o e 实现中这些增强的功 能，但修改了快速重传操作，使用了快速恢复算法。新算法避免了在快速 重传之后通道为空的现象，这样也就避免了在单个报文丢失后，需要用慢 启动去重填通道。快速重传是假定每接收一个重复的a c k 就表示有一单个 报文离开了通道，因此在快速重传期间，t c p 源端能够较好地估计出出现 的数据量，故可避免爆发流的产生。目前，t c pr e n o 是使用最为广泛的t c p 实现。 ( 3 ) t c pn e w - r e n o t c pn e w - r e n o 主要是对t c pr e n o 算法做了一些 小改变，以解决一些性能问题，它能消除有多个报文从一个窗口丢失时对 重发计时器的等待。这种改变考虑了源端在快速重传期间的特性，即收到 的“恢复a c k ”是确认部分而不是全部出现在快速恢复开始时的报文。在 t c p r e n o 中，“恢复a c k ”使可用窗口降回到拥塞窗口大小，从而使t c p 结束快速恢复，而在t c p n e w - r e n o 中，“恢复a c k ”并不结束快速恢复， 相反在快速恢复期间接收的“恢复a c k ”被认为是那些在序列空间中紧跟在 被确认的报文之后的报文已经丢失，必须重发，因此当在一个数据窗口中 有多个报文丢失时，t c p n e w - r e n o 不需重发等待就可恢复，每个往返时间 重发一个丢失的报文，直到从该窗口中丢失的报文全部被重发。t c p n e w - r e n o 直到所有在快速恢复开始时出现的数据都被确认，才会退出快速 恢复。 ( 4 ) t c ps a c k 较简单的t c ps a c k 实现，其拥塞控制算法也是对t c p r e n o 拥塞控制算法的一种简单改进，它们在扩大和减小拥塞窗口上使用的 是相同的算法。在t c p 中增加s a c k 并不改变拥塞控制的基本算法，t c p s a c k 实现保留了t a h o e 和t c pr g l l o 在报文失序时的健壮性，且在必要的 第3 章基于比例因子的t c p 慢启动研究 时使用重发计时等待来进行恢复。s a c k 和t c pr 盯i o 实现的主要差别在于： 当多个报文从一个数据窗口丢失时的性能和所采取的对策。t c ps a c k 和 t c p r e n o 实现一样，当数据发送端收到t e v r e x m t t h r e s h 个重复的a c k 时就 进入快速恢复，发送端重发报文，并把拥塞窗口减小一半。在快速恢复中， s a c k 保持了一个变量p i p e ，用它来表示出现在路由上的报文的估计数量， 这与t c pr e n o 实现的机制不同。当p i p e 小于拥塞窗口大小时，发送端只 发送新的或己重发过的数据。当发送端发送一个新报文或重发一个老报文 时，p i p e 值