Adaptive fault-tolerant wormhole routing algorithms for hypercube and mesh interconnection networks

Abstract

The author presents adaptive fault-tolerant deadlock-free routing algorithms for hypercubes and meshes by using only 3 virtual channels and 2 virtual channels respectively. Based on the concept of unsafe nodes, the author designs a routing algorithm for hypercubes that can tolerate at least n-1 node faults and can route a message via a path of length no more than the Hamming distance between the source and destination plus four. The author also develops a routing algorithm for meshes that can tolerate any block faults, as long as the distance between any two nodes in different faulty blocks is at least 2 in each dimension.