（信号与信息处理专业论文）基于qos路由路径优化的网络拥塞控制.pdf

原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立 进行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含 任何其他人或集体已经发表或撰写过的科研成果。对本文的研究做出重 要贡献的个人和集体，均已在文中以明确方式标明。本声明的法律责任 由本人承担。 学位论文作者： 奇奇 日期：砂1 0 年f 月醒目 学位论文使用授权声明 本人在导师指导下完成的论文及相关的职务作品，只是产权归属郑 州大学。根据郑州大学有关保留、使用学位论文的规定，同意学校保留 或向国家有关部门或机构送交的复印件和电子版，允许论文被查阅和借 阅；本人授权郑州大学可以将本学位论文的全部或部分编入有关数据库 进行检索，可以采用影印、缩印或者其他复制手段保存论文和汇编本学 位论文。本人离校后发表、使用学位论文或与该学位论文直接相关的学 术论文或成果时，第一署名单位仍然为郑州大学。保密论文在解密后应 遵守此规定。 学位论文作者： 赵寸甘 日期：弘f 。年岁月2 9 同 、 摘要 摘要 随着互联网i n t e r n e t 的飞速发展，网络多媒体业务也日趋多样化，网 络拥塞成为制约网络发展和应用的瓶颈。传统的拥塞控制方法仅仅针对 某单一问题的解决，并不能从整体关键部位着手解决拥塞，已经不能满 足网络发展的需要。本文通过分析大量文献资料，找出了拥塞易发症结， 针对网络中的关键节点、关键链路实施新的路由算法，从而使得网络负 载均衡分配，获得一个高q o s 保证的网络环境。 网络中q o s 路由成为近年的研究热点，通过网络路径优化，降低网 络中数据包的丢失率，提高链路吞吐量，减小时延，从而为互联网i n t e r n e t 创建一个更加稳定的环境。本文对基于关键链路节点拥塞控制进行了深 入的研究，其主要工作包括以下几个方面： 1 通过对网络拥塞产生的原因、拥塞控制机制、已有拥塞控制算法 进行分析和总结，提出了利用网络路径优化解决网络拥塞控制问题的思 想。对网络仿真软件n s 2 进行了部分功能扩展，取得了较好的效果。 2 深入细致的研究了路径优化对网络路由选择产生的影响，并对其 在拥塞控制方面所发挥的作用进行 f i j 析，为本文提出基于热点链路的路 径优化奠定了理论基础。i 司时，在对网络拥塞分析的基础上，对网络拥塞 路径优化进行了深入地探讨，为实现网络拥塞提供了条件。 3 经过深入分析已有的网络拥塞控制算法后，提出了以解决热点链 路拥塞为目标的拥塞控制算法，即网络中的关键：宵点链路旦出现拥塞， 往往导致整体网络出现连锁反应，从而整个网络处于瘫痪状态，本文所 提算法，以解决此问题为目标。仿真结果表明，该优化算法可实现网络 拥塞控制，提高网络性能，达到拥塞预防的目的。 关键词：网络拥塞控制服务质量多路径路由路由优化热点链路 a b s t r a c t a b s t r a c t w i t ht h er a p i d d e v e l o p m e n to ft h ei n t e r n e t ，n e t w o r km u l t i m e d i a s e r v i c e sa r ea l s o g e t t i n gd i v e r s i f i e dd a yb yd a y n e t w o r kc o n g e s t i o ni s b e c o m i n gt h eb o t t l e n e c k w h i c hr e s t r i c t st h en e t w o r kd e v e l o p m e n ta n d a p p l i c a t i o n t h et r a d i t i o n a lm e t h o d so fc o n g e s t i o nc o n t r o la r co n l ya i m e da t t h es o l u t i o no fc e r t a i ns i n g l ep r o b l e m i tc a n tf i g u r eo u tc o n g e s t i o nf r o m t h ew h o l es i g n i f i c a n t p o i n ta n d c a n t s a t i s f y t h en e e d s o fn e t w o r k d e v e l o p m e n t w i t hp l e n t y o f a n a l y s i s a n d l e a r n i n g o ft h er e f e r e n c e d o c u m e n t a t i o n ，t h i sp a p e rf i n d so u tt h ek e yn o d et h a tc o n g e s t i o nc a ne a s i l y h a p p e n a i m e da tt h ek e yn o d ea n dk e yl i n ki nt h en e t w o r k ，an e wr o u t i n g a l g o r i t h mi sg i v e ni n t h i sp a p e r s oi tc a nb a l a n c et h en e t w o r kl o a d sa n d g a i nah i g hq o si nn e t w o r ke n v i r o n m e n t r e s e a r c h i n go nt h et e c h n o l o g yo fi n t e r n e tq o sr o u t i n gi sb e c o m i n ga h o ts p o t b yo p t i m i z i n gt h en e t w o r kp a t h ，i tc a nd e c r e a s et h el o s s r a t eo f d a t ap a c k a g ei nt h en e t w o r k ，i n c r e a s et h et h r o u g h p u tc a p a c i t ya n dr e d u c e t i m ed e l a y ，t h e r e b yc r e a t eam o r es t a b l ee n v i r o n m e n tf o rt h ei n t e r n c t t h i s a r t i c l es t u d i e sd e e p l yo nt h ec o n g e s t i o nc o n t r o lw h i c hi sb a s e do nt h ek e y l i n kn o d e ，a n dt h em a i nw o r k si n c l u d et h ef o l l o w i n ga s p e c t s ： 1 t h i sp a p e rs t u d i e sa n ds u m su pt h er e a s o nw h yn e t w o r kc o n g e s t i o n h a p p e n ，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 dc o n g e s t i o nc o n t r o la l g o r i t h m i n o r d e rt os o l v et h en e t w o r kc o n g e s t i o nc o n t r o lp r o b l e m ，am e t h o do fn e t w o r k r o u t eo p t i m i z a t i o ni s p r o p o s e d t h es t u d ye x t e n d st h ef u n c t i o no ft h e n e t w o r ks i m u l a t i o ns o f t w a r en s 2 ，a n da c h i e v e sab e t t e re f f e c t 2 i ti n t e n s i v e l ys t u d i e st h ee f f e c to ft h er o u t i n go p t i m i z a t i o nt on e t w o r k r o u t es e l e c t i o n ，a n da n a l y s e st h ef u n c t i o no ft h ec o n g e s t i o nc o n t r o l ，a n dl a y s t h et h e o r e t i cf o u n d a t i o no ft h e p a p e r m e a n w h i l e ，b a s e do nn e t w o r k c o n g e s t i o na n a l y s i s ，i t m a k e sa n i n d e p t h d i s c u s s i o na tt h en e t w o r k c o n g e s t i o np a t ho p t i m i z a t i o n ，a n dp r o v i d e sac o n d i t i o n t or e a l i z et h e n e t w o r kc o n g e s t i o n n 3 i ti n t e n s i v e l ya n a l y z e sa n dl e a r n st h ee x i s t i n gn e t w o r k c o n g e s t i o nc o n t r 0 1 a l g o r i t h m ，a n dp r o p o s e sac o n g e s t i o nc o n t r o l a l g o r i t h mw h i c ha i m e da t s o l v i n gt h eh o tl i n kc o n g e s t i o np r o b l e m o n c ec o n g e s t i o no c c u r s ，t h ek e v n o d e si nt h en e t w o r ko f t e nr e s u l ti nc h a i nr e a c t i o ni nt h ew h o l en e t w o r k t h e r e b yt h ew h o l en e t w o r kw i l lb ei nas t a t eo fc o l l a p s e s ot h ea i g o r i t h mi n t h ep a p e ri sa i m e da t f i g u r i n go u tt h ep r o b l e m t h er e s u l to fs i m u l a t i o n p r e s e n t st h a tt h ea l g o r i t h mc a nr e a l i z en e t w o r kc o n g e s t i o nc o n t r o l ， n e t w o r kp e r f o r m a n c ea n da c h i e v ea g o a lo fc o n g e s t i o np r e c a u t i o n k e y w o r d s ：n e t w o r k c o n g e s t i o nc o n t r o l ；n e t w o r k q u a l i t y o f m u l t i 。p a t hr o u t i n g ；q o sr o u t i n go p t i m i z a t i o n ；h o t 1 i n k e n h a n c e s e r v i c e ； f 录 目录 摘! 要i a b s t r a c t i 】 i 第1 章绪论1 1 1 研究背景1 1 2 国内外研究现状及问题提出2 1 3 本文的主要贡献5 1 4 论文的结构安排6 第2 章相关知识介绍8 2 1 引言8 2 2 网络拥塞的定义及产生原因8 2 2 1 网络拥塞的基本概念8 2 2 2 拥塞产生的原因9 2 3 拥塞控制机制及其算法分类1l 2 3 1 拥塞控制机制11 2 3 2 拥塞控制算法的分类：1 3 2 4 网络仿真工具n s 2 15 2 4 1n s 2 简介1 5 2 4 2n s 2 体系结构及特点1 6 2 4 3n s 2 仿真软件在网络研究中的应用1 7 第3 章q o s 路由和路径优化的拥塞控制研究2 0 3 1q o s 的定义和度量2 0 3 2q o s 路由的指标选择以及执行过程2 1 i v 日录 3 3q o s 路由算法分类2 4 3 4q o s 路由算法特征2 6 3 5 网络路径优化策略2 7 3 5 1 网络路径优化的现状2 8 3 5 2 负载不均衡路径优化3 0 3 5 3 多路径的路由技术选择比较3 1 3 5 4 仿真分析结果3 3 3 6 总结3 4 第4 章基于热点链路的多路径路由选择算法3 6 4 1 引言3 6 4 2h l s m p r a 算法设计3 6 4 3 算法仿真结果3 8 4 3 1 网络模拟环境3 8 4 3 2 模拟仿真结果3 9 4 4 结束语_ 4 l 第5 章总结与展望4 2 5 1 总结_ 4 2 5 2 展望4 2 参考文献j 4 4 附录：攻读硕士学位期间发表的学术论文4 8 至j 谢。4 9 v 第1 章绪论 第1 章绪论 1 1 研究背景 网络的飞速发展，给人们生活带来巨大的变化，它已经延伸到我们的工作、 学习、生活中的各个方面。计算机网络从产生到发展，总体来说可以分成4 个 阶段。 第一个阶段：2 0 世纪6 0 年代末期到2 0 世纪7 0 年代初期为计算机网 络发展的萌芽阶段。其主要特征表现是：为了增强系统的计算能力，实 现资源共享，于是把小型计算机连成实验性的网络。世界上出现的第一 个远程分组交换网是a r p a n e t ，l9 6 9 年由美国国防部建成的，第一次 将通信网络和资源网络结合成计算机网络系统。这一完美的结合标志计 算机网络的真正产生，从此a r p a n e t 成为早期计算机网络的典型代表。 第二个阶段：局域网( l a n ) 成为2 0 世纪7 0 年代中后期网络发展的 新趋势，其主要特征表现：局域网作为一种新型的计算机体系结构开始 进军产业部门，为网络以后的产业化发展奠定了基础。局域网最初是由 网络研究人员从远程分组交换通信网络和i o 总线结构计算机系统派生 出来的。19 7 6 年，美国p a l oa l t o 研究中心推出以太网( e t h e r n e t ) ，是当 今现有局域网采用的最通用的通信协议标准。它成功地将夏威夷大学 a l o h a 无线电网络系统的基本原理应用到以太网的构件中，使之发展 成为第一个总线竞争式局域网络。19 7 4 年，英国剑桥大学计算机研究中 心成功研制剑桥环局域网( c a m b r i d g er i n g ) ，为局域网开辟了新的网络架 构。这些网络的成功诞生，一方面标志着局域网络的产生，另一方面， 早期的局域网体系结构对以后局域网络的发展起到导航作用。 第三个阶段：2 0 世纪8 0 年代，这一阶段是计算机局域网络的发展 时期。其主要特征表现是：为了使不同体系结构的计算机网络都能互联， 国际标准化组织i s o 提出了一个能使各种计算机在世界范围内互联成网 的标准框架一一开放系统互连基本参考模型o s i 。综合业务数据通信网 络( i s d n ) 矛 i 智能化网络( i n ) 的出现，推动了局域网的飞速发展。19 8 0 年， 第1 章绪论 8 0 2 局域网络标准委员会提出i e e e 8 0 1 5 8 0 2 6 等局域网络标准草案，大 部分网络标准已经得到围际标准化组织( i s o ) 正式认可。作为局域网络的 国际标准，它标志着局域网协议及其标准化的确定，为以后局域网的深 入发展奠定了坚实的基础。 第四个阶段：从2 0 世纪9 0 年代初至今，是计算机网络飞速发展的阶 段，主要特征表现是：计算机网络化，带动计算能力发展以及全球：自：连网的 热潮。目前，计算机网络已经渗透到社会各行各业，并被广泛应用。其次， 虚拟网络f d d i 及a t m 技术的诞生，使网络技术蓬勃发展并迅速产业化，市 场化，建进了平民百姓的生活。 当前，网络技术日趋飞速发展，使互联网遍布全球，应用领域得到 了不断拓展，并丰富了其应用模式。人们可以享受多媒体网络带来的种 种便利，比如，发送邮件、视频会议、网络在线点播和网络电视等各式 各样的网络业务。网络所能给人们提供的服务逐渐多样化，与此同时也 就要求有更加稳定的网络环境去实现这些需求。网络规模的不断壮大， 使得网络环境变得更加复杂，而网络拥塞成为计算机网络通信网中的一 个瓶颈。 1 2 国内外研究现状及问题提出 近年来，计算机网络经历了飞速发展，使得信息的传递和交流变得 。更加方便与快捷。然而，由于网络数据流量不断剧增，在网络资源有限 的今天，拥塞问题随之产生，且变得愈加严重，己经成为当前制约网络 发展和应用的一个瓶颈，如何有效地避免拥塞，以及控制拥塞成为近十 多年来网络研究的热点问题之1 2 , 3 。在i n t e r n e t 中实施拥塞控制是其它服 务质量( q o s ) 机制正常工作的前提，也是优化网络性能、保证网络鲁棒性 的重要手段。 网络之所以产生拥塞，其根本原因在于网络上的用户( 或叫端系统) 负载大于网络资源容量和处理能力，从而导致数据包延时增加、丢包率 加大、吞吐量降低以至于上层应用系统性能下降【4 】4 。 2 第1 章绪论 针对网络出现拥塞的状况，最初的解决方法是基于t c p 拥塞控制， 这是由于i n t e r n e t 上绝大多数的数据流使用的是t c p 协议。因此，有关 t c p 拥塞控制始终是网络拥塞控制研究的重点。t a h o e 算法【5 】是t c p 关 于拥塞控制的早期版本，它由“慢启动”、“拥塞避免”和“快速重传”三部 分组成。r e n o 算法【6 】是在t a h o e 算法的基础上增加了“快速恢复”算法用 来提高拥塞恢复的效率，r e n o 的“快速恢复”优化了单个分组从数据窗口 的传播速率。n e w r e n o 算法【j 7 】也是对r e n o 算法作了一小部分的改进， 从而消除有多个分组从同一数据窗口丢失时对重传定时器的等待。v e g a s 算法【8 】将r e n o 算法进行了改进，使拥塞控制机制的触发不再依靠数据包 的具体传输延时，仅仅与往返时间r t t 有关。 随着网络日趋复杂化，促使网络拥塞的因素逐渐增多，仅仅依靠现 有的t c p 拥塞控制机制已经满足不了网络的需求。因此，需要采用路由 器的拥塞控制方法，即i p 拥塞控制【9 1 。于是，人们将拥塞控制渗入到i p 拥塞控制，其中，先进先出( f i r s ti nf i r s to u t ，f i f o ) f i f o 1 0 】是一种最简 单的调度算法，通过数据包的调度策略，决定着数据包在链路上传送的 顺序。这种方法的优点是实施比较简单，但是忽略了丢包率。随机早期 检测( r a n d o me a r l yd e t e c t i o n ，r e d ) r e d ( 通过早期探测路由器是否 将发生拥塞，采取措施避免其发生拥塞；并且有效地处理t c p 业务流的 异常情况；同时它在吞吐量和时延之间做出合理平衡。显式拥塞指示算 法( 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 ) e c n 不需要重传超时，有效地提高 网络带宽的使用效率。公平排队算法【汜】( f a i rq u e u i n g ，f q ) 它是一种“轮 询”调度算法，该算法可以实现每个数据流不用牺牲其它数据流而多占资 源。加权公平排队算法【”】( w e i g h t e df a i rq u e u i n g ，w f q )w f q 是公 平排队v o 的改进算法，该算法根据不同数据流应用的不同带宽要求，采 用加权方法为每个排队队列分配相应的缓存资源，从而达到增加f o 对 不同应用的适应性。 国内外许多学者通过借助神经网络、禁忌搜索算法、遗传算法、蚁 群算法等智能算法来优化网络路径，从而解决网络拥塞，在一定程度上， 第1 章绪论 取得了很好的成果【。2 0 1 。为了找到“全局最优解”，就不应该执着于某一 个特定的区域。禁忌搜索算法( t a b u 搜索算法) 就是对于找到的一部分 局部最优解，有意识地避开它( 但不是完全隔绝) ，从而获得更多的搜 索区间。遗传算法( g e n e t i ca l g o r i t h m ) 是模拟达尔文生物进化论的自然 选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进 化过程搜索最优解的方法。蚁群算法( a n ta l g o r i t h m ) 是从蚂蚁寻找食 物中得到启发，研究如何将蚁群寻找最短路径应用到网络路由路径的优 化过程中，该算法具有分布计算、信息正反馈和启发式搜索的特点，在 求解组合优化问题中得到了广泛应用。这些算法已经被证明是一种解决 优化问题的有效工具，此方面的研究很多，比如文献【2 l 】利用蚂蚁算法的 自适应性和随机性，探索带宽受限情况下网络拥塞时的动态路由选择。 文献【2 2 中提出了一种基于蚁群算法的拥塞规避路由算法，通过避绕拥塞 链路来提高蚁群算法搜索最优路径的速度。文献【2 3 】中针对蚁群算法在网 络负载分担方面的不足，提出改进算法。通过减少在最短路径上的蚁群 来实现路由的负载分，避免链路负载过重而出现拥塞。文献 2 4 】提出利 用遗传算法，选择带宽( b a n d w i d t h ) 、时延( t i m e d e l a y ) 、丢包率及时 延抖动作为选路时的尺度，找到满足这些q u s 参数约束的最优路径。文 献【2 5 在考虑网络带宽、时延的基础上，将资源利用函数和网络负载分布 作为目标函数利用遗传算法求出最优路径，避免路径出现拥塞。随后， 又出现了上述算法的融合算法，比如文献 2 6 2 7 】提出了将遗传算法融入 到蚁群算法中来解决q o s 路由选择策略，是一种新的求连续空间最优值 的蚁群算法，该算法充分利用了遗传算法和蚁群算法的优点，提高了算 法的寻优效率。粒群算法是一种新的解决多q o s 约束路由问题智能算法， 文献 2 8 】中改进粒子群优化算法采用了新的粒子速度更新策略和粒子抗 拥塞策略，收敛快，该算法在很大程度上解决了路由选路的难题。 鉴于以上拥塞控制中典型算法的分析和介绍，不难看出，已有的这 些算法虽然进行了不断的改进，系统性能得到了有效的提高，但其自身 几乎都存在着这样或那样的不足之处。究其直接原因就是以上算法的设 4 第1 章绪论 计都是针对局部的某一具体问题进行，依据理论分析，凭借经验改进算 法，缺乏一套有效的系统的理论分析工具对算法的设计进行指导。近年 来，国内外的很多专家学者都针对网络拥塞控制进行了更加深入的研究， 然而，由于互联网i n t e r n e t 本身是一个复杂的巨系统，而且其中的各种 不同算法控制策略之间也会互相影响，使得对网络稳定性和动态性能的 分析变得更加困难，因而这方而的研究还不成熟，所以，在已有的算法 基础上，如何更加有效地控制网络中的拥塞现象，将是一个未来研究的 热点问题，也是一个难点问题。 1 3 本文的主要贡献 目前拥塞控制的研究主要分两个方而：t c p 层的拥塞控制和i p 层的 拥塞控制【29 1 。t c p 层的拥塞控制主要是采用基于窗口的端到端的算法， 该类拥塞控制机制对于互联网i n t e r n e t 的鲁棒性起到了关键作用，并且当 前的互联网中，t c p 层的拥塞控制得到广泛应用。随着i n t e r n e t 的发展， 网上业务变得愈加繁忙，网络中通信量的迅速增长让主干网变得日益拥 塞，严重时甚至会导致网络的瘫痪。与此同时，新业务的涌现对网络提 出更高的服务质量要求，仪依靠t c p 拥塞控制机制来提高网络服务质量 还不够；为了满足这些需求主干网路由器就必须采取一定的策略来避 免和控制网络拥塞也就是我们本文中所要讲到的i p 层的拥塞控制，从 而保证网络畅通并能提供一定的服务质量保 正q o s 今后拥塞控制的主 要方向应该足，在7 r c p 层拥塞控制基础之上，采用i p 层的队列管理策略， 以达到共同解决网络拥塞问题。本文从以下几个方面对拥塞控制进行了 相关研究。 第一：定义拥塞现象，分析拥塞产生原因以及学习拥塞控制的相关 知识； 第二：总结、分析和比较了当前网络中拥塞控制算法，指出各种改 进算法在吞吐量、时延、丢包率、利用率和成本等方而的不足，为课题 的研究提供了参考依据和新的研究思路，从而给出了课题的研究方向和 5 第1 章绪论 目的。 第三：从分析q o s 路由出发，以路径优化来解决网络中出现拥塞为 目的，最后通过分析对比已有的多路径算法( 最宽不相交路径w d p 算法、 等代价多路径e c m p 算法、权重多路径w c m p 算法) 。本文通过仿真，得 出三种算法的优缺点，为进一步研究做好铺垫。 第四：分析对比已有算法的不足之处，给出本文所提出热点链路路 由选择的拥塞控制算法，通过仿真得出该算法在性能上的优势。 1 4 论文的结构安排 通过综合分析已有的拥塞控制算法，在其基础上，本文提出了基于 热点链路路径优化的拥塞控制算法，优化了网络资源，达到负载均衡的 目的。论文具体章节安排如下： 陌翮i 绪论l 相关知识介绍 基于q o s , 路- 由路径优化的 拥塞控制的礤宄 基于热点 图1 1 论文研究结构 第l 章绪论。介绍了当今计算网络的发展历程，并引出网络出现危 机一一拥塞，分析了国内外对拥塞研究的现状，提出未来拥塞控制的发 展趋势。 6 第1 章绪论 第2 章相关知识介绍。首先对拥塞的概述，分析了拥塞产生的原因， 以及目前拥塞控制算法机制进行综述。接着给出了网络仿真所用的工具 n s 2 在本文中的应用。 第3 章 基于q o s 路由路径优化的拥塞研究。首先给出网络q o s 的定 义，以及性能指标，然后对目前q o s 路由路径优化进行了研究，并通过 分析具体算法的仿真结果，讨论当前现存拥塞控制算法的利弊问题，指 出当前拥塞面临的挑战。指出这些算法的不足之处，最后引申出本文的 研究方向。 第4 章基于热点链路路径优化的拥塞控制算法。分析热点链路如何 选路以避免拥塞产生，以及如何控制拥塞。最后给出仿真结果，证明该 算法理论上是可行的。 第5 ：e -结论。总结当前网络拥塞控制现状，展望未来拥塞控制的 发展动向。 7 第2 章相关知识的介绍 。 第2 章相关知识介绍 2 1 引言 研究人员最初设计互联网i n t e r n e t 时，对于拥塞的控制是通过t c p 协 议中端到端基于滑动窗口的流量控制完成的【3 0 1 。随着网络应用需求的不 断丰富和技术飞速发展，对网络拥塞的控制策略逐步转向网络中的路由 器等中间节点设备，试图通过增强它们的功能来实现主机端无法达到的 拥塞控制的技术目标。针对拥塞控制，网络中问节点设备有可能更及时， 甚至提前准确获取到网络的拥塞状态信息，以此实施更加有效的资源管 理策略，避免网络产生拥塞，或尽早从严重的拥塞状态中恢复过来。 2 2 网络拥塞的定义及产生原因 2 2 1 网络拥塞的基本概念 拥塞是一种持续过载的网络状态，即当网络中存在过多的数据包时， 网络的性能就会下降，这种现象称为拥塞【3 | 1 。当用户对网络资源( 包括 链路带宽、存储空问等) 的需求超过了链路上固有的容量，网络就会发 生拥塞。就互联网i n t e r n e t 本身的体系结构而言，拥塞的发生是其固有的 属性。在资源共享网络中，由于事先没有经过任何协商，或者请求许可 机制，几个i p 分组同时到达路由器，它们都希望经同一个输出端口转发 的可能性是客观存在的，显然，所有分组不可能同时被处理器处理，它 们必须有一个服务顺序，这时中闸节点上的缓存就为等候服务的分组提 供一定保护。然而，假如这种状况具有一定的持续性，一旦缓存空间被 耗尽，路由器也只有选择丢弃一部分分组。在这种持续过载的状态下， 网络性能会急剧下降，这就不可避免要产生拥塞，于是关于拥塞控制策 略就应运而生了。 目前由于i n t e r n e t 采用了统计复用技术，网络上大量的数据流共享一 条链接，其运行环境在不断发生变化，而i n t e r n e t 中所采用的主流通信协 8 第2 章相关知识的介绍 议是基于t c p 1 p 协议栈的网络通信协议，是一种尽力而为( b e s t e f f o r t ) 的服务模型【32 1 ，所有的数据流将会被不加区分地在网络中传输，网络无 法实现提前给用户一个定量的性能指标( 如吞吐量、时延、包丢失率等) 。 因此，在目前网络带宽有限，数据传输的需求量远远超过网络的瓶颈带 宽时，最终必定会产生拥塞。拥塞导致的直接后果是数据分组丢失率提 高，端到端时延增大，甚至可能导致整个系统崩溃【33 1 。当网络处于或即 将陷入拥塞崩溃状态时，微小的负载增量都将使网络的有效吞吐量急剧 下降。由此可见，拥塞控制策略显得尤为重要。图2 1 给出了负载与吞吐 量之间的关系。从图中不难看出，负载较小时，吞吐量与网络负载之间 呈线性关系；当吞吐量上升至膝点r k n e e ) 之后，随负载的增加，吞吐量 的增长速率逐渐变小；如果网络负载继续增加，当超过崖点( c l i f 0 之后， 网络吞吐量反而开始急剧下降。通常规定k n e e 点附近是拥塞避免区问； k n e e 点和c l i f f 点之间为拥塞恢复区间；而c l i f f 之外统称拥塞崩溃区间【34 1 。 从图可以看出，网络负载在k n e e 附近时，网络的利用率最高。 震 量 网络负载 图2 1 吞吐量与负载之问的关系 2 2 2 拥塞产生的原因 网络之所以产生拥塞，其根本原因是由于用户( 或叫端系统)提 供给网络的负载大于网络自身资源容量和处理能力，表现为数据包延时 加大、丢包率增大、网络上层应用系统性能下降 3 5 1 。大鼍研究表明，网 9 第2 章相关知识的介绍 络产生拥塞的直接原因有以下几个方面： ( 1 ) 存储空间不足。往往几个输入数据流共同需要同一个数据输入端 口，于是它们在这个端口就会建立排队，如果没有足够的存储空间，其 中一部分数据包就会被丢弃，且对突发数据流更是如此。然而，增加存 储空间只能在一定程度上缓解这一矛盾，因为研究证明，如果路由器有 无限存储空间量，拥塞只可能变得更坏，而不是更好。主要是因为网络 里的数据包需要经过长时间排队后才可能通过路由器完成转发，这样不 仅会浪费网络资源，还会加重网络拥塞。 ( 2 ) 带宽不足。这也是造成网络拥塞的直接原因之一，即低速链路对 高速数据流的输入产生拥塞。依据香农信息理论，网络中的低速链路往 往容易形成带宽瓶颈，如果满足不了所有信源带宽要求时，网络拥塞就 会发生。 ( 3 ) 处理器处理能：力弱、速度缓慢。如果路由器的c p u 在执行数据 包排队缓存、更新路由表等功能时，处理速度低于高速链路的承载能力， 这时也会产生拥塞。同样，低速链路对高速c p u 也会产生拥塞。 ( 4 )资源分布不均衡。拥塞往往发生在网络中那些资源“相对”短缺 的位置，而拥塞发生在地理位置上的不均衡性其实恰恰反应了i n t e r n e t 自 身体系结构的不均衡性。i n t e r n e t 中的不均衡性主要体现在资源分布的不 均衡。这些资源主要包括链路带宽、网关中的缓存和网关中的处理能力 等几个方而。图2 2 给出了一个网络带宽不均衡分布示意图。从图中可以 看出，节点1 、2 、3 之问的带宽分布是不均衡的，节点l 和节点2 2 _ 问的链 路带宽为2 0 m b p s ，而节点2 和节点3 2 _ 问的链路带宽仅有2 m b p s ，当1 2 链 路上的数据包流量较大时，发向节点链路2 3 上的数据包很容易产生拥 塞。 图2 2 链路带宽不均衡分布 l o 第2 章相关知识的介绍 由此，网络中拥塞现象发生的原因其实就是“需求”大于“供给”。网 络中有限的资源需要支配给多个用户共同使用。假如没有“接纳控制”策 略，网络就无法根据资源的情况限制用户的数量；同时，互联网络又是 一个分控制系统结构，一旦缺乏中央集成控制，网络就无法控制用户使 用资源的数量0 6 。从而，由于各种因素造成了网络中出现拥塞现象。 2 3 拥塞控制机制及其算法分类 2 3 1 拥塞控制机制 拥塞预防策略的思想就是把即将发生拥塞的可能性降到最低，而不 是任其发生，随后再对其进行相应的反应。不同的网络层将分别采用不 同的拥塞控制策略，从而实现网络拥塞控制的目的。下面将从数据链路 层、网络层、传输层分别介绍拥塞控制策略【39 1 。 首先，在网络中的数据链路层，重发策略是针对那些超时还没到达 的数据包，实施重新发送。与此紧密相连的是缓存策略，如果盲目地丢 弃所有乱序的数据分组，会造成一些数据分组不必要的重传，这将增大 网络上的负载量。确认策略也会影响拥塞，即假如每发送一个数据分组， 都需对其确认，这种确认信息分组也会将造成额外的通信量。一个良好 的流肇控制方案( 例如，一个小窗口) 不但能降低数据传输速率，还可以减 少拥塞。 在传输层，如何确定分组传输超时间隔比较难，因为在网络上的传 输只寸间很难预测。如果时间间隔太短，就会产生额外的不必要的数据分 组；相反，如果太长，虽然拥塞在一定程度上得到减少，但是一旦出现 数据分组丢失时，系统的反应时间又会过长。 网络层中，虚电路和数据报之间的选择同样会对网络拥塞产生影响。 其实，很多拥塞控制算法只用于虚电路子网，比如，分组排队和服务策 略关系到是否为路由器的每条输入输出线路建立一个队列，它还影响处 理数据分组的优先级。丢弃策略则决定当无剩余空间时，将丢弃哪些数 第2 章相关知i 只的介绍 据分组。路由选择算法通过分散通信量到多条线路上，减缓由于数据包 过于集中在一条链路而造成拥塞，而算法的好坏决定了网络的性能优劣。 生命期策略管理是决定一个分组在丢弃前能存活多长时间。生命期的长 短同时也影响了网络拥塞。如果生命期太长，丢失的分组可能会长时间 地阻碍工作；但如果太短，数据分组很可能没有到达目的地就已经超时， 导致重传。 前面已经分析过目前网络拥塞的原因而本文中所指的拥塞是长时 问拥塞，而不是由突发流量造成的短时问拥塞状态。针对资源不足造成 的网络拥塞，通常采取以下两种方法加以解决。 首先，网络扩容，比如，使用更加先进的交换机、路由器或增大传 输媒质带宽。该方法简单易行，但往往要很高的花费。 其次，运用经典的拥塞控制机制，包括速率限制、拥塞窗口控制、 路由器队列管理等策略【37 1 。针对由负载分布不均衡引起的拥塞，单靠增 加网络容量是不能从根本上解决问题的，而且经济开销也比较大。本文 将从路径优化角度提出一种新的路由算法，在既满足服务质量q o s 要求 的同时，又能提高资源优化效率。 拥塞控制就其本质来说是在网络节点采取措施来避免拥塞的发生或 者对已经发生的拥塞状况做出反应。 网络尽最大可能在k n e e 点附近工作。 通常我们所研究的拥塞控制就是让 这就要求在设计网络时，必须具备 灵活高效的拥塞检测、预防与控制机制这一完整的体系结构，才能保证 网络高效率地运行，使网络的鲁棒性增强，但同时又牵涉到网络运行的 经济效益，因此，对于网络拥塞控制的研究具有极其重要的意义。 网络拥塞控制主要是从网络环境中的发送端到接收端进行考虑，其 目的是保证网络中的数据不超过网络的承载及传送能力，避免出现图2 i 中网络性能严重下降的情况。网络拥塞控制策略主要包括两个方面的控 制机制：拥塞避免和拥塞控制【38 1 。拥塞避免则是一种“预防”拥塞发生的 机制，它的目标是事先就避免网络进入拥塞状态，使网络保持在高吞吐 量、低延迟、小丢包率的状态下运行。拥塞控制则是一种一恢复”机制， 1 2 第2 章相关知i 只的介绍 即一旦网络发生了拥塞，该机制能用于把网络从拥塞状态中恢复出来。 在当前所使用的大多数低速网络中，当一个节点发生拥塞时，通常 的解决方法是：该节点通过信令信道将拥塞消息传送给周边相邻节点， 而接到拥塞节点消息的各个节点开始降低转发到拥塞节点的报文数量， 这种状态一直持续到拥塞解除。这种拥塞控制手段称为反映性控制，其 方法偏重于在网络发生拥塞以后再进行控制。不难看出，该控制方法本 质上是一种补救措施，即当拥塞发生以后采取措施，减缓拥塞，以达到 解除拥塞的目的。然而，这种方法仅仅适用于低速运行的网络，因为在 低速网络中，信息传输速率比较低，即便有大量的突发信息在网络中传 输，单位时间内到达网络中某一节点的信息量总体上也是比较少的，所 以，该节点有足够的时问要求相邻节点减少发向该节点的报文量，并在 此基础上消除拥塞，提高网络性能。但该机制不适于高速网络，原因是 1 c p i p 网络中信元的传输速率高，在网络正常的报文传输过程中，单位 时问内到达每一节点的信元数很大，如果网络中出现突发信息，此时处 在v c 上的相应节点必定要承受巨大的信息流压力，一旦瞬间发生拥塞， 在极短的时问内就可能使整条v c 上的所有：市点都处于拥塞状态，并且会 将拥塞状态迅速传染给网络中的其它节点。这势必会促使网络大幅度降 低吞吐量，极大地延长信元传递时间，从而导致大量信元被丢弃，严重 时甚至有可能导致网络崩溃。由此可以看出，预防拥塞机制在高速t c p i p 网络中的意义要远远大于拥塞恢复机制所带来的效益，甚至从某种角度 上说，在高速t c p i p 网络中，传统意义上的拥塞恢复策略往往是不可能 实现的。一个已经进入拥塞状态的节点是没有充足时间与带宽来要求其 相邻节点减少信元发送量。由此可见，拥塞预防机制在高速运行网络中 显得尤为重要。 2 3 2 拥塞控制算法的分类 目前，i n t e r n e t 互联网拥塞控制在拥塞预测、拥塞避免、拥塞抑制的 控制策略研究方面获得了很大成就，大致可以从以下几个方面对拥塞控 第2 章相关知识的介绍 制算法进行分类。 第一方而：从控制论角度出发，可以将拥塞控制算法分为开环控制 ( o p e n l o o p ) ；f i ：i 闭环控制( c l o s e d l o o p ) 两大类【4 0 1 。开环控制策略适用 于那些业务特征可以事先准确规定、性能要求可以提前获得时，例如资 源预留( r s v p 协议) 就是采用开环控制策略来实现的。该方法固然是一种 很直观的控制拥塞的方法，但是由于其实现确定的精确业务特征可能性 极小，因此为保证服务质量q o s 、避免拥塞，往往需要事先预留足够多 的网络资源，因而容易造成网络资源利用率得不到提高。与此相对应的 是闭环控制，它适用于业务特征不能准确描述或者当系统不能提供资源 预留时