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.
展开▼
机译:提出了一种分布式异步算法,用于找到从每个可能的源节点到目标的最小总长度的两条不相交的路径。该算法具有节点不相交和链接不相交的版本,并为每个节点提供足以做出增量路由决策以通过不相交路径转发数据包的信息。对于所有链路都具有单元长度的网络,表明该算法的同步实现分别具有通信和时间复杂度O(mod E mod + D mod N mod)和O(D / sub 2 /),其中D是网络直径,D / sub 2 /是在所有节点i上,从i到目的地的最短不相交路径对中的链路总数中的最大值。
展开▼