Research On Fault Tolerance Based On Network Topology

With the rapid development of computer science and technology,higher requirements are put forward for the computing and storage capacity of the computer,and the parallel computer system came into being.The parallelism and high performance of a parallel computer system depend largely on its interconnection network.Therefore,interconnection networks with high fault-tolerance are particularly important for developing better parallel computer systems.Furthermore,the fault-tolerance of an interconnection network depends on its topology structure,which is often modeled by a graph,where the vertices of the graph represent processors,and the edges of the graph represent the direct communication between a pair of processors.Thus the problem of fault-tolerance of an interconnection network can be transformed into the study of the structural properties of graphs.The connectivity of a graph is a classical structure parameter of a graph and also a classical parameter to measure the fault-tolerance of an interconnection network.However,in practical applications,it is very unlikely that all neighbors of a processor will fail at the same time,and when the network is disconnected,the classical connectivity cannot reflect the structure properties of the remaining network.So the classical connectivity tends to underestimate the level of fault-tolerance of an interconnection network.In order to better evaluate the fault-tolerance of an interconnection network,scholars have generalized the classical connectivity,and proposed the generalized connectivity,the h-extra connectivity,the h-component connectivity and the structure connectivity,etc.,which can measure both the connectivity and elasticity of an interconnection network.This thesis studies the values,the bounds,the extremal problem and the inverse problem of the parameters of the generalized connectivity,the h-extra connectivity,the h-component connectivity and the structure connectivity by using the methods of reduction,induction and graph structure analysis.The main results are as follows:The h-component connectivity of a general graph is studied,and the values of the h-component connectivity of a path,a cycle,a wheel graph,a complete bipartite graph and a complete multipartite graph are calculated.Based on the monotonicity of the h-component connectivity of a graph,the bounds of the h-component connectivity of a general graph and a tree are given.The inverse problem of a general graph and a tree with given h-component connectivity is studied.The extremal problem of the hcomponent connectivity is discussed,and three extremal parameters s(n,k),f(n,k)and g(n,k)are obtained.The hypercube is one of the basic topology structures for constructing parallel computer systems,many complex network structures are obtained by product operation or expansion deformation based on hypercube graph.The cube-connected cycles and the hierarchical hypercube can be obtained by replacing each vertex of a hypercube with a cycle and a hypercube respectively.They not only inherit the regularity,the symmetry,and the high fault-tolerance of the hypercube,but also have more optimized communication capabilities and small fixed vertex degrees,which greatly improve the performance of a interconnection network.By analyzing the structure and properties of the cube-connected cycles and the hierarchical hypercube,the values of the generalized 4-connectivity of the cube-connected cycles and the hierarchical hypercube are obtained.The topology of large-scale and super large-scale networks can be obtained by graph operation.Mycielskian graph is a graph obtained by graph operation,which is a graph class with the arbitrarily large chromatic number but no triangles.By analyzing the structure and properties of Mycielskian graph,we investigate the h-extra connectivity and the structure connectivity of Mycielskian graph,and obtain the relations of the h-extra connectivity and the structure connectivity of Mycielskian graph and the original graph,respectively.The results of this thesis not only have significant practical significance in designing higher-performance parallel computer systems,but also have important theoretical values in improving the fault-tolerance,economy and security of their interconnection networks.