5 ms·

What Happens Inside a 100-Hop IPv6 Wireless Mesh Network?

137 points by tdrnd 6y ago

pantalaimon 6y ago
Is this proprietary? Based on Contiki?
- rektide 6y ago
  Their platform is built on contiki according to https://www.thingsquare.com/docs/firmware-sdk-do-donts/ https://www.thingsquare.com/docs/firmware-sdk-do-donts/
konjin 6y ago
I feel the article ended before it started. Did they find anything? What are some interesting rules of thumb? Is there any theory you can draw about long path networks?
- CliffStoll 6y ago
  Agreement. The article gives a good introduction and methodology - but doesn't say what the experiment showed. Is there any conclusion? Should I stop my network at 50 nodes? What were the propagation delays? Might a star-based topology make more sense?
YarickR2 6y ago
Haven't read article yet - did they reinvent BGP or tuned it for small scale networks and kept full view on each node ?
- takeda 6y ago
  Ironically while BGP gets all the glory it's the routing protocols within the autonomous system, that do the hard work. And the routing protocol used is RPL.
nikisweeting 6y ago
Heh, I walked a similar path ~7 years ago. Wanted to get started developing a mesh network routing algorithm that could handle a hundred hops, got distracted and built a mesh networking test harness / simulation system instead (https://github.com/pirate/mesh-networking https://github.com/pirate/mesh-networking). 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. https://www.open-mesh.org/projects/open-mesh/wiki https://www.open-mesh.org/projects/open-mesh/wiki
- MayeulC 6y ago
  I currently like https://yggdrasil-network.github.io https://yggdrasil-network.github.io 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.
  - rnhmjoj 6y ago
    Do you know what kind of encryption it uses? I couldn't find any information on this from the site. Yggdrasil looks it could be perfect to set up a simple VPN with zero configuration, but it's hard to trust its cryptography if it's not even documented.
    - 6y ago
wyldfire 6y ago
What are some of the biggest public/private wireless mesh networks out there? (I suppose 'biggest' by measure of node count -- or maybe area covered?). For those networks, how deep are they in practice? 100 hops seems unrealstic, but a great way to find scaling problems.
- TickleSteve 6y ago
  I work on mesh networks for the smart utilities (think smart metering in India). 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).
  - snickmy 6y ago
    Intresting. What's the best real world solution to having those meters in basements or behind high density walls?
    - aerostable_slug 6y ago
      I also worked in the space, though from the utility side. Multi-dwelling units are a problem, though not from the networking side. In my experience the commercial stacks had no issue with that kind of density. Also, we found that 900mHz signals can reach a lot further than one would think, at least intermittently (e.g. across the SF bay).
      - snickmy 6y ago
        Where can I learn more about why multi dwelling units are a problem?
llimos 6y ago
Why does the page jump back to the top when I scroll past the bottom? Is this by design? (I'm on Firefox desktop.)
- Maxburn 6y ago
  Not just you, but for me it happened when I tried to read the conclusion. Also Firefox.
gioscarab 6y ago
PJON supports mesh networking too, it is open-source and free to use, check it out: https://github.com/gioblu/PJON https://github.com/gioblu/PJON its address space may be beneficial (more flexible, lower overhead) for many use cases.
londons_explore 6y ago
Most wireless networks seem to have loss in the range 0.1% - 1% due to congestion (ie. when a packet is clobbered by noise of some far off transmitter that the media access control algorithms could not protect against). 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...
- tralarpa 6y ago
  Frame retransmissions exist in CSMA for IEEE 802.15.4.
- sathackr 6y ago
  This is one of the biggest problems I have seen with attempted real-world deployments of wifi-based mesh systems. 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.
- noselasd 6y ago
  Yes, your home wifi does. For unicast frames, an ack is required from the receiver, else the frame is re-transmitted.

137 points by tdrnd 6y ago

pantalaimon 6y ago

Is this proprietary? Based on Contiki?

rektide 6y ago
Their platform is built on contiki according to https://www.thingsquare.com/docs/firmware-sdk-do-donts/ https://www.thingsquare.com/docs/firmware-sdk-do-donts/

konjin 6y ago

I feel the article ended before it started. Did they find anything? What are some interesting rules of thumb? Is there any theory you can draw about long path networks?

CliffStoll 6y ago
Agreement. The article gives a good introduction and methodology - but doesn't say what the experiment showed. Is there any conclusion? Should I stop my network at 50 nodes? What were the propagation delays? Might a star-based topology make more sense?

YarickR2 6y ago

Haven't read article yet - did they reinvent BGP or tuned it for small scale networks and kept full view on each node ?

takeda 6y ago
Ironically while BGP gets all the glory it's the routing protocols within the autonomous system, that do the hard work. And the routing protocol used is RPL.

nikisweeting 6y ago

Heh, I walked a similar path ~7 years ago. Wanted to get started developing a mesh network routing algorithm that could handle a hundred hops, got distracted and built a mesh networking test harness / simulation system instead (https://github.com/pirate/mesh-networking https://github.com/pirate/mesh-networking). 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. https://www.open-mesh.org/projects/open-mesh/wiki https://www.open-mesh.org/projects/open-mesh/wiki

MayeulC 6y ago
I currently like https://yggdrasil-network.github.io https://yggdrasil-network.github.io 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.
- rnhmjoj 6y ago
  Do you know what kind of encryption it uses? I couldn't find any information on this from the site. Yggdrasil looks it could be perfect to set up a simple VPN with zero configuration, but it's hard to trust its cryptography if it's not even documented.
  - 6y ago

wyldfire 6y ago

What are some of the biggest public/private wireless mesh networks out there? (I suppose 'biggest' by measure of node count -- or maybe area covered?). For those networks, how deep are they in practice? 100 hops seems unrealstic, but a great way to find scaling problems.

TickleSteve 6y ago
I work on mesh networks for the smart utilities (think smart metering in India). 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).
- snickmy 6y ago
  Intresting. What's the best real world solution to having those meters in basements or behind high density walls?
  - aerostable_slug 6y ago
    I also worked in the space, though from the utility side. Multi-dwelling units are a problem, though not from the networking side. In my experience the commercial stacks had no issue with that kind of density. Also, we found that 900mHz signals can reach a lot further than one would think, at least intermittently (e.g. across the SF bay).
    - snickmy 6y ago
      Where can I learn more about why multi dwelling units are a problem?

llimos 6y ago

Why does the page jump back to the top when I scroll past the bottom? Is this by design? (I'm on Firefox desktop.)

Maxburn 6y ago
Not just you, but for me it happened when I tried to read the conclusion. Also Firefox.

gioscarab 6y ago

PJON supports mesh networking too, it is open-source and free to use, check it out: https://github.com/gioblu/PJON https://github.com/gioblu/PJON its address space may be beneficial (more flexible, lower overhead) for many use cases.

londons_explore 6y ago

Most wireless networks seem to have loss in the range 0.1% - 1% due to congestion (ie. when a packet is clobbered by noise of some far off transmitter that the media access control algorithms could not protect against). 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...

tralarpa 6y ago
Frame retransmissions exist in CSMA for IEEE 802.15.4.
sathackr 6y ago
This is one of the biggest problems I have seen with attempted real-world deployments of wifi-based mesh systems. 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.
noselasd 6y ago
Yes, your home wifi does. For unicast frames, an ack is required from the receiver, else the frame is re-transmitted.