Fault-tolerant routing in the binary n-cube using unsafety sets

This paper proposes a new fault-tolerant routing algorithm for the binary n-cube, which overcomes the performance limitations of the recently proposed safety vectors algorithm [12]. In this new algorithm, each node A starts by computing the first level unsafety set, SP, composed of the set of unreachable immediate neighbors. It then performs m-1 exchanges with its neighbors to determine the k-level unsafety sets S-k(A) for all 1 less than or equal to k less than or equal to m, where m is an adjustable parameter between 1 and n. The k-level unsafety set at node A represents the set of all nodes at Hamming distance k from A which are faulty or unreachable from A due to faulty nodes or links. Equipped with these unsafety sets we show how each node calculates numeric unsafety vectors and uses them to achieve efficient fault-tolerant routing. A performance comparison of the proposed and safety vectors algorithms through extensive simulation is then presented The results reveal that the unsafety sets algorithm provides better performance than its safely vectors countrepart in terms of routing distances and percentage of reachability.