Networks immune to isolated failures

Abstract

Abstract The notion of isolated failure immune (IFI) networks is introduced. A network is an IFI network if and only if all message transfers between operating sites can be completed as long as all site and line failures are isolated. Failures occurring at any time are isolated if they are pairwise isolated. A pair of site failures is isolated if the down sites are not neighbors. A pair of line failures is isolated if the lines are not incident to a common site. A site and a line failure are isolated if the down line is not incident to a neighbor of the down site. We show that 2‐trees are minimum IFI networks. An algorithm is described which adds lines to an arbitrary tree network to produce an IFI network (a 2‐tree). The algorithm also determines routing tables which allow a simple calling protocol to complete all message transfers between operative sites under isolated failures. Specializations and generalizations of our notion of IFI networks are discussed and issues for future research are proposed.