（计算机软件与理论专业论文）ip网络的qos路由算法研究.pdf

摘要 随着i n t e r a c t 高速网络中实时和多媒体应用业务的迅速发展，要求通信网络 能提供高效的服务质量( q o s ) 支持，但是传统的“尽力而为”网络机制并不能满 足q o s 通信的要求，近几年的研究表明网络路由算法对实现网络质量服务有非 常关键的作用，因此q o s 路由算法日益成为网络研究的核心问题之一。 本论文介绍了q o s 路由技术的发展背景和研究现状以及q o s 路由算法的基 本概念和相关知识，并对当今己有q o s 路由算法进行了分类总结。在对传统的 d i j k s t r a 算法深入分析的基础上，完善了利用m 堆进行改进的思想，重新从理论 上证明了当m 值取为4 时算法的效率最高，可以将d i j k s t r a 算法时间复杂度降为 o ( n l o g 。刀) 。在多q o s 约束条件下，分析了基于最短路径的f a l l b a c k 算法的优缺 点。针对具有时延和带宽约束最小代价路径问题，提出了基于4 _ 堆和改进f a l l b a c k 的多约束条件q o s 路由算法，减少了计算最短路径以及根据q o s 条件重复计算 最短路径所耗费的时间。在多约束q o s 路由模型的基础上，举例分析了该算法 的过程。在n s 的仿真环境下，根据提出的拓扑结构图，进行了仿真试验证明其 性能确实有一定提升。仿真实验表明，该算法较好的满足了用户带宽、延迟服务 等方面的要求。最后进行了总结和展望，指出了该领域中需要进一步研究的热点 问题。 关键词： 路由，q o s ，m - 堆，d i j k s t r a 算法，多约束 a bs t r a c t w i 也t h ef a s td e v e l o p m e n to fr e a l - t i m ea n dm u l t i m e d i aa p p l i c a t i o n si nh i g h - s p e e d i n t e r n e t , t h eh i g h - e f f i c i e n tq u a l i t y - o f - s e r v i c e ( q o s ) s u p p o r ti sr e q u i r e di nt h e c o m m u n i c a t i o nn e t w o r k b u tt h et r a d i t i o n a l ”b e s t e f f e c t ”n e t w o r km e c h a u i s mc a nn o t g u a r a n t e et h eq o sc o m m u n i c a t i o n 1 1 1 er e s e a r c hi n t h e s ey e a r ss h o w st h a tt h e a l g o r i t h mo fn e t w o r kr o u t i n gp l a y sa ni m p o r t a n tp a r ti np r o v i d i n gq u a l i t y - o f - s e r v i c e g u a r a n t e e s ，s ot h eq o s - b a s e dr o u t i n ga l g o r i t h mb e c o m e so n eo ft h en u c l e a rn e t w o r k p r o b l e m s t 地d i s s e r t a t i o ni n t r o d u c e st h eb a c k g r o u n do ft h eq o sr o u t i n gt e c h n o l o g ya n di t s p r e s e n tr e s e a r c h s t a t u sq u oa n db a s i cc o n c e p t i o no fq o sr o u t i n ga l g o r i t h ma n d r e l e v a n tk n o w l e d g e t h e ns u m m a r i z ea n dc l a s s i f yt h eq o s r o u t i n ga l g o r i t h m s o nt h e b a s i so fi n d e p t ha n a l y s i so ft h et r a d i t i o n a ld i j k s t r aa l g o r i t h m ，t h ei d e ao fu s i n gt h e m - h e a pt oi m p r o v et h ed i j k s t r aa l g o r i t h mi sc o n s u m m a t e d i ti sp r o v e da g a i ni nt h i s p a p e rt h a tw h e nme q u a l st o4 ，t h em h e a pa l g o r i t h mc a l lg a i nt h eh i g h e s te f f i c i e n c y , a n dt h et i m ec o m p l e x i t yo fd i j k s t r aa l g o r i t h mc a nb er e d u c e dt oo ( nl 0 9 4 玎) u n d e r m u l t i p l eq o sc o n s t r a i n t sa n a l y z et h ea d v a n t a g e sa n dd i s a d v a n t a g e so ff a l l b a c k a l g o r i t h mb a s e do nt h es h o r t e s tp a t ha l g o r i t h m p u tf o r w a r dt h em u l t i p l ec o n s t r a i n t s q o sr o u t i n ga l g o r i t h mb a s e do nt h e4 - h e a pa n di m p r o v e df a l l b a c ka l g o r i t h mt os o l v e t h ed e l a ya n db a n d w i d t h - c o n s t r a i n e dl e a s t - c o s tr o u t i n gp r o b l e m r e d u c et h et i m eo f c o m p u t i n gt h es h o r t e s tp a t ha n dr e d u c ed o u b l e - c o u n t i n gt i m es p e n to nt h es h o r t e s t p a t ha c c o r d i n gt oq o sc o n s t r a i n t s t a k ea ne x a m p l et oa n a l y z et h ep r o c e s so fq o s r o u t i n ga l g o r i t h mb a s e do nt h em u l t i p l eq o sc o n s t r a i n t sr o u t i n gm o d e l i nt h e s i m u l a t i o ne n v i r o n m e n t0 q s 一2 ) ，a c c o r d i n gt ot h et o p o l o g ym a p ，d o i n gs i m u l a t i o nt e s t s p r o v e st h a tt h e r ei sab i gu p g r a d eo fi t sp e r f o r m a n c e s i m u l a t i o ne x p e r i m e n t ss h o w t h a t ，t h ea l g o r i t h mm e e t su s e r sr e q u i r e m e n t so fb a n d w i d t ha n dd e l a yv e r yw e l l f i n a l l y , s u m m a r i z et h ep a p e ra n dp o i n to u tt h eh o ti s s u e so fq o sr o u t i n gw h i c hn e e d t or e s e a r c h 1 ( e yw o l m s ：r o u t i n g ，q o s ，m - h e a p ，m u l t i p l ec o n s t r a i n t s 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得苤鲞盘鲎：或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：炭印零 签字日期：汐1 年上月2 日 学位论文版权使用授权书 本学位论文作者完全了解墨盎叁堂有关保留、使用学位论文的规定。 特授权苤叠盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：关中彳 签字日期：劫9 7 年 月日 导师签名：三删 签字日期：年月日 第一章绪论 1 1 论文的背景和意义 第一章绪论 当前i n t e r a c t 只提供尽力发送( b e s t - e f f o r t ) j 艮务，在网络层，口包头包含优先 级及服务类型的字段，但路由器选择路由和处理分组时往往忽略这些字段，将网 络资源公平地提供给各类业务，在分组丢失、时延等方面公平地对待各类业务。 这种尽力发送的机制使网络层无法保证传输的要求，但是丢包率、带宽、端到端 时延、时延抖动等对于应用业务往往是至关重要的。文件传输业务要求分组的丢 失率尽可能低，传输时延不是关键因素；实时多媒体业务则更注重时延和时延抖 动。这就要求网络能够区别对待各种业务，并对它们提供不同的服务质量。这种 尽力发送的体系结构是无连接、与状态无关的，它既不能支持资源预留，也不能 预测传输参数，甚至还可能产生多媒体实时业务不希望的乱序等等。由此，面向 服务质量的网络体系结构应运而生。 目前既能支持传统数据业务，又能支持实时多媒体业务的网络是a t m 网络， 然而转向a t m 网络意味着构造第二层网络基础设施，或者用a t m 网络替代已 存在的网络，但这两种方法在费用上都是惊人的。所以应考虑如何在现有的 t c p i p 体系结构中支持有多种q o s 要求的业务，一种方法是研究开发新的网络 协议，如r s v p ( 资源预留协议) 、r y p ( 实时传输协议) ；然而最根本的方法还是改 造路由器，使其具有处理q o s 请求的功能。 新开发的路由算法不再仅仅是为数据传输找到一条通道就行，还需要考虑所 选路径的传输容量和服务质量，即具有q o s ( q u a l i t yo f s e r v i c e ) 能力的路由算法。 随着网络和应用业务的快速发展，q o s 路由日益成为网络研究的核心问题之一。 q o s 问题本质上是研究网络资源的管理和控制问题，由于计算机网络本身存在的 缺陷和i n t e m e t 的复杂性，使得i n t e r n e t 的q o s 研究存在极大的困难。但q o s 的 研究对推动网络应用的发展，提高人们的工作效率，优化i n t o n e t 的利用具有极 其重要的意义。 1 2o o s 概念及研究现状 i pq o s 的目的就是采取适当的措施，满足与各类用户达成的不同服务等级 第一章绪论 协定( s e r v i c el e v e l a g r e e m e n t ，s l a ) ，同时对尽可能多的q o s 参数进行优化。q o s 能用下列可度量的参数来描述： 1 业务可用性：用户到口业务之间连接的可靠性。 2 延迟：也称为时延( l a t e n c y ) ，指两个参照点之间发送和接收数据包的时间间 隔。 3 可变延迟：也称为时延抖动( j i t t e r ) ， 指在同一条路径上发送的一组数据流中 数据包之间的时间差异。 4 吞吐量：网络中发送数据包的速率，可用平均速率或峰值速率表示。 5 丢包率：在网络中传输数据包时丢弃数据包的最高比率。数据包丢失一般是 由网络拥塞引起的。 已经出现了一些q o s 理论模型，r a j k u m a 9 1 】等提出了基于q o s 的资源分配 ( q - r a m ) 模型，c r u z 2 1 提出了需求服务曲线模型。同时m t f 建议了几种服务模 型和机制来满足不同的q o s 需要。其中最著名的就是综合服务资源预留( r s v p ) 模型3 1 ，区分服务( d i f f s e r v ) 模型4 1 ，多协议标记交换( m p l s ) 模型5 1 ，流量工程【6 】 和基于约束的路由【7 1 。 1 2 1 综合业务( i n t s e r v ) 模型 i n t s e r v 体系结构引入了一个重要的网络控制协议r s v p ( 资源预留协议) ，使 得口网络为应用提供所需求的端到端的q o s 保证成为可能。但为了支持这种 能力，数据包所经过的每个网络元素( 子网和路由器) 都必需能够支持r s v p 控 制服务质量的机制。这样网络元素在收到r s v p 预留资源请求后，需要为业务流 保留所需的“软状态( 包括有关业务流的起止地址、路由信息、需占用该路由 器的资源信息等) 。其参考实现模型如图( 1 1 ) 所示： 路有协议 应用 - i r s v p 脑高-数据库 l 摄纳策i 厂 略控制广 1j r 分类器 - i 调度器i i p 流 分类器l - 调度器 图( 1 1 ) i n t s e r v 主机和路由器参考实现模型 可见其中包括实现r s v p 协议所必需的几个模块：分类器( 基于微流的分类 m f ) 、策略器( 判断用户是否拥有资源预留的许可权) 、接纳器( 判断网络可用资 第一章绪论 源是否满足新业务流的需要) 、调度器( 根据服务等级进行优先级排序，进行队 列和时钟管理，流量预估、监控) 。当决策或接纳控制未被允许时，r s v p 处理 模块将产生错误消息发往源端，否则r s v p 处理模块负责设定分类和调度器的通 信服务质量参数。 i n t s e r v 是基于流的、状态相关的体系结构，所提供的服务具有更高的灵活性 和更好的服务级别保证。但在整个i n t e m e t 网络中应用存在以下根本局限：网络 扩展性不好一预留状态信息与业务流个数呈正比，使得路由器负担会随网络扩 大、业务流增多而加重：实现难度大要真正实现端到端的q o s 保证，要求 每个网络元素都要支持复杂的r s v p 协议，而目前只有少量路由器产生r s v p 信令，这意味着要大幅度改造现有网络。 1 2 2 差分业务( d i f f s e r v ) 模型 d i t t s e r v 体系结构及其特点在i n t s e r v 发展遇到巨大障碍时，i e t f 组织针对 其暴露的种种缺陷制定了这个相对扩展性较强的d i f f s e r v 来保证d 网络的 q o s ，从这个意义上来讲两者是一脉相传的。d i f l s e r v 是一种基于业务分类及其 相关质量保证策略的体系，它根据用户的需求将业务分成多种类型( 最多可达6 4 种) ，并将d 包头中的 p v 4 的t o s 域i p v 6 的流类型域重新定义为d s 标识域 ( d s c p ) ，用于标识业务的质量需求类型。网络节点读取数据包的d s c p 值，根 据已建立的d s c p 与每一跳转发方式( p h b ) 之间的映射关系，选择相应的p h b 对数据包进行处理，这种处理主要是指以保证不同业务需求质量的策略体系( 队 列策略、丢包策略等) 为基础的资源( 带宽和缓冲区) 分配。值得注意的是，p h b 并不是路由选择的条件。d i f f s e r v 体系是一个层次化结构，有d s 区域和d s 区 之分。在d s 区域内，服务提供策略与p h b 的语义和实现要一致，但d s 区中的 各d s 区域可支持不同的p h b ，有不同的服务提供策略，它们之间通过服务类 型协定( s l a ) 与传输调节协议( t c a ) 协调提供跨区域服务。d i f f s e r v 体系中路 由器有边界路由器和核心路由器之分，它们的功能模块图如图( 1 2 ) 所示： 第一章绪论 图( 1 2 ) d i t t s e r v 功能模块图 与i n t s e r v 相比，d i f f s e r v 有很大优越性。首先，在网络各节点不需要维护 每个流的信令或状态。第二，可以为一个由许多单个流汇聚映射成的较少的一些 特殊业务流，使得其可扩展性和升级性明显优于i n t s e r v 。第三，d i f f s e r v 中每 个单独的主机或应用程序都可不需要修改就能接收具有优先级的服务，对进入网 络的分组进行分类、标记及可能的调整都是由边界路由器完成的，与此类似，核 心和路由部件也只需很少的改动或几乎不需改动。第四，d i f l s e r v 为网络服务提 供者i s p 所支持的各种服务提供很大的灵活性和自由度，分组头中的服务比特只 被用于对分组进行分类的用途，具体定义和提供什么种类的服务完全由i s p 来 决定，惟一的要求是对这些比特语义的理解需保持一致。d i f p 3 e r v 的另一个重要 的优点是能使区分服务工作于v p n 之上。v p n 是通过在i n t e m e t 中建立安全隧 道形成的，流过一个安全隧道的口分组的传输头及一部分或全部净荷会被加密。 这种情况下，d i f f s e r v 还是能为这些分组提供具有优先级的服务，因为它只检查 分组头中的明文比特。但d i f f s e r v 并不提供从信源端到信宿端的全程q o s 保证， 而将q o s 限制在不同的d s 域中实现。这样会由于局部网络较差影响全网的性 能，此外，d s 区域间的s l a 需要一种体系化的协商机制，便于网络管理者进 行全局管理。 1 2 3d i f f s e r v 与i n t s e r v 相结合的端到端的q o s 提供机制 从第一部分对i n t s e r v 及d i f f s e r v 分析比较可知，两者优势互补，为此将它 们结合来共同实现端到端的q o s 提供机制不失为一个好方案，这样最终能达到 既提供类似状态相关的网络强有力服务，又实现与状态无关网络近似的可扩展性 和鲁棒性。同时两者也具有结合的可行性，i n t s e r v 提供了一种在异构网络元素 之上提供端到端q o s 的方法。一般而言，网络元素可以是单独的节点( 如路由器) 4 第一章绪论 或链路，更复杂的实体( 如a t m 云) 也可从功能视为网络元素，在这种意义上来 说，d i f f s e r v 网络云也可视为更大的i n t s e r v 网络中的一种网络元素。从i n t s e r v 的 角度看，网络中的d i f f s e r v 区被视为连接i n t s e r v 路由器和主机的虚链路。另一 方面，d i f f s e r v 与其它服务质量保障技术( 如i n t s c r v r s v p ，m p l s ，a t m 等) 也 有极好的兼容性。况且，两者在体系结构上存在相似和共同之处，它们都需要进 行服务与流特性的描述机制，都是通过对流量进行控制实现不同等级的服务特 性，都需要一种按分组头中一些域进行流分类的过程，都需要其它性能支持机制 的配合，如q o s 路由机制、基于测量的接纳控制机制等等。 1 2 4m p l s m p l s 多协议标记交换是i e t f 制定的第三层交换规范，它是对第二层a t m 标记交换和第三层口路由协议的有机结合。既实现了a t m 的面向连接、简单高 速交换、q o s 保证、流量管理、流量工程等优点，又实现了d 的灵活性、有效 性和可扩展性等优点。 m p l s 采用面连接的第二层交换支持无连接的第三层p 包转发，以实现d q o s 和流量工程。它采用第三层( p ) 的控制协议( 如沿用已有的口路由协议，新 定义标记分配协议( l d p ) 代替a t m 信令) 来控制第二层( a t m ) 的数据交换。在用 户数据通信之前，通过l d p 协议建立类似a t mp v c s v c 的标记交换通道( l s p ) 。 与a t mv p i n c i 一样，标记只在本地有意义，多个标记可以嵌套构成标记栈， 可以实现显式路由和层次化路由。 m p l s 域的出入口处设备称为边缘路由器( l e r ) ，核心设备称为标记交换路 由器( l s r ) 。只在入口的l e r 进行一次根据i p 包头的相关信息将不同q o s 要求 的i p 数据流划分成不同的转发等效类( f e c ) ，并作相应的标记映射。具有相同标 记的数据流都属于相同的f e c 。沿事先建好的l s p ，内部的l s r 只根据标记进 行简单高速交换，不再作f e c 处理。m p l s 实现了网络核心处理简单，智能在 边缘接入层实现的原则，这符合口的精髓思想。 m p l s 是对i p 现有组网模式的革新，包括路由和转发体系结构。m p l s 提供 了传统路由器与i p 现有组网模式不具备的解决方案，如：显式路由、流量工程、 v p n 、保护现有电信网的投资( 通过a t mm p l s 支持) ，使网络运营商能在业务 量快速增长和q o s 要求的外部因素、网络资源优化的内部因素间找到较优的平 衡点。 第一章绪论 1 2 5 流量工程 从本质上讲，在网络负载严重时，综合服务模型和区分服务模型等q o s 策略 只是为不同的流量提供有区别的性能下降。当通信负载比较轻时，综合服务和最 佳效果业务几乎没什么差别。因此，为什么不在第一步就设法避免拥塞呢? 这就 是流量工程的动机。导致网络拥塞的原因可能会是网络资源不足或通信分布不均 匀。在前一种情况下，所有路由器和链路都会过载，唯一的解决办法是升级基础 设施，提供更多的资源。在第二种情况下，网络的一些地方过载而其它地方的负 载却较轻。现在的动态路由协议r i p so s p f 和i s i s 都会导致不均匀的通信分布， 因为他们总是选择最短路径转发包。结果，在两个节点之间顺着最短路径上的路 由器和链路可能发生了拥塞，而较长路径的路由器和链路却是空闲的。 流量工程就是安排传输流如何通过网络，以避免不均匀的使用网络而导致拥 塞的过程。为使流量工程自动化，约束路由是一种重要的工具。因为在避免拥塞 和提供良好的性能方面，流量工程其实是对区分服务模型的补充。 1 3 本文主要工作 1 3 1 研究问题及解决思路 研究的问题： ( 1 ) 在较大规模的网络环境中如何提高d i j k s t r a 算法选择最短路径的速度。 ( 2 ) 如何将d i j k s t r a 算法用于解决q o s 路由选择问题。 ( 3 ) 如何在多约束q o s 条件下选择较短的路径，并且尽量降低所耗费的时间。 解决思路： ( 1 ) 完善并重新证明基于4 堆的d i j k s t r a 算法，提高选择路径的速度。 ( 2 ) 由于d i j k s t r a 算法选择路径是n p - 完全问题，根据约束条件选择路径才 能在多项式的时间内解决。 ( 3 ) 在多约束条件下，提出基于4 _ 堆和改进f a l l b a c k 的路由算法，来减少路 由选择所耗费的时间。 1 3 2 本文的主要结构 本文的具体内容安排如下： 第1 章：论述本文的研究背景，阐述现有的q o s 体系结构，并对全文的研 究内容作了前瞻性的介绍。 6 第章绪论 第2 章：它是全文的理论基础。介绍了网络加权图模型，分析了q o s 路由 选择、多约束q o s 路由以及q o s 度量的分类，并对q o s 路由策 略的问题进行了讨论。介绍了经典路由算法，分析了单播及分布 式路由算法的特点、作用、分类。 第3 章：完善并重新证明了基于4 堆的d i j k s t r a 算法，提出了基于4 堆和 改进f a u b a c k 的多约束q o s 路由算法，并且给出了q o s 路由指标 评价的模型及形式化描述。 第4 章：介绍了网络仿真软件n s - 2 ，根据第四章提出的算法设计了网络拓 扑结构，修改了路由模块，进行了仿真试验。 第5 章：对全文进行总结，并展望。 第二章q o s 路由理论基础 2 1 网络拓扑结构 第二章q o s 路由理论基础 在网络q o s 的体系结构中，q o s 路由是其中的核心技术和热点问题，其目标 是在网络中寻找满足q o s 要求的路径。解决q o s 路由问题时，先要建立网络模 型，然后在网络模型上求解q o s 路由问题，同时同时优化网络资源的算法。 目前的q o s 路由问题算法，大都建立在链路加权的网络模型基础上，一般忽 略节点的因素。将网络的拓扑结构抽象为一个加权图模型兄，其中 y = v l , v 2 ， 是网络中的节点集合，e = 与，e 2 ，) 是网络中的链路集合。 对于同构网络，其链路是对称的，对称链路两个方向上的数据都有相同的特性， 则加权图的边是无向的，称为无向图。而大多数现实中的网络是异构网络，其链 路是非对称的，则加权图用相反方向的两条有向边表示，称为有向图。为了简化 网络模型，减少计算复杂性，文中的图都是无向图。网络加权拓扑图( 2 1 ) 所示， 图中边上3 个值依次代表( 时延、带宽、代价) 。 ( 2 2 ，8 ，5 ) 图( 2 1 ) 网络加权拓扑图 每一个节点、每一条链路都有用q o s 度量表示的状态，节点状态可以折算到 与节点相连的链路状态中，故这里将节点的度量值忽略不记。足表示正实数集， r 表示非负实数集。对于任一链路e e ，定义4 种度量，分别为时延函数 d e l a y ( e ) ：e 一足、带宽函数b a n d w i d t h ( e ) ：e r 、剩余带宽 f r e eb a n w i d t h ( e ) ：e - - 9 , r 和代价函数c o s t ( e ) ：e 一兄。链路的时延为数据包在 链路中的传播时延，发送节点在传输链路上发送第一个比特时刻至该比特到达接 第二章q o s 路由理论基础 收点的时延称为传播时延；链路中的剩余带宽为链路带宽未被占用的带宽，链路 代价由传输数据包消耗的链路资源决定。这样，链路状态就可以用一个三元组( 带 宽、时延、代价) 表示。 2 2q o s 路由指标性质 服务时被要求提供的q o s ，对于给定路径的指标一般可以分为三类： ( 1 ) 可加性，总q o s 等于构成这条路径的所有链路q o s 值的和( 如跳数、成本、 链路长度、时延和时延抖动等) ； ( 2 ) 可乘性，总q o s 等于构成这条路径的所有链路q o s 值的积( 如误差率、丢包 率和链路利用率等) ； ( 3 ) 最大最小性，总q o s 等于构成这条路径的所有链路q o s 值中的最小者( 如流 量、带宽等) ，或总q o s 等于构成这条路径的所有链路q o s 值中的最大者( 如 带宽利用率等) 。 2 3o o s 路由指标形式化描述 对于无向图g = ( v ，e ) ，eee ( v x v ) ，p 表示从源节点s 到目的节点d 的路径集 合。则： ( 1 ) 时延：d e t a y ( p ) = 以dd ( e ) ：e - - r + e e p ( 2 ) 成本：c o s t ( p ) = 刚c ( e ) ：e - - - r + e e p 链路e 上的时延 链路e 上的成本 ( 3 ) 瓶颈带宽：厢肋厅( p ) = m 。印i n b ( p ) ) b ( p ) ：e 寸尺+ 链路p 上的瓶颈带宽 ( 4 ) 路径条数：h o p ( p ) = 办( g ) 五( p ) ：e r + 链路e 上的路径跳数 e e p ( 5 ) 丢包率：l o s s ( p ) = 1 一兀( 1 一三( 8 ) ) 旧嫩黼溅而：器 其中u ( e ) ：e r + e 路径的利用率， 路径p 的利用率。 l ( p ) ：e r + 链路e 上的丢包率 ) = 等船驴矿_ 】2 ( p ) 为p 路径上业务要求带宽，u 为 ( 7 ) 资源消耗函数：r ( p ) = h o p ( p ) 牛w i d t h ( p ) 木d e l a y ( p ) 9 第二章q o s 路由理论基础 ( 8 ) 时延抖动函数：j i t t e r ( p ) = m a x d ( e ) - m i n d ( e ) ) 丽= 等k 2 驴硎 其中，j i t t e r ( p ) ，j i t t e r ( p ) ，万2 腑( p ) 分别表示时延抖动，平均时延抖动和 时延抖动方差。 2 4o o s 路由选择 2 4 1 路由方式 路由方式选择问题可分为4 大类【l 7 】：单播( u n i c a s t ) 、组播( m u l t i c a s t ) 、广播 ( b r o a d c a s t ) 和选播( a n y c a s t ) ( 1 ) 单播路由选择问题可定义如下：给定一源节点s 、一个目的节点t 、一组服 务质量约束c 和一个可能的最佳化目标，寻找从s 到t 满足c 的最可行路径。 ( 2 ) 组播路由选择问题定义如下：给定一源节点s 、一组目的节点集r 、一组约 束c 、以及可能的最佳化目标，寻找从s 出发覆盖r 中所有目标节点且满足 c 的最可行的树。 ( 3 ) 广播路由选择问题定义如下：给定一源节点s 、一组约束c 、以及可能的最 佳化目标，寻找从s 出发覆盖网络中所有其它节点且满足c 的最可行的传播 树。 ( 4 ) 选播路由选择问题定义如下：给定一源节点s 、一组目的节点集a 、一组约束 c 、以及可能的最佳化目标，寻找从s 出发到目的节点集a 中任意一个节点 且满足c 的最可行传输路径。 关于q o s 的单播、组播路由算法的研究己进行了多年，并取得了许多研究成 果，目前主要集中研究两个算法中n p 难问题的启发式或近似算法。广播路由算 法十分简单，主要考虑网络开销和信息扩散程度之间的关系。选播路由算法的研 究才刚刚起步，相关研究成果不多。目前的网络中单播路由仍然占主导地位，因 此本文主要研究了多约束条件下的单播路由算法。当然，组播路由是下一步的发 展方向。 2 4 2 路由策略 路由选择包含两个基本任务：收集状态信息和基于收集的信息为一新的请求 寻找一可行的路径。网络状态信息可以是局部、全局和汇聚状态信息。局部状态 信息：假定每一节点保持其更新的局部状态，包括排队和传送延迟、输出链路的 1 0 第二章o o s 路由理论基础 剩余带宽、以及其它资源的可利用性。全局状态信息：是所有节点局部状态信息 的组合，每个节点通过链路状态协议簇或距离矢量协议能够保持全局状态，它们 定期地在节点间交换局部状态信息。汇聚状态信息：通过根据大型网络的层次结 构汇聚信息实现，每个节点都保存一个汇聚的网络映象。汇聚状态信息大大减少 了状态数目，但也引入了汇聚信息的不精确性。根据网络状态信息的保存方式和 路由搜寻方式的不同，路由策略可分为三种：( 1 ) 源端路由【8 】：每个节点保存全局 的网络状态信息，包括网络拓扑结构信息、每个节点和每一条链路的状态信息 根据此全局信息，源节点在本地计算出一条合适的路由。然后，在选择的路由上 传送一个控制包，通知路由上的每个节点，说明其前继者和后继者为谁。每个节 点的信息更新由链路状态协议完成。( 2 ) 分布式路由【9 】：路由选择的计算是分布计 算完成的。其路径上的各节点通过交互控制消息，并结合各节点所存储的状态信 息，来完成路由选择的计算。大多数分布式路由算法需要用距离向量协议或链路 状态协议来保持其全局信息，在每个节点上此信息是以距离向量的形式保存。根 据距离向量，路由以接力的形式完成。( 3 ) 层次路由【阳】：物理节点聚合为组，而 组又反复不断地进一步聚合为更高一层的组，从而形成一种多层次结构。每个物 理节点保存有经过聚合的全局信息，此信息包括此物理节点所在组的详细状态信 息和其他组的聚合信息。使用源路由算法来进行路由选择。然后，沿着计算出的 路径传输控制消j 息；。从而建立连接。当代表逻辑组的物理节点收到此消息时，它 将把对应这个逻辑组的链路部分进行扩展，即用物理链路代替其对应的逻辑链 路。三种路由策略的优缺点如表( 2 1 ) 所示： 表( 2 1 ) 三种路由策略的比较 路由策略优点 缺点 源端路由集中处理，简单，不 保存全局信息，在大型网络中有很大的传输 产生回路开销，计算开销较大扩容性差。 分布式路由 可扩容型好，误差小 须引入环路控制机制和解决分布计算的中止 问题，通信开销大 层次路由 可扩容型好；抑制环 各种q o s 度量参数的聚合问题 路的产生 由于以下原因，使源路由不具有良好的可扩容性：通信开销与网络规模和本 地信息的广播频率成正比；存储开销与网络规模成正比；计算开销为网络规模的 多项式时间，且与连接请求的频率成正比；全局信息的准确度与网络规模( 或网 络半径) 和广播频率成反比。当网络规模扩大时，其对应的通信开销、存储开销 第二章q o s 路由理论基础 和计算开销都相应地增长。降低网络信息更新频率并不能解决此问题，因为全局 信息的准确度也会随之下降。 分布式算法可以部分解决扩容性问题。例如基于选择性探测的分布式路由算 法仅需要局部信剧1 1 】【1 2 】，而基于令牌探侧的分布式路由算法可以克服信息的不 确定性问题，从而可以降低网络的通信开销。 目前还没有处理n p 完全问题的高效率分布式算法，特别是在组播传送中， 这主要是由于没有详细的拓扑信息和链路信息可供使用。而如果在不同节点的全 局信息不一致的话，就有可能产生环路。环路可以通过控制包到达同一节点两次 来检测，但环路将导致路由失败，因为距离向量信息不能给出足够的信息来确定 替代路由。 层次路由的可扩展性很好，因为每个节点只需维护部分的全局信息，大小是 网络详尽全局信息大小的对数。在每一层，逻辑节点依据汇聚信息直接采用源端 路由，因而层次路由继承了源端路由的优点，同时路由计算还是由路径上的许多 节点共同分担，因而还继承了分布计算的优点。层次路由是对大型网络而言最有 前途的路由策略，当然，由于汇聚信息引入了不精确性，层次路由在一些情况下 可能导致选路失败。这通常是由于逻辑节点通告的其自身多个q o s 能力可能对 应的不是通过该逻辑节点的同一条路径引起的。如何对状态信息进行聚合目前还 是一个待解决的问题，由于信息聚合会产生附加的不精确性，其算法性能会随网 络规模而急剧降低。因为q o s 路由对网络状态信息的非精确性比较敏感，故而 研究能适应网络状态信息非精确性的路由算法就变得十分重要。 2 4 3 多约束条件下q o s 路由 q o s 路由选择策略显得格外重要，它是实现q o s 保证的关键之一，也是目 前关于q o s 的一个重要的研究方向。由于基于多个约束条件建立的网络模型可 以更准确地反映实际的q o s 路由选择问题，随着人们对网络服务质量要求的提 高和网络规模的不断扩大，研究基于多约束条件的q o s 路由算法，以获得良好 的网络服务质量和高的网络资源利用率具有十分重要的研究意义。多约束q o s 路由问题就是在网络中找到一条满足多个独立限制条件的可行路径。这个问题是 q o s 路由中的一个主要问题，同时也是一个n p 一完全问趔剐。给定一个网络拓 扑结构，要在此拓扑图上找到路由，通过删除不满足所要求的传输带宽的链路获 得一个新的网络拓扑结构，在新的网络拓扑下，传输延时、延时抖动和丢失率等 限制条件可以定义为代价的函数，因此，可以将问题转化为最短路径问剧d 儿1 4 j 。 如果每条链路上的某一限制条件是一致的，则与任何一个其他限制条件下的最优 化问题可以用改进的b e l l m a n - f o r d 算法求解。 第二章q o s 路由理论基础 目前，在q o s 路由的研究领域中研究人员己经提出了一些用于解决多约束 q o s 路由问题的算法。这些算法大体上可分为启发式算法、近似算法和基于某种 调度策略的多约束q o s 路由算法这三类。启发式算法可以降低算法时间复杂度， 但不能保证在即使存在传输路径的条件下发现一条可行的传输路径。采用近似算 法可以求最优化路径的近似解，但这类算法的时间复杂度往往比启发式算法高。 近似算法又可分为多项式近似算法和伪多项式近似算法。两者的区别在于伪多项 式近似算法的计算复杂度不仅仅同网络的大小有关，还取决与网络链路参数的大 小。基于某种调度策略的多约束q o s 路由算法能够较好的解决多约束q o s 路由 问题，但由于它要求某种特殊的调度策略，这使得这些算法在使用上具有一些局 限性。图( 2 2 ) 显示了多约束q o s 单播路由问题的分类。 基本o o s 路由问题组合o o s 路由问题 链路优化路由( 例链路优化一链路约束( 例 如，带宽优化)如，带宽约束缓冲) p 问题 p f a - ；题 l 蟛 l 路径优化一链路约束( 例 碉如，带宽约束最小代价) ip 问题 链路约束路由( 例 多链路约束( 例如，带宽 如，带宽约束) 及约束缓冲) p n 题 p 问题 划路径约束一链路约束( 例 州如，带宽、时延约束) l p i a 7 题 i 路径优化路由( 例y刈链路优化一路径约束( 例 如，最小代价) 卜 州如，时延约束带宽优化) p 问题l 。 i p 问题 l 路径优化一路径约束( 例 卅如，时延约束最小代价) in p 问题 路径约束路由( 例 j 多路径约束( 例如，时延 如，时延约束)及时延抖动约束) p 问题n p 问题 1 薹t ( 2 2 ) 多约束q o s 单播路由问题的分类 1 3 第二章q o s 路由理论基础 2 5 现有o o s 路由算法 2 5 1 最短路径算法 最短路径问题有着非常广泛的应用，这里的最短路径不仅指一般地理意义上 的距离最短，还可以引申到其他的度量，如时间、代价、链路容量等，相应地， 最短路径也就成为最快路径、最小代价路径等。求解最短路径问题的算法有： f l o y d 算法、b e l l m a n f o r d 算法和d i j k s t r a 算法，它们是各种q o s 路由算法的基 础。 ( 1 ) f l o y d 算法n 习 从i 到的路径要么是f 寸，要么中间经过了若干顶点。显然我们要求的是 这些路径中最短的一条。这样一来，问题就很好解决了最初都是源点到目的 点，然后依次添加顶点，使得路径逐渐缩短，顶点都添加完了，算法就结束了。 算法伪码如下所示： v o i d a l l s h o r t e s t p a t h 0 f l o y e d f o r ( i n tk = o ；k n ；k + + ) s h o r t e s t k 】_ t r u e ； f o r ( i n t i = 0 ；i 刀；f + + ) f o r ( i n tj = o ；j n ；j + + ) i f ( 1 e n g t h i k + l e n g t h k j 】 0 ；h ：在算法目 前阶段的链路具有的最大链路数；厶( 刀) ：表示在不多于h 条链路下，从节点s 到 节点n 的最小费用路径费用。 s t e p l ：初始化 厶( 控) = o o ，对所有玎! = s ；h = 0 ：厶( s ) = 0 ； s t e p 2 ：迭代 厶( 刀) = m i n ( 厶( ，) + ( ，刀) ) ，对所有j = 0 刀； ( 式2 - 2 ) h = h + l ，只要有一个l a n ) 被更新，则转s t e p 2 执行，否则程序结束。 b f 算法的迭代过程如( 式2 2 ) 所示。算法的计算复杂度是o ( m n 2 ) ，其中m 为 链路数，n 为节点数。算法伪码如下： v o i ds h o r t e s t p a t h ( i n tv 1 ) f o r ( i n tk = 2 ；k n ；k + + ) f o r ( i n ti = 0 ；i 以；f + + ) f o r ( i n t j = o ；j 辨；歹+ + ) i f ( 1 e n g t h v 1 j + l e n g t h j i 】 l e n g t h v 1 i ) l e n g t h v 1 i 】- l e n g t h v 1 j + l e n g t h j i