（计算机应用技术专业论文）网络多播路由算法的研究.pdf

北京交通大学硕上 毕业论文y5 8 0 2 3 6 摘要 多播是目前网络中研究最多、应用最广的通信方式。实现多播路由 是解决多播通信的关键问题之一，而实现多播路由的一般方式是建立多 播树。多播路由算法主要用来建立 一 棵性能好的多播树，并使它满足各 种业务的 服务质量 ( q u a l i t y o f s e r v i c e ， 简记为q o s ) 需求。 最短路径树( s h o r t e s t p a t h t r e e , 简记为s p t ) 是应用最多的多播树类 型之一。在大型网络中，两节点间的最短路径可能有多条，因而导 致相 应的最短路径树不唯一，不同最短路径树的总代价也不尽相同。本文主 要研究如何降低最短路径树的总代价，在确保传送时延最小的同时尽量 降低带宽消耗。 本文的主要研究工作如 下: 1 . 本文总结了最短路径树的各种启发式算法，分析了各种算法的 的复杂度、适用情况和特点，这为后面的工作打下了基础。 2 . 对已有的一些最短路径树静态算法进行深入分析，指出其不足 之处，并在此基础上给出一种改进算法，通过改进搜索过程，使得在多 播树性能保持不变的情况下时间复杂度更低。 3 . 对于网络中两节点间所有最短路径的求解问题，提出了一种新 的结构最短路径子图，用来存储两节点间的所有最短路径信息，可 以节省存储空间。并给出了最短路径子图的构造算法，其时间复杂度要 远低于原有求解两点间所有最短路径的算法。 4 . 研究了已有的一些最短路径树动态算法，指出其效率低下的原 因。利用最短路径子图的性质，提出了一种新的动态算法，其计算效率 和生成的多播树性能都要优于原有算法。 5 . 对以上算法进行程序实现，验证了算法的正确性，并与一些典 型算法进行比较，取得了较好的结果。 6 . 最后对多播路由算法今后的研究工作提出了一些设想和看法。 关键词多播路由 最小生成树 多播树 最短路径子图 最短路径树 时间复杂度 s t e i n e r 树 来 李 明 竣 少 章 义 公 、 异帅; 1 惠 北京交通大学硕十毕业论文 ab s t r a c t mu l t i c as t i n g i s t h e m o s t w i d e ly - u s e d c o m m u n i c a t i o n p a t t e r n i n c o m p u t e r n e t w o r k s . h o w t o d e t e r m i n e a n e ff i c i e n t m u l t i c a s t r o u t i n g i s o n e o f f u n d a m e n t a l i s s u e s i n m u l t i c a s t c o m m u n i c a t i o n , a n d t r e e c o n s t r u c t i o n i s a c o m m o n ly - u s e d a p p r o a c h i n s o l v i n g m u l t ic a s t r o u t i n g p r o b l e m. mu l t i c a s t r o u t i n g a l g o r it h m s a r e u s e d t o c o n s t r u c t g o o d p e r f o r m a n c e m u lt i c a s t t r e e s w h i c h s a t i s f y q u a l i t y o f s e r v i c e ( q o s ) r e q u i r e m e n t . s h o r t e s t p a t h t r e e ( s p t ) i s o n e o f t h e m o s t w i d e l y - u s e d m u l t i c as t t r e e t y p e . t h e r e a r e m a y b e m o r e t h a n o n e s h o r t e s t p a t h s b e t w e e n t w o n o d e s i n l a r g e - s c a l e n e t w o r k , s o t h e c o r r e s p o n d i n g s p t s a r e n o t u n i q u e a n d c o s t s o f wh i c h a r e d i ff e r e n t . t h i s p a p e r c e n t e r s a r o u n d h o w t o r e d u c e c o s t o f s p t . t h e m a i n r e s e a r c h wo r k s a n d r e s u l t s a r e f o l l o ws : 1 . s u m m a r i z e h e u r i s t i c a l g o r i t h m s f o r s p t a n d a n a l y z e t h e c o m p u t a t i o n a l c o m p l e x it y a n d a p p l ic a b l e c o n d i t i o n s o f e a c h a l g o r i t h m . t h i s i s t h e b a s i s o f f o l l o w i n g w o r k s . 2 . b as e d o n s o m e e x i s t e d a l g o r i t h m s , t h r o u g h i m p r o v i n g o n s e a r c h p r o c e d u r e , a n e w a l g o r i t h m f o r s t a t i c s h o r t e s t p a t h t r e e i s p r e s e n t e d , w h i c h c a n g e t l o w e r c o m p u t a t i o n a l c o m p l e x i t y . t h e o r e t i c a n a l y s i s a n d s i m u l a t i o n r e s u l t s w i t h r a n d o m n e t w o r k m o d e l s h o w t h a t t h e n e w a l g o r i t h m i s m o r e e ff e c t i v e 3 . c o n c e p t i o n o f s h o r t e s t p a t h s u b g r a p h i s p r e s e n t e d f o r t h e p r o b l e m o f a l l s h o r t e s t p a t h s b e t w e e n t w o n o d e s in n e t w o r k . i t i s a b l e t o s a v e s t o r a g e s p e n d i n g b y u s i n g t h i s s t r u c t u r e t o s t o r e a l l p o s s i b l e s h o r t e s t p a t h s . a n d a n a l g o r i t h m f o r c o n s t r u c t i n g s h o r t e s t p a t h s u b g r a p h i s a l s o g i v e n , o f w h i c h c o m p u t a t i o n a l c o m p l e x i t y i s l o w e r t h a n s i m i l a r a l g o r i t h m s . 4 . a n a l g o r i t h m f o r d y n a m i c s h o r t e s t p a t h t r e e i s p r e s e n t e d i n t h i s p a p e r u t i l i z in g s h o r t e s t p a t h s u b g r a p h i n c o m p u t a t i o n p r o c e d u r e , t h i s a l g o r i t h m c a n a v o i d c o m p u t a t io n o f t h e p a t h s t h a t a r e n o t s h o rt e s t . c o m p a r e d w i t h 北京交通大学硕士毕 业论文 s i m i l a r a l g o r i t h m s , t h e n e w a l g o r i t h m i s m o r e e ff e c t i v e a n d g e t b e tt e r p e r f o r m a n c e . 5 . i m p l e m e n t a l g o r i t h m s a b o v e i n p r o g r a m s t o v a l i d a t e t h e c o r r e c t n e s s o f t h e s e a l g o r i t h m s . c o m p a r e d w i t h s o m e t y p i c a l a l g o r i t h m s , t h e n e w a l g o r i th m s g e t s a t i s f a c t o ry r e s u l t s . 6 . a t l a s t , s o m e a s s u m p t i o n s a n d v i e w s o f f u t u r e r e s e a r c h o f m u lt i c a s t r o u t i n g a l g o r i t h m s a r e p r o p o s e d . k e y w o r d s : mu l t i c a s t r o u t i n g ; mu l t i c a s t t r e e ; s h o r te s t p a t h t r e e ( s p t ) ; s t e i n e r t r e e : mi n i m a l s p a n n i n g t r e e ( ms t ) ; s h o rt e s t p a t h s u b g r a p h ; c o m p u t a t i o n a l c o m p l e x i 诊 北京交通大学硕士毕业论文 第一章绪论 1 . 1多播技术背景 随着计算机网络技术的飞速发展，用户对交流质量日益苛求，对网 络带宽的需求呈现直线上升趋势，用户的需求己经不再仅仅局限于简单 的语音数据通信，集语音、数据、图像为一体的多媒体视频通信时代已 经来临。以 a p p l e , c i s c o , k a s e n n a , s u n 等几家公司为代表的 i s m a联 m ( i n t e rne t 流媒体联盟) 的成立宣告了视讯通信新纪元的诞生。 随着计算机网络的飞速发展，远程教学、多媒体会议、分布式计算 以及网络游戏等新兴业务的出现，都依赖于从一个主机向多个主机或者 从多个主机向多个主机发送同一信息的能力，传统的单播方式已经不能 满足这些应用需求。 为了满足新兴业务的需求，如今网络的通信方式主要有以下几种: 1 . 单播 ( u n i c as t : p o in t t o p o i n t ) ， 点 到点的 通信方式 2 .多 播( m u l t i c a s t : p o i n t t o m u l t i p o i n t ) ， 点 到多点的 通信方式 3 . 汇播 ( c o n c as t : m u lt ip o in t to p o in t) ， 多 点 到 一点 的 通信 方式 4 群播( m u l t i p o i n t t o m u lt i p o i n t ) ， 多点 到多点的 通信方式 5 .广播( b r o a d c a s t : p o i n t t o a l l p o i n t ) ，点到所有点的通信方式 当只在两个终端之间传送数据时，一般采用单播方式。单播的实现 一 般 采 用d ij k s t r a 最 短 路 径 算 法 【11 或b e l lm a n - f o r d 算 法2 1 来 建 立点 到 点 的 路由。多播是一个源节点向多个目的节点发送信息的通信方式，涉及多 播技术的应用很多，比 如多媒体会议、远程教育、数据分发等等。当多 播的目的节点包含网络中除源节点外所有节点时，这时的通信方式就成 了广播。 广播通信方式主要应用于局域网。 汇播与多播有许多相同之处， 其应用主要涉及远程数据采集等。 至于群播的典型应用是即时网络游戏， 需要将各自的状态互相同步发送。 北京交通大学硕十毕业论文 在众多的通信方式中，多播是当前研究得最多，也是应用最广泛的 网络通信方式。实践证明，多播能从本质上减轻网络及服务器负荷，符 合新一代的网络运营模式。 多播路由是实现多播通信的关键技术之一，解决多播路有问题可以 有三种方式: 1 ，让源节点简单地发送一个单独的分组到每一个目的节点。 这种方 式不仅浪费带宽，而且还要求源节点维护所有目的节点的信息。 2 .侮个分组含有一张目的节点清单， 当分组到达路由器时， 路由器 检查所有目的节点以确定需要用的输出线路集合( 如果某线路是 到达至少一个目的节点的最好路由， 则需要该路线)。 路由器为 所使用的每一条输出线路复制一个新的分组， 每个分组中仅包含 此线路中的目的节点信息。 实际上，目 的节点集合是划分在各条 输出线路上的。 经过足够多数量的站点后， 每个分组将仅带有一 个目的节点。 这种路由方式就象各自分组寻址一样， 只是若干分 组必须经过同一路有时， 其中一个分组负担全部费用， 而其它分 组则不必承担费用。 3 树型路有。 建立一棵覆盖所有多播目的节点的生成树， 分组沿多 播树传送到每一个目的节点。 树型路由具有两大优点:一是信息以并行方式沿着树枝发送到不同 目的节点， 降低了信息传递的时延; 二是网络中需要传送的复制信息少， 能够节省网络带宽资源，提高每次多播通信时的资源利用率，并能减少 拥塞，降低网络负载。因此构造多播路由树是当前解决多播路由问题的 常用方法。 1 . 2多播路由树 一般要求多播服务的业务对带宽和实时性要求较高， 涉及用户较多 北京交通大学硕一毕业论文 占用的资源也多，因此有必要优化多播路由。多播路由算法就是要寻求 最优多播树，理想有效的路由算法将设计一棵仅覆盖多播组成员的树， 并体现如下特征:树随着组成员变化动态更新;最小化节点需要保存的 状态信息量;避免链路和节点的流量集中;根据费用函数优化路由。 多播路由 树有两种类型3 1 :一种是有源树， 另一种是共享树4 1 1 . 2 . 1有源树 有源树是多播树最简单的一种形式。有源树的根是多播信息流的来 源，分支形成了通过网络到达接收站点的分布树。 有源树也有两种形式: 一 种是 最短 路径 树( s h o rt e s t p a t h t r e e ， 简记为 s p t ) 5 16 1 ， 另 一 种 是s t e in e r 树 7 1 最短路径树以最短路径贯穿网络，即从源节点到所有多播组成员都 是通过最短路径。 最短路径树保证了 从源节点到每个多播组成员为最短 路由，但全树的费用并不一定是最优的，这里树的费用指树中所有边的 费 用( c o s t : 这里的费 用是一 个广义上的费 用， 它可以 根 据距离、 信道带 宽、平均通信量、通信开销、队列平均长度、测量到的时延和其它一些 因素的函数而计算出来的 ) 之和。 为了达到全树的费用最优，因此有第二种形式的有源树，即覆盖所 有组成员的一棵最优s t e i n e r 树。 s t e in e : 问 题是从图论中引申出来的一个 优化问 题:在一个连通图中，给定一个节点子集，要求在图中找到一棵 覆盖给定节点子集的费用最小的生成树。s t e i n e : 树的总费用最小，但是 从源节点到每个组成员不一定是最短路由。 在网络中的 每个节点( 实际是 路由 器 ) 都具有多 播功能时， 求解费 用最小的多 播 树问 题与s t e i n e r 树问 题 是等价的。 有源树的潜在缺点是，它不易于升级到大型网络。假设一个网络有 ” 个组，每个组平均有 m个成员，对于每个组，m棵生成树都要存储， 总共有m n 棵树，如果多播组很大，用于存储树的空间就很可观了。 北京交通大学硕士毕业论文 1 . 2 . 2共享树 共享树也就是核树( c o r e - b a s e d t r e e ， 简记为c b t ) 。这里， 每个组只 计算 一 棵生成树， 其树根( 核心 ) 靠近多播组的中间部位， 要发一个多播消 息，主机先将它发往核心，再由核心沿着生成树发送消息。虽然这棵树 并不是对于任何源节点都是最优的，但它将每组m棵树的存储开销降低 到了一棵树，节省了大量空间。 一些多播组中会存在数个有效发送源， 而c b t只构建一棵共享树给 组中所有成员共享，整个多播流量都在这棵共享树上而不论发送源有多 少或在什么位置。 共享树能极大地减少路有器的多播状态数据。 c b t 共 享树由一个核心路由器构建，路由器发送加入请求给核心路由器，核心 路由器接收到请求后返回确认，这样就构成树的一个分支。加入请求在 被确认之前无需被一直传送到核心路由器，如果加入请求到达核心路由 器之前到达树上的某个路由器，该路由器就收下这个请求包而不继续向 前发送并确认这个请求包，发送请求的路由 器就连接到共享树上。 1 . 3多播路由算法研究现状 构造多播树是解决多播路由问题的常用方法，多播路由 算法主要用 来建立一棵性能好的多 播树， 并使它满足各种业务的 服务质量( q u a l i t y o f s e r v i c e ， 简记为q o s ) 需求。 下面根据不同 类型的多播路由 树对多播路由 算法的研究现状进行介绍。 1 . 3 . 1最短路径树 对于s p t的 构造算 法， 人 们在d ij k s t r a 算法基础上不断 进 行改 进， 到目 前为止， 构造s p t的最快算法的时间复杂度为o ( e + n l o g n ) ( 其中n 表示图 中 节点 数目 ， 。 表 示图 中 边的 数 据 ) 8 ,9 ,10 1 。 采 用图 的 链式 存 储结 构， 利用 f i b o n a c c i 堆构造待发展节点集， 就可以 在 口 ( e 十 n l o g n ) 时间内构造 北京交通人学硕士毕业论文 s p t. 当网络变得足够大时，从源节点到一些目的节点的最短路径常常不 只一条， 因而由此构成的s p t也就不是唯一的， 在众多的s p t中每棵树 的总代价也不尽相同。 文献 1 1 提出目 的 驱动最短 路 径树算 法d d s p ， 它采用d ij k s t r a 算 法 路径递增的基本思想，并结合d d m c 算法1 1 2 1 目 的 节点共享路径的 方法， 来降 低 所构造s p t的总 代价。 文献 1 3 在d d s p 算法的 基础上 通过改 进 节点的 搜索过程， 提出了一种快速算法f l s p t ，该算法的时间复杂度比 d d s p 算法更低而且所构造的多播树性能相同。 文献 1 4 1 提出一种动态算法s b p t ， 同 样通过目 的节点之间 共享路径 来降低所构造的s p t的总代价。 该算法添加一个新目的节点的时间复杂 度 为o ( n 2 ) ， 构 造 包 含m 个目 的 节 点 的s p t 的 时 间 复 杂 度 为o ( m n ) ， 时 间复杂度较高而不适合大型网 络求解。 文献 1 5 提出的d l s p t 算法， 在 构造过 程中 利用最短路径子图 1 6 的 性质， 能 够 避免s b p t 算法中 存在的 对非 最短路 径的 计 算， 提高 计 算效率。 该 算法时间复杂 度为。 ( e + n ) ，比 s b p t算法低，而且所构造的s p t性能优于s b p t算法。 1 . 3 . 2 s t e i n e r 树 构造 s t e i n e r 树己证明是n p c问题，不可能获得多项式时间算法， 在可接受的时间内 只能计算得到一 棵近似的s t e i n e r 树。 针对该问 题 人们提出 了 许多 求 近似最 优解的 启发式算法。 m p h l l 1 8 1 , a d h 1 7 1 , k m b 19 1 , t a k a h a s h i 2 0 l , m a x e m c h u k 2 1 等 算 法 提 供t 较 好的 近 似 最 优 解 ， 但 时 间 复 杂 度 都 较 高 而 难 于 应 用 于 实 际 路 由 协 议 。 m p h 是 大 家讨论较多的 算法， s . r a m a n a t h a n 把m p h作为比 较s t e i n e r 树算法的一 种标 准算 法 122 1 , m s t h 1 17 1算 法 虽 有较 低的时 间 复 杂 度， 但 其 平均 性能 和 最坏情况下的性能较差。 文献【 2 3 在m p h算法基础上改 进， 提出局部搜 索算法l s m p h ， 通过牺牲多播树性能来提高效率， 虽然时间复杂度没有 改 变但计算效率有一定提高。 文 献【 2 4 提出 的 快速算 法f m p h ， 通过改 进 北京交通大学硕士毕业论文 m p h算法的搜索过程， 以增加较少的存储空间为代价， 使得时间复杂度 降低， 而且其多播树性能与m p h算法相同。 d d m c算法1 12 1 通过使日 的 节点之间尽可能共享路径来降低多播树的总代价，其平均性能较 ms t h 算法有较大改进， 但仍不如mp h算法。 较之mp h算法， d d mc算法的 最大优点在于不需维护全网络所有节点对之间的最短路径信息。mc t h 算法12 5 在d d m c 算法基础上进行改进， 通过扩大搜索范围， 使所构造的 多播树总代价比d d mc更低。 1 . 3 . 3时延/ 时延抖动约束的s t e i n e r 树 时延约束指源节点到每个目的节点的传送时延要在约束范围内;时 延抖动约束指源节点到每个目的节点的传送时延的差值要在约束范围 内。显然构造时延/ 时延抖动约束的s t e i n e : 树也是n p c问题。 k p p 12 1 算法扩展了 用于 构 造无约束s t e i n e r 树的k m b算法， 它假定 链路时延和给定时延界限均为整数，先构造满足时延限制的完全图，然 后求出 完 全图的 最小 支撑 树。 b s m a 12 7 1 算法则采用一个切实可行的 搜 索 优化方 法， 由 最小时 延 树( 最 短路 径树 ) 开始， 通过替换树中 代价 较高的 边， 迭代改进时延受限树的总代价。这两种算法均有很好的性能，但时间复 杂度都过高而很难应用于实际路由 协议。 c s p t 12 8 是一个简单快速的算 法， 它通过合并最小代价树和最小时延树来构建满足时延限制的多播树。 c d k s t 1 算法首先构造一棵不带限 制的s t e i n e r 树，如果有目 的延迟大于 延迟约束， 那么计算源节点到此目的节点的最短路径，来代替s t e i n e r 树 中 的 最 小 代 价 路径。 d l m r 13 0 1算 法 在m c t h 2 1 1 算 法的 基 础上 进 行扩 展， 在构造s t e i n e r 树的 过程中， 拒绝违反时延限制的 最小代价路径， 而选择 满足时延限制但可能不是最小代价的路径， 其生成树的 代价接近b s m a 算法产生的多播树， 但其时间复杂度远低于b s m a算法。 文献【 3 1 提出了一个集中式的满足时延及时延抖动约束的多播路由 算法d v m a ， 该算法的时间复杂度较高， 而且由于算法没有考虑多播树 的 代价， 因 此算法的 性能 也 较差。 文献【 3 2 提出了 一种分布式的 满足时 延 及时延抖动的s t e i n e : 树算法， 通过在构造过程中协调时延及其抖动之间 北京交通大学硕士毕业论文 的关系，最终使得每条路径在满足时延约束的同时，也尽量保证彼此之 间的时延抖动最小。 文献 3 3 提出的d v d m r算法， 通过计算己 添加的 路径的平均时延，要求所加入的每一条新路径均最接近当前平均时延。 随着平均时延的不断改变，算法最终可以得到时延抖动最小的多播树。 文献 3 4 1 在d v m a算法的基础上进行简化提出s p - d v m a算法， 算法的 时延抖动比d v ma算法有所增大， 但时间复杂度比d v ma有较大降低。 文献 3 5 提出一个关于” 多播可达” 的限定条件和一个新的最佳链路选择 函数， 并以 此选择函数为基础提出了一个新的启发式算法d d v b m r a 用来构造同时满足时延及时延抖动约束的s t e i n e r 树。 1 . 3 . 4度约束的s t e i n e r 树 在上述的s t e i n e : 树构造算法中， 都假设每个节点可以向与其邻接的 所有节点发送信息，但实际网络中并非所有节点都具备多播能力，或者 节点的多播能力受限，给每个节点指定度约束来表示节点的多播能力， 解决此问题称为带度约束的s t e i n e r 树求解。 文献 3 6 1 提出s p h算法求解带度约束的s t e i n e r 树， 每次将与子树最 近的不违反度约束的目的节点添加到子树，直至得到所需的多播树。文 献 3 7 1 提出 用遗传算法来构造带度约束的m s t ， 文献【 3 8 1 在此基础上进行 改 进， 将之用于求解带 度约 束的s t e i n e r 树。 文 献 3 9 1 提出了 分布式带时 延约束多 播路由 算 法， 文 献 4 0 1 在此基 础上提出了 解决带度约束的多 播路 由问题的分布式算法。 文 献 4 1 提出了 计 算机通信网中 的 一 类新问 题， 即同时带 度约束 和时 延约束的多 播路由问 题， 并 使用l a r g r a n g e 松弛 法来解决这类问 题。 1 . 3 . 5共享树 共享树算法首先由w a l l在文献 4 2 中 提出，以 选定中心为根， 其 它组成员按照最短路的原则与中心建立连接，构造成一棵由 所有发送节 点共享的树。c b t不具备广播特性，即数据只发向明确发出加入组请求 北京交通大学硕十毕业论文 的节点，避免了广播式算法运行时大量无效分组的扩散。由于动态优化 选择树中心的算法是n p c问题， 一种简单可行的算法是在接收成员选择 次优中心。 文献 4 3 在分析了 多种确定中 心算法的 基础卜 ， 给出了儿种实用的分 布式优化选择中心的启发式算法4 4 -0 7 ，它们应用局部网络拓扑知识计算 出一系列备用中心， 以降低中心失败带来的影响。 此外， 采用多中心c b t , 也可有效抑制中心失败的影响，但由于构造和管理多中心 c b t的复杂 性，问题还没有成熟的结论。 妇. 4 本文的主要研究内容 根据上节所述，人们在多播路由 算法的研究上取得了很大进展，尤 其是s t e in e r 树构造问题， 包括带各种约束条件的s t e i n e r 树的构造问题上 展开了深入的研究。但是有关最短路径树的研究相对滞后，在降低最短 路径树的总代价方面，生成的多播树的性能尚待进一步优化，而且算法 大多是静态的，动态算法较少，己有的少数动态算法的时间复杂度也较 高，不适合大型网络求解。 本文主要研究最短路径树算法，即如何构造最短路径树，着重考虑 如何在保证最短路径的条件下尽量降低树的总代价，并提高算法的计算 效率。首先研究最短路径树的静态算法，在已有算法的基础上给出一种 时间复杂度更低的改进算法。然后对最短路径树动态算法进行研究，利 用最短路径子图的性质，提出了一种新的算法，在多播树性能以及计算 效率上较己有算法有所改进。 本文内容安排如下: 第二章简要介绍了多播路由的一些基础知识，包括多播路由的网络 模型、多播路由优化准则、多播路由协议、多播路由问题的分类以及多 播路由树的分类，并介绍了几个相关的基本算法，它们是其后大多数算 北京交通大学硕士毕业论文 法的基础，也是同类算法分析比较的 标准。 第三章首先说明了最短路径树的不唯一性，不同最短路径树的总代 价不尽相同。介绍了如何降低最短路径树总代价，提出一种最短路径树 的静态算法，在己有算法的基础上通过改进搜索过程，使得时间复杂度 降低，而所构造的最短路径树性能相同。 第四章首先针对图中两节点间所有最短路径的求解问题，提出一种 新的概念最短路径子图，用以存储源节点到目的节点之间的所有最短路 径信息，并给出了一种构造算法。然后利用最短路径子图的性质，提出 一种最短路径树的动态算法，能够避免对非最短路径的计算，从而提高 计算效率，并且所构造的最短路径树性能优于同 类算法。 第五章对多播路由算法模拟与实现的几个关键环节及技术( 随机网 络模型、 网络图的 存储结构等) 进行了说明， 介绍了几种新的网 络图存储 结构。 然后对笔者编写的一个多播路由算法模拟分析程序进行简要介绍。 最后总结了全文。 北京交通大学硕士毕业论文 第二章多播路由技术简介 2 . 1 多播路由网络模型 在多播路由中， 网络通常表示成一个带权图 g ( v , e ) ， 其中 v代表节 点集合， e 代表连接节点的 链路集合。 iv i 和e l分别代表节点和链路数 目。不失一般性，这里的带权图中每对节点间至少存在一条链路相连; 每条链路上的参数代表链路的当前状态。 例如， 我们定义链路延迟函数d : e - - r +，它为每条链路赋予一个非负的权重。 d ( l ) 表示一个包经过链路 l c e时所产生的延迟;它包括队列延迟、传送时间和复制延迟。同样， 与每个节点相关的参数代表节点的当 前状态( 例如可用缓存大小等) ， 这些 参数称为节点状态。由网络维护的本地状态和链路状态的集合统称为网 络状态。 假设mcv 是一组通信中所涉及的所有节点， 我们称m为多播组， m 中的节点v e m 为组成员。由 源节点v s 产生的包将被发送到一组接收节 点 m - v 5 。 根据多 播组中 源 节点 和接收 节点的 数目 ， 通信方式可 分为 单 点到单点( 单播) 、单点到多点 ( 多播) 和多点到多点( 群播) 三种。 特别的， 在大多数多点到多点的方式中，一组成员可能是源节点，可能是接收节 点，也可能两者都是。多播树t 是g 的子图，它覆盖了m中所有节点。同 时， t 也可能包括传送节点即 一条路径上的 非成员节点。 我们用p t ( v , ,v d ) 表示树中从源节点 v s 到接收节点v d 的路径。 2 . 2 多播路由问题分类 给定一个多播组m和一组可能的最优目 标函数0 ， 多播路由就是在网 络拓扑结构和网络函数的基础上，构建一棵使目 标函数达到最优的多播 树的过程。在基于约束的多播路由中，一组约束通常用点到点延迟、相 北京交通大学硕十毕业论文 互间延迟抖动限制、最小带宽、包丢失率或者它们的组合形式出现。构 建的多播树不仅要满足从源节点到接收节点的可 达性，而且要满足q o s 要求以满足约束条件。 2 . 2 . 1多播路由优化准则 在树型多播路由算法中，可以采取不同的优化准则，第 一 个准则是 端到端的最小延迟，这对于实时会议及多媒体应用来说是至关重要的。 另一个优化目 标是尽可能有效的利用网络资源， 使网络的费用达到最小。 这个目 标对应于两个参量:最小化利用链路带宽;最小化链路拥赛。一 般主要采用下面的优化目 标对给定信源到指定的信宿集合路由算法的有 效性进行评判，用最小化网络代价来度量网络资源的使用。路由r的网 络代价n c定义为: n c ( r ) = i . - ( 1 ) n c ( r ) 就是r上每一条 链路的 代价和， 式中l 是路由r上的 链路， c ( 是 链路1 的 代 价， c ( l ) o o 在数学上，这种树型路由表现为图中的一棵子树，我们称连接给定 节点 所需的 最小费 用问 题为s t e i n e r 问 题， 也就是给定图g = ( v , e , c ) 中， v 为节点集， e为边集， c为 边集的权值费 用( c o s t ) 函 数。 我们的目 的就是 图g中， 给定基本节点 集k = k i ,k z . . . k m ) ，找出一棵子树t ，使得t 连 接所有k基本点，并使这样的 树的权值最小， 用数学描述为: t 为子树 s .t . v ; e t , i = 1 , 2 , . k m in 艺c ( e ) 在这里，我们假设不考虑信道的延迟和可靠性，也不考虑节点的通 信能力， 我们一律假设每一个节点都具有多点传送能力。如果我们要考 虑传送信息时信号的延迟，那么我们就必须对问题的解进行限制。如果 北京交通大学硕士毕业论文 我们考虑信号的延迟必须限定在某一个时间内的话，s t e i n e : 树就变成 了带时延约束的问题，我们将它描述如 f : t 为子树 5 . t 艺d ( e ) ,i , v d ; ( i = 1 , 2 , . ., l k d m in 叉 c ( e ) ” ， 、 如果我们再考虑每个节点的通信能力，即每个节点所具有的通信能 力不都是很强的 ( 特别是在有的设备比 较陈旧的路由 器或服务器上) ， 而且 有的节点不一定具有多播功能，那么这些节点可以向下转发的能力可能 比较弱， 这时在生成s t e i n e r 树的时候就要考虑每个节点向下传送度的情 况。这种我们把它称作带度约束的多播路由树问题。我们描述为: t 为子树 s .t . d e g i d e c o n ; , i = 1 ,2 , . v m i n 艺c ( e ) 其中， d e g i 为生成多播树节点 i 的 度， d e c o n i为该节点的 通信能力约束， 即 该节点的度约束。 2 . 2 . 2静态和动态多播路由 多播路由算法有静态和动态算法之分。 静态多播路由算法针对初始多播组成员构造一棵多播树:它不能根 据当前实际传输量和拓扑变化来做拓扑选择，而是按初始设计好的路由 传送，它的路由修改经过一定运行后才能进行。 但是真实网络中存在许多动态变化， 如网络拓扑结构的变化、组成 员的变化等，因此动态多播算法显得非常重要。首先多播协议应具备自 适应能力，即协议针对路由器出错的情况，能够重新构造最优多播树， 以及避免因链路出错而造成的回路问题。其次，由于多播应用需要网络 北京交通大学硕士毕业论文 支持动态对话，其中组成员变更频繁，为此动态多播算法要处理成员的 加入和离开之后多播树的更新问题。无论以哪种算法初始多播树，组成 员的动态变更都是树保持优化性能的障碍之一。 构造适应组成员动态变化的算法有三种方式:一种是构造一棵性能 优化的初始多播树， 成员变化之后对树采取最小的变化， 如文献 4 8 中的 算法，成员的加入通过建立节点到树的最短路由完成;成员的离开仅删 除树叶节点，如果删除产生一个非成员树叶，该算法删除该节点，直到 不存在非成员树叶。另一种是变更后，对整个组重新进行路由，这将对 组中原来成员 通信产生干扰( 数据分组顺序打乱) ，当 成员的变化剧烈时， 这种方法是不实用的。 文献 4 9 给出了 一种改进方法， 首先节点的加入和 离开仿照前面第一种方式实现，但在树的局部范围内，考察节点的加入 和离开对树的累计损伤，当这种损伤超过一定门限时，在局部范围内 重 新优化路由，通过改变门限 值达到数的优化和计算时间、复杂性之间的 平衡。第三种是构造一棵富于弹性变化的次优树，即最短路径树，每个 组成员之间相互独立选择最短路由，因此树的性能不受组动态变化的影 响。 2 . 2 . 3集中式和分布式多播路由 多播路由算法按其实现方式，又可分为分布式和集中式算法。 集中式路由算法是由 节点在掌握整个网络的拓扑结构后，确定多播 路由。 集中 式多 播路由 一 般都是 源路由 算法 ( s o u r c e - ro o t e d r o u t i n g ) ， 即 源 节点通过某个链路协议获得完整的网络拓扑信息，进行路由的计算。集 中式算法有一些缺点， 首先是节点在确定路由 之前要收集全网拓扑信息， 这样易造成链路拥塞，有一定的时延;其次节点要定期更新拓扑信息， 以保证不产生回路。 分布式算法不需要每个组成员掌握整个网络的拓扑，每个组成员在 只具有局部信息条件下就可参与路由的确定，这对实现大型网络的多播 路由 是+分有利的。分布式算法有以下三个优点: 北京交通大学硕十毕业论文 1 )算法的执行只限于组成员节点，并不是所有网 络节点都参与路 由算法; 2 )每个节点只用到局部信息，不需要存在 一 个存储有整个网 络信 息的中心节点; 3 )算法所需的通信费用少，并且建立路由的时间短。 2 . 2 . 4 q o s 多播路由 随着网络技术的迅速发展， 交互式会议电视、 分布式网络对战游戏、 协同文档编辑、视频点播、网络电话、远程实时医疗等己经开始应用。 这 些应用 涉及到网 络的 服务 质量q o s 问 题。 q o s 包括许多 方面， 例如 端到 端时延、端到端时延抖动、路径带宽、路径中的数据丢失率等。其中， 端到端时延是实时通信应用中很基本的一个方面。对于实时通信来说， 如果时延过长，就会引起用户视觉和听觉上的不舒服，甚至引起语意的 无法理解。 对于实时多播通信， 端到端的时延抖动则变得很重要。 例如， 电视会议中，要保证各地的与会者要同时听到发言者的讲话，从会场到 各地的消息传输的时延必须限制在一定的范围内，时延值只能在这个范 围内波动。而对于视频点播来说，要保证一定的图象质量，网络必须提 供足够的带宽和可以 接受的数据丢失率。 对于多播q o s 路由问 题， 一般有两种q o s 要求， 即最优化( o p t i m i z a t i o n ) 和给定某个约束( c o n s t r a i n t ) 。 这些要求的 组合就形成了 用户多网 络提出 的 各种q o s 要求。如我们要求多播树中 源节点到各个组成员的时延不高于 d ，但多播树的代价要求最小，这就是多播的路径时延受限和多播树优 化的 组合。多 播q o s 路由问 题中 研究得最多的 是受限多 播树( c o n s t r a i n e d m u lt i c a s t in g a l g o r it h m ) ， 其中 包 括时 延 受限 最 小 代 价多 播树、 度约 束 多 播 树、带宽受限多播树问题。另外，时延抖动受限问题也是研究的重点。 除了启发式多播路由 算法以 外，智能q o s 多播路由 算法也成为 研究 方向。由 于q o s 路由问 题的 复杂性，引入人工智能方法是很合理的，目 前提出的算法有两种:一种是基于遗传算法、神经网络技术的多播路由 北京交通大学硕士毕业论文 算法:另一种是基于模糊理论的模糊寻径。 2 . 2 . 4分层多播路由 随着网络规模的扩 一 大，例如目 前i n t e rn e t 的规模每年都在增大，接入 i n t e rn e t 的主机数量从1 9 9 0 年以来， 每年都以 将近i 倍的速率增长， 到2 0 0 0 年主机数量已超过5 0 0 0 万台，路由器路由表也会成比例增大。增大的表 格不仅占用路由器的内存，而且需要更多的c p u 时间扫描表格，以及更 大的带宽来发送关于表格的状态报告。在某一时刻，网络可能会增大到 不可能让每一个路由 器都给出至其它每一个路由器的路径表项。为此出 现了分层路由 选择( h i e r a r c h i c a l r o u t i n g ) 机制，分层路由 算法是将网络先 按不同等级、不同层次划分，每个路由器知道在自己的区域内怎样选择 路由和如何将分组送到目的端的全部细节，但并不知道其它区域的内部 结构。 采用分层路由算法有许多集中式算法无法相比的优点，例如: 1 )由于采用了分层的方法，顶层的节点数大大减少，由 此减少了 路由表的搜索时间，路由表的计算量也大大减少，每一层节点 内部的路由 表只在内 部有效。 2 )每一层的节点只保存当前层的 状态信息， 与上下层都没有关系， 从而减少了对内存的需求量。 3 )每一层节点只在