（运筹学与控制论专业论文）基于网边缘控制的自适应ip+qos路由研究.pdf

摘要 摘要 随着h 髓m e t 的普及和发展，以及v o i p ，视频会议、视频点播、虚拟现实等 实时多媒体业务的引入，使得网络传输对象不再仅是单纯的文本信息，还包括 视频、音频等多媒体信息。最初，i n t e m e t 设计时并未考虑数据通信的实时性， 采用t c p ，i p 协议主要是为了保证可靠的数据传输。而这种简单的基于“b e s t e 肋r t ”服务模式的端到端传输服务显然已经无法满足目前实际应用的需要。用 户迫切要求b l t 黜t 能够提供应用所需的服务质量( q o s ) 保证。 本文针对端到端的多约束q o s 路由问题，考虑带宽、时延、抖动和丢包率 约束，给出了一种以使q o s 总体评价函数值最小为目标的多约束q o s 路由模型， 并结合i p v 6 提出了一种启发式的基于网边缘控制的自适应pq o s 路由算法一 e d a q ( e d g ed e c i d e ds e l f - a d 印t i v eq o sm 谢n ga l g o r i t h i n ) 。算法中，源节点 发送探测分组进行路由探测，目的节点对获得的可行路径信息进行计算和分析， 生成反馈分组，反馈分组沿途更新路由表信息，核心路由器根据数据信息分组 头上的信息与路由表进行分组转发。可见，该算法正是依靠这种探测和反馈的 机制来自适应地控制多媒体流数据的传输路径，为其提供q o s 保证。从实现机 制上看，e d a q 算法可以减轻网络核心的工作负荷，充分利用网络边缘的剩余 处理能力，提高网络资源的有效利用率：充分考虑现有网络状态的动态性与网 络规模的扩展性，使网络边缘自适应地控制网络的q o s 提供；尽可能地满足当 时状态下的用户需求，同时兼顾传输的稳定性。本文采用珏v 6 作为可路由协议， 既发挥了i p v 6 支持q o s 的优势，又使得研究具有一定的实用性和前瞻性。 最后，通过在网络模拟平台n s 2 上对本文算法进行仿真实验，验证了该算 法的有效性和优越性。 关键词：q o s 路由i p v 6 自适应 一 垒! 璺竺 a b s t r a c t w i t h 也ed e v e l o p m e mo fi i l t 啪e t 锄ds o m en e wr e a l 岫e m u l t i m e d i a a p p l i c 撕o n s ，s l l c h 鹪v o i p ，v i d c oc 0 i l f b 咖c 缸g ，v o d ，v i l t u a lr e a l i 劬如，n o to n i y t 1 1 es i m p l et e ) ( t ，b u ta l s o 、，i d e o 髓da u d i oa r e 订a 1 1 s m i t t e d0 nt l l ei n t e 】m c t o r i g i r l a l i y i n t e m e t 、 ，鹪 j u s td e s i g n e d f o rd a t a c o 姗u i l i c a t i o n s ， b u tt l l ea 1 血n e c o m m l 】n i c a t i o i l sw 船n o tc a r e da b o m t c p pw a sm a i l l l yl l s e dt 0e i l s i h et h a td a 【诅 w e 陀仃黜m m c dr e l i a b l yt o d a y se n d 哟一c n ds e r v i c ep 甜e mb a s e d m es i m 口1 e “b e s te 肋一i m 锄e td e i i v e 巧c 匝n o ts a t i s 匆也e wm u m m c d i a 印p l i c a t i o 璐i ti s u r g e n n yr e q u e 鲫耐m a tt h ei m e r i l e tq u a l i t yo fs e n ，i c c ( q o s ) s h o l l i db eg l l a 瑚m t e e d a c c o r d i n gt oc m t o m e r s r e q u i r 锄e n t s h lt h i sp a p am u l t i c o z l s 缸址n e dq o sr o m i n gm o d e li sf o 】 n l e dt 0s o l v em e p r o b i 锄o fn 卿t i - c o 唧a i de n d - t o e n dq o sr o 嘶n g ，a n dt h eo b j e c ti st om 如血n i z e t l l e 、谥u eo fm ei n 确a t e de 、，a l u a t i o nf h n c t i o n h e 他，b a n d 、i 拙，d e l a y ，d c l a y j i t c e r 粕dp a c k e tl o s sr a t ca r et a k c ni n t oa c c o u n t ah e 面s t i cs e l f a d a 埘v cr o u t i i l g a l g 耐t i l i nb 船c do ne d g ec o m r o l e d a q 倒g cd e c i d e ds e l f a d a 埘v eq o s r o 砸n ga i g o r i 也m ) i sg i v e na c c o r d i n gt 0t 1 1 ef e a n 胛so fi p v 6 mt h ca l g 鲥t h r n ， s o u r c en o d cs c i l d sp m b ep a c k e t st os e a r c hm ea v a i l a b l ep a 恤t h a ts a t i s 句n 璩 c u s t o m 盯s q o sf c q u i r e m e n t s t h ed e s t i n a t i o nn o d ea 1 1 a l y z e sm ei i l f 0 瑚a t i o no ft 1 1 e a v a i l a b l ep a m s ，a 1 1 dt 1 1 e ng e n e r a t e so n co rs e v e r a lf c e d b a c kp a c k e t s t h ef e e d b a c k p a c k e ta d j u s t sm er o u 廿n gt a b l eo ft l l er o u t e r st 1 1 a ta r ei nr e v e r s e dp a t i ln l ec o r c r o u t e r s 蜘1 s m “t l l ei l l f b n n a t i o np a c k e t sa c c o r d i n gt 0t l l er o 埘i l g 诅b l e sa n dt h ei p v 6 h c a d e r s ni so 晰o u sm 砒m i sa l g o r i m mc o u l dc o n 仃0 1t l l e 胁s r n i t t m gp a t l lo ft h e m 山t 妇d i an o wa d 印丘v e l ya 1 1 d p r o v i d ee 虢c t i v eq o sf b rc u s t o m e r sb yt l l e 即b e f c c d b a c ks c h c i l l e e d a qw i i im a k en l eb e s to fn 咖o r kc d g e sr e s i d u a l p r o c e s sc 印a b i l i t ya sw e l l 鹤d c c r e a s en e t w o r kc o r e sl o a d a sar e s 出。证屺砸i i z 撕o n o f m en e t w o r kr e s 0 1 l r c cw i l lb ee m 删e d a si sl 【i l o w nt 0a i l ，也en e t w o r ki sd y n 锄i c 孤ds c a l a b l e a c c o r d i n g l y ，l ce d g e 州i lb ea b l et oc 0 曲帕lm es u p p l yo fq o s a d a p t i v e l yb ye d a q n ea l g o r i t h mw i l l 姆i t sb e s tt os a t i s 匆t 1 1 ec u s t o m 盯s 托q u i r e l n e n t s o fq o s c e r 七a i n l y t h e s t a b i l i t yo ft h em u h i m e d i an o wi sa l s o i i a b s n c t c o i i s i d e r e da tm es 锄et i r n c m v 6i sm e da s 也er o u t c dp r o t o c o li nt 虹sp a p e rb e c a ：i l s e o f i t ss u p p o r tf o rq o s nm a k e sn l i sr e s e a r c hm o r ep m c t i c a b l ea 1 1 da d v a l l c e d a “a 鸥b y 吐屺s i m l l l a t i n go f m ea l g o r i t l l l no nn s 2 ，ak i i l do f n 咖o r ks i l i l u l 撕o n p l a d 咖，i ti sp r o v e dm a tm ep r o p o s c da l g o m b mi se 船c t i v ea 1 1 dp r e f b r a b l e k e yw o r d s ：q o s ； r o m m g ；伊v 6 ；s e l f ：a d a p t i v e i l i 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版j 并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：翮、旭 2 一。年、_ 月z 扫 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 阳、旭 解密时间：年 月日 各密级的最长保密年限及书写格式规定如下： t 内部5 年( 最k5 年，可少丁二5 年) 秘密l 口年( 最长1 0 年一可少于如年) 、 ；机密2 0 年( 最长2 0 年，可多于2 0 年) l i _ _ - - _ _ 。- l - - - - ，_ - 一一一一一 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行研究工作 所取得的成果。除文中已经注明引用的内容外，本学位论文的研究成果不包含 任何他人创作的、已公开发表或者没有公开发表的作品的内容。对本论文所涉 及的研究工作做出贡献的其他个人和集体，均已在文中以明确方式标明。本学 位论文原创性声明的法律责任由本人承担。 学位论文作者签名：7 扣尹硷 乙。彳年，月乙7 日 第一章概述 第一章概述 第一节引言 近年来，i m e m e t 的规模和用户数量一直在不停地迅猛增长，已经发展成为 了一个连通世界各个角落的大型互联网，并逐渐渗入到了商业、金融、政府、 医疗、科研、教育等各个社会部门。与此同时，随着高速网络技术与多媒体技 术的飞速的发展，人们对网络的应用不再仅仅局限于浏览网页、收发邮件等简 单的业务功能，h l t e m e t 上的传输业务已从单纯的数据向语音、视频、图形、图 像、动画等多媒体信息扩展，越来越多的新型分布式多媒体业务迫切要求h l t e m c t 能够提供应用所需的服务质量( q u a l 时o f s e r v i c e ，q o s ) 保证。 然而，传统的h l 垤：r i l e t 本来是面向非实时的数据通信而设计的，其网络结构、 通信协议或质量要求均以数据通信的要求为前提，传输的质量得不到保证。它 采用t p i p 协议簇主要是为了保证可靠的数据传输，这是一种尽力而为( b e s t e 筋r t ) 的服务模式，对于传统的数据应用，如h t t p ( h y p e r t e x t f hp r o t o c 0 1 ) 、 f t p ( f i l et r 觚s 向p r o t o c 0 1 ) 、s m r p ( s 抽p l em a i lt m n s 向p r o t o c 0 1 ) 、t e l n e t 等 较为适用，因为这些业务从本质上来说有很大的弹性，它们可以容忍较大的传 输时延和一定程度的数据丢失，在网络发生拥塞的情况下可以延迟发送，数据 传输的正确性比及时性更为重要。 如今，高速网络中的分布式多媒体应用对网络提出了不同于传统数据应用的 q o s 要求。国际电信同盟( i n t e m a t i o n a it e l e c o n l i i l 吼i c a t i o 璐u i l i o n ，i t u ) 定义 了6 种i pq o s 等级，如表1 1 所示。具体地，对于视频会议这一典型的分布式 多媒体应用业务，要求语音、视频的实时传输，可采用i pq o s 等级o 或等级1 的标准。若网络的0 0 s 度量参数无法达到应用所要求的标准，则会造成声音和 画面出现停顿或延时，以及画面马赛克、爆音等现象。所以，分布式多媒体应 用业务需要网络提供端到端的q o s 控制和保证。传统的简单基于“b e s ce f f o r t ” 服务模式的端到端传输服务显然已经无法满足业务的需要，q o s 的保证对于分 布式多媒体应用尤为重要。 第一章概述 表l 】i t u 定义的6 种i p q o s 等级 q o s 度量度量描述等级b等级l等缀2等级3等级4等级5 l p t d 时延 1 0 0 m s4 0 0 m s1 0 0 m s4 0 0 m sl s 伊d v抖动5 0 m s5 0 m s 未规定 未规定 i p l r 丢包率 l 1 0 0l l o - ，l 1 0 41 1 0 4l x l o - 3 l p e r 错包率 l 1 0 4 未规定 通过增加现有的网络的带宽是满足用户q o s 需求的一种基本途径。但是， i m e n l e t 的数据流量具有突发性，在高峰流量时会出现拥塞局面，不能很好地满 足平均负载的网络带宽。虽然光纤技术和波分复用技术能提供较大的带宽，内 存和处理器的成本也在按摩尔定律下降。但多媒体用户数量和应用的增长将超 过物理带宽的增长也是一个不争的事实，所以带宽的增长并不能完全保证网络 应用的q o s 的要求。 。 因此，i pq o s 的研究对v o i p 、视频会议、视频点播( v o d ) 、网上直播、虚 拟现实、远程教育等这些和国民经济及社会发展关系密切的分布式多媒体业务 具有重要的科学意义和广阔的应用前景。 第二节本文的组织 本文其余部分内容安排如下： 第二章从q o s 的定义出发，探讨了q o s 与用户和网络系统之间的关系；介 绍了m q o s 的体系结构；在系统总结了主要的q o s 路由算法的基础上，引出本 文的算法；简要介绍了i p v 6 的背景及其一些新特性。 第三章是本文的重点，也是核心。首先给出多度量约束q o s 路由选择模型 和q o s 总体评价目标函数，并总体地介绍了算法的基本思想。然后详细描述了 本文用到的几种i p v 6 分组以及路由器上的信息。最后，对本文提出的e d a q 算 法进行详细深入地介绍、分析，并对一些关键性的优化措施进行讨论。 第四章利用网络模拟软件n s 2 对算法进行仿真实验，并与d v 算法对比，说 2 第一章概述 明e d a q 算法的优越性。 第五章总结全文，讨论了e d a q 算法的优势与不足，并对此算法的发展进 行了展望。 第二章i p q o s 2 1 1 什么是q o s 第二章i pq o s 第一节q o s 的定义 q o s ( q u a l 时o f s e r v i c e ) 即服务质量，在r f c 2 3 8 6 1 1 j 中定义为：q o s 是网络 在传输业务流时，业务流对网络服务的需求的集合。其中，业务流是指与特定 q o s 相关联的从源到目的的分组流。也就是说，q o s 是应用业务对网络传输提 出的一系列服务要求，具体可量化为带宽、时延、抖动、丢包率等性能度量参 数，且服务强调端到端或网络边缘到网络边缘的整体性。q o s 反映了网络元素 ( 如应用程序、主机、路由器、交换机等) 在保证信息传输和满足服务要求方 面的能力。 2 1 20 0 s 、用户、网络系统之间的关系 q o s 与用户以及网络系统的关系如图2 1 所示脚。 q o s 协商( 服务类型、性能参数) 图2 1q o s 与用户以及网络系统的关系 从图中可以看出，q o s 涉及到用户与用户、用户与网络以及网络内部节点( 或 4 第二章i p o o s 元素) 的整体行为，而并不只是描述网络中某个个体或元素的行为。例如，当 图中用户1 与用户2 之间要进行通信时，必须事先相互协商通信时的服务类型 以及相应的性能度量参数。否则，若用户2 接收来自于用户l 的实时图像信息 时，用户1 按每秒4 0 帧发送，而用户2 的接收能力只有每秒3 0 帧的话，则即 使i r l t c n l e t 提供了每秒4 0 帧的传输服务，信息也会由于用户2 的接收能力不够 而丢失，从而无法进行满意的实时通信。反之，如果两个用户之间事先经过协 商，用户1 将发送速度放慢，使其满足用户2 的接收能力，则用户2 就会获得 较好的服务质量，而且网络的负载也会相应减轻。 除了用户与用户之间的协商，用户与网络、网络中的各个元素之间也存在着 q o s 协商和管理的问题。当用户的q o s 要求高于网络提供服务的能力时，应使 该用户降低其q o s 要求，甚至为了保证其他用户的q o s 而拒绝该用户的q o s 服 务请求。 第二节i pq o s 体系结构 根据实际应用的需要，国内外同行对i p q o s 问题进行了大量的研究与论证， 已取得了一些基本的阶段性成果。h e r i l e t 工程任务组( m t e m e t e n g i n e c r i n 9 1 缸k f o r c e ，i e t f ) 在此方面作了很多工作，先后提出了综合服务【3 j ( h n e g r a t c d s e r v i c e s ， i n t s e ) 和区分服务【4 j ( d i 仃e r e m i a t e ds e i c e s ，d i 丘s e r v ) 两种体系结构。国际 学术界在这些结构下提出了许多的算法与实现手段，但由于应用与用户需求的 不断发展，仍存在着一些亟待解决的问题，需要提出一些新的解决方案。 2 2 1i n t s e r v i m s e r v 是i e t f 于1 9 9 4 年提出的具有o o s 保证的网络体系结构。r f c l 6 3 3 1 3 】 给出了i n t e m c ti m s e r v 的框架，并将其划分为综合服务模型( i n t e 酗批ds e r v i c e s m o d e l ) 与参考实现框架( r e f e r e n c ei m p l e m e m a t i o nf r 姗e w o r k ) 两大部分。 在服务的层次上，除了传统的基于“b e s te 筋r t ”的服务以外，h l t s e r v 还以 每个流为基础，提供了两种端到端的面向实时传输的服务，即质量保证型服判5 】 ( g l 墙r a n t e e ds e i c e ) 和可控负载型服务1 6 j ( c o n n d l l e d 1 0 a ds e r v i c e ) 。 在实现的层次上，k s e r v 需要所有的路由器在控制路径上处理每个流的信令 第二章i p o o s 消息并维护每个流的路径状态和资源预留状态，并且在数据路径上执行基于流 的分类、调度和缓冲区管理。 在技术层次上，l m s e r v 依靠资源预留协议f h ( r e s o u r c er e s e r 、，a t i o np r o t 0 h l ， r s v p ) 提供q o s 协商机制，逐节点地建立或拆除每个数据流的路径状态和资源 预留状态；依靠接纳控制( a d m i s s i o nc o n 仃0 1 ) 决定链路或网络节点是否有足够 的资源满足用户的资源预留请求；依靠传输控制( t h 施cc o 助1 ) 将口分组分 类成不同的传输流，并根据每个流的状态对分组的传输实施q o s 路由、传输调 度等控制。可见，资源预留、接纳控制和传输控制是实现h l t s e r v 的重要基石。 i p q o s 问题的研究促进了i n t s e r v 体系结构和r s v p 信令协议的发展。r s v p 协议是为支持综合服务模型而设计的，它解决了应用的q o s 需求问题，承诺对 每个流的服务，使应用能够将每个流的请求信号发送给网络。在进行接纳控制 时，使用综合服务参数来量化这些服务请求。实际上，r s v p 信令协议依靠一种 动态的虚电路连接机制而改变了整个网络的体系结构。i n t s e r y 是基于每个流且 与状态相关的体系结构，它和与状态无关的体系结构( 如传统的i p 网络) 相比， 优势在于提供的服务具有更高的灵活性和更好的q o s 保证【2 】。然而，h l t s e r v 还 存在着很多不足之处【耵，主要有： ( 1 ) 其工作方式是基于流的，需要复杂的资源预留、接纳控制、q o s 路由和 调度机制。大规模网络系统状态和链路带宽容量变化的不确定性，使传 输通道端到端带宽预留缺乏有效的保证。 ( 2 ) r s v p 的有效实施必须依赖于分组所经过路径上的路由器。但是许多现 有的路由器和交换机不支持r s v p ，无法实施真正意义上的资源预留。 ( 3 ) 高速网络核心路由器常常被迫去维护、调度数以千计的连接，随着连接 数量的增加，连接建立和连接释放阶段的额外开销也将会增大。每个连 接的状态信息需要保存在路径通过的每个节点上，即需要保存每个流的 状态，其可扩展性较差。 ( 4 ) 提供较好的q o s 保证的h 吐s e n r 具有某种面向连接的特性【引，而m 网络 本身是不具有面向连接特性的，故在具体实施中，如何与现有网络互连 ，。一。一一也是一个困难。”。“7 。 正是由于i m s e r v 的发展遇到了难以逾越的障碍，人们的研究目标便逐渐转向 一种更为简单有效的方法d i 髑e n r 。 6 第二章i p o o s 2 2 2d i f f s e r v 针对i m s e n ，在发展中遇到的困难，i e t f 在r f c 2 4 7 5 f 4 】中提出了d i 宙f s e n ，体 系结构。d i 自f s e r v 的目标在于简单有效，以满足实际应用对可扩展性的要求，其 实现途径是【2 1 ： ( 1 ) 简化网络内部节点的服务机制。在内部节点只进行简单的调度转发，而 流状态信息的保存与流监控机制的实现等只在边界节点进行，内部节点 是状态无关的。 ( 2 ) 简化网络内部节点的服务对象。采用聚集传输控制，服务对象是流聚集 ( s t r e a m a g g r e g a t e ) 而非单流，单流信息只在网络边界保存和处理。 具体而言，边界节点根据用户的流规定和资源预留信息将进入网络的单流分 类、整形、聚合为不同的流聚集，这种聚集信息存储在每个i p 分组头的d s ( d i 彘r e 砸a t e ds e r v i c e s ) 标记域【”1 中，称为d s 标记( d i 髓豫n t i a 钯ds e r v i c e s c o d 印o i n t ，d s c p ) 。内部节点在调度转发i p 分组时根据分组头的d s c p 选择提 供特定质量的调度转发服务，其外部可观察的转发行为称为逐跳行为 ( p e r h o p - b e l l a v i o r ，p h b ) 。网络边界对单流做分类聚合与网络内部对聚集流提 供特定质量的调度转发服务，这两个过程通过i p 分组头内的d s c p 协同起来。 除实现简单以外，区分服务体系还具有以下特点： 。 ( 1 ) 层次化结构。分为d s 区域( d sd o m a i n ) 与d s 区( d s 舱西o n ) 两级。 在d s 区域内，服务提供策略与p h b 的语义和实现要一致，但d s 区内 的各d s 区域可以支持不同的p h b ，有不同的服务提供策略，它们之间 通过服务层协议( s e r v i c e l e v e i a g r e e m e m ，s l a ) 与传输调节协议( t r a 伍c c o n d i t i o n i n ga g r e e m e m ，t c a ) 协调以提供跨区域服务。这种结构适应 了i n t e m e t 中由各i s p 提供接入服务的商业模式。 ( 2 ) 总体集中控制策略。与i m s e r v 的分布式控制不同，d i f f s e r v 网络资源的 分配由总体服务提供策略( s e r v i c ep r o v i s i o i l i n gp o l i c i e s ) 决定，包括在 边界如何分类聚合流，在内部如何调度转发流聚集。 ( 3 ) 利用面向对象的模块化思想与封装思想，增强了灵活性与通用性。各逻 辑模块相对独立，并有多种组合。少量模块可组合实现多种服务，并在 发展过程中保持模块的可重用性。 ( 4 ) 不影响路由。与一些以虚电路方式实现q o s 的方案( a r m ，m p l s ) 以 第二章i p o o s 及服务类型标记方案不同，区分服务节点提供服务的手段仅限于队列调 度与缓冲管理，不涉及路由选择机制。 虽然d i f f s e r v 提供了一定程度上的q o s 保证，但也存在一些不足，主要有： ( 1 ) 由于d i f f s e r v 结构中网络和端系统之间缺乏信号通信，不能提供端到端 的q o s 保证，而端到端的q o s 保证一直是i p q o s 研究的基本目标。 ( 2 ) d i 腿e r v 只能使类型不同的业务享受不同的处理速度、平均带宽和平均 丢包率【l ”。它仅是一种统计上的有限处理，所以仍不能很好的保证业务 流的q o s 。 2 2 3d p s 方案 如前所述，i m s e r v 和d i f j f s e r v 各有各的长处，也各有各的不足【1 2 】，但都不 能彻底实现整个网络的端到端的q o s 保证。为此，许多研究者考虑将i n t s e n ，和 d i 嬲e r v 二者结合起来，互相协同，互相补充，共同实现端到端的q o s 提供机 制，最终达到既能提供类似状态相关网络的强有力的服务，又能实现与状态无 关网络近似的可扩展性和鲁棒性。目前，实现i m s e r v 与d i f r s e r v 的结合以提供 端到端的q o s 仍然是一个开放的研究课题，在此方面已经提出了若干不同的研 究方案和实现机制，面向s c 0 r e ( s t a t e l e s sc o ) 的动态分组状态( d y m i n i c p a c k e ts t a t e ，d p s ) 方案【”j 就是其中之一。 d p s 是近来研究者提出的一种核心无状态结构，该结构在网络边缘节点为 每个流保留状态信息，并由边缘网络节点将部分状态信息记录在每个数据分组 的头部。此信息随着数据分组在网络节点间的转发而不断更新。核心网络节点 根据分组头的状态信息进行处理，从而达到与传统的需要保留每个流状态信息 的方法有相同性能。但这种方案存在实现上的困难，并且，方案中为了保持同 步，加入了一些空分组，浪费了带宽。 ， 、 v 第三节i pq o s 路由 郴科a * # ，p 雕。p r 桃蝴 - 1 扣4 ， 唧。州r 一，叫， 2 3 1 路由算法概述 路由就是指导i p 数据分组发送的路径信息。路由包含两个基本功能1 2 】：一是 第二章i p q o s 搜集网络的状态信息并不断更新；二是根据所搜集到的信息计算可行路径。 所谓可行路径【1 6 】，就是网络中从源节点到目的节点的一条路径，并且该路径 具有足够的尚未分配的资源，能够满足特定的q o s 需求。 路由算法是路由的核心，它为完善路由表提供了算法依据。路由算法的设计 目标通常包括以下几点 2 ，1 4 ，1 5 】： ( 1 ) 算法必须是正确的。沿着路由表所指引的路径，分组一定能够最终到达 目的网络和目的主机。 ( 2 ) 算法应该尽量简单。路由算法应被设计成尽可能地简单，即必须以最少 的开销和使用费用获得高效的功能。 ( 3 ) 算法应具有鲁棒性。路由算法必须是健壮的，在异常或无法预料的情况 下，算法应仍能正确运行。因为，一旦一个重要的网络投入运行，它有 可能需要连续运行数年而不能有全局性的失效。在此期间，将会有各种 各样的硬件和软件失效。主机、路由器和线路可能会经常性地失效，网 络拓扑结构也可能会多次发生变化。路由算法应该能够处理拓扑结构和 流量方面的各种变化，而且不要求所有主机都停止所有的工作，并且每 当某台路由器崩溃时也不要求整个网络重新启动。也就是说，好的路由 算法应经得住时间的考验，在各种网络条件下仍能保证稳定可靠地运 行。 ( 4 ) 算法选择的路径应该是最优的。根据不同的优化目标及其权值大小可能 选择出不同的最优路径。这种最优可能会出于多种考虑，也许并不是仅 由一两个度量值来决定的。 ( 5 ) 算法应具有快收敛的特性。也就是说，路由算法必须在短时间内收敛， 即所有的路由器关于最优路由能在短时间内获得一致。 ( 6 ) 算法应能迅速准确地适应各种各样的网络情况，即具有灵活性。例如， 假定一段网络失效，好的路由算法一旦检测到了该问题，应很快地为使 用该段网络的路由选择次优的路径。 对于最优路径，我们可以在不考虑网络拓扑结构和流量的情况下给出最优化 原则【1 4 】( o 砸m a l 姆p r i n c i p l e ) ，它为各种路由算法提供了一个衡量基准，其具体 论述如下： 如果路由器j 是在从路由器i 到路由器k 的最优路径上，那么从j 到k 的最 优路径也必定沿着同样的路由路径。 9 第二章i p q o s 目前，经典的路由算法有距离矢量算法( d v 算法) 、链路状态算法等，但是 这些算法都不支持q o s ，而且对网络的利用不充分，网络负载也不均衡。 2 3 20 0 s 路由 q o s 路由( q o sr o m i n g ) 是一种基于数据流q o s 请求和网络可用资源进 行路由的机制。它是一种动态路由协议，并且在其路径选择标准里可能包含可 用带宽、时延、抖动、丢包率等q o s 参数。 当前i n t l m l e t 的主要路由协议都是基于“b e s t e m ) n ”的，选择路由时即使源 节点到目的节点之间存在“更好的”路径，只要不是最短路径就不会投入使用， 因此可能导致某些链路处于拥塞状态而另外一些链路却在空闲。q o s 路由就是 将传统的最短路径变为一条更好的路径，其主要目标包括以下两点： ( 1 ) 为每一个接纳的q o s 业务连接请求找到满足其q o s 要求的可行路径； ( 2 ) 优化全局资源利用率，平衡网络负载，从而最大化网络接受其他q o s 请 求的能力。 q o s 路由问题至今无法完全解决，其主要原因有【1 6 】： ( 1 ) 寻找同时满足两个以上路径约束的可行路径问题属于n p 完全问趔1 7 】； ( 2 ) 为了提高可扩展性所使用的层次化模型，产生了多种参数如何聚集的问 题f 1 朝： ( 3 ) 网络状态信息的陈旧性极大地影响了q o s 路由算法的性能【19 】； ( 4 ) 将q o s 路由融入到当前这种尽力而为的路由体系结构中，原有的尽力而 为业务将受到巨大的冲击。 2 3 3q o s 路由算法简介 前面提到，寻找同时满足两个以上路径约束的可行路径问题属于n p 完全问 题，一直是q o s 路由问题中的研究难点，同时，它也是国内外同行的研究重点。 w h g 和c f o w c m f i 使用d i j k s 仃a 最短路径树算法实现了带宽时延受限的源路 。，由求解【1 7 1 首先在网络拓扑图中将不满足带宽要求的链路剔除，然后再对时延 使用最短路径树算法计算，这样求得的路径满足带宽约束并具有最短时延。此 外，他们对最短最宽路径提出了分布式预计算方法。虽然这种多项式非启发类 算法针对的并不是典型的q o s 路由问题，只能解决单一可加性约束的问题，是 o 第二章1 p q o s 多项式可解的，但是这类问题及其求解思路是q o s 路由算法的基础。 如果所有的q o s 度量都与某一类度量相关，那么q o s 路由问题也可在多项 式时间内求解。基于这种思想，m a 和s t n k i s t e 【2 0 】证明了当网络中使用一类加 权公平队列( w f q ) ( 如调度算法【2 l 】) 时，端到端时延、抖动、队列长度等都是 带宽的函数，而不再彼此独立，这样，原来多约束的n p c 问题就有可能简化 考虑到这些参数的相关性以后，通过扩展的b e l l m a l l f o r d 算法( e x t c n d e d b e l l i 哪- f o r da l g 谢t h m ，e b f a ) 在多项式时间内就可以通过源路由策略求解。 o r d a 【2 2 】对基于速率调度的q o s 路由算法做了较为全面的研究。每个节点通过广 播可用速率代替传统的可用带宽等状态，将时延保证映射为速率保证。通过执 行至多m 次标准最短路径树算法，能够找到端到端时延受限的路径，并能够满 足抖动等其他方面的约束幽j 。但是这些分析对传输时延是无效的，因此往往限 定在高速网络中弘。 如果将除了一类之外的所有q o s 度量都限定在一个有限集上，则q o s 路由 问题是多项式可解的口5 0 们。基于这种思想，y u a l l 和l i u 【2 7 1 在e bf _ a 的基础上设计 了粒度受限的启发式算法，通过限制尉z 瞰“) 中最优路径的数目达到减小复杂度 的目的。算法对于七约束问题，将( 肛1 ) 种度量映射到( 扣1 ) 个有限集中。c h e i l 和 n a l l r s t c d t l 2 6 】设计了多重路径受限的源路由算法。算法的思想是将q o s 度量的取 值范围矗或z 映射到一个有限集合c ，从而保证多项式可解。但是，这类限定 q o s 度量的算法复杂度与q o s 度量的粒度关系密切。 c i d o n 和r o m 【2 s j 等人提出了分布式多路路由算法。算法中，每个节点需要维 护全局状态，根据q o s 请求，首先通过广播找到多条花费合理的路径，资源预 留控制信息并行地通过这些路径从源节点向目的节点发送，直到抵达目的节点 时完成连接的建立。在多条路径上同时预留资源可能会加快路由的速度，但大 大增加了网络的动态变化性。s m n 和c h o u 【2 9 】设计了时延受限的分布式算法。算 法中，每个节点不需要保存全局状态，而通过广播方式从源节点向目的节点发 送累加时延的路由信息。中间节点在收到路由信息时，首先累加自己的时延， 如果仍然小于规定的时延，则再向其它邻节点转发。但收到的路由信息必须是 第一次被收到，或信息中累计的时延小于该节点先i ； 收到的信息。路由信息的 扩散路径就是时延受限的可行路径。 i a n 和l i u 设计了多重路径受限的分布式算法f 2 1 。他们在e b f a 中直接限 制i 尉z | 捌的大小从而减小算法复杂度。s a i a m a p o 】等人对复杂度为n p c 的时延受 第二章i p o o s 限最小花费问题( d e l a y c o n s t r a i n c dl e a m c o s t ，d c l c ) 设计了分布启发式算法。 这种通过启发式算法直接限制路径数量，从而在路径集合的子空间中搜索可行 路径的方法称为路径子空间搜索。它在源节点或者中间节点就可以计算出可行 路径，而不需要一直访问到目的节点，因而具有较高的启发性。 f e i 和l u 0 川提出了基于遗传算法( g c n e t i ca l g o r i t h m ，g a ) 的单播和多播 q o s 路由算法，来解决多媒体应用中的q o s 路由问题。遗传算法是一种启发式 随机搜索算法。它的性能与编码以及适应度函数的设计密切相关。 蚂蚁算法田矧是目前q o s 路由研究中应用比较多的一种启发式算法。2 i l g 和l i u 【3 4 】利用蚂蚁算法求解多约束q o s 路由问题，可以实现全局优化。c h u 【3 5 】 和许毅f 3 6 】等人也进行了类似的工作，他们使用蚂蚁算法来实现q o s 多约束多播 路由的优化，取得了一定的成果。 下面，我们简单地介绍一下蚂蚁算法。研究表明，蚂蚁具有找到蚁巢与食物 之间的最短路径的能力。这种能力是靠其在所经过的路径上留下一种称为信息 素( p h e r o m o n c ) 的挥发性分泌物来实现的，该物质随着时间的推移会逐渐挥发 消失。蚂蚁在一条路上| i i 进对，会留下挥发性的信息素，后来的蚂蚁选择该路 径的概率与当时这条路径上该物质的强度成正比。对于一条路径，选择它的蚂 蚁越多，则蚂蚁在该路径上所留下的信息素的强度就越大，而强度大的信息素 会吸引更多的蚂蚁，从而形成一种正反馈。通过这种正反馈，蚂蚁最终可以发 现最短路径。 我们用图2 2 来说明蚂蚁寻找最短路径的原理。最初，如图2 2 ( a ) 所示，假 设一群蚂蚁沿直线在蚁巢与食物之间往返，显然，它们依靠信息素维持着这条 路径。忽然，一个障碍物出现在了原来的路径上，如图2 2 ( b ) 所示。蚂蚁遇到障 碍物时，必须做出抉择：向左走还是向右走。既然初始时没有什么线索可供它 们选择，那它们只能以相同的概率选择路径，结果是一半蚂蚁向上边的路走， 另一半蚂蚁向下边的路走，并在途中分别留下信息素。若假设蚂蚁都具有相同 的速度，则信息素的挥发性会使蚂蚁在较短的路径( 图中上方路径) 上所留下 的信息素的强度会大些。由于蚂蚁会以较大的概率选择信息素强度较大的路径， 所以后来的蚂蚁多数会走上边那条路径，如图2 2 ( c ) 所示，这就会导致该路径上 的信息素强度继续增大，进而该路径会吸引更多的蚂蚁，形成一种正反馈。经 过一段时间后，两条路径上的信息素的强度会有明显的区别，这就会使新到来 的蚂蚁选择较短路径的概率越来越大。不久，绝大多数的蚂蚁都将选择这条较 1 2 第二章l p o o s 短的路径，如图2 2 ( d ) 所示。 图2 2 蚂蚁寻找最短路径原理示意图 目前，大多数相关研究都是将算法应用与已知的路由问题有机地结合起来， 去解决具体的路由选择问题，很少有人将其发展成一个规模的、实用的路由协 议。z h a n 扩刀首先突破了上面的框架，试图将蚂蚁算法的思想应用于基于终端的 大规模网络路由上。樊秀梅【”8 】受蚂蚁算法启发，提出了一种网边缘可控的i p q o s 体系结构和网边缘可控的可扩展q o s 路由算法( t e 肌i n a l e d g cd e c i d e f e e d b a c kq o s ，t d f q ) 。该体系中的q o s 路由选择控制决断主要由边缘路由器 做出，核心路由器的任务简化为通报网络信息和协调用户决断这两个较为简单 的功能，大量的计算工作被推到网络边缘的各个终端去完成。 基于以上分析，我们给出基于网边缘控制的自适应i pq o s 路由算法( e d g e d e c i d e ds e l f - a d a p t i v eq o sr o u t i n ga l g o r i t l l m ，e d a q ) 。它是在1 r i ) f q 思想的基础 上，引入一些必要的优化机制，并根据实际问题的需要，做出进一步改进而得 到的。与t d f q 相比，e d a q 算法能很快地找到一条最优( 或近似最优) 的路 径，并能在网络环境波动不大的情况下保持传输路径相对稳定，还极大地减小 了路由探测造成的网络负载。此外，实际的网络环境并不是一成不变的，无论 是链路还是路由器节点都会由于各种原因( 如负载的变化) 而使自身的性能指 标发生变化，且网络的物理拓扑也随时有可能改变。因此，使q o s 路由算法具 有自适应性是十分必要的。 e d a q 算法与以往的q o s