梅创社

（陕西工业职业技术学院 陕西 咸阳 712000）

网络路由[1]包括两个方面的任务:一方面是收集网络状态信息并力求保持最新；另一方面，在获取状态信息的基础上，为连接请求找到满足某种要求的网络路径。目前所用到的大多数路由算法，不管是单播路由算法还是多播路由算法，都要求网络中的每个节点维护着整个网络的状态信息。然而，由于网络流量负载的快速变化，使得网络中的节点所获取的状态信息变得不及时和不精确，即动态网络中的状态信息存在着固有的非精确性。

随着Internet中多媒体业务与实时业务快速发展，QOS多播路由问题在网络研究领域己经得到了越来越多的重视和关注。多播路由及其QOS扩展的主要目标是要构造一棵满足某些性能约束（例如，端到端的延迟有界、延迟抖动有界、最小可用带宽以及最大包丢失率等）并对某个目标函数（例如，能反应网络资源利用的网络代价）进行优化的多播树。

传统的多播路由协议，例如DVMRP和PIM，主要为“尽力而为”的数据流设计，其多播树的构造主要是基于网络拓扑的连接性，并且不带有QOS约束。但最近却出现了一些带QOS约束的多播路由算法，这些算法通常运用一个启发式的方案来化解带约束的Steiner树（例如，延迟受限的最小代价树）这类NP一完全问题。然而，这些算法在计算路由时，通常需要用到全局的网络状态信息，而且也没有能够很好地处理多播组成员的动态加入和退出，消息交换的负载也很大，因此，它们中的多数在Internet中并不实用。

1 网络模型

1.1 路由模型

设一加权有向连通图 G=（V，E）表示整个通信网络[2]，其中V是网络中节点的集合，E是全双工有向链路的集合，V和E分别表示网络中的节点数和链路数。不失一般性，只考虑简单图（即每对节点之间最多只能有一条链路的网络）。

假设 s（s∈V为一多播树的源节点，M（M⊆c{V-{s}}）为该多播树的目的节点集，R+为正实数集。对于任何一条链路e（e∈E），定义链路状态信息（或称为链路的QOS特征值）为:带宽函数 bw（e）:E→R+，延迟函数 delay（e）:E→R+，代价函数cost（e）:E→R+。 类似地，对于任一节点 n∈V ，定义节点状态信息（或称为节点的QOS特征值）为:延迟函数delay（n）:V→R+。 用 T（s，M}表示一棵多播树。

如前所述，尽管目前有一些分布式的QOS多播路由算法在路由计算时只使用了较为精确的局部（或本地）的状态信息，但它们都是以单播源路由算法作为其路由计算的基础，因此，同样会不可避免地涉及到状态信息的非精确性问题。

这里同样采用概率分布的方式来描述状态信息的非精确性，即希望找到最大可能地满足连接请求对服务性能的要求并具有最小网络代价的路由路径。在全部的QOS度量中，例如，端到端的延迟、延迟抖动、最小可用带宽、最大包丢失率以及网络代价等，由于最小链路带宽和端到端的延迟最具代表性，其它的特征值往往受到这两个特征值的影响和制约，而网络代价通常仅作为优化的目标，同时为了使问题的模型简化，因此这里仅考虑带宽和延迟这两个QOS特征值。

假设B和D分别为多播树T（s，硒中所有路径的最小剩余带宽和最大延迟约束，P*为源节点与某个目的节点t之间全部路径中的最佳路径，那么有带宽和延迟保证的多播路由问题可以表示[3]为:

1.2 非精确状态模型

网络节点在进行路由计算时必然要用到网络状态信息（包括本地的和远程的状态信息），本地的状态信息通常时及时的、精确的，而远程状态信息往往又是不及时和不精确的。同时，远程的状态信息被路由协议按照一定的频率或者机制进行更新，状态更新越频繁，状态信息就越精确，但是，过于频繁的更新会增加网络中的消息负载，反而会降低状态信息的精确性。状态信息[4]包括:1）网络拓扑的连接性；2）链路状态信息，包括链路的剩余带宽、传输延迟和代价；3）节点状态信息，包括节点中的队列延迟以及节点的代价。

在这些状态信息中，链路剩余带宽和节点中队列延迟的变化最为频繁，由此而产生的不精确性也最为显著。由于链路剩余带宽和节点中队列延迟最具代表性，为了使问题简化，这里仅考虑这两种状态信息的不精确性。这种简化对路由性能的影响不会太明显，主要有以下几点原因:

1）网络的拓扑结构经常改变，但它的变化频率要远远低于QOS特征值（如带宽、延迟等）的变化频率；

2）链路的传输延迟由链路的欧几里得长度来决定，其变化量极小，可以忽略；

