4 ms·

Very long story short, the overhead in maintaining the link state information in meshed networks swamps the available bandwidth for even modest (think 20-40) nu

Very long story short, the overhead in maintaining the link state information in meshed networks swamps the available bandwidth for even modest (think 20-40) numbers of nodes. Basically, as nodes are constantly moving/coming on- and off-line, nodes have to know which nodes are in the connection graph, so they exchange that information. But that eats up all of the bandwidth amazingly quickly, leaving no room for actual traffic. There are some other issues with meshed networks (latency, battery usage when you're just a client node, etc.), but especially for those of the kind described/dreamed about here (which are also known as MANETS -- mobile ad-hoc networks), the routing issue is a huge one. Finally, I should note the above isn't just academic; several companies have tried to build products based on these kinds of networks -- military contractors being one of note -- and have pretty much come up short. So until the really fundamental issues are worked out, which is in the realm of academic research, not implementation, we probably aren't going to see anything like this.

robinhoode 12y ago
Do you have any more information on this? I'm definitely curious what the problem looks like when stated in specific algorithmic terms (big-O and all that).
riboflavin 12y ago
This is really interesting. Thanks for this comment. So is something like Multipeer Connectivity Framework in existence mostly because it is a much weaker version of true mesh networking? (Or not mesh networking at all?) Do you think weaker versions of mesh networking that don't solve the underlying problems could also be valuable?
- yohanatan 12y ago
  You're accepting his defeatist attitude too quickly. The problems he lists are easily surmountable. The military uses mesh networking to a great degree of success. A globally-distributed up-to-date copy of the network topology is a faulty starting point.
deleted 12y ago
[deleted]
wilecoyote 12y ago
Doesn't Sonos employ some type of mesh-based network? It appears to work reasonably well in practice, but not sure whether it is in fact a better alternative to current standard wifi alternatives. Anyone happen to know more about this?
ilaksh 12y ago
That's not some academics problem. Its an engineering problem. What those companies have proven is that given the particular approach they took and the constraints they had they could not make their mesh networks work. So the starting point for an engineer is what types of mesh networks work that don't need to globally broadcast topology updates in real time. It always amazes me how quick people are to accept someone else's incorrect approach to a problem or to dismiss a new paradigm because others havent had success. Meanwhile they spend enormous amounts of energy tweaking the parameters of an outdated paradigm to try to make it work a little longer. The main thing holding back new superior approaches to a problem solution is always the people who tried and failed and then kept saying it was unworkable thus preventing others from trying.
- cjbprime 12y ago
  Hi, we spent a few years working on mesh networks at One Laptop Per Child (as engineers rather than academics, obviously). We ended up giving up, for the reasons gsteinb88 mentioned -- another cause of bandwidth saturation was that broadcast packets turn into multicast on mesh. I'm not saying this to discourage others from trying. But they should definitely be teams of network protocol experts, rather than a generalist team trying to put a product together as we were. We used 802.11s, and being the largest deployment of a protocol you weren't planning on having to fix yourself isn't an enviable position.
  - bdickason 12y ago
    I'm incredibly interested in the challenges you guys faced - the mesh network and view source parts of OLPC were (to me) the most important and life-changing aspects. Bummed to hear that one of them at least was problematic. Was there a blog post or anywhere you guys catalogued these problems, your approaches, and what could be learned? I'm looking to take on a similar challenge as a generalist and would love to learn from your attempts :)
    - cjbprime 12y ago
      Thanks! It looks like there were a bunch of academic papers about the mesh performance -- if you search for anything by (or citing) Ricardo Carrano, he was one of the more academic engineers who worked on the problem. For example, here he proposes a hack on top of 802.11s to switch between reactive and adaptive mesh topologies based on measuring the network density -- if you're a small group of kids in a village you want a reactive network, which comes with higher bandwidth saturation costs, but if all the kids come into the same classroom at once you need to quickly switch to adaptive to avoid using up all the spectrum with routing detection: http://wiki.laptop.org/go/MAD_Heuristics http://wiki.laptop.org/go/MAD_Heuristics http://wiki.laptop.org/go/MAD_Architecture http://wiki.laptop.org/go/MAD_Architecture The 802.11s spec is pretty useless for high density areas without such a hack, it seems. I suppose the takeaway message is that your use of mesh networking needs to be extremely tailored to your specific use case, quite possibly including writing custom routing software. John Gilmore also wrote a summary of the OLPC mesh experience here: http://lists.alioth.debian.org/pipermail/freedombox-discuss/2012-June/003944.html http://lists.alioth.debian.org/pipermail/freedombox-discuss/...
ansimionescu 12y ago
I agree that in general the idea is pretty stupid, but what about if we add a couple of layers of master nodes? As Google says, by trading off a bit of decentralisation you can gain a lot of performance (see gfs, etc).
- deleted 12y ago
  [deleted]
- api_or_ipa 12y ago
  route detection would be difficult. you'd throw in leader election on top of the mentioned network mush.
