Loop-free multipath routing using generalized diffusing computations

Publisher Website
Google Scholar
Abstract
A new distributed algopithmfor the dynamic computation of mul- tlple loop-free pathsf~om source to destination in a computer net- work or internet arepresented, validated, and analyzed, According to this algorithms, which is called DASM (D@using Algorithm for Shortest Multzpath), each router maintains a set of entries for each destination in its routing table, and each such ent~ consists of a set of tuples spect~ing 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 ofDijkstra and Scholten 's dljiising computations, With generalized d@sing computations, a node in a directed acyclic graph (DAG) dejined for a given destination has multiple next nodes in the DAG and is able to modlfi the DAG without creating a directed loop. DASM is shown to be loop-free at eve~ instant, and its average performance is analyzed by simulation and compared against an ideal link-state algorithm and the D@using Update Algorithm (DUAL).

This publication has 11 references indexed in Scilit: