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

Wireless networks
Network protocols
Computer simulation
Network routing
Routing protocols
Topology

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.
Fehnker, Ansgar ; Chaudhary, Kaylash ; Mehta, Vinay. / An Even Better Approach : Improving the B.A.T.M.A.N. Protocol Through Formal Modelling and Analysis. NASA Formal Methods: 10th International Symposium, NFM 2018 Newport News, VA, USA, April 17-19, 2018 Proceedings. editor / Aaron Dutle ; César Muñoz ; Anthony Narkawicz. Cham : Springer, 2018. (Lecture Notes in Computer Science).
@inproceedings{fb81788b6bbb45699d097a5c657c404b,
title = "An Even Better Approach: Improving the B.A.T.M.A.N. Protocol Through Formal Modelling and Analysis",
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.",
author = "Ansgar Fehnker and Kaylash Chaudhary and Vinay Mehta",
year = "2018",
language = "English",
isbn = "978-3-319-77934-8",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
editor = "Aaron Dutle and C{\'e}sar Mu{\~n}oz and Anthony Narkawicz",
booktitle = "NASA Formal Methods",

}

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, Springer, Cham, 10th International Symposium on NASA Formal Methods 2018, Newport News, United States, 17/04/18.

An Even Better Approach : Improving the B.A.T.M.A.N. Protocol Through Formal Modelling and Analysis. / Fehnker, Ansgar; Chaudhary, Kaylash; Mehta, Vinay.

NASA Formal Methods: 10th International Symposium, NFM 2018 Newport News, VA, USA, April 17-19, 2018 Proceedings. ed. / Aaron Dutle; César Muñoz; Anthony Narkawicz. Cham : Springer, 2018. (Lecture Notes in Computer Science; Vol. 10811).

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

TY - GEN

T1 - An Even Better Approach

T2 - Improving the B.A.T.M.A.N. Protocol Through Formal Modelling and Analysis

AU - Fehnker, Ansgar

AU - Chaudhary, Kaylash

AU - Mehta, Vinay

PY - 2018

Y1 - 2018

N2 - 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.

AB - 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.

M3 - Conference contribution

SN - 978-3-319-77934-8

T3 - Lecture Notes in Computer Science

BT - NASA Formal Methods

A2 - Dutle, Aaron

A2 - Muñoz, César

A2 - Narkawicz, Anthony

PB - Springer

CY - Cham

ER -

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