Batman

Traditionally, nodes exchange control packets that contain information about the link state (current link utilization, bandwidth, etc).

• Nodes determine the best paths based on control packets.

• Every node must have exhaustive information about the entire network.

BATMAN takes a very different approach:

• The presence or absence of control packets is used to indicate link (and path) quality.

Operation

Each node has a set of direct-link neighbors.

• In the figure, node A has neighbors B and C. These are the nodes through which A sends and receives all its packets.

Each node in the network sends an Originator Message (OGM) periodically, in order to inform all other nodes of its presence.

• OGMs include a sequence number.

If all shown links are perfect, node A will receive node D's OGM through both of its neighbors B and C.

• If all of D's OGMs arrive through both B and C, then when A needs to send something to D, it can use either B or C as the next hop toward the destination node D.

If the link between nodes A and C goes down.

• Node D's OGM will only arrive at A through node B.

• Node A, therefore, considers node B as the best next-hop neighbor for all packets destined for node D.

• Further, node C's OGMs will also only reach node A through node B. Node B is the best next hop for data destined for node C.

BATMAN receives information about the link (and path) quality through the presence or absence of control packets.

• Collective intelligence - retransmission of an OGM implies it arrived successfully through a best-link neighbor.

• No need for nodes to have exhaustive knowledge of the network.

Sliding window

If some but not all OGMs arrive through a link.

• Sliding window.

A sliding window indicates which of the last WINDOW_SIZE (in the example, 8) sequence numbers have been received.

• Uses the sequence numbers received through OGMs.

Sequence numbers and sliding window

When an out-of-range sequence number is received, in this case, seq# 17, the window shifts up.

• From 6 sequence numbers in the range to only 5.

Routing table

All nodes have a sliding window for each originator (another node) in the network for each neighbor.

Transmission Quality (Batman v.3)

To add the local link quality to the TQ value the following calculation is performed:

• TQ = TQ_{incoming} * TQ_{local}

Example: Node A broadcasts the packet with TQ max. Node B receives it, applies the TQ calculation, and rebroadcasts it. When node C gets the packet it knows about the transmit quality towards node A.