Fault tolerance of beta-networks in interconnected multicomputer systems
John Paul Shen · 1981
Several proposals have been made recently for using a class of connecting networks called (beta)-networks in multicomputer systems. A (beta)-network is a connecting network composed of 2 x 2 crossbar switches called (beta)-elements. This dissertation presents a study of the fault tolerance of (beta)-networks intended for multicomputer applications. A fault model is specified which allows (beta)-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 in (beta)-networks. A fault is called critical if it destroys the DFA property. 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 and noncritical faults of a (beta)-network are presented. A (beta)-network is defined to be k-fault tolerant or k-FT if the failure of any k or fewer (beta)-elements does not destroy DFA. The largest k for which a (beta)-network is k-FT is called the fault-tolerance (FT) parameter of the (beta)-network. In the synthesis of practical fault-tolerant (beta)-networks, network performance must also be considered. A performance criterion called the communication-delay (CD) parameter is introduced, which is defined as the worst possible transmission delay through the (beta)-network, measured in terms of the number of intervening (beta)-elements between any pair of communicating devices. It is proven that the FT parameter k and CD parameter of any (beta)-network with n (beta)-elements must satisfy the following bounds:^ 0 (LESSTHEQ) k (LESSTHEQ) n-1 (,(R-PERP))log(,2)n(,(L-PERP)) + 1 (LESSTHEQ) d (LESSTHEQ) n.^ These bounds are shown to be tight. The modified inverse shuffle-exchange (MISE) network is shown to have FT parameter k=1 and CD parameter d= (,(R-PERP))log(,2)n(,(L-PERP)) + 1. Another network called the double parallel ring (DPR) network is shown to have FT parameter k=n-1 and CD parameter d=n. The DPR-network is unique in achieving the maximum value n-1 of the FT parameter. The preceding theoretical results are applied to the analysis of various (beta)-network structures. Some general properties of cascaded (beta)-networks are derived. FT and CD parameters are obtained for several well-known (beta)-networks.