A Loop-Free Algorithm Based on Predecessor Information
Abstract
The loop-free predecessor based routing algorithm (LPRA), is presented. This algorithm eliminates the formation of temporary routing loops without the need for internodal synchronization spanning multiple hops or the specification of complete path information. Like other algorithms, LPRA operates by specifying the second-to-last hop and distance to each destination; in addition, it uses an interneighbor synchronization mechanism. A detailed proof of correctness is presented and its complexity is evaluated. Its performance is compared by simulation with an ideal link-state algorithm and a loop-free algorithm (called DUAL) that is based on internodal coordination spanning multiple hops; both algorithms are representative of the state of the art in distributed routing algorithms. The simulation results show that LPRA is a better alternative than those two algorithms in terms of the number of steps needed to converge after a topological change and is comparable to DUAL in terms of the number of messages and CPU cycles needed to converge after a topological change.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 2006
- Accession Number
- ADA457149
Entities
People
- J.J. Garcia-Luna-Aceves
- Shree Murthy
Organizations
- University of California, Santa Cruz