Trustworthy Systems

A process algebra for wireless mesh networks used for modelling, verifying and analysing AODV

Authors

Ansgar Fehnker, Rob van Glabbeek, Peter Hoefner, Annabelle McIver, Marius Portmann and Wee Lum Tan

NICTA

UNSW

Macquarie University

University of Queensland

Abstract

Route finding and maintenance are critical for the performance of networked systems, particularly when mobility can lead to highly dynamic and unpredictable environments; such operating contexts are typical in wireless mesh networks. Hence correctness and good performance are strong requirements of routing protocols.

In this paper we propose AWN (Algebra for Wireless Networks), a process algebra tailored to the modelling of Mobile Ad hoc Network (MANET) and Wireless Mesh Network (WMN) protocols. It combines novel treatments of local broadcast, conditional unicast and data structures.

In this framework, we present a rigorous analysis of the Ad hoc On-Demand Distance Vector (AODV) protocol, a popular routing protocol designed for MANETs and WMNs, and one of the four protocols currently defined as an RFC (request for comments) by the IETF MANET working group.

We give a complete and unambiguous specification of this protocol, thereby formalising the RFC of AODV, the de facto standard specification, given in English prose. In doing so, we had to make non-evident assumptions to resolve ambiguities occurring in that specification. Our formalisation models the exact details of the core functionality of AODV, such as route maintenance and error handling, and only omits timing aspects.

The process algebra allows us to formalise and (dis)prove crucial properties of mesh network routing protocols such as loop freedom and packet delivery. We are the first to provide a detailed proof of loop freedom of AODV. In contrast to evaluations using simulation or other formal methods such as model checking, our proof is generic and holds for any possible network scenario in terms of network topology, node mobility, traffic pattern, etc. Due to ambiguities and contradictions the RFC specification allows several readings. For this reason, we analyse multiple interpretations. In fact we show for more than 5000 interpretations whether they are loop free or not. Thereby we demonstrate how the reasoning and proofs can relatively easily be adapted to protocol variants.

Using our formal and unambiguous specification, we find some shortcomings of AODV that can easily affect performance. Examples are non-optimal routes established by AODV and the fact that some routes are not found at all. These problems are analysed and improvements are suggested. As the improvements are formalised in the same process algebra, carrying over the proofs is again relatively easy.

BibTeX Entry

  @techreport{Fehnker_GHMPT_13:tr,
    address          = {Australia},
    author           = {Fehnker, Ansgar and van Glabbeek, Robert and H\"ofner, Peter and McIver, Annabelle and Portmann,
                        Marius and Tan, Wee Lum},
    institution      = {NICTA},
    issn             = {1833-9646-5513},
    month            = dec,
    number           = {5513},
    paperurl         = {https://trustworthy.systems/publications/nicta_full_text/5513.pdf},
    title            = {A Process Algebra for Wireless Mesh Networks used for Modelling, Verifying and Analysing {AODV}},
    year             = {2013}
  }

Download