Daniel Aguayo, John Bicket, Sanjit Biswas, Douglas S. J. De Couto, Robert Morris
August 2003
This document describes the implementation of the MIT Roofnet, an experimental multi-hop 802.11b mesh network. Roofnet consists of about 50 nodes in apartments in Cambridge, MA. Each node is in radio range of a subset of the other nodes, and can communicate with the rest of the nodes via multi-hop forwarding. A few of the nodes act as gateways to the wired Internet.
A primary feature of the Roofnet design is that it requires no configuration or planning, and is thus easy to deploy and expand. A new user can turn on a new node and start using it for Internet connectivity with no configuration beyond installing the hardware. The new user need not allocate an IP address, aim a directional antenna, or ask existing users to perform any special actions to add the new node. One consequence of an unplanned network is that each node can route packets through any of a large number of neighbors, but the radio link to each neighbor is typically of marginal quality; finding the best multi-hop routes through a rich mesh of marginal links turns out to be a challenge.
Roofnet performs well. The longest routes are four hops long. Typical latencies are dozens of milliseconds, even for long routes; typical throughputs are dozens to hundreds of kilobytes per second.
While the current network is an experimental prototype, we intend that it turn into a self-sustaining community network in the near future.
The following map shows the current Roofnet node positions, and the quality of the radio links between pairs of nodes. The area shown is about 1.25 miles on a side, in the part of Cambridge to the north of MIT. Each node has a single antenna and a single Ethernet port. Three of the nodes at the lower right have Yagi antennas on top of ten-story MIT buildings and act as gateways to MIT's wired campus net. The other nodes are in apartment buildings, with roof-mounted omni-directional antennas. The radios are only used for inter-node communication, not as 802.11 access points. Each user connects to the net through the wired Ethernet port of the local node.
Most of this part of Cambridge consists of three and four-story houses, so line of sight is not uncommon for long distances. Many buildings have flat roofs, which makes antenna installation possible. Trees are not particularly common, so signal strength is not decreased too much by foliage. The area has a high concentration of MIT students and staff.
The typical maximum useful radio range is about 100 meters, though the variation is enormous.
The initial net included just a few nodes clustered in the center of the map. The initial users were students and staff in our lab, and we installed each node ourselves. Attaching the antenna to the chimney was by far the most time-consuming part of each installation, particularly on houses with peaked roofs.
The rest of the nodes are in the apartments of volunteers. We found these volunteers by posting flyers at MIT, by pushing them under doors in the areas of Cambridge we wanted more nodes in, and by word of mouth. Prospective users signed up on our web site, answering questions which allowed us to concentrate our efforts on the most promising locations. In particular, we required that users be affiliated with MIT; have flat roofs; and be willing to ask their landlord for permission to put an antenna on the roof.
The hardware comes in the form of a complete kit, which we give to each user. The kit includes a computer with pre-installed software, an 802.11b card, an antenna with chimney mount, 50 to 150 feet of low-loss LMR400 cable, and printed instructions. The total cost is about $650, and is paid for out of research funds. The kit is portable, and can be carried home (or returned for repair) in a single trip without a car. The fact that users carry their own nodes home and install them dramatically increases the rate at which the network can grow, given our limited staff resources. A complete installation takes about 45 minutes.
The computer is a $250 iDOT Slim PC, with a 500 MHz x86 CPU, a Mini-ITX motherboard, a 40 GB hard disk, a CD-ROM (for software upgrades), built-in Ethernet, and one PCI slot. The low CPU speed reduces the amount of heat the node generates; even lower would be better, since routing requires relatively little CPU time. The computer has fans, but we disconnect them: the fans generate too much noise for living rooms and bedrooms. The nodes are not waterproof, so they need to be indoors.
The computer is about 2 inches thick, about the size of a large laptop. It's small enough that a user can easily carry a node home, or bring it back to us for replacement. However, since the nodes are indoors, users can easily upgrade the software in place.
As of summer 2004 we're starting to switch to the Metrix Mark I. This is a waterproof box that we will mount directly on the antenna pole. The box contains a Soekris motherboard with an x86 CPU. We'll run ethernet down from the box into the user's apartment, and power the box with power-over-ethernet.
With the exception of the four gateways, all nodes have a Hyperlink Technologies 8 dBi omni-directional antenna. Typically the antenna is mounted on a five-foot pole strapped to a chimney, with 50 feet of cable down the side of the house into a window. The cable connects to a lightning arrestor, and then to the 802.11 card. The details vary considerably, since each user installs his or her equipment. Most users run the cable into a slightly open window packed with foam insulation, which may not turn out to be satisfactory in the winter. Waterproofing the connector between the antenna and cable is important: we find that wrapping the connection several times with electrical tape is sufficient.
Users often have trouble finding a good ground for the lightning arrestor. We're considering lending users an earth ground resistance tester, which basically measures the resistance from (for example) a cold water pipe to a spike driven into the ground outside.
We have experimented with higher-gain 12 dBi omni-directional antennas. These have longer range, but have only a seven-degree vertical beam spread. As a result they tend to stop working after wind storms, since even a small tilt away from vertical moves the beam too far from horizontal. The lower-gain 8 dBi antennas have a more forgiving 20-degree vertical beam width.
Many outdoor mesh networks [15] use directional antennas for increased range, but we do not for the following reasons. First, each new user would have to find an existing user willing to install a new antenna pointing at the new user, which would impede the growth of the network. Second, high-gain directional antennas are difficult to aim accurately, and are easily blown away from true in storms. Third, omni-directional antennas tend to provide a more richly connected mesh, which increases reliability. Fourth, directional antennas increase the per-node cost of the network, since each node requires multiple antennas and radios in order to maintain a well-connected mesh.
Omni-directional antennas do have disadvantages. Our network must be relatively dense to maintain connectivity, though this is mostly a start-up problem. Directional antennas allow better spatial re-use of spectrum, though perhaps transmit power control in a dense network could have similar efficiency [14]. Finally, it is natural with directional antennas to engineer each link so that it has a low error rate; the wider variety of error rates seen with omni-directional antennas requires us to use more sophisticated routing algorithms [3].
We use the Senao/Engenius SL-2511CD PLUS EXT2 802.11b PCMCIA card, in a PCI adapter. It's based on the Intersil Prism 2.5 chip-set, for which drivers and documentation are readily available. It supports a transmit power levels up to 200 milliwatts, which is higher than most cards. We use the cards in ``Pseudo-IBSS'' mode. This is a non-standard simplified version of the 802.11 ad hoc node, which does not suffer from BSSID partitioning (see below).
It turns out that the 200 milliwatt transmit power is probably more than we need. We plan to implement some kind of adaptive transmit power control to avoid interference.
We use the Linux HostAP 802.11 driver, though we do not enable the software access point. The card and driver use programmed I/O to copy packet data, rather than DMA. The resulting slowness means that you cannot keep the radio busy if you want to send one packet at a time in order to monitor transmission success.
These cards use received signal strength for clear channel assessment, with a relatively high threshold. That means that they tend to send when other cards are already sending, which corrupts packets.
We originally used the Cisco/Aironet 350, which generally worked well. However, it suffered from ``BSSID partitioning.'' If different regions of the network started without being able to talk to each other, they would choose different random 802.11 BSSID identifiers. New nodes that came up within radio range of multiple partitions seemed to choose randomly from them, but the partitions would not always ``coalesce''. The problem could eventually worsen until the network consisted of multiple, overlapping BSSID partitions; since a node's 802.11 firmware filters out broadcasts with the wrong BSSID, nodes in the different partitions would be blind to each other despite having radio-level connectivity. It turns out this problem was particularly acute when the network contained both Cisco 350 and Senao cards. The Senao cards, when used by themselves, do not seem to suffer from BSSID partitioning.
As of summer 2004 we're moving to Atheros-based 802.11g cards. We use our own driver derived from Madwifi. Our driver sends and receives raw 802.11 frames, so that we can control most of the functionality to Click.
The nodes we give to users are essentially wireless router appliances. The user just plugs in the antenna, a local wired Ethernet, and power; the node starts operating without requiring any user configuration. The Roofnet source is partially bundled with Click; a preliminary ready-made distribution is available here.
The nodes run Red Hat 9 Linux, kernel version 2.4.20. They use the ext3 file system so that they can tolerate frequent unexpected power-offs by users who view the node as an appliance. The complete system uses about two gigabytes of disk space, though most of the space is used by utilities (such as the compiler) that are part of the default Red Hat installation but aren't needed in ordinary operation.
The nodes use the Click [8] software router toolkit for route discovery and packet forwarding. Section 5 describes our routing protocol. We run all the routing software in the kernel; this gives us precise control over packet queuing and scheduling (to give routing messages high priority), and allows tight integration between routing and the 802.11 driver (to get feedback about failed transmissions, and control transmit power level and bit-rate). Click greatly eases routing protocol development by allowing upgrades without reboots and co-existence of multiple routing and forwarding schemes in the same kernel.
Each node also runs a Web server, a NAT, and a DHCP server on its wired Ethernet port. The DHCP server and NAT allow users' home computers to use the node as a router without any configuration. The Web server provides a simple configuration interface (to turn on and off DHCP, and to set the IP address of the wired interface), a status monitor showing what routes are available and their current metrics, and a means for rebooting the node. We give any user who asks for one a root account on their own node.
We perform most software upgrades over the Roofnet. A complete upgrade is around one megabyte, and consists of the Click kernel modules along with our scripts and configuration files. After copying the new software to a node, typically only Click needs to be restarted.
If something goes wrong with a node, there are a number of options for bringing it back to life. First, each node's Linux IP stack is configured to listen for ordinary IP packets on the radio interface, in addition to listening for Roofnet packets (which use a special ethertype). This allows communication with nodes within radio range even if the Roofnet protocols in Click are broken. Second, each node has a cron entry that reboots it every night. Third, each node has a CD-ROM drive, which it will boot from if a CD is present. We sometimes give users a CD that automatically installs a complete new system; this is useful to update the operating system itself, or to update a node that has been turned off long enough that it no longer runs a compatible routing protocol. These install CDs also make it easy for us to pre-install the software on large numbers of nodes, an otherwise tedious process.
Roofnet uses a new routing protocol called SrcRR. The main goal of SrcRR is to find high-throughput routes. The key challenges it faces are the intermediate quality of most links, asymmetric link loss rates, frequent changes in link loss rates, and frequent losses of routing protocol packets due to interference from hidden terminals.
SrcRR's general design is inspired by DSR [5,6].
When a node 
needs to find a route to a destination 
, it
broadcasts a query for . Each node 
that hears a query
forwards the query, appending its own identifier to a source route in
the packet. Each time hears a query for itself, it sends a reply
back to along the source route accumulated in the query.
Node (and every node that sees the query or reply)
adds all the links mentioned in the reply to a local link-state
database, and uses Dijkstra's algorithm on that database to
find the best route. When sends data packets to ,
it includes that route (i.e. the sequence of node
identifiers) in each packet as a ``source route.''
The primary way in which SrcRR differs from DSR is that SrcRR uses the ETX [3] metric to help it choose good routes. ETX continuously measures the loss rate in both directions between each node and its neighbors using periodic broadcasts. It assigns each link a metric that estimates the number of times a packet will have to be transmitted before it (and the corresponding 802.11 ACK) are successfully received; thus the best link metric is one. The ETX route metric is the sum of the link metrics; thus ETX penalizes both long routes and routes that include links with high forward or reverse loss rates.
A node forwards a query if it has not seen the query before, or if the query's total route metric is better (lower) than the best instance of the query the node has yet seen. This increases the amount of query traffic, but decreases the algorithm's bias in favor of shortest hop count. Nodes also delay for a random period less than one second before forwarding a query to avoid contention. When a node forwards a query, it includes the link ETX metric to whatever node it heard the query from; nodes store these metrics in their link-state databases, and use them to compute the route metric to minimize with Dijkstra's algorithm.
While a source node is sending data along a route, SrcRR uses the following techniques to discover if the route has broken or declined in quality. First, when a node forwards a data packet, it updates the packet's source route to contain the latest ETX metric from the preceding node; if the routes in the two directions are the same, this suffices to keep both ends aware of the current route quality. Second, if the 802.11 card indicates that ten packets in a row have failed to elicit an 802.11-level ACK, the node will send the current link metric to the source. Third, if a node is passing data in one direction but sees no data in the other (i.e. the route is asymmetric or broken), it will periodically send the current link metric to the source. Fourth, if a source node sees a new metric for a link it is using, it re-runs Dijkstra's algorithm to ensure it is using the best known route. Finally, if a source node notices that the route it is using has a current route ETX metric more than twice as high (half as good) as the best it has seen since the last query, it will flood a new query.
SrcRR is independent of IP, and operates at a lower layer. SrcRR uses 32-bit addresses; in the usual case in which it is carrying IP packets, SrcRR use IP addresses in its headers. A SrcRR node maintains a mapping from SrcRR 32-bit addresses to 48-bit 802.11 MAC addresses, derived implicitly from SrcRR query broadcasts.
Roofnet originally used a distance-vector protocol derived from DSDV [13], with modifications described in [3]. The main reason we switched to SrcRR is that the DSDV broadcast updates tended to be lost when competing with data traffic. As a result DSDV tended to choose good routes when the system was idle, but switched to essentially random routes whenever users started to perform file transfers. Source routing gives the source more control over how soon it switches to a new route.
You can see the SrcRR routing tables of the Roofnet gateways here. Each link fetches the routing table from a different Roofnet wired gateway. There's one line for each destination that the gateway has computed a route to. The line show the destination IP address, the route's ETX metric (times 100), various statistics, and the source route with each link's ETX metric.
The routing protocol described in the previous section knows how to deliver packets between Roofnet nodes. Usually the larger problem to be solved is communication between users' home computers and the Internet. Roofnet solves this in a way that allows auto-configuration (without requiring even IP address assignment) and allows multiple users to offer Internet access via their DSL or cable modems to other Roofnet users, although at the moment all Internet access is via MIT's campus network.
The Roofnet uses internal IP addresses of the form 10.x.x.x for management and for SrcRR routing. Using private addresses rather than routable Internet addresses ensures that Roofnet is not tied to any particular ISP, though it requires that we use NAT. A Roofnet node uses the lowest three bytes of its wireless interface's MAC address as the low three bytes of its IP address. This allows new nodes to join the system without any configuration or centralized address allocation.
By default, every Roofnet node uses the IP address 192.168.0.1 on its wired Ethernet port, and runs a DHCP server that answers queries heard on that interface. This allows users to plug the Roofnet node into their hub or computer and start using the network without manual configuration. Each Roofnet node runs a NAT that makes packets from hosts connected by Ethernet appear to come from the Roofnet node's 10.x.x.x address.
Most traffic on the network is destined for the Internet, so Roofnet has explicit support for wired gateways. Any user can configure their Roofnet node to act as a gateway to the Internet if they have, for example, a DSL or cable modem attached to the node's Ethernet port. Because the Internet connection may experience outages, each gateway periodically tests whether it can reach a few sample Internet hosts through the Ethernet port. If it can, the node floods advertisements to all Roofnet nodes saying that it is a gateway. We assume that users will only provide gateway service if their ISP allows not-for-profit sharing, as is the case for Speakeasy and Cyberion.
Each non-gateway node chooses a gateway through which to route its Internet traffic. When a node receives on its Ethernet port an IP packet destined for the Internet, it NATs the packet to its own 10.x.x.x address, encapsulates the IP packet inside a SrcRR packet addressed to the currently selected gateway, and hands the packet to SrcRR. When the gateway receives the packet, it un-encapsulates it, NATs it again so that it seems to come from the gateway's global IP address, and sends the packet out the Ethernet port. The purpose of this address translation is to hide the 10.x.x.x addresses from the Internet.
A node switches gateways only if its current gateway seems to be unreachable. This avoids unnecessarily breaking existing TCP connections by switching gateway NATs, but may cause the node to continue to use a gateway to which it has a low-quality route when better gateways are available.
Would the Roofnet system be viable as an independent community network, without significant subsidy, management, and development from our research project?
As far as technology goes, the answer is probably yes. Roofnet performs competitively with DSL and cable. It is easy for users to buy and assemble their own hardware kits; the software install is even simpler, since we provide a complete system install ISO on our web site. Experience shows that the network architecture allows it to grow easily, since no planning or management is required to add new nodes.
The current hardware cost is high ($650), much more than a cable or DSL modem. This could probably be reduced by a few hundred dollars by using a more stripped-down computer, perhaps one intended for use as a low-cost access point or router. Users who already run Linux could run our software on their existing computer. And there could easily be a Windows version. The only real cost is the wireless card, the antenna and cable, and the time for installation.
The intent is that a subset of Roofnet users will have DSL and cable links to the Internet, will be willing to give away service, and will have ISPs that allow such sharing. All of these appear to be true; multiple users have volunteered to share DSL, and at least two local DSL ISPs (Speakeasy and Cyberion) specifically allow sharing.
SrcRR is not not likely to scale to more than a few hundred nodes in its current form. It could be optimized for the common case in which nodes mostly communicate with the nearest wired gateway, since then routing traffic could be limited to gateways periodically flooding unsolicited queries.
Roofnet would quickly run out of radio capacity if a growing number of users shared a fixed set of wired gateways. We hope that a roughly constant fraction of users will volunteer to share their DSL lines, which will keep most Roofnet traffic relatively local even as the network expands.
We've lost one node due to lightning, though luckily the node's user suffered no damage. Typical users probably cannot be expected to correctly ground their lightning arrestors. Perhaps the antennas should be installed by professionals, though this would likely hinder the growth of the network.
The system currently includes no security mechanisms, and we're not sure what security policy we would want to enforce given that we intend Roofnet to be publically available. Just as in the wired Internet, we expect users who care about privacy to use end-to-end encryption schemes such as SSL and SSH. The only security problem we've had so far involved one of the users sending ``fraggle'' packets through one of the wired gateways, causing the corresponding ISP to disable that gateway's Internet link.
The idea of automatic computer-controlled routing in a mesh network dates back to Paul Baran in the early 1960s [1]. Baran envisioned a mesh of point-to-point microwave links. Baran's routing ideas were first implemented in the NPL network and the ARPANet in the late 1960s, and led to the routing algorithms used in the modern wired Internet. In the 1970s and 1980s the DARPA packet radio network (PRNet) [7] pioneered many techniques in wireless mesh networking.
The Roofnet uses routing protocols derived from prior research in mobile ad-hoc networking (MANET). We current use a derivative of DSR [5] and we've experimented with derivatives of DSDV [13]. The main focus of these protocols is handling highly mobile nodes, while our main concern is finding paths with links of good quality.
A number of research groups maintain wireless test-beds with which to test real-world performance of MANET protocols [11,10,12,9,2]. Some of these groups report that unidirectional links are common, and describe how to modify AODV and DSR to cope with such links.
Sensor networks often use multi-hop wireless networks to collect data, and thus face problems similar to Roofnet. For example, Yarvis et al. [16] observe that hop-count performs poorly as a routing metric for a sensor network, and present the results of using a loss-aware metric instead. Ganesan et al. [4] describe the behavior of a wireless sensor net, including some unexpected phenomena similar to those seen in Roofnet.
A number of community wireless mesh efforts exist, including Seattle Wireless http://www.seattlewireless.net/, the San Francisco BAWUG http://www.bawug.org/, the Southampton Open Wireless Network http://www.sown.org.uk/, and Wireless Leiden [15] http://www.wirelessleiden.nl/. Many of these networks use directional antennas to form a backbone of reliable links, over which they run a traditional wired routing protocol such as OSPF. Some, such as Roofnet and networks built from the LocustWorld MeshBox, use ad-hoc routing protocols that allow nodes to find radio connectivity opportunistically, easing deployment and increasing fault tolerance. This approach requires a more sophisticated routing protocol to avoid low-quality links.
Roofnet was developed with the help of grants from NTT Corporation under the NTT-MIT collaboration, and by MIT's Project Oxygen. We thank the many volunteers who host Roofnet nodes for their time and patience, Ben Chambers for deploying the original Roofnet, and Eddie Kohler for help with Click.
This document was generated using the LaTeX2HTML translator Version 2002-2-1 (1.70)
Copyright © 1993, 1994, 1995, 1996,
Nikos Drakos,
Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999,
Ross Moore,
Mathematics Department, Macquarie University, Sydney.
The command line arguments were:
latex2html -split 0 -no_navigation -white design
The translation was initiated by Robert Morris on 2004-07-16