|
Abstract : |
In this paper, we present a new routing algorithm, which we call 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, 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. 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 PFA constitutes a very efficient distancevector 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., |
