An Algorithm for Multipath Computation using Distance-Vectors with Predecessor Information

Routing algorithms in the IP Internet provide a single path between each source-destination pair and where more than one path is provided, they are paths of equal length. Single-path routing is inherently slow in responding to congestion and temporary traffic bursts; multiple paths are better suited to handle congestion. Also the paths provided in RIP and OSPF are not free of loops during times of network transition, which can be debilitating to network performance. We present a distributed routing algorithm for computing multiple paths that need not have equal length between each source-destination pair in a computer network such that they are loop-free at every instant---in steady state as well as during network transitions. The algorithm is scalable to large networks as it uses only one-hop synchronization which is unlike diffusing computations that require internodal synchronization spanning multiple hops. The safety and liveness properties of the algorithm are proven and its compl..