（计算机软件与理论专业论文）面向移动主机的组播研究.pdf

面向移动主机的组播研究 摘要 q 着无线通信技术、计算机网络技术的发展，组播技术日益成为 研究的热点问题。目前国内外都已经广泛开展了对组播技术的研究， 并有些成熟的技术已经开始在很多地区推广使用。无线组播技术也 得到了很大的发展，提出了很多很有建设性的组播路由协议。这些工 作促进了组播技术和无线网络的应用步文介绍了组播地址，组播的 组管理，主要组播路由算法，现有的固定网络和移动网络中的主要组 播路由协议。然后着重介绍了基于主动网络的一种新的移动组播协议 a n b m o m ，与其它组播协议相比，这种协议在处理主机移动时， 端到端的延迟比较稳定，路由效率高，可以优化，更加可靠，而且具 有很好的伸展性。咚文针对a n b m o m 进行了一些仿真测试，测试结 果是令人满意的，证明了a n b m o m 在处理移动组播上有很好的效率 和灵活性。斗 【关键词】： 组播，d v m r p ，c b t ，p i m ，a n b m o m ? r b m o m a b s t r a c t w i t ht h ed e v e l o p m e n to fw i r e l e s sc o m m u n i c a t i o nt e c h n o l o g i e sa n d c o m p u t e rn e t w o r k s ，m u l t i c a s ti sb e c o m i n go n eo f t h eh o tr e s e a r c ht o p i c s t i l ln o w , s o m em a t u r em u l t i c a s tt e c h n o l o g i e sh a v eb e e np u tf o r w a r di n m a n yf i e l d sa n dm o b i l em u l t i c a s ta l s oh a sg a i n e dh u g ed e v e l o p m e n t ，w i t h m a n yc o n s t r u c t i v em o b i l em u l t i c a s tp r o t o c o l sr a i s e d i nt h i sp a p e r , w e p r e s e n tt h ek n o w l e d g ec o n c e m e dw i t hm u l t i c a s ta d d r e s s ，i g m p , m u l t i c a s t r o u t i n ga l g o r i t h m s ，a n ds o m em a i nm u l t i c a s tp r o t o c o l si nb o t hf i x e d n e t w o r ka n dm o b i l en e t w o r k a f t e rt h a t , w ee m p h a s i z eo ni n t r o d u c i n ga n e wm o b i l em u l t i c a s tp r o t o c o l - - a n b m o m ，a p r o t o c o lb a s e d0 na c t i v e n e t w o r k s c o m p a r e dw i t ho t h e rm o b i l em u l t i c a s tp r o t o c o l s ，i to w n s 。o m p a m t i v e l ys t a b l ee n d t o e n d l a t e n c y , h i g hr o u t i n ge f f i c i e n c y , g o o d f l e x i b i l i t y ，c o m p a r a t i v e l yb e t t e rr e l i a b i l i t ya n d d a nb eo p t i m i z e do n d e m a n d a l s ow em a k es o m et e s t sw i t ht h i sp r o t o c o l ，a n dt h er e s u i t s a r e s a t i s f y i n g ，w h i c hp r o v e si t sb r i g h tf u t u r e 【k e yw o r d s ： m u l t i c a s t ，d v m r p ，c b t ，p i m ，a n b m o m ，r b m o m 2 1 1 研究的意义 第1 章引言 组播是一种一对多的网络传播方式，在组播成员中共享信息。随着网络 技术的发展和普及，组播的地位越来越重要，它在节省网络资源( 尤其是数据量 较大时，比如传输视频、音频、图像时) ，协调小组( 比如视频会议等应用) 工 作方面有着不可取代的优势。目前，在i n t e m e t 和i n t r a n e t 上使用组播的应用越 来越多，企业内部使用组播应用软件进行网络会议，证券信息供应商利用组播为 注册会员提供证券信息等，这些应用使得网络充分体现了群体性、分布性和协作 性方面的合作性能。 但是传统的组播协议，比如d v m r p i 】，m o s p f 2 】，p i m 3 等协议，都缺 省的认为参与组播的主机是静态的。目前，移动电话，p d a 等移动设备的迅速 普及要求组播协议能适应移动网络的发展需求。本文就是面对这问题而展开研 究的。到目前为止，移动组播还没有一个统一的解决方案。移动组员意味组的动 态管理以及组成员位置的动态变化，如何能较好的实现这两点是一个挑战。 一般说来，移动网络可以分为三类，一种是类似手机的网络，移动用户经过 一跳( h o p ) 与基站相连，而基站之间是通过有线网络互连的。第二种是类似a dh o c 的网络，移动用户可能经过多跳相连，而且通常不经过有线网络。第三种是指网 络本身是移动的，比如飞机本身是移动的，把其内部的网络看成一个抽象的整体 进行研究。本文研究的对象是第一种，也就是说，移动主机是经过有线网络进行 通信的。 目前已经提出的移动组播协议中，切换问题是一个很大的问题，移动主机离 开一个网络进入另一个网络后，必须重新向源主机发送加入请求，或者使用 m o b i l ei p 与h a 重新进行绑定。只有这样才能继续加入组播会话，而在这段时 间内可能丢失组播包或者切换完成后接收到重复的组擐包。另外，虽然使用 m o b i l ei p 与h a 重新进行绑定这种方式比较安全以及对整棵树的更改很小，但 是却会造成通道拥塞问题和三角路由问题。这些问题都不是我们希望的。 主动网络 4 】是一种新兴的网络，与传统网络相比，它因为可以充分利用中间 节点的计算处理能力而具有明显的灵活性。本文提出的a n b m o m 就是基于主动 网络的，它在处理上述问题时都有更好的方法，可以避免三角路由问题和通道拥 塞问题，同时使得切换造成的延迟尽可能的小。最后，还为组播的可靠传输提出 了方案，尽嚣避免丢包和重复现象的发生。 1 面向移动主机的组播研究 当然，由于主动网络的应用范围还很有限，很多领域的研究还处于试验阶段 因此本文提出的算法还只是建设性的，需要随着主动网络的普及而发展。 1 2 本文的安排 本文系统地论述了组播管理，组播路由算法的知识，并介绍了一些已经规 范的由组播算法演变而来的组播路由协议。由于这些协议都假设组员和源是固定 的，因此本文讨论了当移动主机参与组播时可能出现的问题，以及几种可能的解 决方法。并在前人提出的移动组播协议的基础上提出了基于主动网络的移动组播 协议a n b m o m ，讨论了它的组播树构造，对移动主机迁移的处理算法。最 后通过在模拟环境下进行的实验，对它的性能进行分析。具体内容如下： 第一章为引言，介绍了研究的意义和本文的安排。 第二章为组播知识的介绍，包括组播地址、组播的应用领域。然后介绍了 组播路由算法，这些算法是i p 组播的理论依据和基础，接下来介绍了现在已有 的一些组播路由协议，这些协议在设计时由于没有考虑到移动的问题，因此在引 进移动主机后，会出现一些问题。 第三章为移动组播的介绍。首先讨论了当引入移动对象后，组播可能会出 现的问题，如包丢失等，然后在移动模型的基础上讨论了几种可能的解决办法， 比如使用h a 作为中间节点。在本章中还针对移动组播的特殊性，改进了 i g m p 5 。然后介绍了当前i e t fm o b i l ei p 6 给出的两种解决方案：b i h a 7 和 g s 7 】。接下来为了解决通道拥塞问题引入d m s p 8 ，该协议称为m o m 8 协议， 是以b i h a 为原型的。 第四章为r b m o m 模型的介绍，该模型是b i h a 和r s 两种方式的一般化， 因为引用了范围参数r 9 】和m h a ，因而具有相当的灵活性，可以根据组成员分 布情况和移动成员的移动频率，调整r 实现较好的性能。 第五章为a n b m o m 协议的介绍、实验设计和性能分析。该协议基于主动 网络，对处理迁移问题有很好的解决方案。而且该协议本身使用的树虽然属于源 根树，但是对系统资源的要求与共享树一样，具有很好的伸展性，并且可以动态 进行优化，是移动组播的一种很好的解决方案。 第六章为结论和工作展望，讨论了a n b m o m 的不足之处和可以改进的方 面，介绍了移动组播领域相关的研究，并对全文做了总结。 2 塑塑堡垫兰! ! 竺塑塑! ! 塑 一 第2 章组播、组播管理与路由技术 2 1 什么是组播 2 1 1 组播的概念 一种把通讯方式归类的方法就是按照信息或数据报接收者的数目分类： 单播( u u i c a s t ) ：把数据包只发送给一个接收者 任意播( a n y c a s t ) 【1 0 ：把数据包发送给一群接收者中的一个 组播( m u l t i c a s t ) ：把数据包发送给一组接收者 广播( b r o a d c a s t ) ：把数据包发送给所有接收者 传统方式有一对一的单播，和一对多的广播。这两种方式的折衷方式是组播， 它支持那些数据或控制分配在多个主机的操作，比如对多个重复的数据库的更新 等。 i p v 4 中有单播，组播和广播，组播是单播和广播的一般形式或者说折衷方式， 把一条消息或数据流发给选定的由多个接收者构成的一个集合。而在i p v 6 中有 单播，任意播和组播，提倡尽可能用组播代替广播，更加强调了组播的重要性。 最开始的时候i p 界通常把接收者看成为一个主机或者一个路由器，但现在把接 收者看作是主机或路由器的一个端口则会使问题更加清晰。 在i p 网络( 数据报网络) 中，组播可以通过几种不同的方式实现：多次单 播，数据报中使用多个地址，或专用的组播地址。而第三种，也就是专用的组播 地址是i p 协议中最通用的组播实现模型所采用的方式。 多次单疆( m u l t i p l eu n i c a s t ) 这种方式通常会浪费网络带宽，因为即使接收者中的几个甚至全部都有相同 的路由，或使用相同的连接，也要为每个接收者单独发一次数据报。在这种方法 中，发送者必须清楚的知道每个接收者的身份( 地址) 。这通常并不是组播应用 服务希望提供的的性质，因为这样就需要一个注册机制，每个接收者都得向发送 者注册。同时这也给发送方带来了负担。 数据报使甬多个遗址 这种方法不会像多重单播一样浪费那么多的网路带宽，因为对所有的接收者 只会有一个数据报的实例发送出去。在一个数据报中，列出了所有的接收者，至 少这些接收者的部分会共享某些连接。然而在这种方法中存在一个与i p 网络相 关的问题，那就是i p 包有一个字节数的上限6 5 5 3 5 字节。这个界限是由i p 包中 包长度字段只有1 6 位决定的。在很多实际使用的网络中，最大容量可能会更小， 比如在以太网中，上限只有1 5 0 0 字节，而在i e e e8 0 2 3 中，上限只有1 4 9 2 字 节。这个问题就限制了一个数据报中可以列出的接收方的数量。因此这种方法只 是部分的解决了前一种方法中提到的浪费带宽的问题。另外，当数据报携带多个 目标地址时，路由器处理时要比只携带一个目标地址复杂得多。 组播她址 在这种方式中，发送方无需知道接收方的细节问题，因此这种方式给发送方 带来的资源负担最小。同时，由于发送方不知道接收方的具体身份或地址，我们 就必须在i p 层上方使用不面向连接的传输协议u d p 。如何节省网络带宽的 问题留给路由器来处理。对这些组播地址如何进行路由的问题就从单播路由中独 立出来，成为一个独立的研究课题。使用好的路由算法和路由协议，可以很好的 避免或减少带宽浪费问题。在这种方法中，接收方需要一个协议，另外还需要能 处理组播的路由器来决定对于某个组播地址哪些主机或路由器需要它们的组播 数据报。现在这个协议是i g m p 协议。组播地址的形式也将会在下面进行介绍。 使用组播的一个基本的出发点是通过共享来节省资源：不是分别把信息发向 每一个接收者，而是利用一些共同的连接来做到只发送一次。我们可以把组播的 路由想象为一棵树，发送者是根，每个接收者是一片叶子，在树分叉的节点上， 网络节点( 路由器) 进行复制继续沿着树发送。对于同一个组，可能有很多不同 的树，我们可以通过一定的算法设计树，从而最大程度利用共享连接，减少资源 浪费。另外，在发送者这个节点上已经节省了很多资源，因为它只需要传送数据 一次。 2 1 2 组播技术的构成元素 组播可以分为局域网络上的组播( n a t i v em u l t i c a s t ) 8 0 广域网络上的组播两种。 不同的组播范围，对端节点和网络有不同的要求。 为了支持局域网络上的组播，发送节点和接收端节点以及位于这两个节点之 间的网络构架( 包括中间的路由器节点) 必须是支持组播的。其中对于端节点的 要求如下： 面向移动主目l 的l n 捕_ f i i f 究 函2 1 组疆的构成元素 首先，要在t c p i p 协议栈中支持i p 组播传输和接收操作 其次，要有相应软件支持i g m p 协议，从而支持处理加入组播组请求以 及接收组播数据的操作 。再次，对于从i p 组播地址映射过来的m a c 地址，网卡可以有效的识别 过滤 最后，应该有i p 组播的应用软件，比如视频会议等 对于局域网络上的组播，以上就够了，不涉及到路由器的操作。若扩展到广 域网络上，情况就不同了，还需要以下要素： 。所有位于发送者和接收者之间的路由器必须支持i p 的组播。很多新的路 由器都是支持组播的，但比较旧的路由器需要升级。 堕塑堡塑兰! ! 塑坐堡塑丝一 防火墙可能需要进行重新设置，以支持组播。 图2 1 表示了组播的构成元素。其中的箭头表示的是组播数据报的流动方向。 图中并没有表示出涉及到组播管理和路由的传输。 这里还要提到i p 通道【l l 】技术。并不是所有的网络都支持组播，如果两个组 播网络中间被一个不支持组播的网络隔离开来，i p 通道可以把这两个网络连接 起来。利用封装技术，组播数据报采用通常的点到点的单播方式传送。这一技术 在组播骨干网上被广泛使用。 另外还要提到组播路由器和组播交换机的概念。组播路由器在广域网上使 用，支持组播路由。而组播交换机可以在局域网上起到优化组播数据传送的作用。 如果局域网络上没有组播交换机时，组播数据报会以扩散法( f l o o d i n g ) 的方式发给 所有本地主机。如果有了组播交换机，它可以自动进行组播过滤，使组播数据报 只发给那些参与本组组播会话的节点。见图2 t 2 。 2 1 3 组播的主要应用 在今天的现实生活中我们利用桌上的电脑实现了很多应用：观看n a s a 宇宙 飞船发射的现场转播或者观看世界另一端某个摇滚乐队的现场演出；在办公室中 参加某个视频会议；与同事问虽然身处异地却用同一个白板来讨论问题。所有这 些都是现在互联网上的最新最普及的应用，同时这些应用也都对带宽和服务质量 都有较高的要求。 现在对这些应用，组播是唯一一个可以节省或高效使用带宽的解决方案。这 6 塑塑竺苎圭! 堂! 坐堡坐! i一 在i p v 6 中要比现在仍在使用的i p v 4 中来得更加重要，因为随着这些应用的普及， 组会变得更大。理想情况下，组播路由可以通过动念调整发送者和接收者之阳j 路 径的方式来节省带宽，比方c 兑，它会在计算路径时考虑要求的服务质量和可以提 供的服务质量。下面列举了组播的几个主要应用： 网络收音机和两络电视 现在工作站和个人电脑都有一定的音频和视频功能，网络带宽和连接程度也 增长很快，因此把多媒体的传输引入计算机网络也成为一个很自然的发展趋势。 与通常的无线电收音机和电视机网络相比，i p 网络有一个很重要的差别，那 就是i p 网络是一个由路由器连接起来的网络。在无线电收音机和电视机网络罩， 使用广播束发送信号是一个很好的方式，因为有足够的带宽来为不同信息分配不 同的频道。而在i p 网络中就不一样了，不同的信息共享同一个通道，因此需要 使用组播来节省网络资源。 群徉 在个工作组范围内使用e m a i l 通讯是一个简单的群件技术，但它不是实时 通讯。通过组播实时文本，对于当前网络资源来说，音频或视频会议也成为可能 的应用。与网络收音机和网络电视相e b ，群件的通讯不仅是从一个发送者发向一 群接收者，还是在某些组成员或全部组成员之间进行通信。电子白板是另一个群 件应用的例子。 资源发掘 一个主机需要在网络中定位一个服务器，但是它并不知道这个服务器的名字 或地址，它只能通过广播来请求这服务。一个例子就是b o o t p 服务。一个需 要启动的主机通过局部广播的方式从一个b o o t p 服务器请求启动需要的内容，这 个服务器通过链路层地址识别出这个主机。这个工作过程由于采用了广播，因此 在该区域内刁i 能提供所请求服务的主机上引起了不必要的处理过程。这时如果采 用组播的方式，把请求只发送给特定的组播地址，这样不能提供该服务的主机就 忽略该请求，这样就大大节省了资源，省却了很多不必要的处理过程。 2 2 组播地址 组播地j ：| f = n ：i p v 4 和i p v 6 中都有明确的定义。 面向移动主机的组播研究 2 2 1l p v 4 在i p v 4 中组播地址以d 类地址来标识。d 类地址的最高4 位是“1 1 1 0 ”，因 此在以通常的点对表示时，组播地址的范围是从2 2 4 0 0 0 到2 3 9 2 5 5 2 5 5 2 5 5 。 如下图i p v 4 组播地址格式为： 昏2 3i p v 4 中经播地址的格式 组播地址2 2 4 0 0 0 保留未用。有些组播地址是一些永久的组地址，比如 2 2 4 0 0 1 分配给由所有直接相连的网络上的所有主机构成的组。其它还有一些著 名的永久组地址，详见r f c1 7 0 0 的“a s s i g n e dn u m b e r s ”。 一些例子如下： 2 2 4 0 0 2 子网上的所有路由器 2 2 4 0 0 9r i p 2 路由器 2 2 2l p v 6 表2 1l p v 4 一些永久组播地址的例子 i p v 6 的组播地址最高8 位是“1 1 1 1 1 1 1 1 ”，因此在以i p v 6 的1 6 进制表示时， 组播地址的范围是从f f 0 1 ：o ：o ：0 ：0 ：o ：o ：o 到f f f f ：f f f f ：f f f f ：f f f f ：f f f f ：f f f f f f f f ：f f f f 。如下图i p v 6 组播地址格式为： j 坐!l 堡坠l 兰匦l ! ! ! 亟 ：二 1 1 1 1 1 1 1 1 i 标志位l 范围 g r o u p l d 图2 4i p v 6 申组播地址的格式 标志字段中的最低位说明该组播地址是否是i a n a 分配的永久地址。如果是 0 ，就是永久地址，否则就不是。范围字段给出了组播组的范围( 本地节点，本地 连接，本地站点，本组织，或全局范围) 。与i p v 4 中一样，在i p v 6 中组播地址 也不可以作为数据报的源地址，不可以出现在路由头部。 一些 p v 6 的永久地址 1 2 】的例子如下： 面向移动主机的组播研究 f f 01 ：0 ：o ：o ：o ：0 ：0 ：1 所有节点 f f 0 2 ：o ：o ：o ：0 ：0 ：0 ：l 所有节点 f f 0 1 ：o ：o ：0 ：0 ：0 ：0 ：2 所有路由器 f f 0 2 ：o ：o ：o ：0 ：o ：0 ：2 所有路由器 f f 0 2 ：o ：0 ：o ：0 ：0 ：0 ：c d h c p 服务器中转代理 f f 0 2 ：o ：o ：o ：o ：1 ：x x x x ：x x x x 被请求的节点地址 表2 2i p v 6 一些永久地址的饲子 2 3 互联网组播管理协议( i g m p ) 为加入跨越物理网络的组播传送，主机必须事先通知本地组播网关关于自己 加入某组播组的的信息，该信息叫做组员身份信息。然后，各组播网关之间再互 相交换各自的组信息，以建立组播传送路径。组播网关与参与组播传送的主机之 间交换组员信息的协议叫作“互联网组播管理协议”( i n t e r n e tg r o u pm a n a g e m e n t p r o t o c 0 1 ) ，简称i g m p 。 类似于i c m p ，i g m p 利用i p 数据包传送报文，反过来又为i p 软件提供服务。 i g m p 是i p 协议的一部分，而不是一个独立的协议。同时，i g m p 也是t c p i p 不可缺少的一个标准协议，所有参与2 级i p 组播传送的机器都必须包含i g m p 软件。 i g m p 工作过程分为两个阶段。第一阶段，某主机加入一个新的组播组时， 按“全主机”组播地址将组员身份传播出去。本地组播网关收到该信息后，方 图2 5 局域网内i 铺p 信息的传送 面向移动主机的组捅研究 面将此信息记录在相应表格中，一方面向互联网上的其它组播网关通告此组员身 份信息，以建立必要的路径。第二阶段，为适应组员身份的动态变化，本地组播 网关周期性地查询本地主机，以确定哪些主机仍然属于哪些组播组。假如查询结 果表明某组播组中已无本地主机成员，组播网关一方面将停止通告相应地组员身 份信息，同时不再接收相应的组播数据包。示意图见图2 5 。 i g m p 实现 当本地网上的组播网关发出组员身份查询报文后，本地网上所有参与组播传 送的主机都将报告自己的组员身份。假如某主机参加了n 个组播组，它必须发送 n 个组员身份报文。也就是说，一旦组播网关发起组员身份调查，本地网上有可 能立即出现大量响应报文，甚至可能导致网络拥塞。 因此，如何避免拥塞和不必要的主机开销，是i g m p 要特别加以考虑的问题。 为此，i g m p 采取三条措施。首先，i 佃报文传送均采用基于“全主机”地址 ( 2 2 4 0 0 1 ) 的方式，使网上不参与组播传送的主机收不到任何i g m p 报文。这样， 一方面避免了无关主机因接收和处理i g m p 报文而付出的额外开销，另一方面又 可能减少i g m p 报文在本地网上的延迟时间( 比如在令牌环中，在无关主机上就 没有1 比特延迟) ，从而提高网络吞吐率，有利于避免拥塞。第二，组播网关一 次查询只发出一个i g m p 报文，这个报文针对所有可能的组播组。这样就比针对 每一个可能的组播组都发送一次i g m p 查询效率高得多。假如本地网主机参加大 量的组播组，因此将节省数量可观的的网络带宽和主机机时。第三，参加组播组 的主机一次发送关于一个组播组的报文，若参加n 个组播组，则发送n 个报文。 主机发送多个i g m p 报文时，不是同时发出，而是每隔0 到1 0 秒之间的以随机 时间发送一个。这样减少了大量i g m p 报文涌入网络的可能性，减少了拥塞机会。 第四，主机收听来自其它主机的i g m p 响应报文时，假如发现已有别的主机报告 某组播组的组员身份，本机就不再发送关于该组的报文。这也是减少网络中报文 数的一种手段。 主机为何可以不报告自己的组员身份呢? 原因在于组播网关的工作方式。对 于本网主机参加的组播组，组播网关不需要一一记录其组员状况，只需要知道本 网络中是否有某组播组的成员。假如有，它就将这一信息广播到其它组播网关， 并接收发往相应组播组的数据报。组播数据报到达组播网关后，再利用硬件组播 能力被传播到本地网络上，由本地网络各主机自己判断是否接收。因此，网关根 本没有必要知道本网上有哪些主机属于哪个组播组，它只需要知道本网络有主机 属于某组播组就行了。基于上述原则，便有了上述第四点避免i g m p 报文拥塞网 络的方法。最小延迟主机首先通告自己属于某组播组后，组播网关便已获取了足 够的信息，其余同组的主机便不必再作出同样的响应了。 以上讨论是基于硬件支持组播传送的假设。假如不支持，网络只能用广播方 式传送组播数据报。这种情况下，组播网关了解组播组组员情况将是有用的。例 如，某组播组在本网络上只有一个成员，则显然不必利用广播方式，端到端传送 是最好的。在一些硬件不支持组播传输的点到点网络上，甚至进行r 1 次端到端传 送的效率可能还比进行一次广播传送的效率高。遗憾的是，为了简便，i g m p 并 没有考虑这些情况。 组员状态表 在参加组播组的主机中，i g m p 软件维护一个表格，每一表目对应于一个组播 组。初始化的时候，各表目均为空。当某应用程序宣布加入一个新的组播组时， i g m p 为之分配个表目，登记上相应信息，并在其中的计数域赋初始值1 。然 后，每当有新的应用程序加入该组播组，计数域加一；每当有应用程序退出该组 播组，计数域减一。当计数域减至0 时，表明主机不再属于该组播组，主机不再 参加该组播组的操作。 i g m p 掇文格式 04 81 6 3 l 氆2 6i g m p 报天格式 i g m p 报文有两种类型，一种是i g m p 查询报文( 类型为“1 ”) ，由组播网关 发出；一种是i g m p 响应报文( 类型为“2 ”) ，由参加组播传送的主机发出。两 种报文格式相同，只是前者的“组地址”域取值为0 ，如图z 彳所示。 另外，当前i o m p “版本”域取值为“l ”。 i g m p 响应报文的特点是不给出主机信息，所以，假如有若干主机参加同一 组播组，它们给出的响应报文完全相同，除第一个外，其余都是不必要的。 生存期t t l 组播数据报使用i p 报头的t t l 字段作为范围常数，用来限制一个i p 组播数 据报可以扩散的范围，也就是跳数( h o p ) 。组播数据报每经过一个路由器，t t l 就减一。过期的数据报( 1 v r l = 0 ) 被丢掉，并且不必向组播源发送任何出错通知。 t t l 防止了组播信息向不必要的范围( 其它不包含组播成员的网络) 传送。 组播骨干网上的几个典型t t l 如下表所示： 面向移动生 l 的组捕研究 t t l 值意义 0 局限于本主机 1 局限于本子网 1 5 局限于同一个网点( s i t e ) 6 3 局限于同一个区域( r e g i o n ) 1 2 7 广域网 1 9 l 广域网，有带宽限制 2 5 5 没有限制 袁2 3 几个典型t t l 馑 2 4 已有的组播路由算法 组播数据包是通过组播树传送到组成员节点的。建立组播树有几种算法，这 几种算法都是建立组播协议的潜在方法。在这部分，我们首先介绍两种较简单的 方法，扩散法和生成树算法。然后我们讨论较为复杂的算法，比如逆向组播树， s t 树，c b t 树。下一部分，我们将会讲述这些算法如何用于建立组播路由协议。 2 4 1 扩散； - 去( f l o o d i n g ) 扩散算法是把组播数据包传向n n n 由器的一种最简单的算法，已应用于 m o s p f 协议。在此算法中，当某路由器收到一个组播包时，它会首先检查它是第 一次收到此包还是以前已经收到过。如果是第一次，路由器会把该包向除收到此 包的端口以外的所有端口转发。否则，路由器就抛弃此包。各个路由器都这样做， 就能保证网络中的所有路由器最终都能收到这个包的至少个拷贝。 虽然扩散法非常简单，它有明显的缺点。扩散法产生数量可观的重复包，很 浪费带宽。而且，每次收到一个数据包时，每个路由器都需要判断它是否是第 一次收到这个组播包，因此，路由器要为每个最近收到的组播包建立并维护个 条目，这样，扩散算法就使用了相当多的路由器内存资源。 2 4 2 扩展树算法( s p a n n i n gt r e e ) 塑塑壁塑圭! ! 堕型堡竺! ! ? 、一 c 】墼! 以b 为源生成的扩展树 一种优于扩散法的算法是扩展树算法。这种算法非常有效，而且易于实现， 已经用于i e e e 一8 0 2m a c 桥。在这种算法中，互联网的一个子集被选出构成一棵 树，使得在任意两个路由器之间只有一条有效路径。这棵树可以扩展到因特网上 的所有节点，所以这种算法被称为扩展树算法。当一个路由器收到一个组播包时， 它会把该包向除出该包到达的路径以外的扩展树的所有树枝转发。显然，在扩展 树算法中，每个路由器需要为每个网络接口维护一个布尔变量，表示该连接是否 属于这棵扩展树。这里用一个由五个节点、六个连接构成的一个小网络来表示不 同的树。为简单起见，我们不对路由器与主机，连接与子网进行区分。同时假定， 连接都是对称的，代价在连接旁标明。图2 8 是以b 为源的扩展树。 扩展树算法有两个缺点。首先，网络连接的一个很小的子集( 也就是覆盖扩 展树覆盖的连接上) 负载过大；其次，扩展树不考虑组播成员资格。 2 4 3 逆向组播算法( i r p i v l ) 逆囱广播算法( r p b ) 蔓| ：2 9 也上a 为源，钍) b 树 图2 1 0 必c 为源生成自懈树 r p b 算法是 b j j 。展树算法进行改进后得到的算法，现在乖用于组播主于网 面向移动主机的组插研究 ( m b o n e ) 上。扩展树算法建立一棵覆盖整个网络的树，而r p b 算法则为每一 个源建立一个潜在的扩展树。每个路由器从连接l 上接收到一个来自源s 的组 播包时，该路由器都会查看连接l 是否在到s 的最短路经上。如果是，将该包 向除l 以外的所有连接转发。否则，丢弃该包。图2 9 和图2 1 0 显示了以实验 网中两个节点为源建立的2 棵组播树。 如果本地路由器不在从源节点到一个邻居节点的最短路径上，数据包将会在 该邻节点上被抛弃。在这个事实基础上，可以很容易的改进i 冲b 算法，因为这 样就可以不向邻节点转发包。以上信息在链路状态路由协议中很容易获得。在距 离向量路由协议中，邻节点可以在路由更新信息中带上通向源的上一跳的地址来 实现。 这个算法有效且容易实现。而且，由于包是通过从源到目标节点的最短路径 转发，所以很快。r p b 算法不需要任何机制来停止转发过程。路由器也没有必 要了解整个扩展树，因为有很多而不是唯一一棵扩展树，包可以通过不同扩展树 传送。与扩展树算法不同，网络流量分布在多棵树上，网络得到了更有效的利用。 然而，r p b 算法也有一个很大的缺点，在建立树的时候，它没有考虑组播成员 资格的问题。 t r p b ( 剪枝逆向| 广攘) t r p b 算法克服了一些在r p b 算法中的局限性。使用i g m p 协议时，路由器 可以判断在路由器所在的子网上是否有某个组的成员存在。如果这个子网是叶子 子网( 即没有其他路由器与它相连) ，并且没有组成员存在，该路由器可以对扩 展树进行剪枝处理。另外需要特别指出的是，与r p b 相似，t r p b 在本地路由 器不在从源节点到一个邻居节点的最短路径上时，也不向邻节点转发包。 虽然，在t r p b 算法中利用了组播成员资格这信息，从而子网可以进行剪 枝，但是t r p b 并不能把没有组成员的非叶子子网剪掉以去除不必要的流量。这 是t r p b 的一个缺点。 逆向路径组搔葬法( 砒m ) r p m 算法( 也称为带有剪枝的r p b 算法) 是在r p b 和t r p b 基础上的改进。 r p m 也建立一棵传播树，这棵树仅仅覆盖两种元素，其一是含有组播成员的子 网，其二是位于从源通向含有组播成员的子网最短路径上的路由器和子网。r p m 可以进行剪枝，使得组播包在通向目标组成员的连接上被转发。 对于给定的( 源，组) 对，第一个组播数据包按照t r p b 算法发送。在t r p b 树中没有下游路由器的路由器被称为叶子路由器。如果一个叶子路由器收到某 面向移动主机的组播研究 ( 源，组) 对的组播包，而在其所在子网上没有属于垓组的成员，它就会向它的 父亲路由器( 即把该组播包发送给它的路由器) 发送p r u n e 信息。这个信息表 示属于这个特定的( 源，组) 的组播包不应该再向收到p r u n e 信息的链路上转 发。这里要强调的是，p r u n e 信息只向回路上传送一个h o p 的距离。而收到该 信息的上游路由器必须在它的内存中记录这个信息，这样当再收到如上述属于该 ( 源，组) 的组播包时，就不会继续向下转发了。另一方面，如果t r p b 树中某 个上游路由器收到来自所有子节点的p r u n e 信息，这意味着该路由器所处网络 范围内没有需要接收属于该( 源，组) 数据的组成员，因此该路由器就会向它自 己的上游路由器发送p r u n e 信息，表示属于这个特定的( 源，组) 的组播包不 应该再向该路由器转发。以此类推，层叠递推的p r u n e 信息沿着t p r b 树发送， 使得组播数据只发往含有组播成员的链路。为了说明网络中经过p r u n e 信息传 递后获得的树，我们需要用一棵更为复杂的树来阐释。图2 1 l 是剪枝过程以及 最后获得的r p m 树。 图2 1 i 剪枝以及结果得到的r 蹦树( 也可以理解为部分r p k l 错) 组员资格和网络拓扑结构都可以动态改变，组播树的修剪状态信息也应该定 期更新。因此，在r p m 算法中路由器中的剪技信息会周期性的删除，删除后发 送的下一个发往( 源，组) 的组播包会转发到每一个叶子路由器。这是r p m 算 法的第一个缺点。另外一个缺点是为了维护所有( 源，组) 的状态信息，需要相 当的内存空间，这使得这种算法缺乏伸展性，因此，不适用于大规模的因特网或 者组员很多的组的情况。 面向移动主机的组播研究 2 4 4s t e i n e r 树 在r p b 算法系列( r p b ，t r p b 和r p m ) 中，组播包通过源节点和目的节 图2 1 2 以c 为源生成的r p b 树 图2 1 3 以c 为源生成的s t 树 点之间的最短路径发送，确保组播数据能够尽快传送。然而，以上算法对如何最 少使用网络资源却都没有任何建树。图2 1 2 中叙述了r p b 树，同时也说明了在 假定c 是源，a ，e 是组员的情况下数据传播路径。 从图2 1 2 和2 1 3 中我们可以很容易地看出第二棵树使用的网络连接较少。 虽然，这棵树比r p b 树慢( 因为在通向e 时需要经历三跳，而在r p b 树中需要 经过2 跳) ，它却使用了较少的网络连接。这种树称为s t e i n e r 树。虽然s t e r n e r 树建立树使用了最少的连接，但计算该树时的复杂度却使得这种算法实用性甚 小。当有节点加入或离开组时，s t e i n e r 树都需要被重新计算，因此这种树不 具备稳定性。 田 亩曲由 图2 i1 4c b t 柱 以及数据流向 路由器 组播包流向 核心路由器 2 4 5c l a t 树 最新提出的的建立组播树的算法是c b t ( c o r e b a s e dt r e e ) 。与以前讨论过 的其他算法不同，c b t 为每个组只建立一棵组播树。换句话说，对于一个特定 的组，用于转发组播数据包的树是唯一的，与源节点的位置无关。某一个路由器， 或路由器的集合，成为这棵传播树的核心( c o r e ) 。所有属于这一特定组的数 据，都先以单播的方式发往核心路由器。当遇到属于这棵树的路由器( 包括核心 路由器) 时，该数据包会向除进入端口以外的所有其余端口发送。见图21 4 。 因为c b t 为每一个组播组只建立一棵树，所以与其它算法相比，它要求组 播路由器存储的信息相对较少。在带宽上也是如此，它不会对组播包进行整个网 络范围的扩散，因而，比较节省带宽。但这种算法也有它的缺点，它可能造成网 络负载过于集中而在核心路出器周围形成瓶颈。另一方面，只使用一棵树，也可 能使路径非最优，从而延迟数据包的传递。 这部分讨论的算法可以用于建立组播路由协议。每一种算法都有胜于其他算 法的优点和缺点，使得它们在有的情况下比较有效，而在其他情况下不是很有效。 接下来我们会讨论组播路由协议。 2 5 组播路由协议 m i p ( m u l t i c a s ti p ) 网络是网络层( 第三层) 组播路由网络。路由器采用各 种成熟算法来决定从源节点到各端节点的最佳路径。从原理上或者晓从概念上来 晚，主要的组播肌议采用以下两种技术： 1 以源节点为似的树( s o u r c e r o o t e dt r e e s ，简称s r t ) 技术：当采用s r t 类型 协议时，这株讨连接源节点和组播组中的各成员。s r t 链路建立路径来连接 源节点，f f l i , i ；, i1 i 。一旦为源节点及其成员建立了s r t ，组播组内所有的流量 都通过这个s m 、求传递。d v m r p 和m o s p f 协议都采用这种技术。著名的 m b o n c 试蟛? 州采川的是d v m r p 协议。 2 公用树( s h a r e dr f e e s ，简称s t ) 技术：s t 技术在网络连接较少、组播成员 较分散的i l l m ii - 他 j 。s t 在源和端节点间建立个r p ( r e n d e z v o u sp o i n t ) 节点，f k zj 戍7 , 1 协山( c o r e ) 路由器。该路由器用一个公用树的路径来转发组 播数扒 l 土州弁爿1 捕成员。一般来说，在个组播组中只有一个公用树。c br 算法剐i ，i 、i s | j ! n 乐川这种技术。 支持川拼j ：门：| x 搽通过i g m p 来获取成员信息，_ | f _ j 1 1 i x b i | ! m i y z ：) j ， j 面向移动主机的组插研究 的构建组播路由。 2 5 1 密集模式组播路由( d e n s e m o d em u l t i c a s tr o u t i n g ) i p 组播路由按照组播成员在网络上分布的密度情况不同可以分为密集模式 组播路由和稀疏模式组播路由。密集模式组播路由假定组播成员在网络中是密集 分布的，并且弼络带宽也是足够的，比如说网络上几乎所有主机都是组播成员的 这种情况。所谓的密集模式路由协议主要是通过周期性地扩散法进行组播传递来 建立和维护扩展树( s p a n n i n gt r e e ) 。距离向量组播路由协议( d i s t a n c ev e c t o r m u l t i c a s tr o u t i n gp r o t o c o l ，简称d v m r p ) ，链路状态组播协议( m u l t i c a s to p e n s h o r t e s tp a t hf i r s t ，简称m o s p f ) 以及密集模式与协议无关组播 ( p r o t o c 0 1 i n d e p e n d e n tm u l t i e a s t d e n s em o d e ，简称p i m d m ，将在下一节介绍) 都属于这种协议。 2 5 1 1 链接状态组播协议( m o s p f ) m o s p f 在r f c1 5 8 4 有明确定义，是建立在o s p f ( 第二版，参见r f c 1 5 8 3 1 5 ，) 基础上的。在o s p f 中，每个路由器监听所有与它直接相连的链路的 状态，当状态发生变化时它就发送一个更新消息给所有相邻路由器。由于每个路 由器都能接收到所有足够的信息，以此来重建整个网络的拓扑结构，它就能够通 过d i j k s t r a 算法来计算出以它自己为根的可以到达所有可能目标的最小路径扩展 树。对于要转发的每个数据包，路由器利用这棵树来决定最佳的下一跳的位置。 m o s p f 利用i g m p 收集的组员信息和o s p f 的连接状态信息数据库建立组播树。 这些树按照最短路径建立，对每个( 源，组) 对都有一棵树。虽然m o s p f 不支 持隧道技术，但是它可以和其他非m o s p f 的路由器兼容。 m o s p f 支持层次路由。因特网上的所有主机被分成若干自治区域 ( a u t o n o m o u s s y s t e m s ，简称a s 1 3 ) 。每个a s 又进一步被分为若干个子区域( 称 为a r e a ) 。接下来会详细介绍m o s p f 如何在3 个层次上实现组播路由。 区域内部路由( i n t r a - a r e ar o u t i n g ) o s p f 本身是一个链接状态路由协议，允许一个a s 分割成若干个区域。每 个路由器上都有o s p f 连接状态数据库，提供了本区域内的整个路由图。为了实 现对组播的扩展，引入一个组员连接广播信息( g r o u p m e m b e r s h i dl i n ks t a t e a d v e r t i