Fault-Tolerance of Dynamic-Full-Access Interconnection Networks

A β-network is an interconnection network composed of 2 ×2 crossbar switches called β-elements. This paper presents an analysis of the fault-tolerance of β-networks. A fault model is specified which allows β-elements to be stuck in either of their two normal states. A new connectivity property called dynamic full access (DFA) is introduced which serves as the criterion for fault tolerance. A fault is called critical if it destroys the DFA property; otherwise, it is noncritical. A minimal critical fault (MCF) is a critical fault none of whose proper subsets constitutes a critical fault. Two graph-theoretical characterizations of the minimal critical faults and the noncritical faults of a β-network are presented. Some applications of the theory developed here are discussed.