Networks immune to isolated line failures

Abstract

Abstract A network is immune to a set of failures if all message transfers between operative sites can be completed in the presence of such failures. A set of line failures is isolated if no two failing lines are incident to the same site. Several classes of isolated line failure immune (ILFI) networks are defined, including a class with fewest lines for a given number of sites. An algorithm is presented which turns an arbitrary tree into one of these minimum ILFI networks and computes routing tables for the new network.