B.A.T.M.A.N Protocol Concept (2011)

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.