B.A.T.M.A.N Protocol Concept (2011)
open-mesh.orgInteresting, the protocol seems to assume symmetrical performance i.e. X-...->Y and Y-...->X will have the same latency so long as they follow the same path?
Apparently it stands for "Better Approach To Mobile Ad-hoc Networking".
All mesh routing protocols suffer from O(N^2) path data and traffic, collapsing at a few thousand nodes.
this isn’t a theorem of network science, and is an easily avoided failure mode. plumtree? kad? aodv? you’re wrong :(
It's observed in practice.
Protocols that run over the internet don't count. I meant actual mesh routing.
aodv works great and is “actual mesh.” the ‘overlays’ scale in practice and are topology agnostic, the hierarchical bgp mesh underneath isn’t altering the message or memory complexity, we can talk about them as algorithms. there are 10ks node meshes in the real world that use batman, geography-contrained hub and spoke, etc. guifi has 37k nodes in its heterogenous mesh with a batman fork, freifunk (originator of batman) around 40k.
edit to add: what is observed in practice is that gossip protocols can’t coordinate peers without centralizing. this is natural, and an artifact of the logarithmics in the routing protocols. the appropriate thing to do is model routing as a revocable proof system, and information theory explains the centralizing dynamics (problem I worked on 2018-2019) https://eprint.iacr.org/2022/1478 proves the global lower bound is linear (in route updates, when applied to routing, naively quadratic if distributed), and the trick routing protocols add to the game is locality, which yields the logarithmic advantage that when multiplied across the entire network is substantially subquadratic.