Extra group network: a cost-effective fault-tolerant multistage interconnection network

Abstract

This paper introduces a new class of fault-tolerant multistage interconnection networks, dubbed as Extra Group Networks (EGNs). An EGN- m of size N is designed to have m + 1 unique path multistage networks of size N/m . This approach of constructing the network allows that an EGN- m can provide “full access” capability in the presence of multiple faults, up to m , in any stage. EGNs can also maintain the permutation capability of the unique path multistage network of size N in the presence of any single fault. We show that EGNs are most cost-effective than other previously proposed fault-tolerant multistage interconnection networks with a similar fault-tolerant capability.