3 ms·

> The number of edges scales O(n^2), where n is the number of people in the network. I don't see how this is true for any reasonable definition of "edge". It's

> The number of edges scales O(n^2), where n is the number of people in the network. I don't see how this is true for any reasonable definition of "edge". It's certainly not the case that every node directly communicates with every other node; if they did, you wouldn't need a mesh.

jeffreyrogers 9y ago
A mesh network is defined as a network where the nodes connect to as many other nodes as possible. In the limit this is a complete graph with O(n^2) edges. It's true that in practice you won't have a complete graph but it's still less efficient than a more hierarchical, tree-like network structure.
- mpfundstein 9y ago
  the fact that a wifi network node only covers a very limited area is sufficient to show that your theoretical limit is never going to be reached -> by a large margin. You can probably assume that in a dense network, every node will be reachable by every other node through at most 7 hops. But thats it [1] https://en.wikipedia.org/wiki/Small-world_network https://en.wikipedia.org/wiki/Small-world_network
- MR4D 9y ago
  Am I missing something here? Let me approach your math with a reasonable argument: Assume a 1 sq mile area (1mi x 1mi). Assume each node has a 50 yard diameter reach. If you space a node every 50 yards, you will have 35 nodes on a side, for a total of 1,225 total nodes. Each node will only be able to physically connect to 3 other nodes on the edges, and 4 other for interior nodes. That means the node connectivity is only .00326 for an interior node. The longest path is diagonal across the square. Given the 35 modes on a side, and A^2 +B^2 = C^2, that means 35^2 = 35^2 = C^2. And c^2 = 2,450, meaning C = 50 (rounding up). So I’m not sure how O^2 even applies in this example. Yes, it’s theoretically a max, but theory >< the real world. Is this not correct?

3 ms·

> The number of edges scales O(n^2), where n is the number of people in the network. I don't see how this is true for any reasonable definition of "edge". It's

by teraflop 9y ago

jeffreyrogers 9y ago
A mesh network is defined as a network where the nodes connect to as many other nodes as possible. In the limit this is a complete graph with O(n^2) edges. It's true that in practice you won't have a complete graph but it's still less efficient than a more hierarchical, tree-like network structure.
- mpfundstein 9y ago
  the fact that a wifi network node only covers a very limited area is sufficient to show that your theoretical limit is never going to be reached -> by a large margin. You can probably assume that in a dense network, every node will be reachable by every other node through at most 7 hops. But thats it [1] https://en.wikipedia.org/wiki/Small-world_network https://en.wikipedia.org/wiki/Small-world_network
- MR4D 9y ago
  Am I missing something here? Let me approach your math with a reasonable argument: Assume a 1 sq mile area (1mi x 1mi). Assume each node has a 50 yard diameter reach. If you space a node every 50 yards, you will have 35 nodes on a side, for a total of 1,225 total nodes. Each node will only be able to physically connect to 3 other nodes on the edges, and 4 other for interior nodes. That means the node connectivity is only .00326 for an interior node. The longest path is diagonal across the square. Given the 35 modes on a side, and A^2 +B^2 = C^2, that means 35^2 = 35^2 = C^2. And c^2 = 2,450, meaning C = 50 (rounding up). So I’m not sure how O^2 even applies in this example. Yes, it’s theoretically a max, but theory >< the real world. Is this not correct?