Analysis of link reversal routing algorithms for mobile ad hoc networks

Costas Busch, Srikanth Surapaneni, Srikanta Tirthapura

Research output: Contribution to conferencePaperpeer-review

40 Scopus citations

Abstract

Link reversal algorithms provide a simple mechanism for routing in mobile ad hoc networks. These algorithms maintain routes to any particular destination in the network, even when the network topology changes frequently. In link reversal, a node reverses its incident links whenever it loses routes to the destination. Link reversal algorithms have been studied experimentally and have been used in practical routing algorithms, including TORA [8]. This paper presents the first formal performance analysis of link reversal algorithms. We study these algorithms in terms of work (number of node reversals) and the time needed until the network stabilizes to a state in which all the routes are reestablished. We focus on the full reversal algorithm and the partial reversal algorithm, both due to Gafni and Berstekas [5]; the first algorithm is simpler, while the latter has been found to be more efficient for typical cases. Our results are as follows: (1) The full reversal algorithm requires O(n2) work and time, where n is the number of nodes which have lost the routes to the destination. (2) The partial reversal algorithm requires O(n · a* + n2) work and time, where a* is a non-negative integer which depends on the state of the network. This bound is tight in the worst case, for any a*. (3) There are networks such that for every deterministic link reversal algorithm, there are initial states which require requires Ω(n2) work and time to stabilize. Therefore, surprisingly, the full reversal algorithm is asymptotically optimal in the worst case, while the partial reversal algorithm is not, since a* can grow arbitrarily large.

Original languageEnglish (US)
Pages210-219
Number of pages10
DOIs
StatePublished - 2003
Externally publishedYes
EventFifteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures - San Diego, SA, United States
Duration: Jun 7 2003Jun 9 2003

Conference

ConferenceFifteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures
Country/TerritoryUnited States
CitySan Diego, SA
Period6/7/036/9/03

Keywords

  • Ad Hoc Networks
  • Gafni-Berstekas
  • Link Reversal Routing

ASJC Scopus subject areas

  • Software
  • Safety, Risk, Reliability and Quality

Fingerprint

Dive into the research topics of 'Analysis of link reversal routing algorithms for mobile ad hoc networks'. Together they form a unique fingerprint.

Cite this