A Fault-Free Unicast Algorithm in Twisted Cubes with the Restricted Faulty Node Set
Jianxi Fan, Shukui Zhang, Xiaohua Jia, Guangquan Zhang · 2009
The dimensions of twisted cubes in the original definition of twisted cubes are only limited to odd integers. In this paper, we first extend the dimensions of twisted cubes to all the positive integers. Then, we introduce the concept of the set of restricted faulty nodes into twisted cubes. We further prove that under the condition that each node of the n-dimensional twisted cube TQnhas at least one fault-free neighbor its restricted connectivity is 2n - 2, which is almost as twice as that of TQnunder the condition of arbitrary faulty nodes, the same as that of the n-dimensional hypercube. Moreover, we give an O(N log N) fault-free unicast algorithm, where N denotes the node number of TQn-1. Finally, we give the simulation result of the expected length of the fault-free path gotten by our algorithm.