Design schemes of dynamic rerouting networks with destination tag routing for tolerating faults and preventing collisions

In fault-tolerant multistage interconnection design, the method of providing disjoint paths can tolerate faults, but it is complicated and hard to choose a collision-free path in disjoint paths networks. A network with disjoint paths can concurrently send more identical packets from the source node to increase the arrival ratio or backtrack a packet to the source and take the other disjoint path, but these two methods might increase the collision ratio. In contrast, a dynamic rerouting method finds an alternative path that tolerates faults or prevents collisions. In this paper, we present methods of designing dynamic rerouting networks. This paper presents (1) three design schemes of dynamic rerouting networks to tolerate faults and prevent collisions; (2) design schemes that enable a dynamic rerouting network to use destination tag routing to save hardware cost in switches for computing rerouting tags; (3) a method to prevent a packet from re-encountering the faulty element again after rerouting to reduce the number of rerouting hops and improve the arrival ratio; and (4) simulation results of related dynamic rerouting networks to realize the factors which influence the arrival ratio including the fault tolerant capability and the number of rerouting hops. According to our proposed design schemes and according to our analysis and simulation results, a designer can choose an applicable dynamic rerouting network by using cost-efficient considerations. This paper was partially supported by the National Science Council NSC-92-2213-E-324-006- and NSC-94-2213-E-035-050-; and the partial part of the preliminary version of this paper was published by the conference ISPA 2005 5].