A loop-free path-finding algorithm: specification, verification and complexity

The loop-free path-finding algorithm (LPA) is presented. LPA specifies the second-to-last hop and distance to each destination to ensure termination; in addition, it uses an inter-neighbor synchronization mechanism to eliminate temporary loops. A detailed proof of LPA´s correctness is presented and its complexity is evaluated. LPA´s average performance is compared by simulation with the performance of algorithms representative of the state of the art in distributed routing, namely an ideal link-state (ILS) algorithm and a loop free algorithm that is based on internodal coordination spanning multiple hops (DUAL). The simulation results show that LPA is a more scalable alternative than DUAL and ILS in terms of the average number of steps, messages, and operations needed for each algorithm to converge after a topology change. LPA is shown to achieve loop freedom at every instant without much additional overhead over that incurred by prior algorithms based on second-to-last hop and distance information