在互联网中计算一个最小生成树的简单快速分布式算法

在互联网中计算一个最小生成树的简单快速分布式算法

摘要

广域网中一个核心问题是有效的多播一条消息到目标组的所有成员。一种最有效的多播一条消息的方法是沿着连接组的所有成员的生成树的边发送消息。本文中，我们提出一种新的全分布式算法来在一般的通讯网络中构造一棵最小生成树（MST）。在执行过程中，算法维系着一个跨所有组成员的不相交的树集。每棵树最初只由一个节点构成，每棵树独立的通过连接最近的树进行扩充，直到所有节点都被连接到单棵树中。所得到的通讯拓扑是健壮的（不会有单点遭受失败）和可伸缩的（每个结点存储有限数量的本地信息，这些信息与网络的大小无关）

1、引言

处理在通讯网络中构造一棵生成树的问题通常和在广域网中设计一种有效的多播算法相关。多播操作所要求的全部带宽是其效率的一个主要度量指标。使用一棵树来路由多播消息的目的是减少消息传播过程中所需要的消息数量。

通常，有一些广域网的应用（比如，计算机支持的会议，互联网音频和视频多播等等）利用居于整个网络中的代理来进行信息共享，并且这些应用属于不相交的逻辑组。这些应用必须考虑如何有效的将信息传播给相同组的所有成员的问题。不同的应用展示了不同的流量模式和通信量需求。这包括首要的目标是优化带宽消耗（通过减少多播递送方案所产生的消息数），但同时必须考虑最小化传输时延和／或通讯链路上所招致的传输成本。在以时延作为边的权值时，一棵最优的多播递送树是指树中所有边的权值之和最小的树。在一个给定的组中，应该使用一棵最优的多播递送树来路由消息。相对于流量的带宽要求来说链路的容量有限时，还可以把容量约束加入到要考虑的问题中来。

本文描述了在把一个一般的通讯网络建模为一个连通图，考虑把相邻节点之间的传输时延作为度量（metric）时计算最小生成树（MST）的一种分布式算法。构造MST是基于这样的假设：节点可以测定发送到一个邻节点的消息的往返时间。算法利用Bollobos的思想：在执行的整个过程中，维持着一个跨初始图中所有节点的不相交的树集（森林），森林中的树通过最小权值的边合并来扩充，直到所有的节点都被连接到单棵树中，该树就是最终的MST。

尽管没有考虑到流量特征和容量约束，但使用其他度量来作为边的权值也是直接的：我们假定预期流量的带宽要求小于链路带宽。然而，流量要求可以被认为是一个特定组的特征，在一个组管理算法的执行过程中，MST将可以重新配置以考虑在有多个具有高带宽要求的组播出现时链路容量有限的情况。

本文的剩余部分组织如下，第2节描述了MST的一般算法，第3节给出了算法的细节：初始化阶段，构造阶段，一个实例和算法消息的复杂度分析。第4节简要的讨论并给出了我们算法实现的测量结果。第5节是一个相关工作的最近调查。最后，第6节我们陈述了我们的结论并列出了对我们工作的一些延伸。

图1一般的MST算法

2、一般的MST算法

假定G＝（V，E）表示一个无向连通图，这里V代表顶点集，E代表边集。然后，假定E 中的每条边关联了一个权值并且没有两个权值是相等的。构造一个MST的一般算法见图1。算法从创建｜V｜个不同的子图开始，每个子图包含一个顶点，接着，每个子图独立的选择具有最小权值的边（该边把他和另外一个子图连接起来），然后与该边现关联的两个子图沿着这条边连接起来。步骤4－6重复直到所有的顶点都被连接起来。

为了证明这个算法的正确性，我们需要证明在构造的过程中没有环出现并且所得到的图正是MST。

引理1图1所描述的算法不会产生环。

证明开始时，每个子图只包含一个顶点因而没有环。

对于步骤3－4假定不存在子图T i包含环，其次，假定一个由子图T i1,T i2,…T ik构成的子集同时选择连接边（也就是，T i1选择e i1，T i2选择e i2,…,T ik选择e ik）使得产生了一个包含T i1,T i2,…T ik中节点的环。因为每个子图T ij（1≤j≤k）只选择一条边，并且要在包含T i1,T i2,…T ik中的节点中创建一个环必须至少要有k条边，很明显所有的e ij必须是不同的，也就是说，没有两个子图选择了相同的边。为简单起见，不妨设e i1连接着T i1到T i2，e i2连接着T i2到T i3,…,e ik连接着T ik到T i1（否则，我们可以轻易的为子图和边重新编号）。因为没有两条边具有相同的权值，这隐含着e i1

