A highly adaptive distributed routing algorithm for mobile wireless networks

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)