Networking From the Rooftop

A few weeks ago, MIT graduate student Shan Sinha canceled his broadband Internet service. Now his Net connection comes through the chimney. From a computer in the living room of his Cambridge, MA, apartment, a few blocks from the MIT campus, a cable goes into the fireplace up to the roof, where it is attached to an antenna. From there, data packets hop to another roof-mounted antenna at a nearby student’s apartment. That way, from roof to roof in multiple hops, Sinha’s data packets finally reach a gateway-a computer connected to the fixed Internet-at MIT’s computer science building. “We can’t use the fireplace,” he says, “but that’s the cost of free Internet.”

Sinha’s “chimney connection” is part of MIT’s Roofnet, a project to create a self-organizing wireless network in which an amorphous, unmanaged collection of cheap Linux computers equipped with Wi-Fi cards collaborate to efficiently route data packets. Each computer and roof-mounted antenna at students’ apartments and MIT buildings is a node on the network and the arrangement in which they are connected to each other-the topology of the network-is constantly changing.  “We want to understand how a whole bunch of computers with short-range radios can self-configure a network, forming order out of chaos,” says computer science professor Robert Morris, who coordinates the project. The network has now more than 30 nodes in a 4-square kilometer area surrounding the MIT campus. “We hope to reach a hundred nodes within a few months,” he says.

Research groups at universities such as Carnegie Mellon, Rice, UCLA, and the University of Illinois at Urbana-Champaign, and at companies such as Nokia, Intel, and Microsoft are developing similar systems. In each case, data packets are routed through geographically dispersed and wirelessly connected nodes that can be fixed in a building or moving with a user or vehicle. Applications of these so-called multi-hop mesh networks include systems to connect people carrying PDAs, tanks on a battlefield, or a large number of sensors in a factory plant. And community mesh networks such as Roofnet, which are much cheaper to deploy than DSL or cable hookups, are a promising way to overcome the “last mile” barrier and bring high-speed Internet access to a large number of people, especially those who live in rural areas or other places where the infrastructure for wired broadband access is not available.

Community-owned wireless networks have appeared in several places in New York, San Francisco, Seattle, London, and other cities. These networks usually consist of a few interconnected base stations-known as wireless access points-located in windows and rooftops providing Internet connectivity in public spaces. The new generation of mesh networks such as Roofnet cover wider areas and are much more dynamic in the way they route data. Their nodes are not permanently connected; instead, they constantly revaluate the existing links and form new ones. As a result, data follows much more tortuous paths to reach the fixed Internet. And with tens or hundreds of nodes-some of them joining and leaving the network in a random fashion and thus constantly changing its topology-a difficult problem arises: how should data in these multi-hop wireless nets be routed? What paths in this labyrinth of rooftop and window antennas optimize the flow of packets?

Distance Matters

Most of the routing protocols now being proposed by mesh network researchers borrow the shortest-path strategy used in the fixed Internet. These protocols try to find the route with the fewest number of intermediate nodes between sender and destination. For the wired Internet-with its nearly static topology and reliable links-this scheme has been working pretty well: our e-mails hop from router to router and reach the other side of the world in a few seconds.

But it turns out that this shortest-path strategy might not be adequate for sending packets through the air. In a wireless network, according to the MIT group, distance matters: the longer the signal has to travel, the more it will degrade. Moreover, the link quality between nodes varies unpredictably due to such transient phenomena as trucks driving by, moisture in the air, or a pigeon sitting on the antenna. The result is a considerable amount of packet loss, transmission errors, and connections that simply appear and disappear throughout the day. A routing protocol that minimizes the number of hops ends up choosing longer distances for each hop-and therefore sending data over low-quality wireless links.

The MIT group realized that new routing strategies were necessary when they deployed an initial version of Roofnet last spring. They tried to implement some of the proposed routing protocols discussed by the Internet Engineering Task Force, the organization governing the Internet’s technical standards. But while these protocols work well in theory-and are generally tested in computer simulations or small-scale, laboratory networks-they don’t take into account many unpredictable factors involved in radio communication. The protocols usually assume, for example, that when one node can detect one nearby, it can communicate well with its neighbor. But that turns out not always to be true. The MIT researchers and other groups have found that many times two nodes can “hear” each other by exchanging small probe packets, but when they try to send real data, communication collapses due to inadequate bandwidth. Morris and his group decided that the best way to develop robust wireless routing protocols was to test them with a real network, real users, and real traffic.

