Optimal Physical Diversity Algorithms and Survivable Networks

One way to improve the reliability of a network is through physical diversity, i.e., via routing of trafic between a given pair of nodes in the network over two or more physically-disjoint paths such that if a node or a physical link fails on one of the disjoint paths, not all of the trafic is lost. Alternatively, enough spare capacity may be allocated on the individual paths such that the lost traflc due to a node or physical link failure can be routed immediately over the predetermined paths. In this paper, we present optimal algorithms for K-disjoint paths (K22) in a graph of vertices (or nodes) and edges (or links). These algorithms are simpler than those given in the past. We discuss how such algorithms can be used in the design of survivable mesh networks based on the digital crossconnect systems {DCS). We also discuss the generation of optimal network topologies which permit K>2 disjoint paths and upon which survivable networks may be modeled. 1