Research On The Fault-tolerant Properties Of Augmented Cube Networks

There are many factors that determine the performance of interconnection network.Fault tolerance is an important reference standard to measure the performance of interconnect network.An interconnection network with good fault tolerance will not affect the performance of the whole network even if some vertices in the network fail.Connectivity is one of the important indicators to measure the fault tolerance of a network.But the traditional connectivity often assumes that when a vertex in the network fails,it has no effect on the surrounding vertices.However,in the actual running environment,when a vertex fails,the probability of the failure of its surrounding vertices is also greatly increased.In order to make up for this kind of defect,the structure connectivity and substructure connectivity reflect the fault tolerance of the interconnection network more practically from the point of view of fault structure rather than single fault vertex.In addition,when the vertex in the network fails,how to diagnose the fault vertex accurately to ensure the normal operation of the network is also the key aspect to improve the fault tolerance ability of the network.The maximum number of fault vertices that an interconnection network can determine is called the diagnosability.Diagnosability is another key index to measure the fault tolerance performance of interconnection network.The augmented cube is an important variant of the famous interconnection network hypercube.The augmented cube not only retains many of the great properties of the hypercube,but also has advantages that the hypercube and its other variants do not have,for example,the connectivity of the augmented cube is 2n-1,almost twice that of the hypercube,this also means that the fault tolerance of the augmented cube is in some ways much better than that of the hypercube.In this paper,we mainly study the properties of fault tolerance of augmented cube,including structure connectivity,substructure connectivity and extra diagnosability.At the same time,according to different fault-tolerant properties,this paper propose corresponding algorithms to verify their effectiveness.The specific research contents are as follows,(1)From the perspective of fault structure,this paper studies the structure connectivity and substructure connectivity of augmented cube.These structures include bipartite graphs,paths,and cycles.The research results show that with the increase of the dimensionality,the number of fault vertices that the augmented cube can tolerate under bipartite graph K1,6 fault structure is almost twice that of the traditional connectivity.(2)Under the condition of substructure connectivity,this paper presents a fault-tolerant routing algorithm between two fault-free vertices.The algorithm analysis and experiments show that the algorithm can construct a fault-free path that is nearly optimal in length in a relatively short time.(3)From the perspective of fault diagnosis,this paper studies the 2-extra diagnosability of augmented cube,and the result is about 3 times that of the the traditional diagnosability.In addition,this paper also gives the 2-extra diagnosis algorithm of the augmented cube under the MM*model.Algorithm analysis and simulation experiments show that the algorithm can correctly diagnose all fault vertices.