Finding maximal link disjoint paths in a multigraph

The problem of fast restoration of lost transport facilities between nodes of the growing high-capacity fiber network has recently emerged as a principle concern of both network operators and their customers. At the same time, there is increasing use of intelligent cross-connects in the telephone network. It should be possible to use the computing and connection capacity of cross-connects to recover from facility outages by enabling the cross-connects to automatically reroute traffic in the event of facility damage or loss. An algorithm by which a network node might be able to establish as many paths as required (up to the theoretical maximum) between itself and another node with which it has lost part or all of its directly connecting transmission facilities is presented. The algorithm has been simulated on a Sun 3/60 workstation and is able to find all four paths of the example network in under one second