Loop-free multipath routing using generalized diffusing computations

Abstract

A new distributed algorithm for the dynamic computation of multiple loop-free paths from source to destination in a computer network or Internet are presented, validated, and analyzed. According to this algorithm, which is called DASM (diffusing algorithm for shortest multipath), each router maintains a set of entries for each destination in its routing table, and each such entry consists of a set of tuples specifying the next router and distance in a loop-free path to the destination. DASM guarantees instantaneous loop freedom of multipath routing tables by means of a generalization of Dijkstra and Scholten's diffusing computations. With generalized diffusing computations, a node in a directed acyclic graph (DAG) defined for a given destination has multiple next nodes in the DAG and is able to modify the DAG without creating a directed loop. DASM is shown to be loop-free at every instant, and its average performance is analyzed by simulation and compared against an ideal link-state algorithm and the diffusing update algorithm (DUAL).