这样，最后连接图G中所有顶点的子图是生成树。

进而由Bollobas[5]，我们有以下结论：

定理1由图1中所描述的算法构造的生成树是图G的一棵MST，并且所得到的MST是唯一的。

3、通讯网络中的MST算法

我们把通讯网络建模为一个无向连接图G=（V，E）。这里节点集V代表工作站（或处理器）集，边集E代表虚连接子集。如果两台工作站（节点）之间存在一条可以交换消息的通讯路径，那么我们说这两台工作站是虚连接的。对每条路径，我们关联一个由两个端节点之间的往返时间（RTT）所构成的权值。

MST算法分为两个阶段：初始化阶段和构造阶段。初始化阶段为图中的每一条边计算往返时间RTT并确保所有的权值都是唯一的。构造阶段实现图1中所给出的一般算法。以下两节给出这两个阶段的细节。

3.1初始化阶段

为简化起见，我们假定MST是作为一个外部请求的结果而被构造起来的，并且图中的任何节点一次不能接收一个以上的请求，也就是说，MST的构造起始于一单个节点，该节点被称为MST启动者。在这个阶段，每个节点管理以下的数据结构：

adj_list-包含所有邻节点的标识；

rtt_list-包含由到每个邻节点的RTT和计算该RTT的节点标识所组成的值对；

MST算法的初始化阶段见图2。首先，启动者节点发送一条START_MST消息到其自身，接着包括启动者在内的所有节点执行相同的代码。当节点在第一次收到START_MST消息时，则该节点将消息转发给除发送者节点之外的所有邻节点（在其adj_list列表中的所有节点），并开始计算到每一个具有更小标识的邻节点的RTT。使用这种方式，每条边的权值只被计算一次，也就是由其具有更大标识的端节点来计算。一旦某条边的RTT被计算出来之后，它就会和计算它的节点一起被利用一条RTT_MST消息插入到两个端节点的

rtt_list中。所有相关联的边的权值都被计算出来之后，节点启动算法的第二阶段。

为确保在边的权值之间保持全序关系，我们定义在rtt_list中任意两元素之间有以下关系：

