An even better approach: improving the B.A.T.M.A.N. protocol through formal modelling and analysis

Ansgar Fehnker; Kaylash Chaudhary; Vinay Mehta

doi:10.1007/978-3-319-77935-5_12

An even better approach: improving the B.A.T.M.A.N. protocol through formal modelling and analysis

Ansgar Fehnker^*, Kaylash Chaudhary, Vinay Mehta

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

1 Citation (Scopus)

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 language	English
Title of host publication	NASA Formal Methods
Subtitle of host publication	10th International Symposium, NFM 2018 Newport News, VA, USA, April 17–19, 2018 Proceedings
Editors	Aaron Dutle, César Muñoz, Anthony Narkawicz
Place of Publication	Cham, Switzerland
Publisher	Springer, Springer Nature
Pages	164-178
Number of pages	15
ISBN (Electronic)	9783319779355
ISBN (Print)	9783319779348
DOIs	https://doi.org/10.1007/978-3-319-77935-5_12
Publication status	Published - 2018
Externally published	Yes
Event	10th International Symposium on NASA Formal Methods 2018, NFM 2018 - Newport News, United States Duration: 17 Apr 2018 → 19 Apr 2018

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	10811
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	10th International Symposium on NASA Formal Methods 2018, NFM 2018
Country/Territory	United States
City	Newport News
Period	17/04/18 → 19/04/18

Access to Document

10.1007/978-3-319-77935-5_12

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 (pp. 164-178). (Lecture Notes in Computer Science; Vol. 10811). Springer, Springer Nature. https://doi.org/10.1007/978-3-319-77935-5_12

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, Switzerland : Springer, Springer Nature, 2018. pp. 164-178 (Lecture Notes in Computer Science).

@inproceedings{fec99d4baaf04157a333f5c7039834d8,

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",

doi = "10.1007/978-3-319-77935-5_12",

language = "English",

isbn = "9783319779348",

series = "Lecture Notes in Computer Science",

publisher = "Springer, Springer Nature",

pages = "164--178",

editor = "Aaron Dutle and C{\'e}sar Mu{\~n}oz and Anthony Narkawicz",

booktitle = "NASA Formal Methods",

address = "United States",

note = "10th International Symposium on NASA Formal Methods 2018, NFM 2018 ; Conference date: 17-04-2018 Through 19-04-2018",

}

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, Springer Nature, Cham, Switzerland, pp. 164-178, 10th International Symposium on NASA Formal Methods 2018, NFM 2018, Newport News, Virginia, United States, 17/04/18. https://doi.org/10.1007/978-3-319-77935-5_12

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, Switzerland: Springer, Springer Nature, 2018. p. 164-178 (Lecture Notes in Computer Science; Vol. 10811).

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

TY - GEN

T1 - An even better approach

T2 - 10th International Symposium on NASA Formal Methods 2018, NFM 2018

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.

U2 - 10.1007/978-3-319-77935-5_12

DO - 10.1007/978-3-319-77935-5_12

M3 - Conference proceeding contribution

SN - 9783319779348

T3 - Lecture Notes in Computer Science

SP - 164

EP - 178

BT - NASA Formal Methods

A2 - Dutle, Aaron

A2 - Muñoz, César

A2 - Narkawicz, Anthony

PB - Springer, Springer Nature

CY - Cham, Switzerland

Y2 - 17 April 2018 through 19 April 2018

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, Switzerland: Springer, Springer Nature. 2018. p. 164-178. (Lecture Notes in Computer Science). doi: 10.1007/978-3-319-77935-5_12

An even better approach: improving the B.A.T.M.A.N. protocol through formal modelling and analysis

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this