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 traffic 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 traffic is lost. Alternatively, enough spare capacity may be allocated on the individual paths such that the lost traffic 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 (K/spl ges/2) 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 cross-connect 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. The study is of particular relevance to fiber networks.