Fault-tolerant routing in hypercube networks without virtual channels

A fault-tolerant wormhole routing algorithm for hypercubes without using any virtual channels is presented. The routing algorithm can tolerate any pattern of faulty nodes as long as the number of faulty nodes is no more than ┌n/2┐, where n is the dimension of the hypercube. Furthermore the algorithm can tolerate 2^n-1 faulty nodes when all faulty nodes are located in the same (n-1) cube. Previous works need at least two virtual channels to achieve the same fault-tolerant ability. The algorithm is the first one that does not require any virtual channels. Simulation results using various workloads and fault patterns are given.