M (?) Bius Cube Interconnection Network Fault-tolerant Routing Algorithm

Mobius cube topology has enjoyed popularity and drawn a great deal of attention from the researchers. In order to improve the degree of fault tolerance for the interconnection network, this paper mentions it below: under the Mobius cube topology of the network, the likelihood of one processor and all its neighbors failing to work at the same time should be ignored, or the distribution of the faulty nodes be considered; in other words, under the conditional connectivity, study the fault tolerance and the fault-tolerant routing.To begin with, this paper takes an example as 0-Mobius to prove that the conditional vertex-connectivity of the Mobius cube is 2n - 2 and the degree of fault tolerance is 2n - 3, provided that all the neighbors of each professor do not fail to work at the same time. Then under the vertex-connectivity of the Mobius cube, the relative fault-tolerant routing algorithm is given, and the time complexity of this algorithm is O(n) . Furthermore, it also shows that, for the two free nodes s and t, there is a free path from s to t in the O(n) time, under the conditions of one given faulty set consisting of at most n-1 number of faulty nodes, and the length of it is no more than [(n-[log|F|J)/2~|+4[log|F|J+2. What is more, if n is large enough, the length will be close to the diameter of the Mobius cube.Following that, a fault-tolerant routing algorithm, in the case of the conditional vertex-connectivity of the Mobius cube is given, and the time complexity of this algorithm is O(n). Apart from this it illuminates that under the conditions of one given faulty set named F, where F(?) V(Mn) and |F|≤2n-3, for the two free nodes s and t, there is a free path from s to t in the O(n) time, and the length of this road is no more than [ (n — (log|F|)/2 ]+4([log|F|]+l). Also, if n is large enough, the length will be close to the diameter of the Mobius cube.Finally, it also demenstrates that the conditional edge-connectivity of the Mobius cube is 2n-2 as well, provided that all the neighbors of each professor is in good operation, meanwhile. And the fault-tolerant routing algorithms, under the edge-connectivity as well as the conditional edge-connectivity of the Mobius cube is similar to the corresponding fault-tolerant routing algorithms, under the circumstance of the vertex-connectivity and conditional vertex-connectivity.The algorithms given in this paper have been proved correct by using the C program.