A PATH-FINDING ALGORITHM FOR LOOP-FREE ROUTING

A loop-free path-finding algorithm (LPA) is presented; this is the fir st routing algorithm that eliminates the formation of temporary routin g loops without the need for internodal synchronization spanning multi ple hops or the specification of complete or variable-size path inform ation, Like other previous algorithms, LPA operates by specifying the second-to-last hop and distance to each destination; this feature is u sed to ensure termination, In addition, LPA uses an interneighbor sync hronization mechanism to eliminate temporary routing loops, A detailed proof of LPA's correctness and loop-freedom property is presented and its complexity is evaluated, LPA's average performance is compared by simulation with the performance of algorithms representative of the s tate of the art in distributed routing, namely an ideal link-state (IL S) algorithm, a loop-free algorithm that is based on internodal coordi nation spanning multiple hops (DUAL) and a path-finding algorithm with out the interneighbor synchronization mechanism, The simulation result s show: that LPA is a more scalable alternative than DUAL and ILS in t erms of the average number of steps, messages, and operations needed f or each algorithm to converge after a topology change.