(RTT i,n i)<(RTT j,n j)≡((RTT i

图2：MST算法的初始化阶段

3.2MST构造阶段

这个阶段实现MST一般算法（见图1）。首先，算法创建一个不连接的树集，每棵树包含一个节点（图1，步骤1-2）。每棵树用其节点的标识来标记（这里，我们假定每个节点都有唯一的标识）。接着，每个节点独立的搜索具有最小权值的边（被称为最小桥），该边将其和另外一棵树连接起来（图1，步骤4-5）。如果存在这样的边，则这两棵树被连接起来，并利用这两棵树中更小的标记来标记新树（图1，步骤6）。连接之后，具有较小标记的树的树根成为新树的根。因为最开始时，每棵单节点的树是用其节点的标识来标记的，很容易看到任何新树的标记是这棵树的所有节点中最小标识，同时树根是具有最小标识的节点（因此，树的标记是其树根的标识）。该过程重复，直到所有的节点都连接起来。

为了计算树的最小桥，我们使用称为COMPUTE的消息。这个消息包含两个域：

●label-树的标记（该消息是在哪棵树中进行传递的？）；

●min_bridge_wt-用于计算最小桥的权值；

除此之外，每个节点还要管理以下数据结构：

●label-节点所属树的标记；

●cand_mst_heap-包含图G中当前节点的所有属于其它树中的邻节点的标识。

这些邻节点按照其权值升序存储。

●loc_min_bridge_wt-把当前节点和另外一棵树中的节点连接起来的最小权值

（也就是候选MST堆中的第一个结点）。若无这样的边，就把

loc_min_bridge_wt设为∞。注意最小桥的权值是该树中所有本节点权值的

最小值。

●mst_adj_list-包含属于同一棵树中的所有邻接点的标识。这样，所有在候

选MST堆中的节点机并上所有MST邻节点列表中的节点集就是图G中当前节

点的所有邻节点的集合。

最小桥的计算是基于Dijkstra和Scholten［10］提出的扩散计算模型。根发送一条COMPUTE消息，消息中的min_bridge_wt被初始化为其自己的loc_min_bridge_wt（也就是把根和另外一棵树中的某个节点连接起来的具有最小权值的边的权值）。每个节点在收到这条消息时就检查COMPUTE.min_bridge_wt是否比其自身的loc_min_bridge_wt大。如果是这种情况，它就把COMPUTE.min_bridge_wt更新为loc_min_bridge_wt，并把这条消息转发给其孩子结点。每个节点一旦收到所有孩子的应答消息之后，它就计算在所收到的消息中所有min_bridge_wt域的最小值，并把结果送回给父节点。最后，当根收到所有的应答之后，它就计算这棵树的最小桥权值。为了阐明我们的想法，一个简单的例子示于图3。

图3：最小桥权值的计算。伴随在每个节点旁边的括号里的数字是与该节点

相关联的边当中把该节点和另外一棵树中的某节点连接起来的具有最小权值

的边的权值（loc_min_bridge_wt），伴随在每条消息旁边的数字是包含在消

息中min_bridge_wt的值。

图4：MST算法

在计算最小桥的过程中，每个节点所执行的完整操作如下（详细的算法描述在图4和图5中）：

1、根把COMPUTE.min_bridge_wt域初始化为自己的loc_min_bridge_wt，把

https://www.doczj.com/doc/0910143844.html,bel域初始化为自己的标识。接着，根把消息送给其孩子结点并

等待应答；

2、每当从父节点收到一条标记和自身标记相同的COMPUTE消息时，当前节点检

查COMPUTE.min_bridge_wt是否比自身loc_min_bridge_wt大。如果是这种

情况，那么COMPUTE.min_bridge_wt被更新为loc_min_bridge_wt。之后，

该节点把消息转发给其孩子结点并等待应答。如果该节点没有任何孩子（也

就是叶子节点），则把COMPUTE消息送回给父节点。

3、如果从某个邻节点收到一条标记比自己标记小的COMPUTE消息时，当前节点

就假定发送节点是其新的父节点。因而它把自己的标记更新为

https://www.doczj.com/doc/0910143844.html,bel并继续操作2；

4、每条标记比自己的标记大的COMPUTE消息被当前节点所忽略。

5、每当从孩子结点收到所有的COMPUTE消息之后，每个节点就计算在所收到的

所有应答之中最小的min_bridge_wt，并把结果送回给其父节点。如果当前

节点是树根，它就检查所收到的min_bridge_wt是否和loc_min_bridge_wt

相等。如果是这种情况（也就是最小桥在与根相关联的某条边中），树根就

沿着最小桥把当前的树和其他的树连接起来。否则，它发出一条包含所计算

出来的min_bridge_wt值的DIFFUSE消息到其所有的孩子结点。

图5：COMPUTE消息处理（计算子阶段）

注意以上操作还执行节点的重新标记的任务。作为一个例子，考虑两棵树T i和T j刚刚被边(v ik,v jl)连接起来，这里v ik∈T i,v jl∈T j,接着，假定label(T i)≤label(Tj)。如果v jl 转发T j的COMPUTE消息到v ik,则v ik忽略该消息，因为在这种情况下，https://www.doczj.com/doc/0910143844.html,bel（＝label(T j)）要比v ik自己的标记（=(label(T i))大。相反，如果v ik转发T i的COMPUTE消息，那么v jl要把自己的标记更新为所收到的消息中的label域中的值，并把消息转发给其孩子结点（步骤3），这样，它的孩子节点依次递归执行相同的操作。这就确保了T j中的每个节点都会把自己的标记更新为T i的标记，这样就成为了T i的节点。同时，注意到当T j的根第一次收到T i的COMPUTE消息时，它就成为了发送节点的一个孩子结点并将不再为T j产生任何其它的COMPUTE消息。这样，T j成为了T i的一棵子树，这就完成了连接操作。

一旦根计算出最小桥的权值，并且这个值和loc_min_bridge_wt不相等（操作5），它就启动发送一条DIFFUSE消息到所有的孩子结点（图4），这条消息包含和COMPUTE消息相同的域：label和min_bridge_wt。Label域包含该树的标记，而min_bridge_wt域包含在前面所计算的该树的最小桥权值。每当结点收到这条消息，它就检查看是否DIFFUSE.min_bridge_wt是否和自己的loc_min_bridge_wt相等。如果相等，这就意味着最小桥在与当前节点相关联的边中。因此，当前的树就沿着该最小桥和另外一棵树进行连接。

树根送出DIFFUSE消息之后，它就为新树启动最小桥权值的计算。注意，正如我们在

前面所指出的，两棵树连接之后，仅仅具有最小标记的树根完成新的最小桥权值的计算；另外一个树根在收到一条具有更小标记的COMPUTE消息时终止，并因而成为新树的一个简单节点。

最后一个必须处理的问题是如何检测MST构造阶段的结束。很明显，一旦构造出了一棵MST之后，每个节点的cand_mst_heap列表变为空（因为所有的节点都属于相同的生成树）。因此，在MST构造好之后，最小桥的权值成为因为没有这样的桥存在了。所以很自然的，当所计算的最小桥权值成为∞时，MST的树根就检测到了算法的结束。

当向MST加入一条新的边时，由最小桥的两个端节点之一调用add_MST_edge(mst_adj_list,cand_mst_search)函数。这个函数的目的是沿着最小桥连接两棵子树。这个任务有两步来完成：首先，调用者从其cand_mst_search列表中删除与该最小桥相关联的邻节点并将其插入到mst_adj_list列表中，接着它沿着最小桥向邻节点发送一条特殊的消息。邻节点在收到这条消息后就把发送节点的标识插入到其mst_adj_list列表中，同时将其从cand_mst_search列表中删除。使用这种方式，最小桥的每个端节点都把对方的标识插入到自己的mst_adj_list列表中。注意，因为两个端节点有可能在同时试图相互连接，所以必须小心以预防在mst_adj_list列表中的重复插入。

3.3一个例子

我们使用图6中的图为例来说明我们算法的构造阶段

在算法的构造阶段的开始，每个节点假定自己就是一棵树（仅由该节点所构成）的树根并且这棵树用该节点自己的标识来标记。接着，每个节点搜索与其相关联的具有最小权值的边。在我们的例子中，节点1找到边（1，3），节点2找到边（2，3），节点3找到边（3，4）等等。此外，因为构造阶段是异步的，从例子的角度出发，我们必须选择一个字树连接的顺序。这个顺序是任意的，也就是说，读者可以选择任何顺序而不影响最终结果。

现在假定节点4是第一个执行连接（也就是边（3，4）被加入到MST中）的节点。由此，节点4在完成连接之后，就启动一个计算子阶段，首先产生一条标记label＝4（根的标识）和min_bridge_wt＝3（也就是把节点4和另外一棵树中的某个节点－在这个例子中是节点5－连接起来的一条相关联的具有最小权值的边的权值）的COMPUTE消息。因为节点3的标记要比所收到的COMPUTE消息中的标记小，故而该消息被节点3所忽略。反过来，节点3独立的选择相同的边（3，4）来和节点4进行连接。连接之后，节点3也发出一条COMPUTE消息，不过这条消息的label=3且min_bridge_wt=2.节点4收到这条消息后，就把自己的标记该为所收到的COMPUTE消息中的标记，并成为由节点3和节点4所构成的新树中的叶子节点（图6.b）。同样，很容易看到因为节点4的loc_min_bridge_wt 是3，COMPUTE消息中的min_bridge_wt域不被修改仍然保持为2。接着，因为节点4是刚刚形成的树的一个叶子节点，所以它把COMPUTE消息送回给其父节点。节点3（它也是树的根）一旦收到这条消息，就发现min_bridge_wt的值是2因而和其loc_min_bridge_wt 相等。节点3因而判定边（2,3）就是把由节点3和节点4所构成的树和另外一棵树连接起来的具有最小权值的边，并且将该边加入到MST中。注意：在这种情况下，没有必要为了发现最小桥而发送DIFFUSE消息。

接着，考虑节点2选择边（2，3），把该边加入到MST中，并启动一个计算子阶段：向其最近的邻节点（节点3）发送一条label=2,min_bridge_weight=11的COMPUTE消息。因为节点3的标记label为3，比收到的COMPUTE消息中的label域的值小，故而把自己的标记改为2，成为新树（把节点2作为树根）的一个节点，并且把这条COMPUTE消息转发给它的所有处于MST中的邻节点，当然发送节点（也就是节点2）除外。同时，在转发该消息之前，它要把消息中的min_bridge_weight更新为它的

图6：一棵MST构造的例子。节点的标识和边的权值都是唯一的。在MST构造的

不同阶段，树根由灰色的圆来表示。每个节点的标记写在括号里。

loc_min_bridge_weight(5)。类似的，节点4在收到由节点3转发过来的消息之后，就把自己的标记改为2，把消息中的min_bridge_weight改为3，接着，由于此时节点4成为了新树的叶子节点，它就把COPUTE消息送回给节点3，再由节点3转发给树根（也就是节点2）。当树根收到这条返回来的消息时，它发现消息中的min_bridge_weight值和

loc_min_bridge_weight的值不等，因此发回一条DIFFUSE消息到其孩子结点。当节点3收到这条消息时，它检测消息中的min_bridge_weight的值是否和本节点的

loc_min_bridge_weight相等。因为不等，所以该消息被转发给节点4。最后节点4发现自己的本节点最小桥权值和所收到的消息中的本树最小桥权值相等，这样，它就选择边（4，5）把节点4所属的树和由节点5构成的树连接起来。

在例子中，我们假定节点6和节点7的连接发生在节点5和节点4的连接之前。（图

6.c.）。在以上所述的过程中，节点5和节点4连接之后，图和部分构造的MST描述在图6.d中。最后两条边（1，3）和（1，6）（图6.3和图6.f）加入到MST中时算法结束。

3.4时间复杂度分析

本节分析我们算法的时间复杂度。算法模型中假定：

1、传播时延最多为一个时间单位；

2、所有消息，无论其类型，包含O（logn）比特的信息，这里n为图中的节点数。

首先，我们导出初始化阶段的时间复杂度结果。

引理2 给定一个具有n个节点的图G，初始化阶段要花O（n）时间。

证明首先，START-MST消息最多需要n个时间单元就会被图G中所有节点接收（图G中任何一条消息最长的传播路径为n）；其次，每个节点必须计算到其所有邻居的往返时间；因为每个节点最多有n-1个邻居，计算到一个节点的往返时延需要2条消息，这个任务最多需要2（n-1）个时间单元。因此初始化任务最多需要3n-2个时间单元。

下面的三个引理决定了构建阶段的时间复杂度。

引理3 给定一个具有n个节点的图G的子树T，在T和其它另外一棵树连接起来之前，在T的节点之间最多交换O（n）条COMPUTE/DIFFUSE消息。

证明假定没有具有不同于T的标记的COMPUTE消息被树中的任何节点所接受。在最小桥权值的计算中，树中的每一条边被COMPUTE消息遍历两次：第一次是父节点把消息传给它的孩子节点，第二次是孩子节点发送的应答。因为发现最小桥最多需要n-1条DIFFUSE 消息（每边一次），这样，最多需要3（n-1）条消息就可以决定最小桥了。一旦决定了最小桥，T就可以沿着它的最小桥和其他树合并。

其次，假定Vi〈T收到一条标记比T的标记小的COMPUTE消息，因此，Vi成为发送节点的儿子并转发该条新消息。此后Vi将不再发应答消息给其在树T中的旧的父节点。因而，从树T中的至少一个节点收到收到一条标记比T的标记小的COMPUTE消息开始，任何由树T的根发起的计算子阶段都不能完成，从而树T的根将不再发出其他消息。因此，在这种情况下，我们再一次的有树T在最多3（n-1）条COMPUTE/DIFFUSE消息之后，就会和另外一棵树连接起来。

最后，如果树T中某节点收到一条标记比T的标记更大的消息时，该节点忽略掉该消息。这样，在所有情况下最多需要3（n-1）条COMPUTE/DIFFUSE消息，树T就能和图G中的另外一棵树连接起来。这证明了我们的引理3。

引理4 给定一棵具有n个节点的图G的子树T，在O（n）个时间单位之后，T完成和另外一棵树的连接。

证明因为我们假定传播时间最多为一个时间单位，在T和另外一棵树连接之前，所交换的COMPUTE/DIFFUSE相当于最多3（n-1）个时间单位。

在计算子阶段，除了COMPUTE/DIFFUSE消息之外，还有其他两种情况有消息交换。

第一：每个节点在收到一条COMPUTE消息之后，就计算与其关联边的最小权值本节点最小桥权值loc-min-bridge-weight）。注意，在上一次计算本节点最小桥权值loc-min-bridge-weight时，和该节点不在同一棵树上的邻节点在该节点的侯选mst列表

cand-mst-list中，因为有可能在此过程中，该节点的侯选mst列表cand-mst-list中的最近邻节点现在和该节点处于同一棵树中，该节点通过向邻节点发送一条查询其标记的消息来核实。如果该邻节点的标记和本节点标记不同，那么本节点最小桥权值loc-min-bridge-weight保持不变，计算过程继续。在这种情况下，对于每条COMPUTE消息，最多交换两条消息：一条是请求邻节点标记消息，另外一条是其应答消息。如果侯选mst列表cand-mst-list为空（也就是所有的邻节点都和该接点在同一棵树中），那么没有消息交换并且本节点最小桥权值loc-min-bridge-weight为∞。另一方面，如果本节点标记和该节点的侯选mst列表cand-mst-list中最近的邻节点的标记相等，这意味着这两个节点处于同一棵树中因此该邻节点从侯选mst列表cand-mst-list中删除，该过程重复下去，直

到发现了具有不同标记的邻节点或侯选mst列表cand-mst-list成为空。现在，注意到可以从侯选mst列表cand-mst-list中删除的最大邻节点数恰好是n-1，也就是树T中的节点数。因为这些删除过程可以在树T的每个节点并发执行，这相当于最多2（n-）个时间单位。

在MST计算子阶段隐含信息交换的第二种情况是当所选择的边被确实插入到MST 中时。更加确切的说，当一个节点选择了一条将要加入到MST中的边时，他会发送一条消息到相应的邻节点。由此，每个节点都把其相应的临节点插入到自己的mst临节点列表mst-adj-list中（比如当加入边（Ni，Nj）时，节点Ni把节点Nj插入到自己的mst-

adj-list，而Nj则把Ni插入到自己的mst-adj-list中）。这个任务增加了两个时间单位，因此在从树T构造完之时到它和另外一棵树完成连接之时的时间间隔最多为3（n-1）+2（n-1）+2=5n-3个时间单位，这证明了我们的引理4。

给定图G，我们定义图G的构造树（简称为CT（G））如下：

1、图G的构造树CT（G）的节点代表了在MST的构造过程中所产生的子树。

2、如果T1和T2是是在子树T的MST算法中所连接的两棵子树，那么T是T1和T2的在图G的构造树CT（G）中的父亲。

为简化起见，我们用CT（G）所代表的子树的标记来标记CT（G）的节点。图7展示了图6中例子的CT（G）。注意：CT（G）的根是G的MST。

图7：图6中例子的构造树（CT）。节点用其代表的子树的标记来标记。

引理5 给定具有n个节点的图G，构造阶段所花时间为O（n）。

证明假定T为CT（G）的根，且T1和T2为其儿子。其次再假定N1〈=N2，这里N1，N2各自代表了T1和T2中的节点个数。从引理1，T1在最多5N1-3个时间单位（从其被创建时开始）后，和T2完成连接。不妨给边（T1，T）关联一个值为5N1-3的权值。因为

N=N1+N2，很容易看到（T1，T）的权值〈=5（N/2）-3。注意：和（T1，T）相关联的权值代表了从T1创建时刻起到T创建时刻止这段时间的一个上界。

接着，我们使用相同的方法，沿着树向下递归；从当前的节点T1，我们选择代表着具有最小节点个数的子树T11的儿子，并且给边（T1，T11）关联的权值为5（N1/2）-3，这里N11是由T1所代表的子树中的节点的个数。下一步，当前节点变成T11，过程继续。结果，我们得到一条从T到叶子Tl的路径，其长度代表了从Tl进入构造阶段开始到最后一条边加入到MST（也就是T被创建之时）止这段期间的一个上界。这样，整个时间间隔

的上界为：

（5n/2-3）+（5n/22-3）+（5n/24-3）+…+2〈5n

另外，我们必须加上用于通知树中所有节点有关算法终止所需时间。因为这个任务要求最多3（n-1）条消息（每条MST的边需要两条COMPUTE消息和一条DIFFUSE消息），构造阶段需要最多8n-3个时间单位来完成。

到目前为止，我们一直假设所有节点同时进入构造阶段。如果情况不是这样。那么在初始化阶段之后，我们必须使用一条特殊的消息（类似于START-MSG）。因为图G中最长的传播路径是n，在这种情况下，构造阶段最多花9n-3个时间单位。

最后，从引理2到引理5我们直接得到以下结论：

定理2 给定一个具有n个接点的图G，构造MST算法所花时间为O（n）。

4 试验结果

我们已经在XTV系统［2］中实现并测试了我们的算法。作为这个系统的一部分，我们使用生成树拓扑把一组信息服务器连接起来，这个互连拓扑结构为发布和广播与会议相关的信息提供了主干。

当前实现的的测试和时间值是在一组二十台DEC／5000和DEC／3000工作站下做的。所有的工作站都连接在相同的局域网上，所有的工作站都运行Ultrix4.2操作系统。

我们通过变化组中服务器的台数运行算法来验证我们实现的正确性，服务器的台数从3台开始到20为止，对每一组实验十次，并将结果和顺行实现的Prim算法相比较。为了确保所构造的MST是真正随机的，我们产生了伪随机RTT的值，而不是让网络中反复无常的行为控制了MST的构造。在180次试验的每次运行中，由我们的算法所构造的树和由Prim算法生成的树是一样的。

为了测试算法的性能，我们在节点的个数从1个变化到20个的情况下分别执行该算法，对每种情况测试10次。在每种情况下，我们都考虑一个全连接的图，也就是说每台服务器的邻节点列表（adj_list）由所有其他的服务器构成。稍后，我们将推导出我们算法在最坏情况下的时间复杂度，并且我们将指出如何将其与真实的测量值作比较。

正如我们在第3节时间复杂度分析中所指出的，初始化阶段最多需要3n-2个时间单位（见引理2的证明），构造阶段最多需要9n-3个时间单位（见引理5的证明），这导致了整个算法在最坏情况下的总的时间复杂度为12n-5。现在回想以下，在我们的分析中，都假定任何消息的传播试验最多为一个时间单位。因此在这种情况下我们选择试验中所测量的最大传播时延（表示为t max）来作为时间单位。这样，我们的算法在最坏情况下，构造一个具有n个节点的图的MST最多需要(12n-5)×t max的时间。

图8展示了实际上测量的时间（多每次实验）对最坏情况的估计时间。可以看到，在所有情况下所测量到的时间都在预期的最坏情况时间之下。尽管我们的结果是在局域网中获得的，但是我们可以期望在广域网中结果至少是差不多的。因为在我们的简化模型中所忽略的象消息处理时间和计算时间这样参数，在出现广域网中所经历的相当大的传播时延这种情况下，这些时间的意义要小得多。

图8：我们的MST算法的测量值对所期望的最差情况时间值。算法在服务器

的台数从2台到20台的每种情况各执行10次试验。

5 相关工作

以前在通讯网络中分布式计算一棵MST的理论方案是基于Gallager,Humblet和Spira所提出的算法。这个算法利用相同的思想；它以所有节点都为子树开始，重复的沿着他们最小权值的边进行连接，直到一棵MST被构造出来。这个算法具有的消息复杂度为O （nlogn）(这是最优的)时间复杂度为O（nlogn）。为了获取消息最优，在两棵树连接时实施了一些规则，每棵子树具有一个相关联的层次数L，以使得子树中的节点个数≥2L （只有单个节点的子树的层次数为0）。假定一棵具有L层的子树T找到一条最小权值的外出边，该边将它和另外一棵具有L＇层的子树T＇连接起来。那么，仅当L≤L＇时T和T＇连接，否则T等待直到T＇足够大为止。这个算法后来的改进减少了时间复杂度到了O （nlog*n）进一步又到达O（n）（它是最优的），但不幸的是，这是以增加算法的复杂性为代价的。尽管这个算法的理论价值是毋庸置疑的，但它的复杂性使得其在实现起来相当困难。作为一种可供选择的办法，我们设计并实现了一个尽管在消息的个数上不是最优的但却是简单的和时间最优的算法。我们这种以消息复杂度换取时间复杂度的决定被互联网中的应用类型证明是有道理的，在这些应用中，对终端用户来说，响应时间往往是要比消息交换的数目更为重要。

多播问题的实际解决方案是基于以前曾经用在分布式路由算法中的方法［18］。当前存在的IP多播构架的解决方案主要是距离矢量路由（DVMRP：距离矢量的多播路由协议）和链路状态算法（LSMRP：链路状态的多播路由协议）的扩展。在［14］中提出了一种对开放最短路径链路状态协议（OSP）的扩展。这些算法的主要缺点是伸缩性问题：路由递送树的计算是基于原点的，它要求潜在的涉及到要为所有现存的组路由消息的每台路由器为所有潜在的多播源存储路由信息。这导致了一个和（源点，组）对的个数成比例的伸缩因子。在广域网的环境中，动态的计算以源为基础树成为路由节点一个繁重的计算任务。

为每个组使用单个把属于相同多播组的所有节点都连接起来的多播递送树而不是使用基于源的树有可能被看作是IP网络中多播路由的一个可能的解决方案。在［17］中提出

了一种在广域网中构造生成树的分布式算法。因为该算法要求每个节点只存储有限数量的

信息（主要是相关联的链路信息），这些信息与网络的大小无关，通讯拓扑更加可伸缩。另一方面，它不再是同质的，也就是具有最小标识的节点（它要成为树根）有特殊的功能。在出现失败时这会有负面影响，也就是说，如果根失败了，将要花上高昂的系统开销来选择一个新的树根。而且由于该算法依赖于树根的位置，故而有可能产生低效的通讯拓扑。例如，考虑一个由三个节点A，B，C构成的网络，其平均试验为：τ(A,B)=500ms, τ(B,C)=500ms,τ(C,A)=2000ms,如果A（具有最小的标识）是树根，则得到的生成树由边（A，B）和边（A，C）构成，因此从B到C的消息要花2500ms，而由边（A，B）和边（B，C）构成的一棵树，在任何节点对之间的消息最多只要1000ms。

最近，在［4］中有人提出了一种以核心路由器为基础的树（CBT）方案作为是对DVMRP和链路状态的多播构架的一种可供选择的办法。这个方案被认为是不仅在糟糕的伸缩性上处于不利地位，而且要遭受到对单播路由算法的依赖性，同时就路由节点上所消耗的资源而言也是代价高昂的。这里，通过在路由器上存储每组信息而不是每多播源信息消除了伸缩性问题。然而，就象前面一样，由于出现了容易遭受失败的单点（路由树的核心），以及为了维持最优的递送树在树中动态的重选和替换核心所招致的系统开销，会产生新的问题。

6、结论

在本文中，我们提出了一个在一般的通讯网络中计算一棵最小生成树的全分布式算法。下层的通讯网络被建模为一个无相连通图，图中的节点代表主计算机，便代表节点之间的虚连接。除此之外，每一条边被赋予一个值为与该边相关量的端节点之间的平均传输时延的权值。尽管这是一个简单的度量值，但是算法可以很容易的推广到使用更加复杂的度量值（metric）。我们还证明了我们的时间复杂度是最优的，也就是计算具有n个节点的图的MST需要花O（n）的时间。为了证明我们想法的可行性，我们实现了该算法，并在XTV 会议系统的环境中测试了该算法。

为多播递送每组使用一棵单树的主要优点是它提供了更好的伸缩性，因为节点只需要存储和其邻节点相关的信息，而不需要为所有潜在的多播源存储所有路由信息。而且，平均而言，当通讯图增量改变时（比如一个节点或链路被增加／删除）为维护已可生成树所招致的系统开销要小得多。这是因为本地变化只会在邻居节点中反映出来，而不会影响到图中的所有节点（比如说，当向图中加入一个新节点时，只有与被修改的边相关联的节点才需要更新他们的信息）。比较起来，如果节点象链路状态的路由协议那样存储通讯拓扑的全局信息，那么任何改变将会要求图中的每个节点更新他们的信息。

这个算法可以在几个方面进行扩充，首先，必须提出一种恢复过程来处理节点／链路的失败。一种简单的方案是对树的构造过程进行改动来重新连接由于失败所产生的不相交树。

另外一个应该处理的问题是由于暂时的（比如，网络拥塞）和永久的因素（比如，网络拓扑的变化）所可能导致的网络性能的巨大变化。因为我们的算法只是基于初始化阶段所获取的数据来构造MST的，通讯树的性能最终有可能严重降级。这个问题的一个解决方案是周期性的重新计算MST并且每当性能收益抵消了由于重新映射过程（也就是利用新树改变当前的通讯树）所引入的系统开销时真正的使用它。一个可供选择的办法是每当两个端节点的通讯时延的增加超过一个特定的阈值时，就重新计算MST。