A highly adaptive distributed routing algorithm for mobile wireless networks

TLDR

Link‑reversal algorithms form a family of distributed routing protocols for mobile wireless networks. The authors propose a new temporally‑ordered routing protocol, TORA, for mobile, multihop wireless networks. TORA reacts to topology changes by executing a temporally‑ordered sequence of diffusing computations that perform directed link reversals, guided by a physical or logical clock. TORA is highly adaptive, efficient, and scalable, achieving localized single‑pass reactions to link failures and maintaining stability across network partitions, making it well suited for large, dense mobile networks.

Abstract

We present a new distributed routing protocol for mobile, multihop, wireless networks. The protocol is one of a family of protocols which we term "link reversal" algorithms. The protocol's reaction is structured as a temporally-ordered sequence of diffusing computations; each computation consisting of a sequence of directed link reversals. The protocol is highly adaptive, efficient and scalable; being best-suited for use in large, dense, mobile networks. In these networks, the protocol's reaction to link failures typically involves only a localized "single pass" of the distributed algorithm. This capability is unique among protocols which are stable in the face of network partitions, and results in the protocol's high degree of adaptivity. This desirable behavior is achieved through the novel use of a "physical or logical clock" to establish the "temporal order" of topological change events which is used to structure (or order) the algorithm's reaction to topological changes. We refer to the protocol as the temporally-ordered routing algorithm (TORA).