A fault-tolerant scheme for multistage interconnection networks

A scheme is proposed to enhance the fault-tolerance of multistage interconnection networks which only have a unique path between each input/output pair (e.g. Omega networks, Baseline networks, etc.). It is done by creating multiple paths between each input/output pair of the network through extra links between switching elements in the same stage. This scheme requires a simple routing algorithm and allows a network to become more robust as its size increases. A reliability analysis is presented to provide a quantitative measurement on the improvement of its fault-tolerance capability. In terms of reliability, a network implemented with this scheme is more cost-effective than a regular one.