THORP: Choosing Ordered Neighbors To Attain Efficient Loop-Free Minimum-Hop Routing

We introduce THORP (Totally Hop-Ordered Routing Procedure), a simple distributed algorithm for minimum-hop routing that works in much the same way as traditional distance-vector routing algorithms do. THORP eliminates routing-table loops by having routers choose as their next hops to destinations those neighbor routers that are totally ordered based on their current distances, without requiring their next-hop routers to correspond necessarily to minimum-hop paths. THORP is shown to be loop-free, to converge to minimum-hop distances within a finite time, and to be faster than the Diffusing Update Algorithm (DUAL), which is the only loop-free shortest-path algorithm that has been used successfully in practice and is part of Cisco’s EIGRP.