Better Approach To Mobile Ad hoc Networking (B.A.T.M.A.N.)

des-batman is our Better Approach To Mobile Ad-hoc Networking (B.A.T.M.A.N.) protocol implementation as a variant for underlay routing.

Description:

B.A.T.M.A.N. was developed as an alternative to OLSR. The assumption is that traditional routing algorithms actually do not work well in mobile ad-hoc networks because of link quality fluctuations, frequent new or lost links, etc. When the routing protocol finds a (optimal) route, it can become suboptimal after some time. Many routing protocols do not immediately react to topology changes which makes them inefficient.

B.A.T.M.A.N. provides a new approach for the route discovery that can considered somewhere between the ideas of AODV and OLSR. All nodes periodically broadcast so called Originator Messages (OGM) that contain the node's address, a sequence number, and a TTL. The tuple source address and sequence number makes the packet identifiable and enables duplicate detection. When a nodes receives an OGM it updates its routing table that mainly contains the following information:

• Originator address: source address of the sender of the OGM
• Current sequence number: sequence number of the last OGM; used to detect duplicates and outdated information
• Sliding windows: one sliding window list of sequence numbers is stored for each originator and each previous hop, i.e., neighbor that forwarded or originated the OGM

The receiver of the OGM will then decrease the TTL and forwarded it to its neighbours. When the same OGM arrives over different paths at a node, all but the first copy will be dropped. Bidirectional links are detected by overhearing the forwarding of the nodes' OGMs by their neighbors.

The sliding windows are used to determine the best next hop for each destination. The number of entries in the windows is evaluated and the neighbor from which the most OGMs arrived from the destination is selected.

Variants:

• des-batman: implementation close to the RFC but with the Packet ID and precursor list mode modification as specified below
• des-namtab: based on des-batman but uses the inversed link metric as specified below
• des-satman: based on des-batman but uses 3-way-OGMs as specified below

Deviations from the Internet-Draft:

• Host Network Announcement (HMA), section 3.1., page 5 and section 3.3., page 8 and section 5.1., page 12. The des-batman implementation currently provides no gateways to other networks as it is out of our focus.
• Packet ID is an modification to avoid looping data packets as only OGMs have normally a sequence number. In some first experiments we noticed that while the loop detection of OGMs works, data packets began to loop at some point.
• 3-way-OGMs are an optional feature where OGMs that are received by node B from node A are only forwarded, after a packet has been sent from B to A and was then acknowledged by A.
• Precursor List Mode is an option where OGMs are evaluated even when the sequence number of a received OGM is equal to the last sequence number in the routing table. This modification was implemented to optimize the protocol for multiple-transceiver devices: when two nodes are connected by multiple interfaces over multiple links, only the OGM that arrived first was used to update the sliding windows. To still be able to detect loops when the sequence number is not higher, a list of precursors, i.e., nodes that forwarded the OGM is contained in the header. This is the same approach as in DSR where the path is accumulated.
• Inversed link metric is an option where each node adds additional information to its OGMs. For each link the number of received OGMs is advertised so that the neighbors can determine the link quality. This way the links quality is determined in the the inversed direction compared to default B.A.T.M.A.N. but in the direction that the data packets will eventuall flow. Especially in networks with many asymmetric or unidirectional links, the routing will be improbed. The option additionally allows to make better use of unidirectional links.