Path-Finding Algorithm for Loop-Free Routing

摘要

A loop-free path-finding algorithm (LPA) is presented: this is the first routing algorithm that eliminates the formation of temporary routing loops without the need for internodal synchronization spanning multiple hops or the specification of complete or variable-size path information. Like other previous algorithms, LPA operates by specifying the second-to-last hop and distance to each destination; this feature is used to ensure termination. In addition, LPA uses an inter-neighbor synchronization mechanism to eliminate temporary routing loops. A detailed proof of LPA's correctness and loop-freedom property is presented and its complexity is evaluated.