Research On The Reliability Of The Generalized Hypercube

As an important part of high-performance computing networks,the interconnection network needs to possess excellent performance since its performance is critical,and the reliability is one of the key indicators to measure the performance of a network.The gen-eralized hypercube(GH)is an interconnection network topology with excellent properties:it has a short diameter;its vertices can be represented in arbitrary system;its connection way and recursive structure make it easy to be constructed.GH is a more general topology,which not only includes many interconnection network structures such as the hypercube,the mesh network,the 3-ary n-cube and the complete graph,but also can be used to design data center networks such as HyperX,BCube,FBFLY,SWCube,etc.Connectivity,disjoint paths,fault-tolerant hamiltonian,and how to remove resources from the network to obtain a network with good performances are important issues in the research of network's reliability.However,there are many deficiencies in using these metrics to measure the reliability of a network.Firstly,when using connectivity to measure the reliability of a network,it usually refers to the traditional connectivity.However,when the traditional connectivity is used to measure the reliability of a network,all neighbors of one vertex can become faulty at the same time,and the probability that this event occurs in the real operating environment is very low.Therefore,this situation cannot well reflect the real scene.Secondly,when constructing fault-tolerant disjoint paths,there is no consideration for restricted connectivity,which makes the number of disjoint paths insufficient.Thirdly,when using the fault-tolerant hamiltonian to measure the reliability of a network,only the single faulty vertex and edge are considered,and a set of edges that satisfy certain conditions are not considered as one faulty element,which makes the research on the fault-tolerant hamiltonian have certain limitations.Finally,deleting some resources from the network can reduce its construction cost,but it is difficult to maintain the key properties of the original network in the resulting network.In this thesis,we deeply study on the above reliability problems in GH and obtain the following research results:1.We study the structure connectivity and substructure connectivity of GH,where these structures include stars,circles with lengths of 3 and 4,and complete graphs with 4 vertices.Our results show that,in the case of reliable communication of GH,the number of faulty vertices that can be tolerated in GH is almost twice the traditional connectivity under ideal conditions.2.We propose the algorithm to construct disjoint paths in GH under the condition that each vertex has at least one fault-free neighbor.The algorithm can construct multiple disjoint paths in GH,the number of disjoint paths is about twice the number of disjoint paths under traditional connectivity,and the maximum length of these paths does not exceed the diameter of GH plus 2.The result shows that,in theory,the communication delay of data transmission using these disjoint paths is at most 2 more than that of data transmission under the traditional connectivity.According to our research results,there exists one fault-free path between any two fault-free vertices of GH when each fault-free vertex has one fault-free neighbor and the number of faulty elements is less than the 1-restricted connectivity.3.We study the fault-tolerant hamiltonian of a family of GH under the condition that the faulty set with three kinds of faulty elements:vertex,edge,and a set of edges satisfying certain conditions.Our results indicate that,compared with the traditional connectivity,the number of faulty elements that can be tolerated against a significant increase when ensuring there are hamiltonian cycle and hamiltonian path(i.e.,the hamiltonian cycle and hamiltonian path that do not include faulty vertex)in such GH.The results of this thesis can also be applied to two kinds of important data center networks:BCube and HyperX.4.In order to reduce the construction cost of GH,we remove several specific edges from GH to get a new network topology—the exchanged generalized hypercube(EGH).After studying the basic properties of EGH,such as diameter,connectivity and routing,we present the fault-tolerant disjoint paths constructive algorithm and two local diagnostic algorithms of EGH.The experimental results show that even if the proportion of faulty vertices in EGH reaches 25%,the probability that these two diagnostic algorithms can successfully determine whether a vertex is faulty is still more than 90%.As a consequence,our results show that EGH not only reduces the construction cost of the network but also maintains the good performances of GH,which further demonstrates that GH has good reliability.In summary,the thesis describes the reliability of GH from four aspects:structure connectivity,disjoint paths,fault-tolerant hamiltonian and the deformation of the generalized hypercube.The research results in this thesis show that GH has good reliability in the above four aspects.This thesis also provides a new method to study the reliability of other networks.