浅谈IP组播路由算法

杭州职业技术学院信息工程学院 吴功才 冯 霞 杨乃如

1 前言

计算机在网络中传送IP分组信息主要通过单播、组播、广播三种方式。近几年来，随着网络及信息共享的普及，网络组播技术的应用越来越广泛，不断赋予了Int er net网络一些新的应用，如网络音频/视频的广播或直播、网络视频会议、远程会诊、多媒体远程教育等，本文就浅谈一下IP组播路由算法。

2 组播简介

单播是在发送者和接收者之间实现点对点数据通信的方式；组播指的是同时把数据分组发送给网络中的一组主机，实现一对多发送分组信息；广播则实现了向子网内全部的节点广播数据包。与广播相比，组播只有相关的路由器和部分主机参与组播信息的发送和接收，而广播则只能很死板的将分组信息发送到全部的主机（可能部分主机根本不想接收此分组信息）。在组播中，最理想的情况是发送方只需发送每个分组一次，而每条物理链路上也最多只有一个分组通过该分组信息。而在单播中要实现一对多发送分组信息的目的，则必须将同一个分组复制多方并多次发送。示意图如图1所示。

3 组播路由算法

组播的最终目标是：实现从发送节点到网络中的一组（而不是全部）接收节点发送分组信息。如图1所示，在组播应用中，通常发送节点（S）和接收节点（R1、R2）都是确定的。组播路由算法主要功能就是根据网络拓扑结构以及链路状态，在满足约束条件的前提下确定发送节点（S）通过哪些中间节点（如：R0、R3等）将分组信息转发到接收节点（R1、R2）。组播路由算法的最终运算结果为：在网络拓扑结构中建立一棵组播树，通过该组播树发送节点可以沿着树的分支并行的将分组信息传送到各接收节点，分组信息只在树的分支处进行复制，从而使复制的份数尽可能的少。

3.1 静态算法和动态算法

按照是否允许网络成员随时加入或离开组播组，组播路由算法可以分为静态路由算法和动态路由算法。静态组播路由算法针对初始的组播组成员构造一棵组播树，它认为网络的拓扑和状态信息是固定不变的，不适应网络状态的动态变化。动态组播路由算法则在网络的状态发生变化时（成员加入或者离开时），能够对组播树的结构进行一定的调整及时的更新组播树。

3.2 Steiner树算法和CBT算法

在数据结构的理论中有一个称作为最小生成树的数据模型，其定义为：在一给定的无向图G=(V,E)中，(u,v)代表连接顶点u与顶点v的边，而w(u,v)代表此边的权重，若存在T=(V,E1）的无循环图，其中E1为E的子集，使得的w(T) 最小，则此T为G的最小生成树。最小生成树的应用非常广泛，最典型的应用就是解决如何在n个城市之间铺设光缆以便可以相互通信，并且铺设的费用又最节省的问题。

在构造组播路由算法时，一般用组播树的费用来衡量组播树的好坏，组播树的费用是指树中所有链路费用的总和。这里，费用是一个广义的概念，可以代表链路上的时延，链路的造价，带宽等[1]。在组播网络中，建立一棵以发送节点为根，覆盖所有接收节点的最小生成树的问题，在数学上归结为St einer树问题。也就是说St einer树其实就是在在组播网络中建立的一棵最小生成树，这棵树的节点包括组播发送节点、接收节点以及中间的分组转发节点。实现建立St einer树的算法有很多，如：KMB算法、MPH算法、ADH算法等。

CBT算法是近年来才提出的一种构造组播树的新方法，最早于1993年由Bal l ar die提出[2]，其基本思想是选定一个中心作为根，其他的组成员则按照最短路由的原则与此中心相连接，从而构成一棵由所有发送节点共享的树。

St einer树算法和CBT算法主要区别：1）St einer树算法的根节点肯定是发送节点，而CBT算法是选定一个中心作为根。2）St einer树其实就是一棵最小生成树，而CBT算法构建的树则并非一定是最小生成树。下面两图表示的是a为发送节点，b、c、d、e、f、g、h为接收节点构成的组播网络，图2为St ei ner树，图3为以c节点为中心构建的CBT算法树。

图2 Steiner树

图3 CBT算法树

3.3 集中式和分布式算法

按其实现的方式的不同， 组播路由算法还可以分为集中式算法和分布式算法。集中式路由算法是在节点掌握了整个网络的拓扑结构后，才确定的组播路由。它的缺点是容易导致拥塞，产生延时。而分布式组播路由计算则由发送节点和接收的节点间的网络节点分布计算组成，不需要所有组成员都知道网络的拓扑，每个组成员只利用局部信息就可以确定路由。它的优点是算法简单并且只需部分节点参与路由算法的计算。

3.4 有约束和无约束的算法

按照是否有QoS约束，组播路由算法可以分为无约束和有约束的组播路由算法[3]。无约束组播路由算法通常应用于非实时网络中，此种网络对组播分组信息的时延、正确率等均不做特殊的要求。有约束的组播路由算法则通常应用在实时网络等，对分组信息的时延、分组信息的逻辑顺序等有一定的要求。

4 结论

尽管目前组播网络存在连接成功率、路由优化片面、部署困难等问题，但由于组播技术具有“一次发送，多点传输”[4]，同时又具有节省带宽及分组通信的优点，因此组播技术在计算机网络有着十分广泛的应用。相信组播的应用会越来越广泛，组播路由算法也会有更深入的研究。

[1]田捷.组播路由算法研究[D].武汉理工大学,2004.

[2]王慧.时延受限组播路由算法的研究[D].重庆大学,2014.

[3]邹德莉.QoS组播路由关键算法研究[D].大连理工大学,2006.

[4]葛连升,江林,秦丰林.QoS组播路由算法研究综述[J].山东大学学报(理学版),2010(01).