The Effect of Backtracking Mechanism in Increasing MIN Fault Tolerant

This paper discusses a Multistage Interconnection Network (MIN) which is called Reliable Interconnection Network (RIN). RIN is a modification of the Gamma network. Gamma network is a network that is always used as a reference in designing MIN with disjoint path. However, it has non-uniform disjoint paths so the failure tolerance between its inputs and outputs is not the same. In RIN, there are a number of disjoint paths that are the same for all input to output connections, namely 4 disjoint paths. In this RIN routing algorithm, a backtracking mechanism is applied that is able to divert packets to other input switches if the next stage link/switch is already occupied by another packet. In this paper, an examination of RIN with an input-output connection (permutation) is carried out where the four disjoint paths have been used by other input-output connections. From the analysis conducted, it was found that the backtracking mechanism is very useful because it is able to cause RIN to be non-blocking, thereby increasing fault tolerance.