Network Matching Troubleshooting And Fault Tolerance Research

The main factor that affects the super large parallel computer system network system is the topological structure between processors.A topology of interconnction network can be modeled as a graph:each processor element is represented by a vertex,and the physical connection between each pair of processor elements is represented by one edge.Therefore,the research on the related properties of the interconnection network can be transformed into the research on the related properties of the graph.In fact,by studying the matching problem and restricted connectivity of the graph,it is a powerful tool to study the hot issues of network matching preclusion and fault tolerance.The concept of matching preclusion for interconnection networks was proposed by Brigham et al in 2005.This paper mainly studies the problem of conditional matching preclusion of graphs.The case of conditional matching preclusion sets satisfying monotonicity is discussed,and a counter-example diagram when monotonicity is not established is given.Consider the upper and lower bounds of the number of conditional matching preclusion and graph classes that can reach the upper and lower bounds.The graphs with the odd and even order of the small conditional matching preclusion number and the large conditional matching preclusion number are respectively described.Some extremal problems of condititional matching preclusion number are discussed.Consider using the value in[0,1]to assign values to the edges of the M?bius cube,and discuss the case of the fractional matching preclusion set of the M?bius cube when only the edges are deleted.It is obtained that the number of M?bius cube fractional matching preclusion is n when n?3.When deleting edges and deleting vertices at the same time,the structure of the preclusion set of strong fractional matching preclusion for n is 3 or 4 is determined.For n?5,the number of strong fractional matching preclusion sets of the M?bius cube is given.In order to consider the maintenance ability of some special properties of the system when the network fails at the vetex and edge.The traditional parameters such as connectivity and edge connectivity of graphs are often used to evaluate the fault tolerance of networks.In this paper,l-extra edge connectivity and g-good neighbor edge connectivity are studied.The monotonicity holds for both connectivity of the same graph,but the monotonicity of the graph and the subgraph is only valid when the l=0 and g=0,that is,the classical connectivity.We give graphs whose monotonicity does not hold when l?1 and g?1.The upper and lower bounds of l and g are determined.The values of the two connectivity of path,cycle,tree,complete graph,complete multipartite graph and crown graph are given.The upper and lower bounds of the two connectivity are given respectively,and it is shown that the upper and lower bounds are reachable.Some extremal problems of l-extra edge connectivity and g-good neighbor edge connectivity are discussedNetwork fault diagnosis is the process of identifying fault processors.Fault diagnosis plays an important role in network fault tolerance.Diagnosability is not only an important index of diagnosis ability,but also an important parameter to judge network fault diagnosis ability.The g-extra conditional connectivity and g-extra conditional fault diagnosis of round matching composition network are studied.PMC model and MM*model are two common fault diagnosis models.Firstly,the necessary and sufficient conditions for the diagnosis of round matching composition network under the two models are determined.This paper discusses the value of the g-extra conditional connectivity of round matching composition network and characterizes the structure of g-extra conditional cut set of round matching composition network.Based on the g-extra conditional connectivity of round matching composition network and the existence of isolated vertex,the g-extra conditional diagnosis of round matching composition network in the PMC model and in the MM*model is considered respectivelyAfter deleting the fault vertex,we hope that the branch topology of the network can still maintain a certain structure.For example,there are cycles in the branches,and the existence of cycles can make the branch connectivity stronger.Star graph Sn,is a special case of(n,k)-star graph Sn,k,and the result of cyclic vertex connectivity of star graph Sn has been obtained.In this paper,we study the cyclic vertex connectivity of(n,k)-star Sn,k graph.Firstly,we obtain that the minimum cycle is 3 and all edges on the cycle are 1-type edges,then get the structure of the cyclic vertex connectivity of Sn,2 and the cyclic vertex cut set of Sn,2.Finally,we discuss the cyclic vertex connectivity of(n,k)-star graphIn this paper,graph theory is used as the main research method and tool.The research results provide valuable theoretical reference for engineers to design large-scale reliable interconnection network,and also provide theoretical basis for improving the fault tolerance and security of large-scale interconnection network.