B.A.T.M.A.N

Welcome techies, I am sure that you landed up on this page because the title is the name of a famous superhero.

I am not going to write an article on the legendary Batman, but something very different. Neither is this article related to any gadgets that are used by Bruce Wayne in the famous movies.

What is it then?

Sorry for being a spoilsport, but the B.A.T.M.A.N we are talking about is a routing protocol.

Let us get into the details of this routing protocol.

According to the website, http://www.open-mesh.org, B.A.T.M.A.N is a routing protocol for multi -hop ad-hoc mesh networks. The acronym B.A.T.M.A.N stands for ‘Better Approach to Mobile Ad-hoc Networking’.

This protocol is under development by the ‘Freifunk’-community and is intended to replace OLSR. For those who do not know what OLSR means, here is a quick short summary: The Optimized Link State Routing Protocol or OLSR is an IP routing protocol developed and optimized for mobile ad-hoc networks, which can be used on other ad-hoc networks. It is a link state routing protocol that uses Hello and TC (Topology Control) messages to discover link state information through a mobile ad-hoc network. It computes the next hop destination using the shortest hop first forwarding paths.

Getting back to the topic, B.A.T.M.A.N was developed to create a protocol that was small, easy and fast as possible. Using the iterative process, the development was divided into three phases:

1. Version 1: The protocol was implemented and tested for its practicality and suitability for the task. UDP port number 1966 was used to send and receive the originator message.

2. Version 2: In radio networks, it is possible that devices are only capable of one-way transmission. Hence, a mechanism was introduced to the protocol to solve this problem. This mechanism allowed the node to determine whether a neighboring node provides bi-directional communication facility. Only bi-directional nodes were considered as a part of this network.

3. Version 3: Now a computer or a router running this protocol can be deployed on a central point. This system will have several wired or wireless network interfaces attached to it. When deployed, B.A.T.M.A.N can now relay data in one or more than one direction. There will be no transmission delays during this relay of data. Determining the best path during routing can cause unusual phenomena like circular routing that can hamper data from reaching its target destination. This issue was tackled and counteracted. B.A.T.M.A.N can be used to determine which gateway to be used based on criteria such as connection speed.

Announcing devices that are not running the B.A.T.M.A.N protocol were introduced in this version.

B.A.T.M.A.N’s crucial point is the decentralization of information regarding the best route through the network, thus no single node has all the data. This technique avoids the need to spread information concerning network changes to every node in the network.

A network of collective intelligence is developed because an individual node saves information only about the direction from which it received data and to send data accordingly. Hereby the data is passed on from node to node and packets get individual, dynamically created routes.

The basic strategy what B.A.T.M.A.N uses is to discover the next step to the destination node, but it does not concern itself with the entire path to the destination machine.

Routing in wireless mesh has made it difficult by the fact that such networks are noisy, and thus there is a high rate of packet loss and high amount of interference. It takes the advantage of the ‘Loss’ property by calculating a statistical analysis on loss of information and speed. Lost packets due to unreliable links are detected and are used for much enhanced routing decisions.

On a regular basis, each node sends a broadcast message, thereby informing all its neighbors about its existence. These neighbors can then relay this message to their respective neighbors and this goes on and on. In order to find out the best path, B.A.T.M.A.N counts the originator message and logs from which neighbor the message came in.

Besides the radio networks, B.A.T.M.A.N can utilize common cable connections such as Ethernet.

B.A.T.M.A.N maintains a table with best link local router towards every originator on the network.

The number of sequence numbers recorded in the sliding window is the metric to determine the quality of detected links and paths.

Properties:

• There are no routing loops in the network.
• No redundant or repetitive OGM messages from the same source.
• Each node in the network periodically broadcasts an originator message to its immediate neighbor.
• Only bi-directional links are present in the network.
• All OGMs that have entered the network will leave the network after one of the following conditions: every node has received at least one and re-broadcasting stops; they have been lost due to packet loss; their TTL value has expired.

When is a B.A.T.M.A.N packet dropped?

• When the OGM version number isn’t equal to the internal version number.
• If the sender address of the OGM is equal to the address of one of local interfaces.
• When the sender address of OGM equals the broadcast address of one of the B.A.T.M.A.N interfaces.
• If the unidirectional flag is set.

While broadcasting an OGM:

• Time to Live or TTL must be decremented by 1.
• The ‘is-direct-link’ bit MUST be set to one if the OGM was received from a direct-link neighbor AND if it is re-broadcasted over the link via which it was received.
• The unidirectional flag must be set if the OGM to be re-broadcasted was received via a unidirectional link.

Summary:

There are many other developments like Batman-adv, Batcave (Security for B.A.T.M.A.N) and RO.B.IN.

References:

• https://www.open-mesh.org/projects/open-mesh/wiki
• http://en.wikipedia.org/wiki/B.A.T.M.A.N.
• http://opensourcemesh.org/links.html
• http://bucs512.wordpress.com/2013/03/08/quick-overview-on-b-a-t-m-a-n/#more-16
• http://www.open-mesh.org/projects/batman-adv/wiki