（计算机软件与理论专业论文）一种基于cosslowstart的新拥塞控制机制.pdf

摘耍 摘要 随着i n t e r n e t 的深入发展，互联网上的用户数量和应用规模部急剧膨胀，这种爆炸性 的增长所带来的一个严重问题就是网络拥塞。现今，铡塞已经成为一个十分敏感而重要 的话题，而其控制机制也已成为确保i n t e m e t 稳, 定性、鲁棒性的关键因素。 本文分析了目肓i f t c p 拥塞控制机制的基本原理，重点针对源算法中慢启动策略的不 足，分别从往返延时的组成、拥塞控制微分模型及链路等效带宽估计等方面提出了改进 方法，显著地减小了往返延时r t t 及动态门限阈值s s t h r e s h 选取误差。 针对目f i _ f f t c p 拥塞控制机制的慢启动算法中存在的实际问题，本文在上述条件下提 出了一种基于余弦函数的慢启动策略：c o s s l o w s t a r t 。又进一步对窗口初始值作了适 当推广，并从数学角度对新策略的稳定性、高效性以及公平性进行了理论分析与证明。 最后n s 2 仿真结果表明，该策略能有效地减少分组丢失、平缓突发流量冲击，并可增加 带宽利用率，对搠塞窗h c w n d 也提供了更好的粒度控制。同时，它还有助于改善系统吞 吐量。 需要指出的是，传统的拥塞控制机制无法适应于同新月异的多媒体业务，因为它需 要发送窗口对速率变化具有更好的平滑性。为此，本文改进了原有的a i m d 算法，提出 了一种可凋参数的a a i m d 机制。它能根据业务对象，实现参数的自适应选择，并与 c o s s l o w s t a n 一起构成完整的新拥塞控制机制。仿真显示，新机制能改善t c p 连接的 性能并具有令人满意的友好性。同时，新机制还有利于改善路由器的队列管理性能，提 高网络服务质量。 关键字：拥塞控制；慢启动；拥塞窗口；往返延时；门限阈值 江南大学烦i ? 学位论文 a b s t r a c t w i t ht h ef u r t h e rd e v e l o p m e n to ft h ei n t e r n e t ，b o t ht h en u m b e ro fc o n s u m e r sa n dt h e a p p l i e ds c a l eo ft h ei n t e r a c ta r er a p i d l ye x p a n d i n g as e r i o u sp r o b l e mo ft h i sk i n do fb u r s t g r o w t hi st h en e t w o r kc o n g e s t i o n n o w ，t h ec o n g e s t i o nh a sa l r e a d yb e c o m eav e r ys e n s i t i v e a n di m p o r t a n tt o p i c ，a n di t sc o n t r o lm e c h a n i s mh a sa l s ob e e nt h ek e yf a c t o ro fa s s u r i n gt h e i n t e r n e t ss t a b i l i t ya n dr o b u s t n e s s w ea n a l y z e dt h eb a s i cp r i n c i p l eo ft h ec u r r e n tt c pc o n g e s t i o nc o n t r o lm e c h a n i s m t o m a i n l ya i ma tt h es h o r t a g eo ft h es l o w s t a r ts t r a t e g yi nt h es o u r c ea l g o r i t h m ，w ep u tf o r w a r d t h ei m p r o v e m e n ti nt h ec o m p o s i n go fr o u n d t r i pt i m e ，t h ed i f f e r e n t i a lm o d e lo ft h ec o n g e s t i o n c o n t r o la n dt h et a n t a m o u n tb a n d w i d t he s t i m a t eo ft h en e t w o r ke t c ，w h i c hm i n i s h e st h ee r r o r o ft h er t ta n dt h ed y n a m i cs s t h r e s ho b v i o u s l y t h i sp a p e ri n v e s t i g a t e st h ec u r r e n ts t a n d a r ds l o w s t a r ta l g o r i t h mo ft c pc o n g e s t i o n c o n t r o lm e c h a n i s ma n di t sa c t u a lp r o b l e m an e wv a r i a n ts l o w s t a r ts c h e m ew h i c hi sb a s e do n t h ec o s i n ef u n c t i o n ，a n dc a l l e d “c o s s l o w s t a r t ”i sp r e s e n t e d a tt h es a m et i m e ，a n a p p r o p r i a t eg e n e r a l i z i n gt ot h ei n i t i a lw i n d o wi sf u r t h e rg i v e n m a t h e m a t i c st h e o r ya n a l y s e s a n dp r o v e st h a tt h i sn e ws c h e m ec a no b v i o u s l yi m p r o v et h es t a b i l i t y , e f f i c i e n c ya n df a i m e s s o ft h en e t w o r k f i n a l l y , n s 2s i m u l a t i o nr e s u l t sd e m o n s t r a t et h a ti tc a ns i g n i f i c a n t l yr e d u c e b o t hp a c k e tl o s s e sa n dt r a 衔cb u r s t i n e s s a n di n c r e a s et h eb a n d w i d t hu t i l i z a t i o nr a t i o i ta l s o p r o v i d e sab e t t e rg r a n u l a r i t yc o n t r o lo v e rt h ec o n g e s t i o nw i n d o w ，a n ds t i l lc o n t r i b u t e st o i m p r o v i n gas y s t e mt h r o u g h p u t i tm u s tb ep o i n t e do u tt h a tt h et r a d i t i o n a lc o n g e s t i o nc o n t r o lm e c h a n i s mc a n ta d a p tt h e m u l t i m e d i as e r v i c e sw h i c ha r er a p i d l yd e v e l o p i n g b e c a u s ei tn e e d sb e r e rs m o o t hs e n d i n g w i n d o wt ot h ev e l o c i t yv a r i e t y ，w ei m p r o v et h eo r i g i n a la i m dr u l e ，a n dp u tf o r w a r dak i n do f a d j u s t a b l ep a r a m e t e rm e c h a n i s mn a m e da a i m di n t h i sp a p e r i tc a nc a r r yo u tt h e s e l f - a d a p t i n gs e l e c t i o no ft h ep a r a m e t e ra c c o r d i n gt ot h et r a f f i co b j e c t ，a n dm a k et h en e w c o n g e s t i o nc o n t r o lm e c h a n i s mt o g e t h e rw i t hc o s - s l o w - s t a r t t h er e s u l to ft h ec o m p a r a t i v e s i m u l a t i o ns h o w st h i sn e wm e c h a n i s mc a ni m p r o v et h ep e r f o r m a n c eo ft h et c pc o n n e c t i o n a n dh a v e 锄i t yo fs a t i s f a c t i o n f u r t h e r m o r e ，i ti sc l e a rt h a tt h en e ws l o w s t a r ts t r a t e g ya l s o c o n t r i b u t e st ot h em a n a g e m e n tp e r f o r m a n c eo ft h er o u t e rb u f f e r , a n de l e v a t e st h en e t w o r k s e r v i c eq u a l i t y k e yw o r d s ：c o n g e s t i o nc o n t r o l ，s l o w - s t a r t , c o n g e s t i o nw i n d o w ( c w n d ) ，r o u n d - t r i p t i m e ( r t t ) ，s l o ws t a r tt h r e s h o j d ( s s t h r e s h ) i i 独创性：声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含本人为获得江南 大学或其它教育机构的学位或证书而使用过的材料与我一同工作的同志 对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意 签名：蓄名蠕日期：哆j 矿7 关于论文使用授权的说明 本学位论文作者完全了解江南大学有关保留、使用学位论文的规定： 江南大学有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许论文被查阅和借阅，可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文， 并且本人电子文档的内容和纸质论文的内容相一致 保密的学位论文在解密后也遵守此规定 签 名： 导师签名： 益丝王盟：! 三2 锄南日飙 第一章绪高 1 1 研究背景和意义 第一章绪言 近2 0 年来，i n t e m e t 经历了爆炸式的增k = ，网络规模急剧膨胀，全球每大都有成千上万台主机联 入i n t e m e t 。如今，网络已深入剑了社会的方方面面，成为生活中不可或缺的一部分。它把人们的学 习、1 ：作和休闲紧密的联系在一起，涉及内容包括政治、经济、军事和文化等各领域利部l 、j ，这已 成为整个社会基础设施的重要组成部分。而我国网比数鲢的快速增k 更是被t t c 界所瞩目，根据中 国：互联网络发展状况统计报告【l 】显示，截至2 0 0 4 年1 2 月底，我圈内地网比数己达9 4 0 0 万， 总人 口的7 2 ，上网计算机达至u 4 1 6 0 万台。从国外的发展经验看，这正是网k 数量增长最快的“雪崩期”。 可以预见，在未来儿年内我国的网氏数量还会继续保持高速增长态势。 虽然i n t e m e t 在过去几十年里得到了突飞猛进的发展，但其有限的资源容鼙和处理能力，使得拥 塞问题日益严重，这已成为制约网络发展的瓶颈。拥塞导致的直接后果是端到端的延时加人，分组 丢失率居高不下，甚至还可能引起整个系统崩溃。当网络处于崩溃边缘时，微小的负载增量都将使 网络吞吐量急剧下降。例如，1 9 8 6 年1 0 月，由于拥塞崩溃的发生，l b l 剑u cb e r k e l e y 的吞吐量从 3 2 k b p s 跌落至4 0 b p s 2 1 ，白此人们开始关注拥塞控制。 拥塞崩溃对i n t e m e t 的威胁可追溯到其早期的发展中，1 9 8 4 年n a g l e i3 】报告了由于t c p 连接中没 必要的重传所引发的崩溃，1 9 8 6 1 9 8 7 年间这种现象曾多次发生。除此之外还有其它一些诱发崩溃 的原因，例如不可达分组( u n d e l i v e r e dp a c k e t s ) 导致的崩溃。它与前一种有所不同，是一种不稳定状态， 当负载减小时，可自动恢复。f l o y d 4 1 也报告了一种分片拥塞崩溃现象，即网络传输了大量的分组分 片，但因无法在接收端重装成有效的分组而只好将其丢弃。而网络传输大量川户不再需要的陈l f l 分 组( s t a b l ep a c k e t s ) 也会导致另一种形式的拥塞崩溃现象。 其实，拥塞就是当网络中有太多分组时，其 性能会降低的现象【5 】。图1 1 描绘了这种症状。当 主机转储剑网络中的分组数量在其传输容量之 内时，它们将全部送达目的地( 除了因传输错误 而不能被正确发送的少量分组外) ，且成功传送 的分组数与发送晕成正比。然而，当发送量继续 增人时，路由器不再能够应付，开始丢失分组， 并导致情形恶化。在发送量1 f 常高情况下，网络 完全瘫痪，几乎没有分组能够送达目的地。拥塞 控制发生在传输的分组数量开始接近网络对分 组的处理能力时，若分组数量超过这个水平，则 性能就会急剧下降。 拥塞产生的根本原冈在于用户提供给网络 的负载大于网络实际拥有的资源容量和处理能力嗍。其一般表现为数据包延时增加、丢弃概率增大、 上层应用性能下降等。目前i n t e r n e t 大都是基于“尽力而为”( b 骼t e f l f o r t ) 的服务，其数据报可能会失 i 江南大学硕l ：学位论文 序、丢失或重发，而且端剑端的延时也时刻变化着。像这样的异质网络，当对带宽和缓存等资源的 需求超过现有资源时，由于超载i 而造成的拥塞以及随之而米的数据包丢火是很酱遍的，甚至可能造 成崩溃。| 天| 此，拥寒控制已成为确保i n t e r n e t 稳定性、鲁棒性的关键冈素。它对丁稳定的数据传输， 公平的带宽分配以及高效的吞吐昔都具有格外重要的意义。 由1 - t c p i p 协议能够适应不同的网络体系结构和传输链路，并为客户一服务器( c s ) 模式提供了 较好的支持，使之成为网络通信的事实标准【7 】，其拥塞控制机制对控制网络拥塞也就具有特别重要 的意义。随着现代网络飞速膨胀，拥塞现象越发严重，现有的t c p 拥塞控制机制在某些方面已无法 适戍拥挤不堪的网络了 8 1 。 近年来，网络应川的深入发展为多媒体服务提供了新的机会。随着日新月异的多媒体业务和组 播技术的人量山现，目前诸如音频、视频等多媒体数据流日益成为网络业务的主流。而新兴的应用 如宽带接入、i p 多播、流媒体和内容传输分发等“尽力”服务则需要更高的带宽和服务质量( q o s ) 来保证，这些都离不开拥塞控制的支持。 同时，无线技术( 如卫星通信、移动i p 等) 以不可比拟的优越性获得了蓬勃发展，但它们易受 剑天气、地理、移动速度等外界环境影响，信道误码率较高，丢包率大大增加。而这种由传输引起 的丢包现象与拥塞丢包并不等同，需要改进的拥塞控制机制米为它们服务。同时由t a t m 网络的特 殊性，也给传统t c p 拥塞控制技术的实现带米了新的挑战。 1 2 研究现状及发展态势 1 2 1 研究现状 随着信息产业的匕速发展，新的网络应用、网络服务不断涌现，但其中潜在的危机也日益暴露， 如拥塞严重、传输速度瓶颈、带宽利刚率低下等。为了确保i n t e m e t 的稳定发展，人们对拥塞控制展 开了大量研究，先后提出了多种算法，其中以v j a c o b s o n 丁1 9 8 8 年提出的t c pt a h o e 【2 l 最具代表性而 被j “泛采用，后米又在上世纪9 0 年代相继出现了t c p r e n o 、t c p n e wr e n o 和t c ps a c k 等，但上述 改进都具有一定局限性。 最近儿年，端到端的拥塞控制已逐渐成为互联网的研究热点，而使用的控制策略基本上都是建 立在t c p 上的，相关的理论成果有【9 】：k e l l y 建立了流体流模型，同时提出了基于速率的p r i m a l 算 法，并证明了它在无延迟网络中的稳定性。他还为基于窗口的m u i - t c p 算法建立了连续动态模型。 j o h a r i 和v i n n i c o m b e 则分别论证了p r i m a l 算法在同构、异构网络中的局部稳定性，以及t c p r e n o 算法的局部稳定性。如今对i p 层路由拥塞的研究也逐渐增多，已成为一个新的热点。拥塞控制的研 究方向还包括：对t c p 友好性( t c p f r i e n d l y ) 研究，以及如何“惩罚”不遵守拥塞控制协议的行为 等。 需要指出的是，拥塞控制也会产生具有短相关和长相关的自相似数据流1 6 ，可以用h u r s t 参数描 述。t c p 拥塞控制本身的白相似性也构成了i n t e r a c t 数据流的分形特征，而这一特性与更高层的应 用或协议无关。由于t c p 拥塞控制- t 作在自时钟方式，每个事件( 例如发送数据或计算超时) 都完 全由过去决定，即系统的未来可以由过去描述，所以其拥塞控制是一个确定性过程。而且，它的反 馈控制还具有非线性和周期性等特点。目前，基于自相似性的t c p 拥塞控制也是个开放的问题。 2 第一章绪高 如今，拥塞控制算法的设计和实现面临着许多折中1 6 j ( 例如在复杂性和高效性之问的折中) ， 不可能有一种方案在所有环境中都是“最好的”，必然存在着局限性。例如基丁窗口的h s t c p 和s t c p 算法虽然加速1 r 拥塞窗u 的a i m d 过程，但其网络稳定性不足、效率低卜，冈此在普通网络中性能还 不如传统算法。基丁速率的f a s t t c p 和t c pv e g a s 虽然在一定科度上改善了网络效率，但在竞争可 川带宽方面存在着严重的不公平性。现有的拥塞控制思路、方法和技术在多口标的不同环境中更是 面l 临着挑战，它们还有很多要改进的地方，有待丁作进一步的研究与分析。 1 2 2 发展态势 基于上述现状，以下两方面将可能成为其未来的发展趋势。 1 提出并改进t c p 拥塞控制的数学模型与描述方法【l o j 拥塞控制算法的提山与改进在很人科度上依赖于网络模型，数学模型的好与坏、精确与否直接 关系剑基于该模型的拥塞控制算法在实际运圳时是否有效。而最最要的是，数学模犁取决于对流昔 的精确数学描述。最新研究表明，酱通队列模犁并不能很好地模拟t c p 包的传输过程。由f t c p 的拥 塞控制产生具有短相关和长相关的白相似数据流，具有分形特性，这与基丁前后无关的马尔可大性 相矛盾。所以，p a x s o n 等人在研究了t c p 连接的特性后，指出马尔可夫无关性严重低估了t c p 传输的 突发性。在连接建立后，包的剑达能否用更精确的模型米描述，目前还是个讨论的话题。 2 改进拥塞原理的描述以及发展新的智能控制方法 传统控制理论方法的应用在很大程度上依赖丁- 结构已知的系统数学模型，而这些模型由丁进行 了理想化，往往受到很多严格的限制，无法准确地表达实际的t c p 流。冈此传统方法不能从根本上 解决拥塞问题，在实际运用中也会遇到许多难以逾越的障碍，网络性能仍未得到充分的提高或明显 的改善。近年来，系统利用控制理论的方法分析或设计拥塞控制系统的研究已，“泛展开。随着智能 控制理论的发展，提出了网络拥塞的智能化控制方法。主要有【l i 】：模糊逻辑控制方法。该方法从 行为上模拟人的模糊推理和决策过程，又有入提出了f c c ( f u z z yc o n g e s tc o n t r o l l e r ) 调节器，它适用 于对难以建模的对象实施鲁棒性控制，且操作形式简单，易于实现。但其控制效果取决于是否正确、 全面、有效地将控制经验总结为一系列控制推理语言；神经网络控制。随着神经网络在复杂系统 控制、信号与图像处理中的广泛应用，当前计算机学科的发展趋势和研究方向是将网络性能分析与 控制理论、神经网络、人上智能以及专家系统等技术进一步进行交叉与有机结合，以适应高速网络 的建模及性能分析的需要。这些控制算法还有待丁进一步完善并推广应用。 1 3 本文主要工作 本文综合分析了现有的拥塞控制机制基本原理，尤其重点研究了慢启动问题，并在此基础上， 提出了一种基于余弦函数的新慢启动策略。同时为了机制的完整性，针对目前多媒体业务的广1 泛应 用，最后又提出了一种可调参数的拥塞控制机制。论文主要完成的工作内容具体包括： 1 阐述了拥塞控制的基本概念及其算法分类，并主要针对源算法的基本策略及出现的问题，提 出了相应的改进方向。 2 在对现有慢启动原理进行分析的基础上，深入研究了拥塞控制中的慢启动问题，并指明了相 应的解决方向。通过分析往返延时r t t 的组成及拥塞控制微分模型，给出了r t t 的预测方法。同时 3 江南人学硕f ：学位论文 借助于等效带宽原理，提供了基于带宽的动态阂值选取方案。 3 鉴于慢启动过科对w e b 流量的特殊意义，本文在客观评价原慢启动算法不足的基础上提出 了一种基于余弦函数的新慢启动策略：c o s s l o w s t a r t ，并对其窗口初始值作了适当推广。同时从数 学角度对新策略的稳定性、高效性以及公平性进行了理论分析与证明，使之更具可靠性。仿真表明 它有效地提高了网络稳定性及带宽利用率，避免了过多的流量颠簸，改善了服务质量。 4 针对传统的t c p 拥塞控制机制不能适应多媒体流的传输要求，我们提出了一种可调参数的 拥塞控制机制：a a i m d 。重点借助于对a i m d 响应函数的推导及友好性分析，给出了多媒体流参 数选取的依据，并通过n s 2 仿真验证了其有效性。它与3 中所提出的新慢启动策略共同构成一完整 的新拥塞控制体系。 1 4 论文的组织结构 本文各章i 了的内容分布如下： 第一章是对课题的相关背景总的概述，引出了本文将要研究的主题，同顾了自拥塞崩溃发生以 米对拥塞控制机制及其慢启动策略展开的研究。 第二章研究了拥塞控制的基本概念及其分类，并对t c p 源算法存在的不足和改进方向作了详细 地阐述。 第三章通过对拥塞控制中慢启动原理及其出现的问题进行分析研究，提出了相应的解决方向， 重点讨论了对往返延时及i j 限阂值的选取方法，为下一章服务。 第四章我们设计了一种基丁余弦值的慢启动策略，起剑了减少丢包率、提高吞吐量的效果。同 时对新策略的应用作出了推广，并对其性能给出了理论分析与证明。最后通过仿真实验，对新| 只策 略的性能进行了分析比较。 第五章针对当前形式，把原有的a i m d 机制作了改进，提出一种可调参数的拥塞控制机制，使 之适应多媒体应用的需要，并与上述新慢启动策略一起构成一完整的拥塞控制体系。n s 2 仿真也验 证了其有效性，改善了网络性能。 第六章是结论，同时介绍了今后需要进一步完善的t 作及研究方向。 4 第一二章拥寒控制及其算法研究 第二章拥塞控制及其算法研究 端剑端的拥塞控制是目i ) i j i n t e m e t 的研究热点。迄今为止，拥塞问题还没有得剑很好的解决。本 章首先介2 “拥塞控制的基本原理，包括拥塞和拥塞控制的概念以及拥塞发生的原冈。第一二1 ，介坌“拥 塞控制算法的分类，紧接着义阐述了t c p 源算法的基本策略及存在问题，并且提出了s hj , j l 的改进方 向，为本文土旨服务。 2 1 拥塞控制基本原理 2 1 1 拥塞和拥塞控制概念 拥塞是指在网络传输的分组数量开始接近其处理( 传输) 能力时，不能很好地提供通信服务米满足 用户要求的情况，以及当网络中存在 过多分组时，其性能会下降的现象 【1 2 】【1 3 】。拥塞的表现是分组丢失，往返 延时增长。拥塞控制就是采取某种策 略，将网络中的分组数鼍维持在一定 水平，使之尽可能保持高的吞吐量。 它主要考虑端： 了点之间的网络环境， 目的是使负载不超过网络的传送能 力。 用图2 1 【1 米描述拥塞的发生。当 负载较小时，吞吐量的增长与负载基 本呈线性关系，延迟增长缓慢。到达 膝点( k n e e ) 后，随着负载的增加，吞吐 量的增量逐渐减小，增长缓慢，延迟 却增长较快。当负载越过崖点( c l i f f ) 后，吞吐量急剧下降，延迟反而急剧 上升。可以看出，负载在k n e e 附近时， 网络的使用效率最高。拥塞控制就是 使网络：肖点采取措施来避免拥塞的发 生或者对其作出反应【15 1 。通常将k n e e 点附近称为拥塞避免区间，k n e e 和 c l i f 使二间是拥塞恢复区间，c l i f f = 艺外是 拥塞崩溃区间。为了最大限度地利用 资源，网络工作在轻度拥塞状态时应 该是比较理想的，但这也增加了滑向 吞 吐 量 o = 厶 二 暑 o 二 日 拥塞避免 崖点 ( c l i f 0 一一 、 一j一 拥塞恢复拥塞崩溃负 卜 载 ( l o a d ) 图2 1 ( a ) 负载与吞吐量的关系 崖点 ( c l i f d 隙点 ( k n e e ) l 拥塞避免拥塞恢复拥塞崩溃负载 ( l o a d ) 图2 1 ( 6 ) 负载与延迟响应时间的关系 拥塞崩溃的可能性。因此需要一定的控制机制来加以限制和约束，这也是研究拥塞控制的本质意义。 5 延迟响应时间(a量苫口odso邑 江南人学硕i j 学位论文 2 1 2i n t e r n e t 中拥塞发生的原因 网络拥塞来源于资源和流量分布的不均衡性，发生的原冈是“需求”人丁“供给”【1 4 】。网络中 有限的资源由多个圳户共享使川，它无法根据资源状况限制用户的数鼙，也无法控制刚户使川资源 的数量，拥塞总是发生在网络中资源“相对短缺”的位置。如图2 2 ( d ) ，由丁带宽分布的不均衡，当 s 以1 0 m b s 的速率向d 发送数据时，在网关r 就会发生拥塞。图2 2 ( 6 ) 中冈为流量分布的不均衡，当s l 和s 2 都以1 0 m b s 的速率向d l 发送数据时，在r 处也会拥塞。i n t e r n e t 中资源和流量分布的不均衡是j “ 泛存在的，由此导致的拥塞不能t j j 增加资源的方法解决，也不会随着网络处理能力的提高而消除， 有时共至会加重拥塞稃度i ”】。例如，增加网关缓冲会增人报文通过网关的延迟，如果总延迟时问超 过了端系统重传定时器值，就会导致分组重传，反而加重了拥塞。 同1 0 厂司m 厂司 bd2 ： l 一 图2 - 2 ( 口) 网络资源分布的不均衡 图2 2 ( 6 ) 网络流量分布的不均衡 下面讨论拥塞产生的具体原冈i l o 】： ( 1 ) 存储空间不足。网络中经常出现若干输入流冈需要同一条通信链路，而向同一个端口发送数 据，此时它们将在输出端口处排队。如果端口没有足够的存储空间，当队列已填满缓存，这之后到 达的数据就会被抛弃，而对于突发的数据流更是如此。增加存储空问在某种程度上可以缓解这一矛 盾，但当存储容量无限增加时，拥塞将会更加严重。冈为当数据包经过长时间排队完成转发时，它 们早己超时，源端会认为它们已经被丢弃，而这些数据包还会继续向下一跳路由器转发，从而加重 了拥塞程度，浪费了网络资源。 ( 2 ) 带宽容量不足。高速的数据流通过低速链路时也会产生拥塞，只有信源的发送速率r 小于或 等于信道容量c 时，才有可能避免拥塞。如果r c ，无差错传输通常是不可能的。所以网络中的 低速链路将成为带宽的瓶颈和拥塞产生的重要原因之一。依据香农公式，一条信道所能够传输的信 息量( 即信道容量) 是有限的，最多为c = 曰l o g ：【1 + ) ，这是一条信道可接近但永远无法达到 的目标。因此，在某些较差的链路上，就必然形成瓶颈，j a c o b s o n 对此作了详细描述【1 6 】。 ( 3 ) 处理器能力弱、速度慢。当路由器的c p u 执行排队缓存、更新路由表的处理速度无法满足高 速链路的传输速度时，它就不能及时对分组进行处理，必然在某些节点处形成排队，队列过长就会 导致传输延时增加甚至数据包丢失，最终形成拥塞。 因此，解决拥塞必须从系统各部分的关系入手，从整体上加以优化。例如，提高链路速率而不 相应地提高处理器速度，只会转移网络瓶颈，而无法避免拥塞。 6 回 b m0 0 1 上 1 1 一 一r b ， b m、m 0 ，01 量1 工 卜 p j 一1 2 一s s 第一二章拥采控制及j c 算法研究 2 2 拥塞控制算法的分类 拥塞控制算法包含拥塞避免( c o n g e s t i o na v o i d a n c e ) 年l l 拥塞控$ 1 ( c o n g e s t l o nc o n t r 0 1 ) 这两种不同的 机制 1 。拥塞避免足“颅防”机制，它的口标是避免网络进入拥塞状态，使之运行住高乔吐量低延 迟的环境r 卜；拥塞控制是“恢复”机制，它川丁把网络从拥塞状态中恢复过来。 2 2 1 开环和闭环 从控制论角度来讲，拥塞控制算法w 分为开环利闭环两人类1 7 】。开环算法致力于通过良好的设 计来避免问题出现，确保一开始就不会发生拥塞。当流量特征可以事先获得时，适合使川开环控制。 显然对丁i n t e r n e t 这样不断变化的复杂系统米说，这并不是理想的选择。当流量特征不能被准确描述 或者当系统不提供资源预留时，适丁使川闭环控制。闭环的解决方案是建立在反馈环路概念之上的， 按其反馈方式可分为：显式反馈和隐式反馈。在显式反馈算法中，由拥塞点将拥塞信号反馈给源端； 而在隐式算法中，源端通过局部脱测米推断是否存在拥塞。 t c p 拥塞控制算法采川的是基丁窗口的端剑端的闭环控制方式，它通过反馈的确认信号a c k 来 控制分组的发送。过程可分为以下三个阶段【1 8 】：检测拥塞的发生；将拥塞信息报告给控制点；控制 点根据信息进行调整。其原理如图2 3 所示1 ”j 。 如果往时刻f ，第z 个刚户传送的负载为x ，o ) ，那么输入网络的总负载虑为x f 0 ) 。系统 状态可用力维向量表示为： xo ) = & ，o ) ，x 2 ( tl 不人于网络的承受能力x g o 口，则 所有刚户的负载请求都会被接收， 这样x ；o ) 也同时表示网络系统 分配给每个用户的资源。用户与系 统之间通过反馈控制函数yo ) 相互作用，实时地改变传送负载大 小。假设改变量为u ；o ) ，则 图2 - 3t c p 拥塞闭环控制原理图 x fo + f ) = xfo ) + “fo ) 。变化“，o ) 就代表了对第f 个用户的控制，它应该 是用户在f 时刻的负载和系统反馈的函数：“，o ) = f & ；o ) yo ) ) ，也就是 x ，o + f ) = x ，o ) + f & ，o ) ，yo ) ) 。 闭环控制可以动态地适应网络变化，但它的缺陷是算法性能易受到反馈延迟的影响n7 1 。当拥塞 点和控制点之间的延迟很大时，算法性能会严重下降。而且瓶颈资源反馈给发送端的状态只有过载 7 、l - 、l vx 月崩 粜 n h 细 、l歹 、j l v 疗x 江南大学硕f j 学位论文 或欠载两种，并不能反映出过载羽i 欠载量的大小，完全由发送节点的控制函数来调节发送数据量， 往往导致发送端数据溢出，引起丢包。 2 2 2 源算法和链路算法 根据算法的实现侮置，可将拥塞控制算法分为源算法( s o u r c ea l g o r i t h m ) 币1 1 链路算法( 1 i n k a l g o r i t h m ) 2 0 1 两人类。源算法在主机和网络边缘设备中执行，作川是根据反馈信息调整发送速率。链 路算法在网络设备( 如路由器和交换机) 中执行，作州是检测拥塞的发生，产生反馈信息。拥塞控制算 法设计的关键就是如何产生力：响应反馈信息。 t c p 是目前在i n t e r n e t 中使用最j “泛的传输控制协议。据m c i 统计2 1 1 ，总字1 ，数的9 5 和1 总报文 数的9 0 都使川了t c p 传输，源算法则是应川最j 泛的t c p 拥塞控制算法。近年来，t c p 协议中采用 了许多新的源算法，大人提升了网络传输的性能，这已成为i n t e m e t 稳定性的重要保障【2 2 1 。 链路算法的研究目前主要集中在“主动队列管理”( a c t i v e q u e u e m a n a g e m e n t ，a q m ) 算法方面。 与传统的“队尾丢弃”( d r o p t a i l ) 相比，a q m 在网络设备的缓冲溢出之前就标记或丢弃报文2 3 1 ，其 优点是： ( 1 ) 增强了网关容纳突发流量的能力，降低了报文丢欠率。 ( 2 ) 有效地减小了平均队列k 度，缩短了报文在网络设备中的排队延迟。 a q m 的一个典型代表是r e d ( r a n d o me a r l yd e t e c t i o n ) t 2 4 1 算法。研究表明，r e d l 匕d r o p t a i l 具有 更女，的性能。但它对参数的设置过分敏感，至今没有在i n t e r n e t 中得到广泛应用。 2 3 源算法及存在问题 2 3 1t c p 源算法的基本策略 鉴于本文的研究方向，下面重点 讨论t c p 拥塞控制的源算法，它可分 为以- 卜四个步骤：( 如图2 _ 4 ，其中 m s s ( m a x i m u ms e g m e n ts i z e ) 为最人 分组长度，即网络能够传输的最人数 据单元的字节数。) ( 1 ) 当拥塞窗口( c w n d ) 小于门 限阂值( s s t h r e s h ) 时，采用慢启动 ( s l o w s t a r t ) 机制来获得网络可用带 宽。收到每个应答包a c k 后， c w n d = c w n d + l ： ( 2 ) 当c w n d 大于s s t h r e s h 时， 进入拥塞避免( c o n g e s t i o na v o i d a n c e ) 状态，并尽可能地重新探测网络可用 带宽。收到每个应答包后， c o n n e c t ，飞、 ( d u p a c k j c w n d - , 一c w n d + ms s 2 ) 图2 4 现有拥塞控制机制的有限状态自动机f s m t 2 5 1 8 第二章拥塞控制及j e 算法研究 c w n d = c w n d + 1 c w n d ： ( 3 ) 当收到三组霞复应答返同报文a c k 时，采川快速重传( f a s tr e t r a n s m i t ) 机制重发a c k 指 示的数据包，并利川快速恢复( f a s tr e c o v e r y ) 机制对c w n d 和s s t h r e s h 重新赋值，避免进入慢启动阶 段，s s t h r e s h = c w n d 2 ，c w n d = s s t h r e s h + 3 ； ( 4 ) 当一旦发现重传定时器r t o ( r e t r a n s m i s s i o nt i m eo u t ) 超时后，发送端将不得不再次进 入剑慢启动阶段，s s t h r e s h = c w n d 2 ，c w n d = l 。 由于t c p 缺少显式拥塞发现机制，它假设分组丢失是由网络拥塞引起的。这通过两种方法来判 断：( 1 ) 发送端对最近未确认的分组维护一个重传定时器r t o 。每确认一个新分组，其r t o 重新设定， 发送端通过检测r t o 超时而判断分组丢失；( 2 ) 三组重复确认a c k ( t h r e ed u p a c k ，记作t d a c k ) 。 其产生不外乎二种原闪【2 6 l ：分组丢火；分组乱序；网络对分组或a c k 的复制。为了尽鼙避免 后两原冈，规定当发送方收到t d a c k 时，则认为该分组丢欠。因此只要发送端没有按时收到应当返 同的应答报文a c k ，就可认为网络出现了拥塞。 2 3 2 源算法的主要问题及缺陷 为了保证i n t e m e t 的稳定性，现有的t c p 采用了较保守的a i m d 算法，其最人缺点在于频繁的 粗粒度超时【2 7 ( c o a r s e g r a i n e dt i m e o u t ) 。这种超时将恶化t c p 性能，降低其吞吐量，导致连续的突发 性丢包( 对带宽为b 的t c p 链路，最大丢包数可达8 1 8 m s s ) ) 。随着人容量链路的引入，t c p 连接带宽的增加，这一问题将更加突出。为此，人们义提出了快速重传和快速恢复( f a s tr e t r a n s m i s s i o n a n df a s tr e c o v e r y , f r f r ) 算法，它能减少几乎5 0 的粗粒度超时，提高约2 0 的吞吐型2 引。 目前，这种基于窗口的端到端( e n d t o - e n d ) 拥塞控制机制对于i n t e r n e t 上大批量文件传输等尽量做 好( b e s t - e f f o r t ) 型服务具有较好的适应性。但在现代网络高带宽低延迟的环境卜，它仍被证明是极其 低效的。有个典犁的例子2 9 】：一条7 2 g b p s 的链路，设i 唧为l o o m s ，t c p 包大小1 5 0 0 b y t e s ，发送 窗口峰值可达8 0 0 0 0 。当一次分组丢失后，窗口速率减半，那么发送端需要4 0 0 0 0 个i m 时间来恢 复到它丢包前的发送速率，约需要近7 0 分钟时间，这意味着链路将在相当长的一段时间得不到充分 利用。冈此速率增长过慢减少过快是a i m d 的主要问题。 需要指出的是，在t c p 端系统处主要是通过降低数据发送速率米缓解拥塞。但这种算法不能及 时地对佣塞进行处理，而只能通过滞后的处理减缓对网络的压力。它可在一定程度上控制注入的业 务流量，缓解网络拥塞程度。但由于拥塞控制的复杂性，使得现有方案还都存在着亟待解决的问题。 如何建立一整套有效的分析理论来指导目前单纯凭经验来改进算法的不足? 这些都是研究的热点， 也是难点。 2 3 3t c p 协议的公平性问题 在i n e t m e t 中，面向连接的t c p 和无连接的u d p 在发生拥塞时将会作出不同的反应和处理，从而 在两者之间产生对网络资源不公平使用的问题。当拥塞发生时，有拥塞反应机制的t c p 数据流会退 出拥塞避免阶段，并主动减少送入网络的数据量。而无连接的u d p 缺乏这种机制，即使出现了拥塞 9 江南大学硕f ：学位论文 指示( 如数据包丢失、收到重复a c k 等) ，也不会减少输入网络的流量。结果使得t c p 流得剑的资源越 米越少，而u d p 流将获得更多的资源，这就导致了网络资源分配的不公平。而这种不公平性义反过 米将进一步加重拥塞，共至可能导致拥塞火控。冈此必须设法判断在拥塞发生时各个数据流是否遵 守t c p 拥塞控制机制，同时惩罚那些不遵守拥塞控制的流量。目前，针对这个需求已有人提出了 t c p f r i e n d l y 机制，其定义为【4 】：k 时间的u d p 吞吐量不能超过相同条件一v t c p 迩接的吞吐量。它使 川基丁速率的拥塞控制，速率的计算建立在t c p 吞吐餐模型之上。 另外，一些t c p 连接之间也存在着公平性问题。产生问题的原冈在于一些t c p 在拥塞前使j f 了大 窗口尺寸，或者它们的i u t 较小，或者其数据包比其它t c p 包大，这样它们也会占据较多的带宽。 总之，解决t c p 拥塞控制公平性问题的根本出路是在i n t e r n e t 上全面采用端剑端的拥塞控制并融合i p 层拥塞控制的新算法。目前，基丁m 层进行的控制实施在网络层。它可以不依赖于信源，实现均匀 的资源分配，但不可避免地增加了路由器等中间设备的复杂性。解决上述问题可以通过在路由器处 使用公平队列【3 0 i 雨i t c p 友好缓存管理【3 1 1 米增加公平性，并且要求t c p 源端的拥塞控制机制也作相应 改变。 2 4 源算法的改进方向 目前拥塞