Fault-tolerance and performance analysis of beta-networks

Abstract

The relationship between fault tolerance and performance is explored for [beta]-networks used as interconnection networks in multicomputer systems. The networks of interest are composed of 2 x 2 switches ([beta]-elements) and are represented by a graph model called a [beta]-graph. Two parameters derived from [beta]-graphs are used to characterize [beta]-networks. The fault tolerance (FT) parameter is the maximum number of [beta]-element faults that can be tolerated. The communication delay (CD) parameter, representing the worst-case delay between any pair of computers, is used as a measure of the performance of the [beta]-networks. Tight bounds for both FT and CD parameters are derived. Two important classes of [beta]-networks are introduced, namely, DPR-networks and MISE-networks. It is shown that DPR-networks possess the maximal fault tolerance, and the class of DPR-networks is unique in achieving the maximum possible fault tolerance. The class of MISE-networks is minimally fault tolerant, but has the minimum communication delay. A class of [beta]-networks, called RDTT-networks, that achieve an optimal balance of the FT and CD parameters is also presented.