An Even Better Approach: Improving the B.A.T.M.A.N. Protocol Through Formal Modelling and Analysis

Ansgar Fehnker, Kaylash Chaudhary, Vinay Mehta

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

    Abstract

    This paper considers a network routing protocol known as Better Approach to Mobile Adhoc Networks (B.A.T.M.A.N.). The protocol has two aims: first, discovery of all bidirectional links, and second, identification of the best-next-hop to the other nodes. A key mechanism of the protocol is to flood the network at regular intervals with so-called originator messages.
    In previous work we formalised the B.A.T.M.A.N. protocol in Uppaal and found several ambiguities and inconsistencies [2]. More importantly, explicit choices in the RFC had, unfortunately, a negative impact on route discovery. This previous work compared a literal model based of the RFC with an incremental improvement. This paper goes one step further and proposes an alternative that departs from the RFC. We compare the performance using simulations in Uppaal, for static as well as dynamic topologies. The analysis shows that the proposed alternative reduces the number of suboptimal routes significantly, and recovers better from routing errors that are introduced by mobility.
    Original languageEnglish
    Title of host publicationNASA Formal Methods
    Subtitle of host publication10th International Symposium, NFM 2018 Newport News, VA, USA, April 17-19, 2018 Proceedings
    EditorsAaron Dutle, César Muñoz, Anthony Narkawicz
    Place of PublicationCham
    PublisherSpringer
    Number of pages15
    ISBN (Electronic)978-3-319-77935-5
    ISBN (Print)978-3-319-77934-8
    Publication statusPublished - 2018
    Event10th International Symposium on NASA Formal Methods 2018 - Newport News Marriott at City Center, Newport News, United States
    Duration: 17 Apr 201819 Apr 2018
    Conference number: 10
    https://shemesh.larc.nasa.gov/NFM2018/

    Publication series

    NameLecture Notes in Computer Science
    PublisherSpringer
    Volume10811
    ISSN (Print)0302-9743

    Conference

    Conference10th International Symposium on NASA Formal Methods 2018
    Abbreviated titleNFM 2018
    CountryUnited States
    CityNewport News
    Period17/04/1819/04/18
    Internet address

    Fingerprint Dive into the research topics of 'An Even Better Approach: Improving the B.A.T.M.A.N. Protocol Through Formal Modelling and Analysis'. Together they form a unique fingerprint.

  • Cite this

    Fehnker, A., Chaudhary, K., & Mehta, V. (2018). An Even Better Approach: Improving the B.A.T.M.A.N. Protocol Through Formal Modelling and Analysis. In A. Dutle, C. Muñoz, & A. Narkawicz (Eds.), NASA Formal Methods: 10th International Symposium, NFM 2018 Newport News, VA, USA, April 17-19, 2018 Proceedings (Lecture Notes in Computer Science; Vol. 10811). Cham: Springer.