The problem they solve
In a mesh network of moving radios, nobody hands out routes. Each device has to work out, by talking to its neighbours, which neighbour to pass a message to so it reaches a device several hops away. Links appear and vanish as devices move, so whatever a device learns goes stale.
The IETF working group on mobile ad hoc networks (MANETs) described this setting in RFC 2501: nodes “free to move arbitrarily”, topologies that change “randomly and rapidly”, links with limited and variable capacity, and devices running on batteries. AODV, OLSR and BATMAN are three widely documented answers. They differ mainly in when they do the work of finding routes, and how much of the network each device tries to know.
AODV: find a route when you need one
The Ad hoc On-Demand Distance Vector protocol is specified in RFC 3561, an Experimental RFC published in 2003. It is reactive: it does nothing for a pair of devices until one of them has something to send.
- Route request. A device that needs a route broadcasts a route request (RREQ). Neighbours rebroadcast it outwards, each recording which neighbour it came from, so a path back to the sender forms as it spreads.
- Route reply. When the request reaches the destination, or a device with a fresh enough route to it, a route reply (RREP) is unicast back along that reverse path.
- Route error. Devices watch the next hops on routes in use. When a link breaks, a route error (RERR) tells the devices that were relying on it.
To keep routes loop-free, AODV attaches to every route a destination sequence number, created by the destination itself, and a device given two routes must pick the one with the greater number. To avoid flooding the whole network for every request, a sender can use an expanding ring search, starting with a small hop limit and widening it only if no reply comes.
The cost of this design is delay at the start: the first message to a new destination waits while a route is found.
OLSR: keep a map ready
The Optimized Link State Routing protocol was first published as RFC 3626, also Experimental and from 2003. It is proactive and table-driven: every router exchanges topology information regularly, so it holds routes to every destination before anyone asks.
OLSR is an optimisation of classic link-state routing, built to cut the number of transmissions needed on a shared radio channel. Its key idea is the multipoint relay (MPR). Each router chooses a subset of its neighbours that together reach all its two-hop neighbours. Only MPRs rebroadcast flooded control messages, and only MPRs need to advertise link-state information, which is enough to compute shortest paths.
OLSRv2, published as Standards Track RFC 7181 in 2014, keeps those mechanisms and adds link metrics other than hop count, so a router can prefer a route over good links to a shorter route over poor ones. It separates flooding MPRs from routing MPRs, and builds on the MANET Neighborhood Discovery Protocol (RFC 6130) and a common packet format (RFC 5444).
The cost here is constant background traffic, even when nobody is sending data.
BATMAN: know only the next hop
B.A.T.M.A.N., short for Better Approach To Mobile Ad-hoc Networking, is developed and documented by the open-mesh.org project. Its designers argued that a link-state protocol’s need to recalculate the whole topology graph is hard on small embedded routers.
Instead, each node periodically broadcasts a small originator message (OGM) with its address and a sequence number. Neighbours rebroadcast it according to set rules, so it floods the network. A node never builds a map. It notes which neighbour delivers a given originator’s messages most often and most reliably, and treats that neighbour as the best next hop towards that originator. Messages that travel over poor links arrive less often, so poor paths lose out.
BATMAN has evolved through versions. B.A.T.M.A.N. IV added a Transmit Quality measure to cope with links that work better in one direction than the other. B.A.T.M.A.N. V moves neighbour discovery to a separate Echo Location Protocol and uses throughput, rather than packet loss, as its metric.
Its kernel implementation, batman-adv, works at layer 2: it carries Ethernet frames and makes the whole mesh look like one virtual switch, so protocols such as IPv4, IPv6 and DHCP run over it unchanged.
How they compare
| AODV | OLSR / OLSRv2 | BATMAN | |
|---|---|---|---|
| When routes are found | On demand | Continuously | Continuously |
| What each device knows | Routes in active use | Topology of the network | Best next hop per destination |
| Path choice | Fresh sequence number, fewer hops | Shortest path; OLSRv2 adds link metrics | Most reliable (IV) or highest throughput (V) next hop |
| Specification | RFC 3561, Experimental | RFC 3626, Experimental; RFC 7181, Standards Track | open-mesh.org documentation; Linux kernel module |
RFC 2501 sums up the basic trade-off. Demand-based operation can use energy and bandwidth more efficiently “at the cost of increased route discovery delay”; proactive operation avoids that delay where bandwidth and energy allow. The batman-adv kernel documentation makes the same point about its own tuning: a lower originator interval makes the mesh more responsive to topology changes “but will also increase the overhead”.
All three run beneath applications, in routers and operating system network stacks. A mesh built inside an app, such as one over Bluetooth LE between phones, sits at a different layer, but it faces the same questions: how to learn neighbours, when to spend airtime on route information, and how to react when devices move.