Biswapped网络(BSN)的拓扑性质研究:点对称性和极大容错性  

Topological Properties of Biswapped Networks(BSNs):Node Symmetry and Maximal Fault Tolerance

作　　者：陈卫东[1] 肖文俊[2] 

机构地区：[1]华南师范大学计算机学院,广州510631 [2]华南理工大学软件学院,广州510641

出　　处：《计算机学报》2010年第5期822-832,共11页Chinese Journal of Computers

基　　金：广东省自然科学基金(04020130);国家自然科学基金(60973150)~~

摘　　要：Biswapped网络(BSN)是一类两层结构的互连网络,它以任意图为模块且模块间采用一种完全两部图方式互连.BSN的互连形式与OTIS网络(即Swapped网络)类似但互连规则更一致,使得BSN展现出更好的性能.文中主要研究BSN的点传递性和容错性能.首先证明BSN能继承因子网络的点传递性质,为BSN上的分析和算法简单性找到理论依据.其次,通过直接构造网络中两点间最大数目的点不相交路径证明以任意连通图为因子网络的BSN是一致极大容错的.这些结果表明BSN既能继承因子网络的理想性能还展现某些好的新特性.最后,通过与OTIS网络、卡式积网络等层次类网络比较表明,BSN提供了一种构建可扩展性、模块化、容错性的大规模并行计算机系统的潜在有竞争力的体系结构形式.Recent Niswapped Networks （BSNs） are a class of two-level structure interconnection networks taking any graph as modules and connecting them in a complete bipartite manner. A simple rule for connectivity in BSNs, similar to but more uniform than the one in well-known OTIS networks or swapped networks, leads to better performances in BSNs. In this paper, the node symmetry and the fault tolerance of BSNs are investigated. It is showen that if a factor network is node transitive then so is the resulting BSN, which gives a justification for simplicities in analyses and algorithms in BSNs. Moreover, by giving a simple general construction of a maximal number of node-disjoint paths between nodes in a BSN built of a connected graph, it is proven the BSN possesses uniformly maximal fault tolerance property regardless of whether the factor network is maximally fault tolerant or not. In contrast with OTIS networks and Cartesian product networks, these results further confirm that the connectivity rule in BSNs provides a systematic competitive construction scheme for large, scalable, modular, and robust parallel architectures, while maintaining favorable properties of their factor networks.

关 键 词：互连网络 OTIS网络 Biswapped网络 拓扑性质 点传递性 极大容错性 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]