A more efficient path-finding algorithm

Publisher Website
Google Scholar
Abstract
Presents a new routing algorithm, which the authors call a path-finding algorithm (PFA). It drastically reduces the possibility of temporary routing loops, which accounts for its fast convergence properties. Like other path-finding algorithms, the PFA operates by specifying the second-to-last hop to each destination, in addition to the distance to the destination. A detailed proof of correctness and complexity is presented elsewhere. The PFA's performance is compared quantitatively by simulation with DUAL (a loop-free routing algorithm) and an ideal link-state algorithm (ILS). A number of parameters, including the length of the messages and the number of steps required for convergence, are used in the comparison. The simulation results indicate that the PFA constitutes a very efficient distance-vector algorithm. It provides about 50% improvement in performance compared to DUAL in terms of the convergence time and the number of updates after single link failures, and provides comparable or better convergence speed and traffic overhead than ILS, with orders of magnitude fewer CPU cycles.

This publication has 3 references indexed in Scilit: