Never got around to finishing a full routing algorithm, though we did have a lot of fun testing wacky network topologies and protocols that solved subsets of the problem.
The closest we came was designing a 2 or 3 tiered system, where nodes self-arrange into clusters of up to 256 nodes with one elected leader to coordinate. The routing table is replicated on all nodes (eventually consistent), but the leader handles all changes. Then there's Layer 2 routing between clusters with a similar leader election system to handle inter-cluster routing.
We tried to figure out a way to make the routing stateless, (e.g. by encoding a node's position in the graph in its id, sort of like a phone number has a country code, then area code, etc.), but stopped working on it before figuring out a good approach for broadcasting ID changes without flooding the network with broadcast traffic beyond small network sizes.
Nowadays there are established mesh routing algorithms that solve all these problems (like B.A.T.M.A.N., Contiki, 802.11s, or even BGP), but it's still a really exciting field that I dream of working in professionally someday.
AFAIK, each node generates its own key, and keys are then deterministically organized in a tree topology. Then, as you said, there's a lot of established systems. Yggdrasil is from the cjdns lineage.
Did they find anything? What are some interesting rules of thumb? Is there any theory you can draw about long path networks?
In that case, Layer 2 retransmission (ie. retransmission at an individual link rather than needing to retransmit a packet across the entire route) becomes absolutely necessary if there are many wireless links on a route.
What systems use layer 2 retransmission? My home wifi does not seem to...
Another issue is the half-duplex, CSMA nature of Wifi. It all but guarantees high amounts of jitter and latency instability. Particularly when several nodes in the same path are still in signal-range of one another so effectively share the same collision(and inteference) domain. A->B->C->D
I've found this wreaks havoc on TCP connections as well as applications that require some ability to detect and adjust to link condition.
This becomes significantly worse once the typical levels of WIFI interference come into play, causing multiple retransmissions and lost packets.
its address space may be beneficial (more flexible, lower overhead) for many use cases.
Our deployments are in the hundreds of thousands and individual meshes of up to 1000 nodes. We use similar technologies to described in the article (802.15.4, RPL, IPv6, CoAP, 6LoWPAN, DTLS, etc).
Topology-wise, our meshes don't tend to exceed 10 hops (chains like described here aren't great, tho can function).
And the routing protocol used is RPL.
