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

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

1 Citation (Scopus)

2 Downloads (Pure)

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
Publisher	Springer
Pages	164-178
Number of pages	15
ISBN (Electronic)	978-3-319-77935-5
ISBN (Print)	978-3-319-77934-8
DOIs	https://doi.org/10.1007/978-3-319-77935-5_12
Publication status	Published - 2018
Event	10th International Symposium on NASA Formal Methods 2018 - Newport News Marriott at City Center, Newport News, United States Duration: 17 Apr 2018 → 19 Apr 2018 Conference number: 10 https://shemesh.larc.nasa.gov/NFM2018/

Publication series

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

Conference

Conference	10th International Symposium on NASA Formal Methods 2018
Abbreviated title	NFM 2018
Country/Territory	United States
City	Newport News
Period	17/04/18 → 19/04/18
Internet address	https://shemesh.larc.nasa.gov/NFM2018/

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. 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 : Springer, 2018. pp. 164-178 (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",

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

language = "English",

isbn = "978-3-319-77934-8",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "164--178",

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

booktitle = "NASA Formal Methods",

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

url = "https://shemesh.larc.nasa.gov/NFM2018/",

}

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, pp. 164-178, 10th International Symposium on NASA Formal Methods 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: Springer, 2018. p. 164-178 (Lecture Notes in Computer Science; Vol. 10811).

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

TY - GEN

T1 - An Even Better Approach

T2 - 10th International Symposium on NASA Formal Methods 2018

AU - Fehnker, Ansgar

AU - Chaudhary, Kaylash

AU - Mehta, Vinay

N1 - Conference code: 10

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 contribution

SN - 978-3-319-77934-8

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

CY - Cham

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: Springer. 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