Modelling, Verification, and Comparative Performance Analysis of the B.A.T.M.A.N. Protocol

Kaylash Chaudhary, Ansgar Fehnker, Vinay Mehta

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    2 Citations (Scopus)

    Abstract

    This paper considers on a network routing protocol known as Better Approach to Mobile Ad hoc Networks (B.A.T.M.A.N.). The protocol serves two aims: first, to discover all bidirectional links, and second, to identify the best-next-hop for every other node in the network. A key element is that each node will flood the network at regular intervals with so-called originator messages.
    This paper describes in detail a formalisation of the B.A.T.M.A.N. protocol. This exercise revealed several ambiguities and inconsistencies in the RFC. We developed two models. The first implements, if possible, a literal reading of the RFC, while the second model tries to be closer to the underlying concepts. The alternative model is in some places less restrictive, and rebroadcasts more often when it helps route discovery, and will on the other hand drop more messages that might interfere with the process.

    We verify for a basic untimed model that both interpretations ensure loop-freedom, bidirectional link discovery, and route-discovery. We use simulation of a timed model to compare the performance and found that both models are comparable when it comes to the time and number of messages needed for discovering routes. However, the alternative model identifies a significantly lower number of suboptimal routes, and thus improves on the literal interpretation of the RFC.
    Original languageEnglish
    Title of host publicationProceedings 2nd Workshop on Models for Formal Analysis of Real Systems, MARS@ETAPS 2017
    Subtitle of host publicationUppsala, Sweden, 29th April 2017
    EditorsHolger Hermanns, Peter Höfner
    PublisherEPTCS
    Pages53-65
    Number of pages13
    DOIs
    Publication statusPublished - 2017
    Event2nd Workshop on Models for Formal Analysis of Real Systems, MARS 2017 - Uppsala, Sweden
    Duration: 29 Apr 201729 Apr 2017
    Conference number: 2
    http://mars-workshop.org/mars2017/

    Publication series

    NameElectronic Proceedings in Theoretical Computer Science (EPTCS)
    PublisherEPTCS
    Volume244
    ISSN (Print)2075-2180

    Conference

    Conference2nd Workshop on Models for Formal Analysis of Real Systems, MARS 2017
    Abbreviated titleMARS
    CountrySweden
    CityUppsala
    Period29/04/1729/04/17
    Internet address

      Fingerprint

    Cite this

    Chaudhary, K., Fehnker, A., & Mehta, V. (2017). Modelling, Verification, and Comparative Performance Analysis of the B.A.T.M.A.N. Protocol. In H. Hermanns, & P. Höfner (Eds.), Proceedings 2nd Workshop on Models for Formal Analysis of Real Systems, MARS@ETAPS 2017: Uppsala, Sweden, 29th April 2017 (pp. 53-65). (Electronic Proceedings in Theoretical Computer Science (EPTCS); Vol. 244). EPTCS. https://doi.org/10.4204/EPTCS.244.3