A Simple, Practical Distributed Multi-Path Routing Algorithm
Johnny Chen, Peter Druschel, Devika Subramanian · 1998
We present a simple and practical distributed routing algorithm based on backward learning. The algorithm periodically floods scout packets that explore paths to a destination in reverse. Scout packets are small and of fixed size; therefore, they lend themselves to hop-by-hop piggy-backing on data packets, largely defraying their cost to the network. The correctness of the proposed algorithm is analytically verified. Our algorithm also has loop-free multi-path routing capabilities, providing increased network utilization and route stability. The Scout algorithm requires very little state and computation in the routers, and can efficiently and gracefully handle high rates of change in the network's topology and link costs. An extensive simulation study shows that the proposed algorithm is competitive with link-state and distance vector algorithms, particularly in highly dynamic networks. 1 Introduction We introduce a simple distributed routing algorithm that is based on the idea of ba...