Fault-tolerance for multistage interconnection networks

A new fault-tolerant multistage interconnection network architecture is proposed. Using k redundant processors and f redundant switching elements per stage, the authors scheme can tolerate any k processor failures and any f switching element failures per stage. A fault-tolerant multistage interconnection network constructed using their scheme can operate as if it is a non-redundant multistage interconnection network. That is, no additional control information is necessary for routing even when some initial processors and initial switching elements have already failed and been replaced. Furthermore, the reconfiguring process of replacing failed processors and failed switching elements with spare ones can be carried out distributively. The authors scheme also compares favorably with other proposed fault-tolerant multistage interconnection architectures in terms of extra hardware requirements and it can also provide higher system reliability than other proposed schemes. Finally, even for systems with a large number of processors, n⩾1024, their scheme can still achieve very high reliability. Hence, their scheme is well-suited for use in long-life unmaintained applications