api 12y ago
Another problem: I've never seen a meshnet protocol that isn't vulnerable to a variety of flooding, cache pollution, DDOS, and other attacks that could basically make the network unusable. This is a problem for the idea that mesh nets should be used to create resilient decentralized networks. Unless the meshnet is safe against attacks, any government or other organization that wanted to take a meshnet down might actually find it easier than taking down a multi-path tree-shaped or centralized infrastructure.
sliverstorm 12y ago
Let's not forget that wireless has very limited bandwidth in the first place. Once you start "sharing" your bandwidth by relaying packets for other nodes, in any large network the bandwidth available for you to use will drop off a cliff. In other words, even setting aside maintenance overhead, simple relay overhead is also going to bring the network to its knees.

robinhoode 12y ago

Do you have any more information on this? I'm definitely curious what the problem looks like when stated in specific algorithmic terms (big-O and all that).

riboflavin 12y ago

This is really interesting. Thanks for this comment. So is something like Multipeer Connectivity Framework in existence mostly because it is a much weaker version of true mesh networking? (Or not mesh networking at all?) Do you think weaker versions of mesh networking that don't solve the underlying problems could also be valuable?

yohanatan 12y ago
You're accepting his defeatist attitude too quickly. The problems he lists are easily surmountable. The military uses mesh networking to a great degree of success. A globally-distributed up-to-date copy of the network topology is a faulty starting point.

deleted 12y ago

[deleted]

wilecoyote 12y ago

Doesn't Sonos employ some type of mesh-based network? It appears to work reasonably well in practice, but not sure whether it is in fact a better alternative to current standard wifi alternatives. Anyone happen to know more about this?

ilaksh 12y ago

That's not some academics problem. Its an engineering problem. What those companies have proven is that given the particular approach they took and the constraints they had they could not make their mesh networks work. So the starting point for an engineer is what types of mesh networks work that don't need to globally broadcast topology updates in real time. It always amazes me how quick people are to accept someone else's incorrect approach to a problem or to dismiss a new paradigm because others havent had success. Meanwhile they spend enormous amounts of energy tweaking the parameters of an outdated paradigm to try to make it work a little longer. The main thing holding back new superior approaches to a problem solution is always the people who tried and failed and then kept saying it was unworkable thus preventing others from trying.

cjbprime 12y ago
Hi, we spent a few years working on mesh networks at One Laptop Per Child (as engineers rather than academics, obviously). We ended up giving up, for the reasons gsteinb88 mentioned -- another cause of bandwidth saturation was that broadcast packets turn into multicast on mesh. I'm not saying this to discourage others from trying. But they should definitely be teams of network protocol experts, rather than a generalist team trying to put a product together as we were. We used 802.11s, and being the largest deployment of a protocol you weren't planning on having to fix yourself isn't an enviable position.
- bdickason 12y ago
  I'm incredibly interested in the challenges you guys faced - the mesh network and view source parts of OLPC were (to me) the most important and life-changing aspects. Bummed to hear that one of them at least was problematic. Was there a blog post or anywhere you guys catalogued these problems, your approaches, and what could be learned? I'm looking to take on a similar challenge as a generalist and would love to learn from your attempts :)
  - cjbprime 12y ago
    Thanks! It looks like there were a bunch of academic papers about the mesh performance -- if you search for anything by (or citing) Ricardo Carrano, he was one of the more academic engineers who worked on the problem. For example, here he proposes a hack on top of 802.11s to switch between reactive and adaptive mesh topologies based on measuring the network density -- if you're a small group of kids in a village you want a reactive network, which comes with higher bandwidth saturation costs, but if all the kids come into the same classroom at once you need to quickly switch to adaptive to avoid using up all the spectrum with routing detection: http://wiki.laptop.org/go/MAD_Heuristics http://wiki.laptop.org/go/MAD_Heuristics http://wiki.laptop.org/go/MAD_Architecture http://wiki.laptop.org/go/MAD_Architecture The 802.11s spec is pretty useless for high density areas without such a hack, it seems. I suppose the takeaway message is that your use of mesh networking needs to be extremely tailored to your specific use case, quite possibly including writing custom routing software. John Gilmore also wrote a summary of the OLPC mesh experience here: http://lists.alioth.debian.org/pipermail/freedombox-discuss/2012-June/003944.html http://lists.alioth.debian.org/pipermail/freedombox-discuss/...

ansimionescu 12y ago

I agree that in general the idea is pretty stupid, but what about if we add a couple of layers of master nodes? As Google says, by trading off a bit of decentralisation you can gain a lot of performance (see gfs, etc).

deleted 12y ago
[deleted]
api_or_ipa 12y ago
route detection would be difficult. you'd throw in leader election on top of the mentioned network mush.

api 12y ago

Another problem: I've never seen a meshnet protocol that isn't vulnerable to a variety of flooding, cache pollution, DDOS, and other attacks that could basically make the network unusable. This is a problem for the idea that mesh nets should be used to create resilient decentralized networks. Unless the meshnet is safe against attacks, any government or other organization that wanted to take a meshnet down might actually find it easier than taking down a multi-path tree-shaped or centralized infrastructure.

sliverstorm 12y ago

Let's not forget that wireless has very limited bandwidth in the first place. Once you start "sharing" your bandwidth by relaying packets for other nodes, in any large network the bandwidth available for you to use will drop off a cliff. In other words, even setting aside maintenance overhead, simple relay overhead is also going to bring the network to its knees.