（信号与信息处理专业论文）基于新型向量网的多播路由体制研究.pdf

中文摘要 摘要：随着计算机网络的迅速发展， 也由单点问的通信向多点问的通信发展， 网络功能日益强大。网络中的通信方式 因此对多播技术的研究也成为网络通信 领域中的一个重要研究课题。多播是一个源节点将同一信息传送到多个目的节点 ( 但不是所有节点) 的通信方式。远程会议、交互式仿真、分布式内容系统、多方 游戏等应用都对多播业务( m u l t i c a s ts e r v i c e ) 提出了需求 历经2 0 多年的研究和发展，i p 多播已经形成了较为完整的多播协议体系，由 于i p 网中的多搔基于组地址实现，因此也称为“组播”。从因特网中i p 组播的 应用现状看，尽管经过了2 0 多年的发展，i p 组播并没有取得预期的成功。一方面， 因特网中的网络极少开放i p 组播业务，至今还没有全因特网范围的组播业务；另 一方面，基于i p 组播的上层应用也屈指可数，相对于w w w 等新的体系结构，i p 组 播的发展非常缓慢。 本文通过分析利用一种新型第三层网络一一向量网的特性，与现有因特网的 多播机制进行比较，提出一种在向量网中可行的实现多播路由的方法。此方法完 全不同于口网的多播体系结构，而是基于全新的地址编码方法一一向量地址，利 用类似于p n n i 协议的分层路由体制的特性，通过分布式递归调用最小生成树 p r i mj a r n l k 算法，在网络中确定一棵多播分布树。此多播分布树可作为多播数据 包的实际路径。从网络总体代价来看，沿此路径多播传送数据时所花费的代价最 小。此外，还提出了一种与此多播路由机制相配套的向量地址，此向量地址采用 树状结构，利用这种向量地址。多播数据包可以通过各种路由器而不用关心它是 否支持多播，使得多播成本减少，效率提高。在提出一套可行方案之后，通过o p n e t 网络仿真软件和v i s u a ls t u d i o6 0 调试环境对此多播路由体系进行了验证。 关键词：向量地址；多播分布树；最小生成树；源限定寻由 分类号： a b s t r a c t a b s t r a c r w i t ht h ef a s td e v e l o p m e n to f t h ec o m p u t e rn e t w o r ko f w h i c ht h ef i 】删砸 i sm o r ea n dm o r ep o w e r f u l ，t h ew a yo fc o m m u n i c a t i o ni nt h en e t w o r kh a sb e e n d e v e l o p e df r o mo n e - t o - o n et oo n e - t o - m u l t i p l eo rm u l t i p l e - t o - m u l t i p l em o d e s ot h e r e s e a r c ho nm u l t i c a s tt e c h n o l o g yh a sb c c o l n eas i g n i f i c a n tp r o b l e mi nt h ef i e l do f n e t w o r kc o m m u n i c a t i o n m u l t i c a s ti saw a yo f c o m m u n i c a t i o ni nw h i c ht h e5 0 u r c on o d e o rt h e8 0 u r h o s ts e n d st h e $ 8 1 n ep a c k e tt ot h em u l t i p l ed e s t i n a t i o nn o d e sa tt h es a m e t i m e ，1 1 ”a p p l i c a t i o n ss u c h 够r e m o t ec o n f e r e l 3 c o , i n t e r a c t i v es i m u l a t i o n , d i s t r i b u t e d c o n t e n ts y s t e ma n dm u l t i - u s e r 学u l 螂r e q u i r et h em u l t i c a s ts e r v i c ev e r ym u d l i pm u l t i c a s tt h a th a sb e e nr e s e a r c h e da n dd e v e l o p e df o r2 0y e a r si sm a d eu po fa c o m p l e t em u l t i c a s tp r o t o c o ls t a c k e v e nt h o u g hi te x p e r i e n c e dl o n g - t e r md e v e l o p m e n t , i pm u l t i c a s td o e s u ta c h i e v e dt h ea n t i c i p a t e d 飘l c c e 鼹w h i c hc 锄b e 翻渤f r o mi n t e m e t o nt h eo n eh a n d , i n t e m e ts c a r c e l ys u p p o r t si pm u l t i c a s ts e r v i c e s of a r , t h em u l t i c a s t s e r v i c eh a sn o tc o v e r e dt h ew h o l er a n g eo ft h ei n t e r n e t o nt h eo t h e rh a n d ，t h en u m b e r o f a p p l i c a t i o n st h a tb a s e0 1 1t h ew m u l t i c a s ti ni n t e r n e tc a nb ec o u n t e do no n e sf i n g e r s s o1 1 m u l t i c a s ti sd e v e l o p i n gs l o w l yi nc o m p a r i s o nw i t ho t h e rn e wa p p l i c a t i o ns y s t e m s t l i i sp a p e rp r e s e n t sam e t h o df o rm u l t i c a s tw h i c hi sf e a s i b l ei nan o wt h i r d - l a y e r n e t w o r kc a l l e dv e c t o rn e t w o r kb ya n a l y z i n ga n du s i n gt h ep r o p e r t yo ft h i sn e t w o r k t h i sm e t h o db a s e so nt h et l c ww a yo fa d d r e s sc o d i n g , a n du 懿t h ec h a r a c t e r i s t i co f h i e r a r c h i c a lr o u t i n ga r c h i t e c t u r e a st h ep a t hm u l f i c a s td a t ap a c k e t sp a s sb y , am u l t i c a s t d i s t r i b u t i o nt r e ec a nb eb u i l tb yi n v o k i n gm i n i m ms p a n n i n gt r e ea l g o r i t h m d i s t r b u t e d l ya n dr e e u r s i v e l yi nt h i sm e t h o d i nt e r m so ft o t a lc o s t , 1 1 坼m u l t i c a s tc o s t w i l lb em i n i n l u ma l o n gt h em u l t i c a s td i s t r i b u t i o nt r e e a d d i t i o n a l l y , an e wv e c t o r a d d r e s sf o r m a th a sb e e nd e s i g n e dw h i c hh a sad e n d r i f o r ms t r u c t u r e t h ee x p e n s eo f m u l t i c a s tc a l lb ed e c r e a s e dg r e a t l yb yu s i n gt h i sn 钾v e c t o ra d d r e s sf o r m a t i na d d i t i o n , t h i sn e wm u l t i c a s tm u t i n ga r c h i t e c t u r eh a sb e e nv e r i f i e db yu s i n go p n e tn e t w o r k s i m u l a t i o ns o f t w a r ea n dv i s u a ls t u d i o6 0 k e y w o r d s ：v e c t o ra d d r e s s ；m u l t i e a s td i s t r i b u t i o nt r e e ；m i l l i l x l u i l ls p a n n i n gt r e e ； s o u r c ed e f i n e d r o u t i n g c l a s s n o ： 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 募辱 导师签锑彩芝气7 ” 签字日期：卿年，) 月加e t签字日期；明年， 月饥日 独创性声明 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意 学位论文作者签名： 蒙昂 签字日期：一 年2 月弘日 致谢 本论文的工作是在我的导师梁满贵教授的悉心指导下完成的，梁满贵教授严 谨的治学态度和科学的工作方法给了我极大的帮助和影响。在此衷心感谢三年来 梁满贵老师对我的关心和指导 梁满贵教授悉心指导我们完成了实验室的科研工作，在学习上和生活上都给 予了我很大的关心和帮助，在此向梁满贵老师表示衷心的谢意。 梁满贵教授对于我的科研工作和论文都提出了许多的宝贵意见，在此表示衷 心的感谢。 在实验室工作及撰写论文期间，岑护平、陈宇迪、武可新、张琰彬等同学对 我论文中的路由体系初始化方面的研究工作给予了热情帮助，在此向他们表达我 诚挚的感激之情。 另外也感谢我的父亲和母亲，他们的理解和支持使我能够在学校专心完成我 的学业。 序 从因特网发展的过程和口网络的体系结构看，阻碍口组播业务发展的主要因 素为： 1 p 组播体系结构缺乏可扩展性。这是由口网的地址编码方式所导致的。 2 开放的口组播模型在开放的因特网环境中难以支持有效的管理和控制机 制。标准的m 组播业务模型是一种a n ys o u r e 圩，a n yr e c e i v c l - 的开放模型， 任何节点都可以创建组，可以向组发送数据，节点可以加入任何感兴趣的 组接收数据，发送节点不知道具体的单个接收节点，接收节点也不需要知 道发送数据的节点。在这种模型下，接入控制、组管理、组地址的协调机 制一直没有有效的解决方案。 向量网中的多播与m 组播有很大的不同。因特网中的网络层多播是由两个互 补的组建构成的：i g 枷p 协议与多播选路协议。在因特网体系结构中，由于m 地 址的编址特点，若使得发送方在多播分组中标识出每一个接收方，则分组中编址 信息的量将淹没该分组中有效载荷中实际可携带的数据量，因此多播分组采用间 接地址一一组地址来编址。虽然多播组的抽象是简单的，但随之而来的是关于组 员管理的一堆问题，因此产生了i g m p 。在向量网中则没有多播组的概念，其多播 服务模型采用最小化网络层的观点，即在多播数据之前，发送方就已知各接收方 以及多播路由器( m u l t i c a s t i n gr o u t e r ，m r ) 的名称地址，至于如何获得则交给上层 的协议机制去完成；为了多播向量网设计出一种特别的树状向量地址格式，m r 通 过读取这种向量地址便可将多播数据包复制并转发到相应的出端口处。因此向量 网中的m r 可以这样定义：能够理解多播地址项信息，具有按照这些信息复制并 转发数据包能力的路由器。因特网中，多播选路的目标就是发现一棵链路树，称 之为多播分布树( m u l t i c a s t i n gd i s t r i b u t i o nt r e e ，m o t ) ，该树连接了所有与属于该多 播组的主机相连的路由器。有两种方法可以确定m d t ，使用组共享树和使用基于 源的树。在向量网的多播中。相同的是也要生成一棵m d t 作为多播数据包的实际 传输路径；不同的是生成多播树的过程由发送方“委托”一个m r 发起计算，计 算过程也是分布式的，最终生成的是一棵以发送方为树根，接收方为树叶的m d t ， 发送方保存m d t ，各m r 不需要像讲网那样记录多播信息。因特网中多播分组通 过单播路由器时，必须运用隧道技术。而隧道是由手工配置的，显然这样做是很 低效的。而向量网通过采用树状的向量地址结构，单播路由器可以理解其中的一 部分分量地址，使得多播数据包可以顺利的通过路由器，而不管它们是否支持多 播。最后一点，也是很重要的一点，因特网中由于自治系统的存在，多播路由协 议纷繁复杂，而向量网是一种具有分形特征的网络，一种统一的方法或协议是可 以解决问题的。 引言 第一章引言 传统的解决一点向多点发送信息的方法有两种：以单播的方式分别向目的点 发送信息；以广播的方式发送信息。对于前者，同一个数据包需要重复地传送， 这样就会严重浪费网络带宽，容易导致网络拥塞，而且在发送端会产生巨大的延 迟，发送端的主机工作量也非常大对于后者，数据包发给了网络上所有节点， 给非目的节点增加了大量没有意义的负载，影响了网络性能。 1 9 8 8 年，d e e r i n g 提出了m 多播的概念多播介于单播通信和广播通信之间， 它可以让发送者将数据发送到指定的多个接收者，而不用担心其他的主机会接收 到这些数据包。m 多播使用组的概念，这个组没有任何物理或地理的限制，可以 是在任何一个角落的任何一个子网内。每个想从指定的组接收数据的主机必须先 加入多播组。当数据包发向多播组时，这个组中的所有主机都会收到。 1 1 多播技术背景 口网多播需要从主机到路由器和交换机都能够支持。多播通过组的方式管理 成员，通过树的方式管理路由，因此提出了i g m p ( 英特网组管理协议) 和p i m ( 协 议无关多播) 、d v m r p ( 距离矢量多播路由协议) 等协议，用于在网络上运行多 播。 1 1 1 多播数据的发送 当一个数据包要发向n 个目的节点时，需要复制成n 个拷贝，然后逐一对应 每个目的点的路径发送。单播采用了这样的的方式，如图1 所示。 发送方 图1 单播数据包的传送 3 接收方 北京交通大学磺士论文 多播对数据包采用分叉复制的方法，数据以单个包的方式发送，在某个中间 位置出现分叉时，则复制并且朝每个出口发送一个拷贝。这样在同一条路径上只 存在一个拷贝，节省了网络带宽和中间路由器的负载，而且避免了由于目的节点 过多导致发送端出现过大发送时延的情况如图2 所示 1 1 2 多播地址 图2 多播数据包的传送 接收方3 主机的地址有两种；m 地址和m a c 地址，分别对应于网络层和数据链路层。 m 地址由4 个8 位字节组成，按照首字节的值进行区分。其中2 2 4 0 0 0 - - 2 3 9 2 5 5 2 5 5 2 5 5 这个d 区段用于多播。 m a c 地址由6 个8 位字节组成，i n t e r n e t 权威机构把0 1 - 0 0 5 e , 0 0 - 0 0 - 0 0 弼 0 1 - - 0 0 5 8 7 f - f f f f 范围的多播地址保留用于以太网和光纤分布式数据接口 ( f d d i ) 中以支持多播。为了将一个口多播地址映射到一个m a c 层多播地址， 理多播地址的2 3 个低序位被直接映射到m a c 层多播地址2 3 个低序位。映射方式 如图3 所示。 墼堕 ， 2 bn i 槛 图3 m 组地址到m a c 组地址的映射 2 三乏 引言 根据d 类地址约定，口多播地址的前4 位是固定的，p 多播地址中有5 位没 有映射到m a c 层多播地址。因此，某个主机可以接收不是它所属的组的m a c 层 多播数据包。然而，一旦确定了目标口地址，这些数据包就会被i p 丢弃。令牌环 网也使用同样的方法进行m a c 层多播寻址 1 1 3 多播分布树 一般要求多播服务的业务对带宽和实时性要求较高，涉及用户较多，占用的 资源也多，因此有必要优化多播路由多播路由算法就是要寻求最优多播分布树， 理想有效的路由算法将设计一棵仅覆盖多播组成员的树，并体现如下特征：树随 着组成员变化动态更新，最小化节点需要保存的状态信息量；避免链路和节点的 流量集中；根据费用函数优化路由。多播路由树有两种类型：一种是有源树，另 一种是共享树i l i 。 有源树是多播分布树最简单的一种形式。有源树的根是多播信息流的来源， 分支形成了通过网络到达接收方的分布树。有源树也有两种形式：一种是最短路径 树( s h o a e s t p a t h t r e e ，简记为s p t ) t 2 l ”，另一种是s t e i n e r 树t 4 l 。最短路径树以最短 路径贯穿网络，即从源节点到所有多播组成员都是通过最短路径。最短路径树保 证了从源节点到每个多播组成员为最短路由，但全树的费用并不一定是最优的， 这罩树的费用指树中所有边的费用之和，这里的费用是一个广义上的费用，它可 以根据距离、信道带宽、平均通信量、通信开销、队列平均长度、测量到的时延 和其它一些因素的函数而计算出来的。为了达到全树的费用最优，因此有第二种 形式的有源树，即覆盖所有组成员的一棵最优s t e i n e r 耪j 。s t e i n e r 问题是从图论中引 申出来的一个优化问题：在一个连通图中，给定一个节点子集，要求在图中找到 一棵覆盖给定节点子集的费用最小的生成树。s t e i n e r 栖l 的总费用最小，但是从源节 点到每个组成员不一定是最短路由。在网络中的每个节点( 实际是路由器) 都具有 多播功能时，求解费用最小的多播树问题与s t e i n e r 树问题是等价的。有源树的潜在 缺点是：它不易于升级到大型网络。假设一个网络有n 个组，每个组平均有m 个成 员，对于每个组，m 棵生成树都要存储，总共有n l n 棵树，如果多播组很大，用于 存储树的空间就很可观了 共享树也就是核树( c o r e - b a s e dt r e e ，简记为c b t ) 。这里每个组只计算一棵生 成树，其树根( 核心) 靠近多播组的中问部位，要发一个多播消息，主机先将它发 往核心，再由核心沿着生成树发送消息。虽然这棵树并不是对于任何源节点都是 最优的，但它将每组m 棵树的存储开销降低到了一棵树，节省了大量空间。一些多 播组中会存在数个有效发送源，而c b t 只构建一棵共享树给组中所有成员共享， 北京交通大学硕士论文 整个多播流量都在这棵共享树上丽不论发送源有多少或在什么位置。共享树能极 大地减少路有器的多播状态数据。c b t 共享树由一个核心路由器构建，路由器发 送加入请求给核心路由器，核心路由器接收到请求后返回确认，这样就构成树的 一个分支。加入请求在被确认之前无需被一直传送到核心路由器，如果加入请求 到达核心路由器之前到达树上的某个路由器，该路由器就收下这个请求包而不继 续向前发送并确认这个请求包，发送请求的路由器就连接到共享树上 1 2 多播算法研究现状 为进行有效的多播通信，确定多播路由是非常关键的。多播路由算法就是用 来确定一棵性能好的多播分布树，并使它满足各种业务的服务质量( q u a l i t yo f s e f v i ，简记为q o s ) 需求。下面根据不同类型的多播分布树对多播路由算法的研 究现状进行介绍。 1 2 ，1 最短路径树 对于s ”的构造算法，人们在d i j k s t r a t 算法的基础上不断进行改进，到目前 为止，构造s 盯的最快算法的时间复杂度为帅l o 驴) 晦7 朋( 其中n 表示图中节点数 目，e 表示图中边的数目) 。采用图的链式存储结构，利用f i b o n a c c i 堆构造待发展节 点集，就可以在o ( 洲o g n ) 时间内构造s i t 。当网络变得足够大时，从源节点到一 些目的节点的最短路径常常不只一条，因而由此构成的s p t 也就不是唯一的，在众 多的s p t 中每棵树的总代价也不尽相同。文献 9 1 提出目的驱动最短路径树算法 d d s p ，它采用d i j k s 觯法路径递增的基本思想，并结合d d m c 算法【1 0 1 目的节点 共享路径的方法，来降低所构造s p t 的总代价。 1 2 2s t e i n e r 树 构造s t e i n e r ： $ j 己证明是n p c 问题，不可能获得多项式时间算法，在可接受的时 间内只能计算得到一棵近似的s t e i n e r 树。针对该问题人们提出了许多求近似最优解 的启发式算法。m p h t “1 , a d h t 幢j k m b t ”】, t a k a h a s h i t “i ，m a x e m c h u k l l 5 i 等算法提供了 较好的近似最优解，但时间复杂度都较高而难于应用于实际路由协议。m i h 是大 家讨论较多的算法。s 。r a m 删m p h 作为比较s t e i n e r 树算法的种标准算法， m s t h 算法虽有较低的时间复杂度，但其平均性能和最坏情况下的性能较差。文献 在m p h 算法基础上改进，提出局部搜索算法l s h 口h ，通过牺牲多播树性能来提高 引言 效率，虽然时间复杂度没有改变但计算效率有一定提高。文献f l 卅提出的快速算法 f m p h ，通过改进m p h 算法的搜索过程，以增加较少的存储空间为代价，使得时间 复杂度降低，而且其多播树性能与m p h 算法相同。d d m c 算法通过使日的节点之间 尽可能共享路径来降低多播树的总代价，其平均性能较m s t h 算法有较大改进，但 仍不如m p h 算法。较之m p h 算法，d d m c 算法的最大优点在于不需维护全网络所 有节点对之间的最短路径信息。m c t h 算法i l 刀在d d m c 算法基础上进行改进，通 过扩大搜索范围，使所构造的多播树总代价比d d m c 更低 1 2 3 时延时延抖动约束的s t e i n e r 树 时延约束指源节点到每个目的节点的传送时延要在约束范围内：时延抖动约 束指源节点到每个目的节点的传送时延的差值要在约束范围内。显然构造时延时 延抖动约束的s t e i n e r 树也是n p c 问题。 k p p l l 埘算法扩展了用于构造无约束s t e i n e r 树的k m b 算法，它假定链路时延和 给定时延界限均为整数，先构造满足时延限制的完全图，然后求出完全图的最小 支撑树。b s m a | ”1 算法则采用一个切实可行的搜索优化方法，由最小时延树( 最短 路径树) 开始，通过替换树中代价较高的边，迭代改进时延受限树的总代价。这两 种算法均有很好的性能，但时间复杂度都过高，因此都很难应用于实际路由协议。 c s p t 脚j 是一个简单快速的算法，它通过合并最小代价树和最小时延树来构建满足 时延限制的多播树。c d k s 2 1 1 算法首先构造一棵不带限制的s t e i n e r 树，如果有目的 延迟大于延迟约束，那么可以计算源节点到此目的节点的最短路径，来代替s t e i n e r 树中的最小代价路径。d l m r i ”i 算法在m c t h t 铆算法的基础上迸行扩展，在构造 s t e i n e r 耪t 的过程中，拒绝违反时延限制的最小代价路径，而选择满足时延限制但可 能不是最小代价的路径，其生成树的代价接近b s m a 算法产生的多播树，但其时间 复杂度远低于b s m a 算法。文献1 提出了一个集中式的满足时延及时延抖动约束 的多播路由算法d v m a ，该算法的时间复杂度较高，而且由于算法没有考虑多播 树的代价，因此算法的性能也较差。文献提出了一种分布式的满足时延及时延 抖动的s t e i n e r 树算法，通过在构造过程中协调时延及其抖动之间的关系，最终使得 每条路径在满足时延约束的同时，也尽量保证彼此之间的时延抖动最小。文献忙6 1 提 出的d v d m r 算法，通过计算己添加的路径的平均时延，要求所加入的每一条新路 径均最接近当前平均时延随着平均时延的不断改变，算法最终可以得到时延抖 动最小的多播树。 ， 北京变通大学硕士论文 1 2 4 动态s t c i n e r 榭 由于网络拓扑的变化和节点的加入和离开，都会对s t c i n e r 树的性能造成巨大影 响。因此需要s t c i n e r 树构造算法在这些变化发生时调整s t e i n e r 树的结构，使多播树 保持高性能的状态。这使得动态s t e i n e r 耦i 成为必要。构造动态s t e i n e r 耦i 的算法有两 种方式：一种是构造一棵性能优化的初始多播树，成员变化之后对树采取最小的变 化，如文献田l 中的算法，成员的加入通过建立节点到树的最短路由完成：成员的离 开仅删除树叶节点，如果删除产生一个非成员树叶，该算法删除该节点，直到不 存在非成员树叶。另一种是变更后，对整个组重新进行路由，这将对组中原来成 员通信产生干扰( 数据分组顺序打乱) ，当成员的变化剧烈时，这种方法是不实用 的文献【2 町给出了一种改进方法a 蒯匣s ，首先节点的加入和离开仿照前面第一种 方式实现，但在树的局部范围内，考察节点的加入和离开对树的累计损伤，当这 种损伤超过一定门限时，在局部范围内重新优化路由，通过改变门限值达到数的 优化和计算时问、复杂性之间的平衡。 1 2 5 共享树 共享树算法首先由w a l l 在文献例中提出，以选定中心为根，其它组成员按 照最短路的原则与中心建立连接，构造成一棵由所有发送节点共享的树。c b t 不 具备广播特性，即数据只发向明确发出加入组请求的节点，避免了广播式算法运 行时大量无效分组的扩散。由于动态优化选择树中心的算法是n p c 问题，一种简 单可行的算法是在接收成员选择次优中心。文献( 刈在分析了多种确定中心算法的 基础上，给出了几种实用的分布式优化选择中心的启发式算法，它们应用局部网 络拓扑知识计算出一系列备用中心，以降低中心失败带来的影响。此外，采用多 中心c b t ，也可有效抑制中心失败的影响，但由于构造和管理多中心c b t 的复杂 性，问题还没有成熟的结论 1 3 多播路由算法的性能指标 多播路由算法的好坏，也就是多播树的好坏。影响多播路由算法的因素有很 多，但随着应用的不同，其要求也各不相同。对大多数应用来说，有些特性如时 延、树费用等比算法的其它特性更重要。而对于某些多媒体应用，丢包率和时延 抖动也非常重要。下面是多播树的各种特性参数： 1 ) 费用：一棵多播树的费用等于多播树上每一条链路的费用之和。好的多播路由 引言 算法就是使得费用尽量低。 2 ) 时延：这里时延是指源节点到目的节点的路径上各条链路和节点的时延之和。 多播树应尽量使得任何源至目的节点之间的端到端时延最小。 3 ) 可扩展性：多播树的可扩展性表现在两个方面：一是在多播成员很多的情况下 构造多播树的时间和占用的资源应尽可能少，二是网络中的交换机或路由器应能 够同时支持大量的多播组。 4 ) 复杂度：复杂度是指计算一棵多播树所需的时间与网络规模之问的关系。好的 算法应该是低复杂度的算法。 5 ) 动态特性：多播组可以划分为静态和动态二类。静态多播组的成员自始至终不 改变，而对于动态多播组来说，新成员可以随时加入，老成员可以随时离开。好 的多播路由算法应该允许多播成员无缝加入或离开，而且多播树的性能不能由于 多播动态特性而变得很差。 6 ) 强壮性：多播树能够在多个网络节点或多条链路失效时依然正常工作，并且性 能不会受到很大影响。 7 ) 公平性：多播路由算法的公平性体现在两个方面，一是对于多播组的每一个成 员都提供最低标准的服务，而不是以惩罚某些成员来换取另一些成员的q o s 。第二 应该尽量使得参与的节点平分多播任务。 1 4 本人所做工作概述 总之，本人所傲的主要工作包括以下几个方面： i 分析向量网的多播属性，并比较其与口组播在多播服务模式上的异同， 提出一套能够在向量网中实现多播的路由方案。 2 通过递归调用最小生成树算法，在向量网体系结构中动态生成一棵以 数据发送端站设备为树根，多播路由器或者交换机为树权节点，数据 接收端站设备为树叶的多播分布树并将此实现过程在对等组内的情 况进行了仿真验证。 3 比较向量网中单播与多播情况的不同，对单播情况下的寻由过程进行 改进，设计出了一套多播寻由方法，并将此方法定名为源限定寻由 4 设计出一种专门用于多播的地址项格式一一予树格式，在多播数据包 中包含此地址项，使得多播数据包能够被多播路由器正确地识别、复 制、选路。并在o p n e t 中仿真实现了多播路由器的相关操作。 5 利用多目标路由原理，实现多播的传送面，即多播数据包从一到多的 传送过程。并在o p n e t 中仿真实现。 7 北京交通大学硕士论文 分析向量网中多播数据接收方动态变化情况，并与i p 网的这方面内容 进行比较，总结了异同。 i 口冈多播技术简介 第二章口网多播技术简介 2 1 多播网络体系结构 网络设备包括终端主机、路由器和交换机必须运行不同的多播协议来支撑一 个完整的多播网络架构。 多播协议从结构上划分主要分为三部分：主机和路由器之间建立及维护多播 成员关系的协议一互联网组管理协议( r o m p ) ；多播路由器之间构造多播分发树的 协议一多播路由协议；路由器和交换机之间控制多播扩散的协议- - c g m p ，i g m p s n o o p i n g 。主机通过组成员管理协议加入和离开多播组，而多播流量则由成员主机 所属子网的路由器负责转送，因此多播流量的传送顺序应该是多播源主机发送给 源所在子网的路由器，然后路由器根据多播树转发到所有的树上节点路由器，树 上的节点再将多播流量转送给成员主机。 2 2 因特网组管理协议( i g m p ) i g m p ( i n t e m e tg r o u pm a n a g e m e n tp r o t o c o l 。因特网组管理协议1 运行在口站点 和它所在的子网多播路由器之间，用来控制组成员的加入和退出。当某个m 站点加 入某一个多播组时，它需要通知它所在的妒子网的多播路由器该多播组是它想加入 的，同时将自己的口模块准备开始接受从特定的多播组传来的多播数据：如果该p 站点是它所在的口子网中第一个加入该多播组的，通过路由信息的交换，多播路由 器将被加入该多播组的转发树。这是一种由接收方来初始化的加入方法，在多播 组的数据越来越多时，这种方法可以使新加入的多播组成员尽快找到离它很近的 多播组的分支，从而加入多播组。在i g m p1 0 中，当每一个站点离开某一个多播 组时，它不通知任何人就自然地离开，多播路由器定时向m 子网中的所有多播组询 问，如果某一个多播组在m 子网中己经没有任何成员，则多播路由器在确认这一事 件后，不再将该多播组的数据在子网中进行传送，同时通过路由信息的交换，将 相应的多播路由器从特定多播组转发树中删除，这种不通知任何人而悄悄离开的 方法，使得多播路由器知道口子网中己经没有任何成员的时间延时了一段时间，所 以在i g m p 2 0 中，当每一个m 站点离开某一个多播组时，需要通知子网多播路由器， 多播路由器立即向口子网中的所有多播组询问，从而减少了系统处理停止多播的延 9 北京交通大学颈士论文 时。路由器通过i g m p 获得消息，并在每个端口基础上维护多播组成员表。只要端 口上有一个主机通过i g m p 发出信号想接受多播组信息，多播组成员之间的关系就 发挥着作用。 2 3 多播转发方式 基于多播的数据传送，其基本机理是通过多播数据包在路由器分叉处的复制 和分发，这个过程被称为前转( f o r w a r d ) 。多播数据包的前转由三种方法：反向路径 广播( r p b ) ：路由器从某个接口收到多播数据包，则将该数据包向其他所有端口转 发。这个方法有显而易见的缺点，多播包会向网际所有的子网发送，而实际上多 播组的成员只是在子网的个子集中。而且将一个多播的包扩散( f l o o d ) 到各个子 网中不仅违背了多播的目标，也违背了路由的原则。截断的反向路径广播( 1 r i 蹬b ) ； 路由器通过i g m p 发现它相连的子网上没有一个组员，并且子网没有下一跳的路由 器时，路由器就停止向这个子网前转多播数据包。不能通过的子网，用树形结构 的术语，称为叶网络。t r p b 保护了叶网络的资源，但实际上并没有比r ib 有更大 的改进。反向路径多播( 薹u ，m ) ：路由器只将数据包前转到连接有多播组成员的子 网的路径上的路由器对应的端口，这就要建立“多播树”，并且进行管理。多播 树就是覆盖所有直接连接有多播组成员子网的路由器的生成树。多播树具有两大 优点：一是信息以并行方式沿着树枝发送到不同目的节点，降低了信息传递的时 延；二是网络中需要传送的复制信息少，能够节省网络带宽资源，提高每次多播 通信时的资源利用率，并能减少拥塞，降低网络负载。因此构造多播树是当前解 决多播路由问题的常用方法。 2 4 域内和域间多播路由 由于实际网络的路由器规模庞大，如果每个路由器都保存到所有其他目标的 前转表，则路由表规模会非常庞大。所以需要将网络结构按层次分级，分为域内 路由和域问路由。所谓的域是指一个自治系统伍s ) ，比如一个局域网或校园网， a s 内部通过某种机制( 静态配置或者动态选举) 产生一台路由器作为网关a s 内的 路由器判断路由是否要出这个域，如果是，则将数据前转到网关，由网关代为转 发，否则根据域内路由表前转数据包。域问路由是网关和网关之间的路由。为了 避免环路，网关还分为核心网关和末梢网关，末梢网关只能发送它自己域的有关 网络的信息，而核心网关则可以转发它接收到的其他域的网络信息。 m 同多播技术简介 2 5 多播路由协议 要确定多播路由，首先要收集网络中的相关状态信息，路由算法就在这些信 息的基础上来确定路由。网络的状态信息包括网络的拓扑结构、链路和路由器的 负载程度、链路和路由器的生效和有效、网络中路由器的类别( 是否具有多播功能) 等。这些信息的收集是由路由协议来完成的。这一部分介绍几个实际应用中的多 播路由协议，其中d v r m p 和m o s p f 是i n t e m e t 上的点到点路由协议g i p ( 路由选择 信息协议) 与o s p f ( 开放式最短路径优先) 派生出来的 2 5 1 距离矢量多播路由协议 d v m r p 采用广播和剪除的方法来为每个多播源建立一个基于源的树。它采用 路由信息协议( r i p ) 的变量来发现到源的最短路由。每个多播树在组员退出和加入 组时剪除和加入树枝来进行动态维护。d v m r p 共有七种包的类型：p r o b e , r e p o r t , p r u n e , g r a r ，g r a f ta c k n o w l e d g e m e n t , a s kn e i g h b o r s 2 ，n e i g h b o r s 2 。所有包的目 的地址都是2 2 4 0 0 4 ，这个地址时保留的“所有d v m r p 路由器”地址。d v m r p 有多个版本，最新版为第三版，也是目前在用的版本。d v m r p 路由器启动时第一 个步骤就是用p r o b e 包发现邻居，每一个p r o b e 包都含有信息：一组描述发起路由器 d v m r p 能力的标志；一个声称d ，用于检测邻居状态的变化；一组发起路由器收 到p r o b 咆的邻居地址。这个包的t t l ( 生存时间) 为l ，这样包只能扩散到相邻的路 由器上。当一个d v m r p 路由器收到一个p r o b e g 时，它记录下这个发起路由器的地址 和收到这个包的端口，这样，它知道了直连路由器的地址。当这个路由器发出自 己的p r o b e g 时，将列出所有它所获得的邻居地址。当一个路由器看到它自己的口 地址在邻居发出的p r o b e 包中时，它就知道它与邻居建立了双向通信。发现邻居后， 路由器继续发送p r o b e g 来保持联系。p r o b e 包定期发送以维持邻接路由的有效性。 d v m r p 采用广播和剪除的方法建立多播树，这种路由协议一定要保存剪除状态， 如果路由器重启，它不知道是否发出和收到7 剪除信息。如果等待下一次常规更 新，则重新建立多播包的前转可能会很慢。为此，加入了生成d 的设计，一旦路 由器重启，它的生成d 就会改变，邻居通过收到的p r o b e 邑检测到这个变化时，就 会刷新这个路由器发出的所有剪除状态，也会立即向这个邻居发送自己的路由表。 多播数据因为清除了剪除信息，所以会重新流到这台路由器上。d v m r p 采用了r i p 的许多变量来对外告知路由表和直连的予网，路由通过r q o r t 消息发送到 2 2 4 0 04 路由更新定期发送，但如果发现了一个新的路由器时，路由表马上通过 单播送到新的路由器处。如果没有下游邻居，且叶网络中也没有组员，那么路由 北京交通大学硬士论文 器向上游路由器发送一个p r u n e 消息，上游路由器收到消息后停止向相应端口前转 多播流量。上游路由器还保存了这个地址和生成i d 的剪除状态，时限为p r u n e 消息 的存活时间这一参数，过了这个时限，继续向该端口前转数据。如果，被剪除的 路由器向重新接入树中，那么必须向上游路由器发送g r a f t 消息，这个消息向上游 一跳一跳的传送，直到建立一条多播树的树枝为止。上游路由器收到消息后，会 应答一个g r a f ta c k n o w l e d g e m e n t 消息，如果下游邻居没有收到，则会重发g | 瓣消 息。a s kn e i g h b o r s 2 和n e i g h b o r s 2 消息用于查询和响应某个目标路由器的网络情况， 包括各个端口的地址及d v m r p 参数、邻居地址。主要用于捧错。 2 5 2 多播开放最短路径优先协议 m o s p f 是利用点到点的链路状态数据库，以o s p f 为基础的多播路由协议，由 于o s p f 应用o i j k s t r a 算法进行路由选择，因此每个节点都要保存全网的拓扑信息， 所有节点对网络的看法一致，它不需发送任何分组，节点就可根据全网；链路状 态表计算组中每个信源的多播树，而且各节点对此树的看法一致。为了减少计算 量，m o s p f 可以按需执行算法，即只有当一个节点收到一个信源关于某个多播组 的第一个分组时，才执行算法。这种做法的缺点是对第一个分组带来较大延时 m o s p f 的最大优点是享有o s p f 对网络拓扑的变动快速反应能力。然而这个能力是 以对路由器c p u 资源的巨大消耗为基础的，而且随着网络中组数量的增加。这种 消耗也在迅速增加。 2 5 3 核心树( c b t ) c b t 是一个与协议无关的稀疏模式的共享树协议。c b t 可以用下层的任何路由 协议来发现源和其他c b t 路由器，并建立自己的树。除了提高了灵活性，也减小 了开销。c b r 树根植于一个核一i c b t 路由器，而非源网络。这个核心可被放置在网 络的任何位置。当前有三个版本的c b t ，c b t v l 己经作废，c b t v 3 正在提出c b t 采用了9 种消息类型：j o i nr e q u e s t ，j o i na c k ，e c h or e q u e s t ， e c h o _ r e p l y q u i t _ n o t i f i c a t i o n ，f l u s h _ t r e e ，b o o t s t r a p ，c a n d i d a t ec o r e a d v e r t i s e m e n t ，h e l l o 。c b t 采用自举机制来产生核心，使用y b o o t s t r a p 和 c a n d i d a t ec o r ea d v e r t i s