Efficient Path Selection Algorithm for On-Demand Link-State Hop-by- Hop Routing

摘要

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.