（信号与信息处理专业论文）高带宽时延网络模型中xcp的性能研究.pdf

| l i i ii i ii iiii i ii ii iiiil y 17 8 0 8 5 9 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 提供阅览服务，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。 同意学校向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：身酾丽 导师签名：协 签字日期：勾年月甜日签字r 期：声矽年月夕铲同 l ，博 j 】 中图分类号：t n 9 1 u d c ：6 5 4 学校代码：1 0 0 0 4 密级：公开 北京交通大学 硕士学位论文 高带宽时延网络模型中x c p 的性能研究 p e r f o r m a n c er e s e a r c ho nx c pf o rh i g hb a n d w i d t hd e l a yn e t w o r k m o d e l 作者姓名：宋丽丽 导师姓名：肖扬 学位类别：工学 学号：0 8 1 2 0 4 3 9 职称：教授 学位级别：硕士 学科专业：信号与信息处理 研究方向：通信与信息处理 北京交通大学 2 0 1 0 年6 月 致谢 本论文的工作是在我的导师肖扬教授的悉心指导下完成的，肖扬教授严谨的 治学态度和科学的工作方法给了我极大的帮助和影响。在此衷心感谢两年来肖扬 老师对我的关心和指导。 鲁凌云老师悉心指导我们完成了实验室的科研工作，在学习上和生活上都给 予了我很大的关心和帮助，在此向鲁凌云老师表示衷心的谢意。 在实验室工作及撰写论文期间，特别感谢毛鹏轩师兄，他对我论文中的x c p 协议研究工作给予了热情帮助，他优秀的工作给了我很大的启发。感谢刘之幸、 刘晓丽和刘静这三位女性同门，对我这两年的关照，以及在找工作方面的经验交 流。感谢王磊、刘晏昌和王铠尧的关照，也要感谢张南学姐和诸位学弟妹们，是 他们一起创造了良好的实验室学术氛围，在此向他们表达我的感激之情。 另外也感谢家人、朋友，他们的理解和支持使我能够在学校专心完成我的学 、i k 。 中文摘要 中文摘要 摘要：当前的技术发展趋势表明，未来网络将呈现带宽时延乘积( b a n d w i d t h d e l a y p r o d u c t ，b d p ) 较大的特点。当网络b d p 增加时，t c p 协议的性能将严重下降， 其不仅不能有效地利用高带宽，而且在高速网络中传输速率很不稳定，成为实施 各种新型网络应用的巨大障碍。针对以上问题，d i n ak a t a b i 提出了一种新的显式 控制协议( e x p l i c i tc o n t r o lp r o t o c o l ，x c p ) 。x c p 采用终端与路由器联合设计的思 想，即通过中间路由器通知终端瓶颈链路的拥塞程度，实现高利用率、低排队时 延和几乎为零的丢包率，同时具有很好的扩展性。无论在传统的还是高带宽时延 乘积网络环境下，x c p 比t c p 在效率性、公平性以及稳定性方面都表现的更出色。 本文首先分析了t c p 协议存在的不足，然后对x c p 协议的结构和执行算法进 行详细阐述，并对x c p 协议做了相应的仿真与性能分析。x c p 是考虑较全面并且 可行的协议，是未来高带宽时延乘积网络协议中的强有力竞争者，因此我们对x c p 协议做了进一步研究改进。本文的改进工作主要有两方面：第一，通过对x c p 协 议的参数口和进行的实验研究，发现口对网络的利用率影响较大，所以本文提 出一种参数改进算法，即根据网络的当前状况适当调节口值；第二，当传输流为 x c p 流和非x c p 流的混合流时，x c p 路由器无法准确地计算不同数据流所占用的 带宽，导致链路利用率及总吞吐量发生严重的抖动现象，基于此本文又提出一种 改进算法( n e w x c p ) 。通过仿真实验证明，改进后可以提高网络利用率并维持系 统的稳定性。 关键词：高带宽时延乘积网络；拥塞控制；显式控制协议( x c p ) ；t c p 分类号：t n 9 1 a b s t r a c t a bs t r a c t a b s t r a c t ：t h ec u r r e n tt r e n ds h o w st h a tt h ef u t u r en e t w o r kp r e s e n t saf e a t h e ro fh i g h b a n d w i d t h - d e l a yp r o d u c t ( b d p ) w h e nb d pi n c r e a s e s ，t h ep e r f o r m a n c eo ft r a d i t i o n a l t c p p r o t o c o lw i l ld e c l i n ec r i t i c a l l y , a n di tn o to n l yb eu n a b l et ou s eh i g hb a n d w i d t h e f f i e n t l y , b u ta l s oi t st r a n s f e rr a t ei su n s t a b l ei nh i g hs p e e dn e t w o r k ，b e c o m i n gt h eg r e a t b a r r i e ri ni m p l e m e n t a t i o no fn e wn e t w o r ka p p l i c a t i o n s b a s e do nt h ea b o v ep r o b l e m s ， d i n ak a t a b ip r o v i d e san e w e x p l i c i tc o n t r o lp r o t o c o l ( x c p ) x c pa d o p t sa ni d e at h a t t h ec o r er o u t e r sc a ns e n dt h ec o n g e s t i o nl e v e lo fb o t t l e n e c kl i n k st oi t st e r m i n a l s ， a c h i e v i n gh i g hb a n d w i d t hu t i l i z a t i o n ，l o wq u e u ed e l a y , n e a rz e r od r o p sa n dg o o d e x t e n s i b i l i t y x c ph a sb e t t e rp e r f o r m a n c et h a nt c p i ne f f i c i e n c y , f a i r n e s sa n ds t a b i l i t y , r e g a r d l e s so ft h et r a d i t i o n a lo rb d p n e t w o r k i nt h i sp a p e r , w ef i r s ta n a l y s et c p sd e f i c i e n c i e s ，t h e ni n t r o d u c et h ed e t a i l so f x c p sf r a m e w o r ka n d a l g o r i t h m ，a n d m a k e s o m es i m u l a t i o n e x p e r i m e n t s a n d p e r f o r m a n c ea n a l y s i s x c pi sam o r ec o m p r e h e n s i v ea n dp r a c t i c a lp r o t o c o l ，a n da s t r o n gc o m p e t i t o r i nf u t u r eb d pn e t w o r k s o ，w ew i l ls t u d ya n de n h a n c ex c p i n t e n s i v e l y t h e r ea r ct w oa s p e c t so fp r o g r e s s i v ew o r k ，硒f o l l o w i n g ：f i r s t ，b a s e do nt h e r e s e a r c h i n gf o rt h e aa n d po fx c p , w ef i n dt h a t 口w i l li n f l u e n c en e t w o r k u t i l i z a t i o ng r e a t l y , s ow ep r o p o s eae n h a n c e da l g o r i t h mt h a t 口s h o u l db ea d j u s t e d a c c o r d i n gt oc u r r e n tn e t w o r k ；s e c o n d ，w h e nx c p t r a f f i ca n dn o n - x c pt r a f f i cc o e x i s ti n t h es a m en e t w o r k ，x c pr o u t e r sc a n tc a l c u l a t et h eo c c u p i e db a n d w i d t ho fd i f f e r e n t f l o w s ，c a u s i n gs e r i o u sj i t t e rw i t ht h eb o t t l e n e c kl i n ku t i l i z a t i o na n dt h et o t a lt h r o u g h p u t ， t h e nw ep r o p o s ea ni m p r o v e da l g o r i t h m ( n e w x c p ) o u rs i m u l a t i o n si n d i c a t et h a tt h e e n h a n c e da l g o r i t h m sc a ni m p r o v en e t w o r ku t i l i z a t i o na n dm a i n t a i ns t a b i l i t yo ft h e s y s t e m k e y w o r d s ：b a n d w i d t h d e l a yp r o d u c ti n t e m e t ；c o n g e s t i o nc o n t r o l ；e x p l i c i tc o n t r o l p r o t o c o l ( x c p ) ；t c p c i a s s n o ：t n 9 1 i 序 序 本文是我的硕士学位论文。本文集中讨论了高带宽时延乘积网络环境下显式 控制协议( x c p ) 的性能，与传统t c p 相比的优势所在，仍存在的一些缺陷等问 题，并提出了一些新见解。 随着计算机网络的迅速发展，互联网用户数量激增，多媒体数据流迅速增长， 网络的拥塞问题变得越来越严重。拥塞是一种复杂的现象。拥塞控制也是一个复 杂的课题，而拥塞控制是确保i n t e r n e t 鲁棒性的关键因素。因此网络的拥塞控制问 题成为目前关于i n t e r n e t 研究的一个热点问题和难点问题。 t c p 是数据传送所使用的最为广泛的传输协议，但该协议在高带宽时延乘积 的环境下无法表现出很好的性能。因此，显式控制协议( x c p ) 诞生了，它是一 种路由器参与协同工作并使用显式反馈控制的协议，可以显著的提高网络性能， 减小排队时延和丢包率，并具有良好的公平性和稳定性。x c p 不需要在路由器为 每个流维持一个队列，只需要在路由器中增加很少的运算，即使对于高速路由器 而言也是可行的。x c p 的弹性结构使得q o s 的设计和执行变得十分便利。 文中既有前人科研成果的总结，也有我辛苦钻研的创意发挥，虽远算不上是 什么惊世骇俗之作，但对于我这样一个科学研究道路上的新手和后行者，可以藉 此文为机会，瞻仰前辈科学家们的伟岸形象，了解他们在浩浩汤汤的科研历史长 河中提出的诸多天才思想与高深理论，又可仅凭自己所做的一点工作而与前辈忝 列同文，实在算是莫大的荣幸。 l ， ， j 目录 目录 中文摘要i i i a b s t r a c t 。i v 序、， l 弓i 言1 1 1研究背景及意义1 1 2国内外研究现状2 1 3 本文各章节内容安排4 2 拥塞控制研究5 2 1网络拥塞的基本概念。5 2 1 1 拥塞和拥塞控制5 2 1 2 拥塞发生的原因6 2 1 3 拥塞控制评价标准7 2 2t c p 拥塞控制机制。8 2 2 1t c p 协议介绍8 2 2 2t c p 拥塞控制算法存在的问题1 0 3 显式控制协议( x c p ) 1 3 3 1 e c n 协议1 3 3 2 x c p 协议框架结构15 3 2 1x c p 协议的拥塞头1 6 3 2 2x c p 协议的终端行为17 3 2 3x c p 协议的路由器控制规则18 3 3x c p 的处理程序分析2 2 3 4x c p 的稳定性分析2 6 4x c p 协议的仿真与性能分析3 0 4 1n s 2 网络仿真器介绍3 0 4 1 1n s 2 简介3 0 4 1 2t e l 简介3 1 4 1 3 t r a c e 文件简介3 2 4 1 4a w k 简介3 3 4 1 5 g n u p l o t 简介3 6 学位论文 3 7 3 7 ：；9 ：；9 4 0 4 1 路的仿真与分析4 1 4 3 1 仿真拓扑结构及参数设置4 1 4 3 2 拥塞窗口变化4 2 4 3 3 序列号4 3 4 3 4 平均缓冲队列4 4 5x c p 协议的改进4 5 5 1x c p 路由器中参数的分析及改进4 5 5 1 1x c p 路由器中参数存在的不足4 5 5 1 2x c p 路由器中a 参数的分析4 6 5 1 3 x c p 路由器中b 参数的分析4 8 5 1 4x c p 路由器中参数的改进及实验分析4 9 5 2 改进的x c p 算法( n e w x c p ) 5 2 5 2 1x c p 算法的不足：。5 2 5 2 2n e w x c p 算法5 3 5 2 3n e w x c p 算法的稳定性分析。5 3 5 2 4n e w x c p 算法的仿真5 4 6 结论与展望。6 1 6 1结论6 1 6 2 展望。6 2 参考文献6 3 作者简历6 7 独创性声明6 9 学位论文数据集7 1 引言 1 引言 1 1 研究背景及意义 随着网络技术如光通信技术的发展，出现了高带宽时延乘积网络，即每个数 据流所分配的带宽高达g b p s ，时延大至数据流在传输管道中有数m b 的数据，而 且带宽和时延还有不断增加的趋势。当带宽时延乘积不断增大时，当前广为使用 的标准t c p 的拥塞控制算法【l j 已经不能满足高速网络中数据传输的需要。原因主 要有两点：一是在有大量空闲带宽时t c p 的a i m d 法则增长的速度太慢；二是 t c p 的吞吐量与丢包率的平方根成反比，巨大的吞吐量需要极小的误码率，这对 于低误码率的光纤链路而言也是极大的挑战。因此研究改善高速网络数据传输性 能的拥塞控制算法就有重要意义。 针对未来的高带宽时延乘积网络，出现了很多新的解决方案，主要有以下两 种： 一是端到端的拥塞控制机制【2 1 ，诸如h s t c p t 3 1 、f a s t - t c p 4 1 、b i c t c p 、 s t c p t 5 1 、h - t c p t 6 j 等，他们都是以丢包或者r 盯为反馈信号，通过改进终端拥塞 控制算法来提高性能，但是这些协议普遍存在着性能上的缺陷，例如公平性问题、 收敛速度太慢、对网络参数依赖性强等，而且丢包并不是一个很好的拥塞反馈信 号，它只能反映网络是否拥塞，而不能反映网络的拥塞程度。使用丢包作为拥塞 的指示，会使得在高速网络中传输数据面临三大困难：( 1 ) t c p 必须引入丢包来估 计带宽，然而在高带宽网络中丢包是极少发生的，当它们不可避免地发生的时候， 必定是发送端在传送爆炸性的数据，但这样就增加了超时的可能性，同时也没有 充分地利用网络带宽。( 2 ) 为了支持高带宽时延乘积中的窗口机制，包丢失应该 是极为罕见的。在时延为2 0 0 m s ，包的大小为1 0 0 k b 时，要获得5 0 g b p s 的吞吐量， 丢包率必须达1 0 _ o ，如果包的大小为1 2 k b ，则丢包率需要为1 0 。1 2 ，而这显然是极 不现实的。( 3 ) 即使丢包率能达到这个要求，对发送端来说，这也是一个极为不 精确的反馈。 二是显式拥塞控制机制，诸女i j x c p 、v c p 、e m k c 、r c p 掣7 1 ，他们都是在以 路由器反馈的网络拥塞状况为信号的基础上提出的算法，即确切地以显式的方式 通知终端用户网络的拥塞情况，终端用户据此调整发送速率，从而用户可以最大 限度地利用网络资源，又避免网络发生拥塞。一系列实验证明显式拥塞控制有较 好的鲁棒性，在效率和公平性上都远胜于传统的基于t c p 的端到端拥塞控制，并且 北京交通人学硕士学位论文 具有良好的扩展性，无论是在传统的网络环境中还是高带宽时延积网络环境中， 都能表现出很好的性能。其中，v c p 是唯一不需要扩展包头的协议但是其收敛到 公平的速率太慢，e m k c 与v c p 的思想类似，同样也存在连接收敛速率太慢的问题， r c p 与x c p 思想类似，它更多的顾及了多瓶颈链路的网络状况和收敛到公平的性 能，但是r c p 对于网络参数的估测并不准确，这会影响其性能。x c p 虽然需要额外 扩展包头，但是与其他机制相比，它在单瓶颈链路中能取得几乎完美的性能，因 此本文选择x c p 做深入研究与改进。 针对未来的高带宽时延乘积网络，x c p 是一个全新的、典型的算法，是一种 路由器参与协同工作并使用显式反馈控制的协议。它引入了效率控制和公平控制 解耦合得新概念，这能够更为高效地利用网络资源，并能够灵活地执行不同的带 宽分配策略。x c p 协议能够更直接准确地向发送端反馈网络的拥塞信息，具有很 好的鲁棒性。但是，通过对x c p 协议的深入研究，发现它也存在一些缺陷，如当 非响应流突然进入网络时，现有的x c p 协议不能很好地对这些数据流进行控制， 网络性能会受到影响。因此，我们需要对现有的x c p 算法进行深入研究并做出合 理的改进，使其在未来高带宽时延乘积网络环境中有更好的性能表现。 1 2 国内外研究现状 随着i n t e m e t 的迅猛发展，i n t e r n e t 给人类社会带来了巨大的变革。但就在 i n t e m e t 深刻影响人类历史发展进程的同时，其自身的发展却面临着种种困难，其 中之一就是网络拥塞( n e t w o r kc o n g e s t i o n ) 。从i n t e m e t 诞生起，网络拥塞就与其 如影随形。现在，网络拥塞控制已经成为确保i n t e m e t 鲁棒性( r o b u s t n e s s ) 的关键 因素，也是各种管理控制机制和应用的基础。1 9 8 8 年，j a c o b s o n t 首次将端到端的 拥塞控制算法引入到t c p 传输协议中。基于端到端的t c p 拥塞控制【8 】研究蓬勃发 展，致使现在t c p 有不低于2 0 0 个实现版本，而它们之间的主要区别就在于拥有 不同的拥塞控制算法。 虽然人们在t c p 拥塞控制方面展开了广泛的研究【9 】，并取得了一定的研究成 果，相继提出了一些如t a h o e 、r e n o 、n e w r e n o 1 0 1 、s a c k 1 1 1 、v e g a s 1 2 】等著名的 算法。但是人们随后发现单纯依靠t c p 端到端的拥塞控制策略很难解决i n t e m e t 拥塞问题，网络本身必须参与到拥塞控制中来。1 9 9 8 年，b r a d e n 等人在i e t f 提 出了“主动队列管理( a c t i v eq u e u em a n a g e m e n t ，a q m ) 研究动议【i 引，期望a q m 能改善队列管理性能，减少排队延迟提高系统吞吐量，为t c p 拥塞控制提供支持。 a q m 拥塞控制算法通常又称为口链路算法，它一般是通过显式拥塞指示( e x p l i c i t c o n g e s t i o nn o t i f i c a t i o n ，e c n ) 来实现的。 2 引言 对于低速低时延的局域网和广域网，t c p a q m 算法设计框架在保留了端到端 的设计原则的基础上加入了拥塞预警机制，提高了算法性能和业务服务质量，保 证了当前网络的鲁棒性。 随着计算、通信和存储技术的迅猛发展，全球网络系统为计算和科学研究提 供了足够的容量和高速有效的硬件环境。发展新一代网络所面临的挑战在于现有 的网络拥塞控制算法和资源共享算法不能扩展到新一代的高宽带通信网络中。主 要表现在宽带高速网络环境下，现有的协议算法不能保证低的丢包率和低的时延 及时延抖动等业务服务质量需求，甚至会导致整个网络的不稳定运行，显著降低 网络的业务服务质量。 近年来，高带宽时延乘积网络的拥塞控制研究引起了国内外的网络研究者、 非线性科学工作者和控制理论专家的广泛关注，并由此在全球范围内掀起了一股 研究高带宽时延乘积网络的拥塞控制理论的热潮。当前国内外的研究一部分集中 在修改现有的t c p 协议参数和a q m ( a c t i v eq u e u em a n a g e ) 1 1 4 】算法以满足新的需 求，一部分旨在提出新的协议以满足未来的综合网络环境和q o s 等新的应用需求。 至今，已经提出了一些很好的协议，女1 h i g h s p e e d t c p 15 1 、f a s t t c p 16 1 、x c p 、h t c p 、 b i c t c p 、r c p 等【1 7 】。同时随着网络复杂性的不断增加，也便成为一个令人关注的 问题，良好的工程环境与仿真实验固然必不可少，但也需要更为系统的分析与设 计手段，以往的拥塞控制研究基本上都是基于主观的方法，缺乏严谨科学理论的 指导，因此国内外有部分原来从事控制理论和非线性动力学工作的研究人员也相 继转而进行网络的拥塞控制研究，并且在这方面取得很大的成绩j 提出了7 些严 格的理论模型，其中突出的有l o w 等基于优化理论提出t t c p a q m 对偶性模型； m i s r a 等提出- j t c p a q m 微分方$ 呈_ f l u i d f l o w 模型1 8 】；p a g a n i n i 等利用多变量鲁棒控 制理论，设计了一个新的拥塞控制系统，它对于任意网络拓扑、容量及时延能保 持局部稳定性；h e s p a n h a 等提出一个采用“去尾”策略的t c p 拥塞控制的混杂系统 模型。 重大的合作研究计划( g e n i 和f i n d ) 最近正在设计和开发一个完全不同的第 三代互联网，它能够从根本上提高当前网络的可扩展性、有效性和鲁棒性。基于 此，最近在设计下一代拥塞控制方面做出了很大的努力。实验表明，所提出的显 式拥塞控制机制( 如x c p ) 能够实现带宽和往返传输延迟的可扩展性、稳定性和 数据流间的公平性，能够适应将来的以高带宽时延积为特点的高速网络，被认为 将来有可能取代t c p 协议，成为现在拥塞控制研究领域的一个热点和重要研究方 向。 3 北京交通人学硕十学位论文 1 3 本文各章节内容安排 x c p 协议是针对传统的t c p 协议应用于高带宽时延乘积网络存在不足而提出 的。大量的研究证明x c p 具有很好的性能，但是，经过对其深入研究，发现x c p 算法也存在一定的问题，会严重影响网络的性能。因此，本论文主要对x c p 协议 进行了性能研究，并根据它存在的缺陷，提出了相应的改进算法，同时利用n s 2 仿真工具进行仿真实验。论文安排如下： 第一章简单介绍研究背景、意义及国内外相关研究现状。 第二章首先介绍t c p 拥塞控制机制，并分析t c p 针对未来高带宽时延乘积网 络存在的不足。 第三章介绍显式反馈机制和显式拥塞控制协议，即e c n 和x c p 协议。 第四章利用n s 2 仿真工具对x c p 协议进行了仿真与性能分析，并与t c p 协 议进行比较，实验结果表明，x c p 协议的性能优于t c p 协议。 第五章针对现有x c p 算法存在的问题，做出相应的改进，并通过仿真加以验 证与分析。结果表明，改进后的算法能达到更高的网络带宽利用率，保证系统的 稳定性。 最后，总结全文，并指出下一步的研究工作。 4 拥塞控制研究 2 拥塞控制研究 2 1 网络拥塞的基本概念 2 1 1 拥塞和拥塞控制 拥塞是一种持续过载的网络状态，此时用户对网络资源( 包括链路带宽、存 储空间和处理器处理能力等) 的需求超过了固有的容量。就i n t e m e t 的体系结构而 言，网络拥塞的发生是其固有的属性。图2 1 刻画了网络负载与吞吐量、响应时间 和网络性能的关系。当网络负载较小时，吞吐量的增长和负载基本呈线性关系。 响应时间增长缓慢；当负载超过k n e e 之后，吞吐量增长缓慢，而响应时间急剧增 加；当负载超过c l i f f 之后吞吐量开始急剧下降，响应时间急剧上升。为了最大限 度地利用资源，负载在k n e e 附近时应该是较为理想的，但这也增加了滑向拥塞崩 溃的可能性，因此需要一定的拥塞控制机制来加以约束和限制。 拥塞控制就是网络节点采取措施来避免拥塞的发生或者对拥塞的发生做出反 应，在图2 1 中就是使负载保持在k n e e 附近。拥塞控制主要考虑端节点之间的网 络环境，目标是实现网络利用率和传输延迟等综合性能指标达到最优化，保证网 络系统长期的稳定性和鲁棒性。 拥塞控制算法包含拥塞避免( c o n g e s t i o na v o i d a n c e ) 和拥塞控制( c o n g e s t i o n c o n t r 0 1 ) 这两种不同的机制。拥塞避免是预防机制，它的目标是使网络运行在k n e e 附近，避免网络发生拥塞，使网络运行在高吞吐量、低延迟的状态下。拥塞控制 是恢复机制，它用于把网络从拥塞状态中恢复出来，使网络运行在c l i f f 左侧区域， 从而进入正常的运行状态。 吞 吐 量 ( a ) 5 网络负载 网 络 性 能 网络负载 ( c ) 图2 1 网络负载与吞吐量、响应时间及网络性能的关系 f i g 2 1t h e r e l a t i o n s h i po fn e t w o r kl o a d i n gw i t ht h r o u g h p u ta n dr e s p o n dt i m e 拥塞不会随着网络处理能力的提高而消除。拥塞控制算法的分布性、网络的 复杂性和对拥塞控制算法的性能要求又使拥塞控制算法的设计具有很高的难度。 2 1 2 拥塞发生的原因 拥塞发生的主要原因在于“需求”大于“供给”，即网络能够提供的资源( 包 括缓存空间、链路带宽容量和处理器的处理能力) 不足以满足用户的需求。原因 主要有以下三个： ( 1 ) 缓存空间不足。几个输入数据流共同使用同一个输出端口，在这个端口 6 拥塞控制研究 就会建立排队。如果没有足够的缓存空间进行存储，数据包就会丢弃，突发数据 流更是如此。增加缓存空间在某种程度上可以缓解这一矛盾，但如果路由器有无 限存储量时，拥塞只会变得更严重。因为网络旱数据包在经过长时间排队完成转 发时，它们早已超时，源端会认为它们已经被丢弃，而这些数据包还会继续向下 一路由器转发，从而浪费网络资源，加重网络拥塞。 ( 2 ) 链路带宽容量不足。低速链路在高速数据流的输入时也会产生拥塞。根 据香农信息理论，信源发送的速率r 必须小于或等于信道容量c 。如果r c ，则理 论上无差错传输是不可能的，所以在网络低速链路处就会形成带宽瓶颈。当其不 能满足通过它的所有源端带宽要求时，网络就会发生拥塞。 ( 3 ) 处理器处理能力弱、速度慢也可能引起拥塞。如果路由器的c p u 在执行 排队缓存，更新路由表等功能时，处理速度跟不上高速链路，也会产生拥塞。同 样，低速链路对高速c p u 也会产生拥塞。 目前，i n t e r n e t 上用户和应用的数量都在迅速增长，如果不使用某种机制协调 资源的使用，必然会导致网络拥塞。虽然拥塞源于资源短缺，但单纯地增加网络 资源不能解决拥塞问题。因为拥塞本身是一个动态问题，它不能只靠静态的方案 来解决，而需要某种机制避免网络发生拥塞或在网络出现拥塞时恢复网络的正常 运行。 2 1 3 拥塞控制评价标准 在设计和比较拥塞控制算法时，需要一定的评价方法。从用户的角度出发， 可以比较端系统的吞吐量、丢包率和延迟等指标。 ( 1 ) 吞吐量：单位时间内被成功传送的信息量，即给定时间内有效传输的数 据。 ( 2 ) 延迟：分组从源端开始传输直到最后被成功地传送到目的端所需要的时 间，也称为时延，包括：节点处理延迟( p r o c e s s i n gd e l a y ) 、排队延迟( q u e u i n gd e l a y ) 、 传播延迟( p r o p a g a t i o nd e l a y ) 、传输延迟( t r a n s m i s s i o nd e l a y ) 。 ( 3 ) 丢包率( p a c k e tl o s s ) ：在网络中传输数据包时丢弃数据包的最高比率。 由于丢弃的数据包需要重传，导致总的传输时间加长。所以，包丢失率通常被用 来作为反映网络拥塞状态的一个指标。 ( 4 ) 抖动( j i t t e r ) ：延迟的变化就是抖动。如果所有的包都通过相同的路由到 达接收端，则这些包应该具有相同的传播延迟；如果数据包大小也一样，那么，传 输延迟也基本一样；但是，如果网络中的业务量有变化，排队延迟就会不一样，正 是排队延迟的变化造成了抖动。拥塞发生时，网络的延迟和抖动会急剧增大。 7 北京交通人学硕+ 学位论文 ( 5 ) 信道资源利用率：信道传输信息的有效时间与信道总可利用时间之比。 它通常不包括包头开销、传输冲突等各种形式的开销。 ( 6 ) 响应时间：网络服务请求和响应该请求之间的时间。 由于拥塞控制算法对整个网络系统都有影响，在评价算法时应该从整个系统 的角度出发进行考虑。两个重要的评价指标是资源分配的效率和资源分配的公平 性。 因此可以从以下几个方面来评价拥塞控制算法： ( 1 ) 效率：即网络的利用率，它只与总资源的利用率有关，而与各个源端之 间的资源利用无关。 ( 2 ) 公平性：指在发生拥塞时各源端能公平地共享同一网络资源。我们以 m a x - r a i n 公平标准作为评价标准，即每个用户的吞吐量和其他共享相同瓶颈的用户 的吞吐量相同。 ( 3 ) 收敛性：收敛性需要从两方面来考虑，一是收敛到效率；二是收敛到公 平。 2 2t c p 拥塞控制机制 2 2 1t c p 协议介绍 t c p 是一项从实践中诞生的，并在实践中不断得到发展和完善的网络技术， 也是目前互联网中使用最为广泛，占主导地位的端到端传输协议。根据m c i 的统 计，互联网上总字节数的9 5 及总数据包数的9 0 使用t c p 协议传输。t c p 的目 的是为了解决i n t e m e t 的稳定性、异质性( 接收端缓冲区大小、网络带宽及延迟等) 、 各流之间享用带宽的公平性、使用效率及拥塞控制等问题，从而为i n t e m e t 提供可 靠、健壮( r o b u s t ) 的端到端通讯。因此，当今i n t e m e t 的稳定性与t c p 成功的拥 塞控制算法密不可分。 随着i n t o n e t 本身规模的迅速扩大、i n t e m e t 用户数的剧增、以及网络应用类 型的快速增加，网络正经历越来越多的包丢失和其他的性能恶化问题，其中一个 比较严重的现象就是网络拥塞。为了防止网络的拥塞现象，t c p 提出了一系列的 拥塞控制机制。最初由vj a c o b s o n 在1 9 8 8 年的论文中提出的t c p 的拥塞控制由 “慢启动( s l o ws t a r t ) 1 9 1 和“拥塞避免( c o n g e s t i o na v o i d a n c e ) 2 0 】组成，1 9 9 0 年出现的t c pr e n o 版本中又针对性的增加了“快速重传( f a s tr e t r a n s m i t ) 和“快 速恢复( f a s tr e c o v e r y ) 算法【2 1 1 ，避免了网络拥塞不严重时采用“慢启动算法 而造成过大地减小发送窗口尺寸的现象，这样t c p 的拥塞控制就由这4 个核心部 拥塞控制研究 分组成。 拥塞 窗口 e w n d s s h t h r e s h = o w n 北 拥塞 窗口 ( a )慢启动和拥塞避免 ( a ) s l o ws t a r ta n dc o n g e s t i o na v o i d a n c e 时间 时间 ( b ) 快速重传和快速恢复 ( b ) f a s tr e t r a n s m i ta n df a s tr e c o v e r y 图2 2t c p 拥塞控制的4 个阶段 f i g2 2f o u rp e r i o df o rt c pc o n g e s t i o nc o n t r o l t c p 拥塞控制四个主要过程如图2 2 ( a ) 和( b ) 所示简要介绍如下： 慢启动阶段：早期开发的t c p 在连接建立成功后会向网络中发送大量的数据 包，这样很容易导致路由器缓存空间耗尽，从而发生网络拥塞，并导致t c p 连接 的吞吐量急剧下降。因此新建立的t c p 连接不能一开始就发送大量数据包，而只 能根据网络情况逐步增加每次发送的数据量，以避免上述现象的发生。具体来说， 当建立新的t c p 连接时，拥塞窗口( e w n d ) 初始化为一个最大报文段( m s s ) 大 9 北京交通人学硕十学位论文 小。发送端开始按照c w n d 大小发送数据，每收到一个a c k 确认，c w n d 就增加一 个m s s 大小，这样c w n d 就随着网络往返时间( r o u n dt r i pt i m e ，r t t ) 呈指数增 长，发送端向网络发送的数据量将急剧增加。事实上，慢启动的速度一点也不慢， 要达到每i 盯发送w 个数据包所需时间仅为r t t xl o g w ，只是它的起点比较低 而已。 拥塞避免阶段【2 2 】：如果t c p 发送端监测到数据包丢失( 其原因可能是重传计 时器超时，亦可能是收到重复的a c k 信令，即认为网络发生了拥塞，此时就进入 拥塞避免阶段。慢启动阙值( s s t h r c s h ) 被设置为前拥塞窗口大小的一半，同时拥 塞窗口将降低到一个报文段。然后，随着通信过程的恢复，拥塞窗口持续增长。 在拥塞窗口大小未达到s s t h r e s h 时，它以指数速度增长，到达之后则开始线性增长。 快速重传和快速恢复阶段l z 3 j ：当t c p 发送端收到三个相同的a c k 时，就触 发了其快速重传算法，将s s t h r e s h 设置为当前c w n d 值的一半，并且将c w n d 设置 为s s t h r e s h 的值( 有些为s s t h r e s h 的值加3 ) ，然后重传丢失的报文段。快速恢复和 快速重传算法一般同时使用，快速恢复是基于“数据包守恒”的原则，即同一时 刻在网络中传输的数据包数量是恒定的，只有当“旧”数据包离开网络后，才能 发送一个“新 的数据包。如果发送端收到一个重复的a c k ，那么根据t c p 的 a c k 机制就表明有一个数据包离开了网络，于是将c w n d 加l 。如果能够严格遵守 “数据包守恒”原则，那么网络中将很少会发生拥塞，事实上，拥塞控制的目的 就是修正违反该原则的地方。 2 2 2t c p 拥塞控制算法存在的问题 9 0 年代中后期到2 1 世纪以来，i n t o n e t 得到迅猛发展，首先是拥塞现象变得 越来越严重，其次是高带宽网络的出现，再者很多对数据敏感的应用越来越多， 如音视频应用等，这些对t c p 的传统拥塞控制算法提出了巨大的挑战。特别是随 着网络高带宽时延乘积的增加，t c p 协议的性能将严重下降且不稳定，难以发挥 其原有的效能，成为实施各种新型网络应用的巨大障碍【2 4 】【2 5 1 。因此，t c p 算法体 现出越来越多的问题【2 6 1 。主要体现在以下几个方面： 首先，传统的t c p 总是把丢包作为拥塞发生的信号，而假定链路错误造成的 分组丢失是忽略不计的，然而在高速网络中，这种假设是不合理的，当数据传输 速率比较高时，链路错误是不能忽略的。在无线网络中，链路的误码率更高，因 此，如果笼统地认为分组丢失就是拥塞所引起的，从而降低一半的速率，不仅会 导致发送端进行不必要的拥塞控制响应，也是对网络资源的极大浪费，并加剧数 据流之间带宽分配的不公平性。 1 0 拥塞控制研究 其次，在高带宽时延乘积( h i g h b a n d w i d t h d e l a y - p r o d u c t ，b d p ) 2 7 】【2 8 】【2 9 1 网 络中，t c p 算法的带宽利用率极低。随着网络带宽增加，发送端将不断增大其数 据发送速度，导致节点路由器的队列长度较大且频繁振荡，增大了数据包的转发 时延和丢包概率，造成发送端数据吞吐量振荡频繁。随着r 1 广r 不断增加，发送端 拥塞窗口增长缓慢导致数据吞吐量下降，当r 1 丌远大于超时重传时间，由于确认 信息超时，发送端认为网络发生拥塞而成倍地降低数据吞吐量。因此，在b d p 较 大的网络环境中，t c p 数据流难以保持较高吞吐量和充分利用网络带宽资源【3 0 】【3 l 】。 如图2 3 所示，t c p 的平均带宽利用率会随着网络带宽和往返传输延迟的增加而 不断降低。实验和理论推导都证明随着带宽时延乘积的增加，不管是用什么排队 模式，都使t c p 变得越来越低效和不稳定。 最后，t c p 的公平性也存在着问题，主要表现在两方面： 一是拥塞响应的t c p 流和非响应的u d p 流之间资源享用不公平； 二是t c p 流之间资源享用的不公平。不同的窗口大小