Span-disjoint paths for physical diversity in networks

Diversity has been widely recognized as a critical factor for robustness in networks. In order to resist isolations due to link and node failures, we need to route along paths which are both span-disjoint (physically disjoint) and node-disjoint. In this way we can design the network for fault tolerance or graceful degradation. We demonstrate the procedure to obtain span-disjoint paths. This procedure may be applied to an arbitrary network topology, without restrictions on the span sharing configurations. In those cases where two completely disjoint paths do not exist, the procedure still tries to find a pair of paths which are as diverse as possible. The solution path pair we obtain is not guaranteed to be optimal, but gives us an optimal or near-optimal design, relatively quickly. The algorithm also accepts parameters which can be used to specify the cost-robustness tradeoffs.