CarNet: A Scalable Wireless Network Infrastructure

MIT2000-06

Progress Report: January 1, 2002—June 30, 2002

Robert Morris and Frans Kaashoek

Project Overview

The central goal of the Carnet project is to design and build decentralized, self-organizing network systems. Existing networks depend on centralized management at all levels, from deployment of physical infrastructure all the way up to the structure of client/server applications. Centralized architectures are an obstacle in the way of many new uses of networks, including interacting smart devices, peer-to-peer applications, and pervasive deployment in environments without existing infrastructure. The Carnet project addresses this obstacle at two related levels: the Grid network protocol provides communication, and the Chord lookup service organizes distributed applications.

The Grid network protocol automatically organizes radio-equipped nodes into a network. It does this without relying on any pre-deployed infrastructure; in particular, it does not depend on base stations or access points. Instead, Grid nodes cooperatively forward each others' data, with each node essentially acting as a router. This architecture is an ideal way to avoid pre-configuration for smart devices; it also works well when infrastructure is not convenient, as in rooftop radio networks. A major contribution of Grid is its scalable routing protocol, which is built around a peer-to-peer lookup system. Grid also includes power-saving radio control mechanisms for battery-powered nodes, location tracking support for position-aware applications, and hardening techniques to limit the damage caused by malicious or malfunctioning participants. Much of the project effort has gone into the construction and evaluation of a working implementation, consisting of about 30 nodes distributed on multiple floors of the LCS building.

In the last year we have started a second major area of effort in support for robust peer-to-peer applications. Such applications are appropriate in the same situations as Grid: when centralized servers are not available, or not desirable, and the participants in the system must organize themselves into a cooperative service. The key challenges in this area are scalability, load balance, and robustness in the face of unreliable participants. The current focus of our work is a distributed hash-table algorithm called Chord; this one data structure turns out to be powerful enough to form the basis for a wide variety of peer-to-peer applications. Examples that we are exploring include file sharing, distributed web servers, backup storage systems, and DNS-like lookup services.

Progress Through June 2002

In the first half of 2002 we worked on three main areas: expanding the roof-top Grid network, investigating robust routing in the face of low-quality wireless links, and designing a read/write peer-to-peer file system.

The roof-top network consists of nodes in about 10 graduate student apartments in Cambridge. Each node consists of a PC running the Grid software, an 802.11 wireless card, and an antenna mounted on the apartment roof (typically attached to the chimney). The goal of the roof-top network is to help us gain experience of real use, since the students will eventually be able to use the net to connect to MIT. It will also give us a second, very different, environment in which to take measurements and test new ideas. The current network is still not dense enough, in the sense that most of the inter-node links are at or beyond the radio’s rated maximum range. On the other hand, the network is close to working; a relatively small number of additional nodes would probably increase the node density sufficiently.

We continued to investigate the impact of low-quality wireless links on the robustness of routing. The problem is that many links are of relatively low quality (i.e. they lose many packets), and that link quality changes at all time scales. The result is essentially that routing protocols are tricked into using paths that include low-quality links, even though higher-quality (but perhaps longer) paths exist. In order to understand the problem better, we finished a complete survey of the link characteristics between all pairs of nodes in both the in-building LCS network and the roof-top network; the information gathered includes time series of loss rates and signal strengths. We used this data to drive simulations of existing routing protocols and analyze how they would handle our network conditions. The next steps include designing and evaluating new algorithms for choosing high-quality routes.

Our third area of effort was the design of the “Ivy” read/write peer-to-peer file system. Most existing peer-to-peer storage systems support only read-only publishing; that is, each piece of data can only be written by whoever originally published it. Supporting multi-user shared read/write access poses two main challenges: maintaining the consistency of the file system’s internal data structures despite multiple writers, and tolerating malicious and faulty participants. Both these problems are exacerbated by the decentralized peer-to-peer structure of the system; for example, a central lock manager is not a reasonable way to ensure consistency. The Ivy design solves these problems. The key idea is to have each participant append information about writes only to its own log, but to read the logs of all participants; this allows Ivy to completely avoid centralized data structures, and allows participants to simply not read the logs of untrustworthy users. Ivy will allow users to collaborate in maintaining shared files in very unstructured environments, in particular without any need for dedicated file servers.

Research Plan for the Next Six Months

We plan to continue work in all three of the above areas. We’ll continue to expand the roof-top net and improve it until it is production-quality. We will continue to measure the behavior of routing algorithms on our wireless test-beds and to design improved algorithms. Finally, we will continue to design and implement Ivy.

Project Web Sites

http://www.pdos.lcs.mit.edu/grid/

http://www.pdos.lcs.mit.edu/chord/