Sequence Numbers Do Not Guarantee Loop Freedom: AODV Can Yield Routing Loops

Rob van Glabbeek, Peter Höfner, Wee Lum Tan, Marius Portmann

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

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 specifications 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.
Original languageEnglish
Title of host publicationProceedings of the 16th ACM International Conference on Modeling, Analysis & Simulation of Wireless and Mobile Systems
Place of PublicationNew York, NY, USA
PublisherAssociation for Computing Machinery (ACM)
Pages91–100
Number of pages10
ISBN (Print)9781450323536
DOIs
Publication statusPublished - 3 Nov 2013
EventThe 16th ACM International Conference on Modeling, Analysis and Simulation of Wireless and Mobile Systems, 2013 - Barcelona, Spain
Duration: 3 Nov 20138 Nov 2013
Conference number: 16
http://mswimconf.com/2013/

Publication series

NameMSWiM '13
PublisherAssociation for Computing Machinery

Conference

ConferenceThe 16th ACM International Conference on Modeling, Analysis and Simulation of Wireless and Mobile Systems, 2013
Abbreviated titleMSWiM
Country/TerritorySpain
CityBarcelona
Period3/11/138/11/13
Internet address

Keywords / Materials (for Non-textual outputs)

  • AODV
  • wireless mesh networks
  • routing protocols
  • process algebra
  • loop freedom

Fingerprint

Dive into the research topics of 'Sequence Numbers Do Not Guarantee Loop Freedom: AODV Can Yield Routing Loops'. Together they form a unique fingerprint.

Cite this