Paper Info
Title
Sequence numbers do not guarantee loop freedom: AODV can yield routing loops
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 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.
Year
DOI
Venue
2013
10.1145/2507924.2507943
MSWiM
Keywords
Field
DocType
protocol specification,proposed proof,sequence number,common belief,distance vector,loop freedom,loop freedom hinge,mobile ad-hoc network,aodv-based protocol,classical example,process algebra,routing protocols,aodv
Ad hoc On-Demand Distance Vector Routing,Dynamic Source Routing,Computer science,A priori and a posteriori,Computer network,Destination-Sequenced Distance Vector routing,Mathematical proof,Wireless mesh network,Distance-vector routing protocol,Distributed computing,Routing protocol
Conference
Volume
ISSN
Citations 
abs/1512.08891
Proc. Modeling, Analysis and Simulation of Wireless and Mobile Systems, MSWiM'13, ACM, 2013, pp. 91-100
17
PageRank 
References 
Authors
0.77
18
4
Name
Order
Citations
PageRank
Rob J. van Glabbeek11930134.34
Peter Höfner239127.80
Wee Lum Tan335624.62
Marius Portmann41116.95