Optimal Fault-Tolerant Routing Scheme for Generalized Hypercube
Shaohuai Tian, Yingping Lu, Dafang Zhang · 2006
We propose node path vector (NPV) to capture complete shortest routing information for a generalized hypercube system. We also introduce the concept of relay node technique to reduce the computation complexity in obtaining NPV. Optimal fault-tolerant routing scheme (OFTRS) is further proposed to derive an optimal or sub-optimal routing path for any communication pair in a generalized hypercube system. Compared to previous work, OFTRS does not omit any routing information for optimal and sub-optimal path even in a generalized hypercube system with large number of faulty nodes and links while the previous schemes can potentially omit 60% routing paths. Thus it considerably improves the quality of fault-tolerant routing. In addition, our proposed scheme is distributed and relying only on non-faulty neighboring nodes, thus it has high applicability. Finally, the algorithm guarantees to route through the optimal or sub-optimal path as long as a path between the source-destination pair exists.