Fault-tolerant routing in multiply twisted cube topology

In an attempt to improve the communication diameter of the hypercube interconnection network, variations of the hypercube topology, called the twisted cubes have been proposed in the literature. Among these, the Multiply Twisted Cube (MTC) proposed by Efe [5] is a good candidate for massively parallel multiprocessors due to its properties such as smaller network diameter, high connectivity, regularity and recursive structure. The routing algorithm proposed by Efe in [5] suffers from two disadvantages, Due to its complex nature, a software implementation of the algorithm can be slow, and a hardware implementation expensive. Secondly, the algorithm is not tolerant to network conditions such as faults and congestions. In this paper, we present a simple hierarchical router for the MTC, which has an efficient hardware implementation. We also present a simple, randomized variation of the hierarchical router which makes the algorithm adaptive to network conditions without excessive hardware overhead. We compare the dynamic performance of our router with that of Efe's router, Our algorithms perform better in terms of network throughput and mean delay. Furthermore, the performance degradation is only marginal in the presence of a tolerable number of faults.