On Independently Finding Converging Paths in Internet

F. Dai and J. Wu (USA)


Converging paths, Dijkstra’s shortest path algorithm, Internet routing protocols, shortest paths


Two shortest paths P(u, v) and P ( v, u) are called con verging paths if path P(u, v) is exactly the reversal of path P ( v, u). Independently finding two converging paths, one from node u and the other from node v, is not trivial even if both nodes have the correct and complete network link state information. This paper presents three different converging path algorithms. The first one is a simple extension to the Dijkstra’s shortest path algorithm. The other two make use of the routing information associated with each node. Both theoretical complexity and simulated performance results for these algorithms are given and discussed.

Important Links:

Go Back