Architecture and Evaluation of an Unplanned 802.11b Mesh Network

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

One line summary: This paper describes Roofnet, an unplanned wireless mesh network built with 37 nodes over an area of about 4 square km; this paper presents its design and implementation as well as an evaluation of the actual network constructed.

Summary

This paper discusses the design and evaluation of an unplanned community wireless mesh network called Roofnet. Community wireless networks are usually constructed in one of two ways: by constructing a planned multi-hop network with nodes in chosen locations and directional antennas or by operating hot-spot access points to which clients directly connect. Roofnet aims to combine the advantages of both approaches by employing the following design decisions: (1) unconstrained node placement, (2) omni-directional antennas, (3) multi-hop routing, and (4) optimization for routing in a slowly changing environment with many links of varying quality.

Roofnet consists of 37 nodes spread across about four square km. Node locations are neither random nor truly planned. Roofnet provides Internet access. The nodes are self-configuring. Roofnet uses its own set of IP addresses on top of the IP layer. Each node runs a DHCP server and provides NAT to the hosts connected to it. If a Roofnet node can connect directly to the Internet it acts as a gateway to the rest of Roofnet. At the time the paper was written Roofnet had four gateways. Roofnet uses its own routing protocol called Srcr. It uses source routing and attempts to use the highest throughput routes using Dijkstra’s algorithm. The routing metric used in lieu of exact information about the throughput of routes is the estimated transmission time (ETT), which is a prediction of the amount of time it would take a packet to traverse a route given each links’ transmit bit rate and the delivery probability at that bit rate. Nodes choose among the available 802.11b transmit bit rates using an algorithm called SampleRate, which attempts to send packets at the bit rate which will provide the most throughput.

Roofnet was evaluated using four sets of measurements: (1) multi-hop TCP, (2) single-hop TCP, (3) loss matrix, and (4) multi-hop density. Some simulation was also used. A brief overview of their findings follows. Roofnet’s one-hop routes have a speed consistent with the 5.5 Mb transmission rate but longer routes are slower. That is, throughput decreases with each hop faster than might be expected. The authors speculate that this is due collisions of concurrent transmissions. The maximum number of hops to a gateway is 5. Roofnet’s routing algorithm Srcr prefers short, fast hops. The median delivery probability of the links used by Srcr is 80%. Roofnet approaches all-pairs connectivity with more than 20 nodes and as the number of nodes increases, throughput increases. The majority of Roofnet nodes route through more than two neighbors for their first hop, suggesting the network makes good use of the mesh topology. The best few links in Roofnet contribute considerably to overall throughput but dozens of nodes must be eliminated before throughput drops by half. Fast links are more important for throughput but long and fast links are more important for connectivity. In Roofnet, if only single-hop routing is used, five gateways are needed to cover all nodes. For five or fewer gateways, randomly chosen multi-hop gateways are better than randomly chosen single-hop gateways, but for larger number of gateways carefully chosen single-hop ones are better. The authors also examined one 24-hour period of use of the Roofnet network by their volunteer users, monitoring one gateway. They found that 94% of the traffic through the gateway was data and the rest was control packets. 48% of the traffic was from nodes one-hop away and 36% from nodes two-hops away and the rest were three-hops away or more. Almost all of the packets through the gateway were TCP. Web requests made up 7% of the data transferred and BitTorrent made up 30%, although 67% of the connections were web connections and only 3% were BitTorrent.

Critique

I thought this paper was very interesting. I thought the results of their evaluations were so in particular. However, I don’t think it is good that they allowed users to use Roofnet while they were doing their experiments. It seems like this would definitely have some affect but one that is difficult to quantify and explain. This seems especially true considering they had not an insignificant amount of BitTorrent traffic on their network. Also I think they should have explained how they did their simulations a bit more. I wasn’t entirely clear on that point; for instance, in these simulations, did they still let SampleRate determine what at what rate to transmit? Since SampleRate adjusts over time, I am not sure what this means for their simulations. Despite these things I still liked their evaluations. I thought they selected interesting aspects of Roofnet to examine and their results were presented in a very nice and clear way.

I think that the design of Roofnet itself is pretty cool. Also I often tend to prefer papers that talk about things actually built as opposed to just simulated. Their routing algorithm is clever although they point out that it may not be scalable. One thing that confused me is that in the section on addressing, they explain that each Roofnet node assigns itself an address from an unused class-A address block. They say these addresses are only meaningful within Roofnet and are not globally routable, so I wonder if they need to be unused addresses. If they do, that’s obviously a huge constraint, and if they don’t, I’m not sure why they state they are unused but don’t explain that they don’t need to be unused. I may be misunderstanding something very basic there, but if not, they may be leaving something out.

In summary, this paper was fun to read and I think it should stay in the syllabus.