Incorporating Dependent Node Damage in Deterministic Survivability/Connectiv ity Analysis and Synthesis of Networks.

Deterministic analyses of the survivability of a communication network often include a simplifying assumption that failures of, or damages to, various components of the network are independent. This assumption can be quite unrealistic and can lead one to conclusions that are grossly in error. Survivability analysis and synthesis of robust networks should incorporate dependencies introduced by single events that affect large geographical areas. In this memorandum we present a model for deterministic dependence between the resources of a communication network. We generalize the definition of connectivity, an often used measure of network survivability, and present analysis and synthesis results, both theoretical and algorithmic. We introduce the notion of a dependence graph and define two types of dependence relations between pairs of nodes: strong dependence and weak dependence. Connectivity is defined as the minimum number of events, rather than the minimum number of node removals required to disconnect the network. Techniques are presented for calculating the (generalized) connectivity of a graph, and for synthesizing minimum link graphs with prescribed connectivity. Some of these techniques apply standard procedures to reduced versions of the original graph.