A distributed algorithm for finding shortest pairs of disjoint paths

摘要

A distributed asynchronous algorithm is presented for finding two disjoint paths of minimum total length from each possible source node to a destination. The algorithm has both node-disjoint and link-disjoint versions, and provides each node with information sufficient to make incremental routing decisions for forwarding packets over the disjoint paths. For a network in which all links have unit length, it is shown that a synchronous implementation of the algorithm has communication and time complexities O( mod E mod +D mod N mod ) and O(D/sub 2/), respectively, where D is the networks diameter and D/sub 2/ is the maximum, over all nodes i, of the total number of links in the shortest pair of disjoint paths from i to the destination.