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

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

摘要

广域网中一个核心问题是有效的多播一条消息到目标组的所有成员。一种最有效的多播一条消息的方法是沿着连接组的所有成员的生成树的边发送消息。本文中,我们提出一种新的全分布式算法来在一般的通讯网络中构造一棵最小生成树(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重复直到所有的顶点都被连接起来。

Word文档免费下载Word文档免费下载:在互联网中计算一个最小生成树的简单快速分布式算法 (共13页,当前第1页)

你可能喜欢

  • 数据结构与算法分析
  • 算法设计分析清华大学出版社
  • 实验逆波兰式产生计算流程图
  • 汉字计算机中表示形式称为
  • 数据结构快速排序算法

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

最新文档

返回顶部