AN ANALYSIS OF EDGE FAULT-TOLERANCE IN RECURSIVELY DECOMPOSABLE REGULAR NETWORKS

Fault tolerance of interconnection networks is one of the major consid erations in evaluating the reliability of large scale multi-processor systems. In this paper, the reliability of a family of regular network s with respect to edge failures is investigated using four different f ault tolerance measures. Two probabilistic measures, resilience and re stricted resilience, are developed, used to evaluate disconnection lik elihoods using two different failure models, and compared with corresp onding deterministic measures. The network topologies chosen for the p resent study all have the recursive decomposition property, where larg er networks can be decomposed into copies of smaller networks of the s ame topology. This family of graphs includes the k-ary n-cube, star an d cube connected cycle graphs, which have optimal deterministic connec tivities. The probabilistic fault tolerance measures, however, are fou nd to depend on topological properties such as network size and degree .