A new approach to on-demand loop-free multipath routing

Abstract

We present and verify ROAM, an on-demand routing algorithm that maintains multiple loop-free paths to destinations. Each router maintains entries only for those destinations for which data flows through the router which reduces storage space requirements and the amount of bandwidth needed to maintain correct routing tables. In ROAM, routes are established and maintained on demand using diffusing computations. A router does not send updates for active destinations, unless its distance to them increases beyond a given threshold. ROAM maintains a state that informs routers when a destination is unreachable and prevents routers from sending unnecessary search packets attempting to find paths to an unreachable destination. ROAM is shown to converge in a finite time after an arbitrary sequence of topological changes and is shown to be loop-free at every instant. The time and communication complexities of ROAM are analyzed.