J. Bicket, D. Aguayo, S. Biswas, R. Morris, “Architecture and Evaluation of an Unplanned 802.11b Mesh Network,” ACM Mobicom Conference, (September 2005). [PDF]

Summary

Planning and deployment of a large wireless mesh network in a urban area is complex, time-consuming, and expensive . This paper argues that an unplanned wireless mesh network with commodity hardware can do quite as well. The authors presents their experience with such an unplanned architecture, Roofnet, and evaluate multiple characteristics of Roofnet architecture.

Primary design decisions for Roofnet are as follows:

1. Unconstrained node placement: No topology or planned coverage. 37 Nodes are pseudo-randomly spread over 4 square kilometer urban area.
2. Omni-directional antenna: No directional high-fidelity connection. Nodes should be able to connect to anyone within their reach (based on some clever formula)
3. Multi-hop routing: No base-station- or access-point-centric single hop connection. Nodes should be able to find their way to the Internet through multiple hops over the network.
4. Routing optimization for throughput: No routing optimization for route route repair as in a mobile network. Routes are optimized for throughput in a slowly changing network.

Architecture

Roofnet is deployed in a densely populated urban area where line-of-sight propagation between nodes is often obstructed. Most Roofnet nodes are on top of three-four storeyed building with a few on higher ones. Each Roofnet node consists of a PC (running Linux, routing s/w on Click, DHCP server, and a web server), an 802.11b card (with RTS/CTS disabled), and a roof-mounted omni-directional antenna.

In order that Roofnet nodes be self-configuring several challenges must be addressed: address allocation, finding gateway to the Internet, finding best route to the gateway. Roofnet uses internal addressing mechanism which are translated using NATs for local network under each Roofnet node. Gateways are speacial Roofnet nodes that have wired connection to the Internet and provide NAT service for TCP flows originating inside Roofnet.

Roofnet routing protocol, Srcr, tries to find the highest throughput route between any pair of Roofnet nodes. Each Srcr node maintains a partial database of link metrics between other pairs of nodes and uses Dijkstra’s algorithms on that database. Nodes learn fresh link metrics by pushing, pulling (through flooding), or overhearing. Srcr chooses route with in estimated transmission time (ETT) metric that predicts the total amount of time it would take to send a data packet along a route (taking into account each link’s highest-throughout transmission bit-rate and its delivery probability at that bit-rate). Roofnet has its own bit-rate measuring and selection algorithm SampleRate to choose among the 802.11b transmit bit-rates.

Evaluation Results

• Over all pairs, Roofnet throughput and latency averages are 627 kbps and 39 ms, respectively. The authors also found that Roofnet nodes are most possibly working at 5.5 Mbps.
• Srcr uses mostly shorter links, almost all of the which that are faster than 2 Mbps, and it ignores most of the links slower than that.
• Through simulation, the authors found that the network approaches all-pairs connectivity after total of number of node crosses 20, and average throughput increases with higher density. They postulate that higher density gives more shorter links with higher transmission rate to increase throughput.
• In terms of robustness, the authors found that there are a few links (around a dozen) that contribute to half the throughput. They also found that there are two nodes that carries 43% of the total throughput.
• A comparison against single-hop alternative shows that multi-hop architecture can operate with fewer number of gateways since it can take multiple hops to reach gateways (duh!). For single-hop scenario, minimum number of gateways for full Internet connectivity is found to be 5.
• Distribution of throughout is dictated by hop-count with throughput decreasing significantly faster with increasing hop-count.The authors postulate that this is because of packet loss from inter-hop interference. However, they also found that RTS/CTS scheme, that is supposed to avoid such collisions, does not even performance.

Critique

This paper performs an elaborate measurement study to propound unplanned mesh network deployment as a considerable alternative to engineered network deployment in an urban area. However elaborate, there are several things that require further explanation. First of all, Roofnet ‘layer’ and Roofnet addressing scheme could use better explanation. It is not clear why they needed a different layer and how they used it.

Secondly, a significant number of evaluations have been done using a mathematical formula of end-to-end throughput, which – the authors admit – has estimation error. However, there was no evaluation regarding the level of estimation mismatch it is causing. If the introduced error is quite high, then all the results will be affected. Since the total number of nodes is very low, even smaller changes in required number of nodes for ‘X’ is significant.

In addition, there is no evaluation regarding how SampleRate works, what it selected in practice, and what was used for simulation. One might assume that the authors were using 5.5 Mbps in simulation based on their findings from basic performance analysis. A little clarification could help.

Finally, based on their results (e.g., 2 nodes carrying 43% throughput, 12 links carrying 50%, very few links were highly used) it seems plausible that a spanning tree was formed. It would have been nice to know the properties of such formation (even though on pseudo-random graphs).