An Efficient Path Selection Algorithm for On-Demand Link-State Hop-by-Hop Routing
Abstract
Traditional routing protocols based on link-state information form a network topology through the exchange of link-state information by flooding or by reporting partial topology information, and by computing shortest routes to each reachable destination using a path-selection algorithm like Dijkstra's algorithm or the Bellman-Ford algorithm. However, in an on-demand, link-state routing protocol, no one node needs to know the paths to every other node in the network. Accordingly, when a node chooses a next hop for a given destination, it must be true that the next hop has reported a path to the same destination; otherwise, packets sent through that node would be dropped. In this paper, the authors present a new path-selection algorithm that, unlike traditional shortest path algorithms, computes shortest paths with the above on-demand routing constraint.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 2002
- Accession Number
- ADA461324
Entities
People
- J.J. Garcia-Luna-Aceves
- Soumya Roy
Organizations
- University of California, Santa Cruz