Achitecture and Evaluation of an Unplanned 802.11b Mesh Network

Summary
This paper looks at a deployment of Roofnet, an unplanned mesh network in an urban environment. The basic architecture is that the nodes connect to each other and use a shortest path routing algorithm to find paths to gateway nodes, that is, those small percentage of Rootnet nodes that are also connected to the Internet.

The nodes maintain a database of link metrics and do Dynamic Source Routing, in which each TCP session computes the best route using Dijkstra's algorithm over the link DB. The metric that gets used is the link throughput in conjunction with the probability that packets will get through. This sometimes required putting the WiFi cards into high-loss but also high-throughput modes, which required setting a custom policy on the wireless NIC. To discover the link metrics nodes can flood the network and listen for replies, or snoop on other nodes' floods.

The paper evaluates the performance and the robustness of Roofnet, noting that they get mean throughput of 627 kbit/sec. They also look at simulated results of handling failures, noting that most nodes choose a wide variety of neighbors for their first hop so failure of a single neighbor shouldn't effect performance too much. They do find, however, the throughput will drop significantly as there is often only one or two 'fast' neighbors.

Thoughts
I thought this was an interesting paper. They manage to get a working network set up with minimal work by the volunteers and it actually appears to work. They get decent throughput (although the median isn't as good as the mean and might have been a better metric).

On major concern I have is that the paper does not seem to take the performance of the gateway's connection to the WAN into account. It's all well and good if I can get to my gateway at 600kbps, but if that gateway is overloaded on it's WAN routes I won't see good performance overall. This does not seem to be captured by anything in their algorithm and should really be addressed.

Still, an interesting paper and one well worth reading.