“Architecture and Evaluation of an Unplanned Mesh Network”

This paper discusses the design of the Roofnet, a 37-node “mesh network” that covers four square kilometers in Cambridge, MA. The authors are trying to get “the best of both worlds”: the performance of a carefully-planned wireless deployment, with the lack of planning and easy deployability of a collection of independent “hot spots.”

Design

A small fraction of Roofnet nodes are connected to the Internet; the remainder of the Roofnet nodes access the Internet by finding a route through the Roofnet that terminates at a gateway node (4 of the 37 Roofnet nodes are gateways). Each Roofnet is assigned a non-routable IP address, based on the node’s MAC. Gateway nodes use NAT to route traffic into and out of Roofnet. Similarly, each Roofnet node runs a local “hot spot,” and assigns local (192.168.1.x) addresses to clients via DHCP. NAT is used to rewrite these addresses into the Roofnet node’s address, before they are routed through Roofnet. Using two levels of NAT means that no manual configuration of the address space is required: both Roofnet ndoe IPs and node-local client IPs can be automatically assigned, without risk of conflict.

Each node keeps track of the performance of all the gateway nodes it is connected to, and chooses the best route for each new TCP session. Roofnet uses dynamic source routing (DSR): each node maintains a database of link metrics for each pair of nodes in the network. It chooses the best route for each new connection by applying Dijkstra’s algorithm, and “source routes” (the entire route for a flow is assigned by the originating end point, not intermediate routers). The link metrics are periodically updated: link metrics for the source route are included by each node that forwards a packet; periodic flooding of link metrics is done; and nodes “snoop” and overhear link metrics sent by other traffic they can listen to. Flooding is only necessary when no route to the destination host can be found—the authors argue that this will rarely occur, since most routes terminate in a gateway.

To choose among routes, Roofnet uses an “estimated transmission time” (ETT) metric: it combines the link’s highest-throughput bit rate with the probability that a packet sent over the link will be successfully delivered. The authors found that this policy often results in using relatively high-bandwidth routes with relatively high link-level loss rates. This situation was unanticipated by the firmware designers of their wireless NIC, so they had to use a custom policy they call “SampleRate” for choosing which 802.11b transfer bit rate to use (high-bandwidth, high-loss rates are often preferable). SampleRate varies the 802.11b transfer rate dynamically, measuring the current throughput vs. delivery probability for the different rate options. SampleRate is similar in principle to the ETT routing metric they use, but differs because:

  1. SampleRate selects only the link-local transfer rate, not the route.
  2. SampleRate is based on measurements of actual packet transmissions rather than broadcasting or snooping, and hence can respond to changes in network conditions much more rapidly than ETT can.

Evaluation

The authors found that the average throughput between a node and its closest gateway is 1395 kbit/sec, with a latency of 22 msec: this is quite impressive, and matches typical budget consumer-grade DSL performance at the time (2005). Roofnet routes most traffic over short, high-bandwidth hops, ignoring most of the long-distance links available that perform poorly.

The authors found that a density of about 5 nodes per square kilometer is necessary (in this environment) for all-pairs connectivity. Increasing node density leads to higher throughput, because there are more alternate routes to choose from.

Roofnote is a true “mesh” network, in the sense that each node routes at least some packets through most of its neighbors (rather than preferring a single neighbor for most traffic, which would suggest that a directional, planned design would be better). On the other hand, eliminating the two best-connected nodes decreases average throughput by 43%, which suggests that, despite the mesh architecture, good network performance depends on having a few “supernodes”.

Comments

The authors are careful to brag more prominently about the mean all-pairs average throughput (627 kbits/sec) than about the median (400 kbits/sec). This is a little disingenuous, given the presence of a small number of high-bandwidth links that skew the distribution.

Using NAT is understandable, but doesn’t work well with some networking applications (e.g. BitTorrent, running a server inside Roofnet). It would be interesting to extend the Roofnet design to allow incoming connections from the Internet to an arbitrary Roofnet node, as well as allowing a TCP connection to remain connected as its route is changed on-the-fly.

It would be interesting to compare the connectivity of mesh networks with peer-to-peer networks: many of the concepts (auto-configuration, peer-to-peer topology, the importance of a small number of well-connected “supernodes”) seem to apply to both kinds of networks.

Advertisements

1 Comment

Filed under Paper Summaries

One response to ““Architecture and Evaluation of an Unplanned Mesh Network”

  1. Pingback: “A Path Metric for Multi-Hop Wireless Routing” « Everything is Data

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s