二进制递归网络的多故障容错性分析

项目名称： 二进制递归网络的多故障容错性分析

项目编号： No.61300018

项目类型： 青年科学基金项目

立项/批准年度： 2014

项目学科： 自动化技术、计算机技术

项目作者： 董强

作者单位： 电子科技大学

项目金额： 28万元

中文摘要： 并行计算系统的性能很大程度上取决于连接计算结点的互连网络的有效性。为了保证系统在某些结点出现故障时仍能继续运行的能力，非常有必要研究互连网络的容错性。二进制递归网络（BRN）具有结构规则、易于分割等优点，是理论研究和实际应用中颇受欢迎的网络结构。现有的BRN容错性研究成果大多基于故障数小于连通度、网络仍然连通的少故障假设，不能反映故障数大于连通度、网络不再连通的多故障模式下网络被破坏的程度。本项目针对BRN多故障容错性研究中的3个关键科学问题开展研究，首先，提出最大连通分支规模和基于邻接矩阵特征值的特征连通度参数，解决不连通网络容错性度量问题；其次，研究故障网络中最大递归子网络规模和最长圈/路径嵌入性，给出容错性好的网络具有的特征；最后，基于小世界网络理论改进BRN，设计容错性好的小世界立方体网络。预期成果能够完善互连网络容错性度量体系，为我国高性能可信计算机的发展提供理论依据和技术支持。

中文关键词： 复杂网络；容错性；哈密尔顿圈；影响力结点；推荐算法

英文摘要： The performance of a parallel computing system heavily depends on the effectiveness of the underlying interconnection network that connects the computing nodes. With the size of a parallel computing system increasing, it becomes much likely that some computing nodes fail to work in the interconnection network. Hence, in order that the system continues to function in the presence of failures, it is essential to investigate the fault tolerance of the interconnection network, i.e., the ability to exchange data between healthy computing nodes in a faulty network. As an important generalization of hypercube, the Binary Recursive Network (BRN) is regular in structure and easy to be split, which has become a popular network topology both in theoretical research and practical application. Most of the existing results on the fault tolerance of BRNs are under the assumption that the number of faulty nodes is smaller than the connectivity such that the network remains connected. These results cannot reflect the degree of damage to the network wherein the number of faulty nodes is larger than the connectivity such that the network may be disconnected. This proposal addresses the fault tolerance of BRN with more faulty nodes, which partially answers the three key scientific questions in the study of fault tolerance of BRN

英文关键词： complex networks；fault tolerance；Hamiltonian cycle；influential node；recommendation algorithm