CarNet: A Scalable Wireless Network Infrastructure
Progress Report: July 1, 2001December 31, 2001
Robert Morris and M. Frans Kaashoek
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 December 2001
In the last six months we have made the following progress:
1. We designed, simulated, and analyzed a hardened ad-hoc wireless routing system. The problem to be solved is that malicious or faulty participants in a wireless network might jam each others' transmissions, refuse to forward data correctly, or provide incorrect routing or topology information. The solution we're working on takes advantage of physically limited radio ranges; it robustly searches for a path that is outside the range of any malicious node.
2. We partially analyzed the effect of widely varying radio link quality on routing algorithms. Most routing algorithms rely on the assumption that links, to a first approximation, either work well or don't work at all; this is true in wired networks. However, the majority of links in a wireless network are of intermediate quality. This causes routing algorithms to choose paths that are good enough to carry the routing protocol's probe packets, but not good enough to be useful for user traffic. This effect turns out to be of great practical importance, especially in multi-hop routing, and little is known about how to fix it at the routing level. We've acquired a good understanding of the problem, and are developing solutions.
Research Plan for the Next Six Months
One major focus for the next six months will be completion of a routing protocol that chooses paths based on link quality. This is a high priority task -- our prototype network is almost unusable without it.
We plan to deploy a rooftop radio network, consisting of Grid nodes in the apartments of participating graduate students in the Cambridge area. This will help us gain experience of real use, since the students will use the Grid network to connect to MIT. It will also give us a second, very different, environment in which to take measurements and test new ideas. We have already built a small (4-node) rooftop net to establish that the idea is practical with the equipment available to us.
We will continue development of the Chord lookup system and peer-to-peer applications based on Chord. The areas we plan to focus on are file indexing and sharing and distributed backup.
Project Web Sites