3）在所有的QOS度量中，网络代价与其它的QOS特征值不同，它通常不作为一个QOS约束，而是作为一个目标函数进行优化，因此，网络代价的非精确性可以被忽略。

2 QMRI算法描述

2.1 基本思想

我们所提出的路由算法工作在某些单播路由协议 （例如，距离向量协议）的上层，需要这些单播路由协议为我们的算法执行某些预计算。与其它的QOS多播路由算法不同，由QMRI构造的多播树不仅能够满足带宽和延迟的要求，而且能够最大可能地满足带宽和延迟的要求，且具有最优（或近优）的整体代价。我们的算法是一种基于交通灯（（Traffic Lights，TL）的路由算法，它能够在两种工作模式下并行地探索多条可行的路由路径，并通过观察控制报文的颜色来决定路由。这种路由机制与交通灯控制道路交通的原理类似。

QMRI[5]所用到的主要控制报文定义如下:

1）加入请求报文（Join-Req）

Join-Req是一种加入请求的探测报文，它由准备加入多播会话的节点发向该多播会话的源节点，该报文不仅能沿路累计可加性的QOS度量（如延迟、延迟抖动、代价等），还可以记录链路带宽等凹性状态参数的最小值；

2）绿色确认报文（Reply-G）

Reply-G是一种接受确认报文，它由接受加入请求的多播源节点发向准备加入的新成员（这里的成员指的是成员节点，为了描述方便，我们经常混用成员和成员节点的概念，其实，它们的含义并不相同），这就意味着某条路径完全满足带宽和延迟的要求，该路径称为可行路径；

3）黄色预警报文（Reply-Y）

Reply-Y是一种预警报文，它由某个上游节点发向准备加入多播会话的新成员节点，这意味着某条路径只能部分满足带宽和延迟的要求，这种路径称为可能可行路径；

4）红色拒绝报文（Reply-R）

Reply-R是一种拒绝报文，它由某个拒绝加入的上游节点发向准备加入多播会话的节点，这就意味着某条路径根本不能满足带宽和延迟的要求，这种路径称为不可行路径。

在多播会话进行的过程中，其组成员应该能够动态地加入/退出该多播会话，而且组成员的加入/退出不能对正在进行的多播会话产生干扰。为此，采取渐进生成多播树的方式以实现多播会话各个状态之间的无缝迁移[6]。另外，当一个多播成员欲退出多播会话时，它应沿着多播树枝向树上的分叉节点发送一退出报文，分叉节点在接收到退出报文后，将释放相应的网络资源，多播树其它的部分保持不变。

2.2 资源预留

在加入请求报文最终到达了源节点并通过了合法性检查之后，连接初始化和资源预留过程开始启动。这时，资源预留报文Resv由源节点，加上时间戳T，之后发向新成员t，并沿着加入请求报文in-Req经过的路径反向进行资源预留。当Resv到达某个中间节点（例如k，且k目前还不是多播树上的节点）时，如果节点k有可供预留的资源，就为该多播会话预留资源并继续前递Resv，否则它将沿着Resv和Join-Req经过的路径向s和t分别反向发送一预留撤消报文Resv-Und，通知它们资源预留过程失败，并沿路撤消己经预留的资源。

2.3 退出过程

当成员节点t要求退出多播会话时，如果r是多播树的叶子节点，则向其上游节点发送一剪枝报文Prune，Prune被传送至树叉节点后，树又节点将删除关于t的路由信息并释放相关的网络资源，多播树其余的部分保持不变；否则，不需要作处理。从上述过程可以看出，在我们的算法中，中间节点能够执行一个分布式的路由计算，因此QMRI是一个分布式的多播路由算法，具有分布式路由算法的优点，但它仅适用于平面网络或层次网络的域内工作环境。

3 正确性与复杂性

3.1 正确性

下面几个非形式化的定理可以证明QMRI算法的正确性。

定理1在QMRI算法的UR工作模式下，如果有一条路径满足带宽和延迟约束，那么，这条路径是一条新成员节点连向多播树的可行性路径，并且也是最优的路径。此时，算法只需要探索这条单一的路径。证明如前所述，满足带宽与延迟约束的路径的值等于可行性路径，又因为UR模式使用了以网络代价作为优化目标的链路状态协议，因此，这条可行性路径也是一条最优（代价最小）的路径，算法只需要探索这条路径。此定理得证口

定理2在TL工作模式下，如果存在一条最优或次优的路径，那么，QMRI就能够找到它。 证明在TL模式下，QMRI以分叉路由的方式启动，分叉节点向多个直接上游节点发送多条探测报文，因此，多条可行的或者可能可性的路径能

够被探测到。多条Reply-G或Reply-Y消息被回送给分叉节点，相应的代价或概率值能够被比较。在多条可行或者可能可性的路径中，如果某条路径的代价最小或者概率值最小，那么，这条路径就是最优或次优的路径。

