互连网络故障直径的研究

摘要：

考虑了至多可以删除多少个顶点才能保证互连网络的连通,给出了网络的容错能力.根据Menger定理可以得到BC互连网络之间至少存在n条内部节点互不相交的路径.利用广度优先搜索的思想,给出了求任意两个节点之间的n条内部节点互不相交,且在两点间所有路径中是最短的n条路径的算法.该算法为网络故障直径的研究提供了依据.而且,在故障存在但是网络连通的情况下,可以求得网络中任意两节点间的n条最并行路径,提高了网络的容错能力.本文对提出的方法及算法的正确性进行了证明,为研究互连网络的性质提供了新的研究方法.

关键词：并行系统、互连网络、广度优先搜索算法(BFS)、故障直径

所属期刊栏目：21

分类号：TP301(计算技术、计算机技术)

在线出版日期：2007-05-14（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：32-35,39