A new deterministic fault tolerant wormhole routing strategy for k-ary 2-cubes

Multicomputers have experienced a rapid development during the last decade. Multicomputers rely on an interconnection network among processors to support the message-passing mechanism. Therefore, the reliability of the interconnection network is very important for the reliability of the whole system. In this paper a new fault-tolerant routing algorithm, which is based on dimension order routing, is proposed for k-ary 2-cubes. Packets are sent to their destination through XY routing algorithm and if this transmission is not possible, YX routing algorithm is applied. The XY routing algorithm nullifies offset in "X" direction before routing in "Y" direction, but the YX routing algorithm first nullifies offset in "Y" direction and then start routing in "X" direction. For evaluation, this algorithm is compared with the Gomez method [1] which uses intermediate nodes for tolerating faults. The results show that our method is preferred, especially in the environments where the fault probability is low and the message generation rate is high.