定理3 QMRI所探测的可行或者可能可行的路径不存在环路。证明在QMRI算法中，多播路由表的条目包括一个数据包入口和多个出口，因此，加入多播会话的成员节点将形成一个树状结构，QMRI所探测的可行性路径或者可能可行的路径也会形成一个树形结构，从而不存在环路。此定理得证口

定理4如果存在一条可行或者可能可行的路径，那么，QMRI能够发现它。

证明在QMRI算法中，路径探测过程以UR模式启动，根据定理1，如果被探测的路径满足带宽与延迟约束，那么该路径即为可行且最优的路径。当这种条件不成立的情况下，也就是当某个节点收到了Reply-Y或Reply-R消息的时候，QMRI就从UR模式切换到TL模式。在这种情况下，该节点将分别沿着多条路径向源节点发送多条Join-Req信息，用于对各条可能路径的探索。在这些分支路径中，如果存在可行或者可能可行的路径，那么，它们定能被发现。因此，使用UR和TL两种工作模式，QMRI一定能发现那些可行或者可能可行的路径。

3.2 复杂性

构造一棵多播树的计算复杂性和所需要的消息数量是影响QOS多播路由算法复杂性的两个主要因素。

如果采取按需路由的计算方式，那么，QMRI的计算复杂性仅仅依赖于QOS单播路由协议。目前，带2个QOS度量约束（带宽和延迟约束）的启发式QOS单播路由算法的计算复杂度为 O（|V||E|）。这里的|V|为网络中的节点数，|V|为链路数。对于大多数网络，|E|=O|V|，因此，QOS单播路由算法的计算复杂度为O（|V|2）。对于有|M|个成员的多播组，其计算代价应为|V|2|M|，因此，QMRI的计算复杂度为 O（|V|2|M|）。

对于消息交换，QMRI主要处理4种类型的消息:Join-Req，Reply-G，Reply-Y和Reply-R。然而，在计算过程的每一步，QMRI最多只处理3种消息。这就意味着对于一个有|M|个成员的多播组，需要处理的消息数应该为3|M|。在被接受或被拒绝之前，Join-Req消息所经过的跳数至多为|E|，因此，在多个成员节点的加入过程中，需要处理的消息数最多为3|ME|。 由此可见，QMRI的消息复杂度应为 O（3|ME|）。

4 结束语

提出一种基于交通灯的分布式QOS多播路由算法一QMRI，该算法能有效地工作在状态信息不精确的动态网络中。大量的仿真实验显示了我们的路由算法具有较高的路由成功率和适度的消息负载[7]，而且生成的多播树具有很低的网络代价。最为重要的是，QMRI能够高度适应网络状态信息的非精确性。

[1]张宝贤，刘越，陈常嘉.QOS路由的多路径算法[J].电子学报 ，2000（7）：55-57.

ZHANG Bao-xian，LIU Yue，CHEN Chang-jia.QOS routing path algorithm[J].Chinese Journal of Electronics，2000（7）:55-57.

[2]李腊元，李春林.动态QOS多播路由协议[J].电子学报，2003（9）：23-24.

LI La-yuan，LI Chun-lin.Dynamic QOS multicast routing protocol[J].Chinese Journal of electronics，2003（9）：23-24.

[3]顾军华，侯向丹，宋洁，等.基于蚂蚁算法的QOS组播路由问题求解[J].河北工业大学学报，2002（4）：52-54.

GU Jun-hua，HOU Xiang-dan，SONG Jie，et al.Based on Ant Algorithm for solving QOS multicast routing problem[J].Journal of Hebei University of Technology，2002（4）:52-54.

[4]陆慧梅，向勇，史美林.支持QOS的层次组播路由算法框架QHMR[J].计算机学报，2004（6）：56-57.

LU Hui-mei，XIANG Yong，SHIMei-lin.QOS support hierarchical multicast routing algorithm framework of QHMR[J].Chinese Journal of Computers，2004（6）:56-57.

[5]王征应，石冰心.基于启发式遗传算法的QOS组播路由问题求解[J].计算机学报，2001（1）：65-68.

WANG Zheng-ying，SHI Bing-xin.Based on heuristic genetic algorithm for solving QOS multicast routing problem[J].Chinese Journal of Computers，2001（1）:65-68.

[6]闵应骅.计算机网络路由研究综述[J].计算机学报，2003（6）：41-42.

MIN Ying-hua.Survey on computer network routing[J].Chinese Journal of Computers，2003（6）:41-42.

[7]雷擎，王行刚.计算机网络模拟方法与工具[J].通信学报，2001（9）：78-82.

LEI Qing，WANG Hang-gang.The computer network simulation methodologies and tools[J].Journal of communication，2001（9）:78-82.