基于多项服务质量的组播路由算法

    摘 要： 多点组播是指一个源点传送信息到多个目的节点，它是网络支持多媒体业务的关键技术之一。以服务质量（QoS）指标中的带宽和时延为优化选路准则，提出了一种受限的组播路由算法，仿真结果证明了该算法的有效性。

    关键词： 网络 组播 路由

    通信网络在进入90年代后，向着综合业务的方向发展。在传统的数据网络中，路由所需考虑的仅是可连接性[1]，路由算法在寻找最优（短）路径时采用单一的指标，如跳数或时延。新出现的多媒体通信带来了多点组播的需求，即未来的计算机网络应该能够提供例如电视会议、视频点播等具有点对多点的业务要求。而这种网络应该支持范围广泛的服务质量（QoS）需求，确定路由需要相当复杂的模型来描述网络，即路由的优化指标要包括时延、带宽、丢失率等。

    近年来，各国学者开始在这方面探索，提出了一些快速有效的算法。如：基于最短路径的Dijkstra算法[2]，即计算源点到各目的点的最短路径；另一类是求最小网络代价（NC）的应用斯坦利（Steiner）树路由算法[3]，即计算组播树（Multicast tree)，使其在任意一对源和目的节点之间都存在通路，并使其代价（cost）最小。

    本文使用改进的受限Steiner树路由算法，构造树型路由结构来实现多点通信（Multicast或MC)。这是由于基于树实现有效ＭＣ路由具有以下两个优点：（１）分组以并行方式沿着树枝发送到不同的信宿；（２）网络中需要传送的复制分组最小，而且分组的复制只是在树叉处进行。在QoS的参数中，本文选取最小化占用链路总带宽和满足端到端的时延限制为优化准则。

    １ 受限组播路由的算法

    １．１ 网络模型

    一个网络可以表示为图G（V，E）；其中Ｖ是顶点的集合，包括ｎ个顶点；Ｅ是边的集合，包括ｍ条边。每条边ｅ∈E具有两个参数：C（e）和D（e），C（e）是边e上的正实数代价函数，D（e）是e上的正整数时延函数。在给定信源Ｓ和信宿集合Ｄ条件下，给定允许延迟极限Δ，构造根为Ｓ，覆盖所有信宿节点的受限Steiner树，满足条件，树上路径（i，j）的延迟小于Δ，即：如果P（i,j）是树上从i到j的路径，那么对D满足：

    １．２ 算法实现机理

    由于网络中的Steiner问题属于图论中的ＮＰ完备问题[4]，即，一般地说，最优算法无法在多项式时间内完成。因此，用启发式算法可降低算法难度，而在性能上逼近理论算法。由于构造最小生成树（MST）相对简单，因此常用的是MST启发式算法。

    本文通过改进Prim算法[2]来求解MST问题。Prim算法的基本思想为：假定G＝（V，E）是连通图，T是G上MST中边的集合。算法从U＝{S}（S为源点），T＝Φ开始，重复执行下列操作：在所有u∈Uｖ∈{V－U}的边（u,v)∈E中找一条权值最小的边（u0,v0)并入集合Ｔ，同时u0并入U，直到U＝V为止，则T为G的MST。

    改进算法的基本思想是：首先利用Dijkstra第k最短路径算法，计算从源节点到目的节点以时延为优化准则的路径，并将所求的路径中最大的时延与Δ比较，若该值比Δ大则表明限制条件太苛刻，可令Δ等于该值。然后以cost最小为首要优化目标，用Prim算法求出图G的MST树。用Prim算法每生成一条边（i,j）时，就计算由Ｓ到该边的累计时延,若≤Δ，则用Prim算法继续寻找下一条边。否则令该边对应的cost(i,j)为∞，并且将j(i∈U,j∈{V－U}仍保留在原来集合中。当用Prim算法完成一次全局搜索后，再对那些仍保留在Ｖ－Ｕ集合中的点重新进行全局搜索（除开前次让cost(i,j)为∞的ｉ点外），寻找符合时延条件的新边。当U中已包含全部组播目标节点Di后，算法结束。

    １．３ 算法的实现过程

    可采用一个整型二维数组a[MAX][3]来表示在构造最小生成树U，{V－U}和权值cost的变化。其中数组的第一列a[][0]放生成树的顶点集合U中的各顶点，初始值为源点s；第二列a[][1]放顶点集合{V－U}中的各顶点；第三列a[][2]放{V－U}到U所构成的边的最小权值。同时，采用二维数组mat[MAX][MAX]来存储图的邻接矩阵，矩阵（i,j）对应的值就是边（i,j）上的cost值。开始对a[MAX][3]的初始化可表示为：

a[i][0]=1；

if(i＝＝1)

a[i][1]＝0；

else

a[i][1]＝i;

a[i][2]＝mat[1][i];

    然后按前面所述的改进Prim算法来搜索MST。具体实现过程可以用C语言编程实现。其流程图如图1所示。这里设Δ是合理的时延限制值，且整个网络有n个节点。

    ２ 仿真及实验结果

    采用文章中提出的算法在图2所示结构的网络（设为无向图）上进行仿真（其中节点1为源点S，节点4、5、6、7、8、9、10为目的节点）设Δ＝20和15时均能得到建立在受限Steiner最小树上的组播路由。结果如图3和图4所示。

    本文提出的算法兼顾了满足时延限制和代价最小两个QoS要求，仿真结果也证明了该算法在力求代介最小的前提下，能根据组播应用时延的限制要求，快速有效地构造组播树，有较强的实时性。