Open Source Mesh Routing Protocols
4 min read
This blog was originally published on October 16th, 2007. It was published on TypePad and can be found here.
There is an excellent discussion going on over in the Open Source Mesh Google Group.
James Ewing from Sveasoft gave an excellent rundown on the state of Open Source mesh protocols. He said: Couple thoughts on currently available mesh protocols and standards -
CuWIN - OSPF adapted to mesh networks. It is basically designed to connected seperate subnet "islands" into a larger network. If you want to link several local bu physically seperate community networks this would be a good protocol.
AODV - on-demand protocol. Bit of overhead for route discovery. No builtin wireless specific metrics in the RFC though specific implementations may exist.
OLSR - link-state protocol. The RFC spec requires each node to maintain a routing table for the entire mesh, which is impractical. No builtin wireless route metrics. The olsr.org implementation threw the RFC out the window and implemented a fisheye algorithm to limit route table size and an ETX metric for "best wireless route" discovery. The olsr.org implementation has been deployed in fairly large (1000+) node networks.
WDS - store and forward 802.11 semi-standard. It suffers from bandwidth halving at each hop (wheter you have 2 antennas or not). Not always interoperable among different OEM chipsets.
BATMAN - created as a reaction to percieved limitations in the olsr.org early implementations without the Fisheye or ETX modifications. Seems to be a stipped Internet node discovery protocol with a focus on wireless metrics for optimized routes. Currently at the alpha or pre-alpha stage.
SCrr - don't know much about this one. Seems to be a Djikstra algorithm based protocol like OSPF. A criticism in this post listes.ilesansfil.org/pipermail/mesh/2004-A.. says it does scale well. Apparently used in Meraki units.
802.11s - IEEE L2 mesh networking standard. Uses a modified and stripped form of AODV at L2 with a stripped version of OSLR as an option. Most chipset manufacturers seem to be lending support to 802.11s but the only implementation "in the wild" seems to be from Marvell via a firmware patch to their chips supplied to the OLPC (one laptop per child) organization. The OLPC firmware runs a ThreadX based micro kernel and apparently uses a proprietary virtual tunnel or repeater wireless protocol specific to Marvell for node-to-node communication. 802.11s uses a common channel for node discovery and provisioning, similar to how a cellular phone discovers its local network.
802.11n - multi-channel MIMO technique to increase thoughput over 802.11b/g and 802.11a networks. Since 802.11b/g has only 3 real channels using n is impractical in most real life situations as 2 of the 3 available are used for each n node. 802.11a has up to 31 separate channels and will likely be where 802.11n is practical.
I have some experience with the SrcRR protocol, but I was never really impressed by it. It was originally designed as a research protocol in the MIT Roofnet. The roofnet project consisted of 40-60 nodes spread around MIT. Each node's radio card was attached to a large high-gain dipole antenna, which was attached to the flashing or chimney of a partipant's roof. All in all, it is a really neat research project and idea, but the protocol shows its roots. It was designed with mesh healing as one of its primary attributes. This forces the nodes to communicate link information more and run a Dijkstra algorithm more often. Both of which take up considerable network and computational resources.
I have recently been turned on to the B.A.T.M.A.N. protocol. I haven't worked with it, but it appears to have better(more efficient) use of resources. It will determine the best link, and then stick with it. If that link goes down, it will look for a new one. I love the design, and developer's approach.
Forget city wide wireless. The most interesting mesh networks are going to be small-to-medium size, and they are going to be run on low cost Linux routers. I love the idea of a small efficient routing protocols on those little machines. It is definitely the approach to take.