Other mesh network researchers say the MIT work represents an important advance for debugging these routing schemes. “Their work is grounded in real system building,” says Victor Bahl, a senior researcher who leads the networking group at Microsoft Research in Redmond, WA. “The insight that you get out of building things is a lot more than you’ll ever get if you just simulate things.” Demonstrating that such networking is viable in a real, large-scale implementation, he says, is a crucial step toward attracting more industry attention to the technology’s potential.

Deploying such a network became possible because Wi-Fi technology has gotten so cheap. A few years ago, Morris says, the price of the wireless cards would have made the project prohibitively expensive. Each Roofnet node uses an 802.11b wireless networking card installed on a cheap PC running Linux and the routing software. A coaxial cable connects the wireless card to an omnidirectional antenna. The user then connects the PC to the Roofnet node. The total cost of the equipment for each node is $685.

To deploy the network quickly, the MIT group distributes free self-installation kits to students who want to participate in the project. For these students, getting the Roofnet node running is part of the fun. “Our antenna was put up by a friend of mine who does rock climbing,” says graduate student Roshan Baliga, who lives in a two-story building with no easy roof access. “He scaled the side of the apartment to get to the roof, installed the antenna, and then rappelled down.”

MIT students are happy to participate in the project, especially because they can save some money. “We compared a broadband cable connection to Roofnet and couldn’t tell the difference, so we cancelled the cable,” says MIT senior Walt Lin, who installed the antenna on his sloped roof.

The Road Ahead

With students surfing the Web, downloading music files, and working on problem sets on remote servers, the network is running with real traffic. Now Morris and the four graduate students working with him full time on the project can test different routing strategies that better adapt to the hostile wireless environment.

Their idea to cope with the unpredictable environmental disruptions is to figure out not just whether two nodes can hear each other, but also measure how well they can communicate. Instead of finding the shortest path between two nodes, their protocols try to find the best path-the one in which data packets won’t get stuck or corrupted along the way. This requires a constant monitoring of the links. Roughly once per second, each node sends out a small “hello” broadcast packet. All the other nodes record whether they receive this probe, keeping a history of the last 10 probes. So if, say, node A has sent out 10 probes and node B received 8 and node C received 4, then the routing software knows that the path A-B is better than path A-C. Also, every 15 seconds, every node sends a broadcast message that lists the nodes it knows how to reach-and the link quality for each associated path. That way, all nodes have a complete, continually updated, routing map of the entire network-and know the optimal routes for reaching one another.

In building Roofnet, the MIT researchers found many things they didn’t expect. For example, the range of the 802.11b cards and antennas vary considerably. “We’re now skeptical about what manufacturers say,” says John Bicket, one of the grad students working on the project. “We found nodes that couldn’t talk across the street, but others could talk half a kilometer apart.” The cause might be local environmental conditions or even multiple reflections of the same signal that cancel themselves out. Another surprising phenomenon is the lack of symmetry in the link transmission quality: it is not uncommon for node A to be able to send data to node B easily, while node B can’t reciprocate. Such anomalies complicate the development of routing schemes.

By debugging and fine-tuning their routing schemes, the MIT researchers hope they will be able to use them in even more complicated systems. One such situation would be when nodes are not static in rooftops, but moving at different speeds in all directions-a scenario not far in the future, as more and more people carry personal digital assistants and cars are beginning to be equipped with computers. “It’s a matter of tuning the protocol so that it can handle mobility,” says Sanjit Biswas, another student involved in the project.

Ultimately, Morris says the group plans to release the Roofnet routing software as a freely dowloadable open source program. That means that anyone with a computer and a Wi-Fi card would be able to install the routing software and become a node in the network. Other people in other areas could also download the software and create their own rooftop community networks.

Of course, many problems still need to be addressed. First, MIT can’t provide Internet access to non-MIT affiliates; the network would therefore eventually have to find other gateways to the fixed Internet. But that raises another complicated issue: most Internet service providers don’t want their users sharing their bandwidth. Also, the community networking technology needs to guarantee a certain level of security and privacy. With users literally sending their data through the air, via other people’s nodes, some sort of encryption will probably be necessary to avoid eavesdropping. It is also necessary to guarantee a fair, balanced used of the system, to avoid that a single user sucks all the bandwidth and clogs the network. Finally, the system needs to be robust enough to resist some more pragmatic problems-such as when snow forms in the antennas.

When the day comes, what will happen? Again, the MIT group wants to learn by doing. “We’ll see,” says Morris.