Trustworthy Systems

Sequence numbers do not guarantee loop freedom — AODV can yield routing loops

Authors

Rob van Glabbeek, Peter Hoefner, Wee Lum Tan and Marius Portmann

NICTA

Abstract

In the area of mobile ad-hoc networks and wireless mesh networks, sequence numbers are often used in routing protocols to avoid routing loops. It is commonly stated in protocol specifi?cations that sequence numbers are sufficient to guarantee loop freedom if they are monotonically increased over time. A classical example for the use of sequence numbers is the popular Ad hoc On-Demand Distance Vector (AODV) routing protocol. The loop freedom of AODV is not only a common belief, it has been claimed in the abstract of its RFC and at least two proofs have been proposed. AODV-based protocols such as AODVv2 (DYMO) and HWMP also claim loop freedom due to the same use of sequence numbers. In this paper we show that AODV is not a priori loop free; by this we counter the proposed proofs in the literature. In fact, loop freedom hinges on non-evident assumptions to be made when resolving ambiguities occurring in the RFC. Thus, monotonically increasing sequence numbers, by themselves, do not guarantee loop freedom.

BibTeX Entry

  @inproceedings{vanGlabbeek_HTP_13,
    address          = {Barcelona, Spain},
    author           = {van Glabbeek, Robert and H\"ofner, Peter and Tan, Wee Lum and Portmann, Marius},
    booktitle        = {16th ACM International Conference on Modeling, Analysis and Simulation of Wireless and Mobile
                        Systems},
    doi              = {10.1145/2507924.2507943},
    keywords         = {wireless mesh networks; mobile ad-hoc networks; loop freedom; routing protocols; aodv; process
                        algebra.},
    month            = nov,
    pages            = {91--100},
    paperurl         = {https://trustworthy.systems/publications/nicta_full_text/7276.pdf},
    publisher        = {ACM},
    title            = {Sequence Numbers Do Not Guarantee Loop Freedom --- {AODV} Can Yield Routing Loops},
    year             = {2013}
  }

Download