We gave a brief introduction about BATMAN in the earlier post, now we expand it more and explain how its algorithm works.
B.A.T.M.A.N., is a proactive routing protocol for mobile ad-hoc networking. Nodes within the network maintain fresh lists of destinations, called Originators, and properties about those Origina- tors. The basic strategy of B.A.T.M.A.N. is to find the best next-hop to the destination Originator given the source’s direct-link neighbors. The protocol is not concerned with the full forwarding path; it only chooses the best next-hop for a packet as a function of its intended destination.
Routing in wireless mesh networks is made difficult by the fact that such network can be noisy and, therefore, have high rates of interference and packet loss. B.A.T.M.A.N. takes advantage of these loss properties by doing statistical analysis on loss information and propagation speed. Although it does not depend explicitly on information from other nodes, it does depend on the receipt of control- plane packets from other nodes to be able to make routing decisions. Lost protocol packets due to unreliable links are not countered with redundancy, but are detected and utilized for better routing decisions.
Under this scheme, B.A.T.M.A.N. gives guarantees regarding the successful routing of packets, a list of which will be given in later post.
B.A.T.M.A.N. detects the presence of other Originators in the mesh network regardless of the number of hops in a communication path. Based on the magnitude and recency of these detections, the protocol learns which link-local neighbor is the best gateway to each Originator without calculating the full routing path.
Every node in the network, on a regular basis, broadcast an Originator message, or OGM, to in- form its link-local neighbors about its existence. In the literature, this mechanism is often described as a ”heartbeat mechanism.” Upon receipt of an OGM, several checks are performed. Only OGMs that satisfies certain conditions will be received by the link-local neighbors. Then, those link-local neighbors can relay OGMs by re-broadcasting them to its neighbors. This flooding process is there- fore first performed by single-hop neighbors, then by two-hop neighbors, third-hop neighbors, and so forth until every node has received a re-broadcast of the original OGM or until the TTL value expires.
To facilitate each node’s responsibility to calculate the best first-hop destination for every Orig- inator, two key data structures are used: a sequence number which is unique to the initial broadcast of an OGM and a sliding window which counts the number of these sequence-numbered OGMs in a range at every node. The total count of all sequence numbers received in the sliding window is the metric for how well a given neighbor should be regarded as a gateway for some Originator. The direct-link neighbor with the greatest such count of sequence numbers in the sliding window is then considered the best first-hop link for a given Originator node.
For example, consider the mesh network figure below. There, a source node (in red) is attempting to route a packet through the network to a destination node (in purple). To do this, the source examines how many Originator messages it has recently received (in the sliding window) from the destination via each of its direct-link neighbors (in blue). Because the left-most link has received the most mentions of the destination, that is selected as the first-hop link.
Using this algorithm, B.A.T.M.A.N. provides a variety of safety and service guarantees. We outline those in the later post.