ADAPTIVE ROUTING IN K-ARY N-CUBES USING INCOMPLETE DIAGNOSTIC INFORMATION

In this paper, we present a fault-tolerant routing algorithm for k-ary n-cube interconnection networks which have become increasingly popula r for the construction of massively parallel computers. The k-ary n-cu be is a generalization of 2-ary hypercube network, and can model sever al interesting topologies such as the 2-d torus, 3-d torus, and the bi nary n-cube. In our routing algorithm, we assume that each node has st atic knowledge of the fault status of its immediate neighbours. Using this information, the nodes of the network execute a distributed diagn osis procedure whereby each node i learns the fault status of all othe r nodes that are reachable from i within k hops, k greater than or equ al to 1. We refer to k as the diagnostic radius. Our simulation result s indicate that a diagnostic radius larger than 1 can improve the perf ormance of the routing algorithm. Our routing algorithm is a significa nt improvement over a similar algorithm due to Blough and Najand in th at our algorithm does not place overheads on each message. The Blough- Najand algorithm requires each message to store the entire path from t he source to destination, which can be quite large for a massively par allel multiprocessor. We compare the relative merits and demerits of o ur algorithm with those in the literature.