9807-04
Progress Report
January 1 – June 30, 1999
Hari Balakrishnan and John V. Guttag
Graduate Students: William Adjie-Winoto, Anit Chakraborty, Jeremy Lilley, Bodhi Priyantha
Graduated: Elliot Schwartz
URL: http://wind.lcs.mit.edu/
The goal of the WIND project at MIT is to design and implement self-organizing networks with a high degree of decentralization, robustness and distributedness in their operation. The WIND protocols and middleware provide built-in support for user and device mobility, resource discovery, service location, and group communication in a decentralized manner. Our key innovation is the use of an intentional naming architecture where applications describe what they are looking for (i.e., their intent), not where to find it (which is how most network naming schemes work today). In this architecture, name resolvers can also route messages to the eventual destinations, leading to an integrated approach to resolution and routing. Thus, WIND is built around the premise that a flexible naming architecture and the ability of the name resolution process to be involved in data routing is a key enabler of large-scale self-organizing device networks.
Our application scenario uses these building blocks to demonstrate a location-aware applications over heterogeneous indoor wireless technologies (in-building RF wireless LAN and Infrared). Here, users can access data and control dynamic, mobile information sources (e.g., mobile cameras, sensor nodes) as well as enable devices to obtain information based on their location (e.g., if you walk into a specific room, the devices, nodes and users in that room automatically become known to your handheld or laptop computer) or other system characteristics. Our vision is to achieve all this with no prior
manual configuration. The navigation metaphor for WIND is via an active map application called "floorplan".
1. WIND Applications
Over the past few months, we have developed the following WIND applications and have deployed them in a limited fashion within our group: (i) floorplan, an active map navigation tool, (ii) camera, a mobile camera application for both image updates from locations as well as real-time streaming and conferencing, (iii) printer, printer utility that allows users to print to "locations" or other attributes, where the system picks the nearest, least loaded printer to direct the request to, and (iv) TV, a remote television and MP3 control using WIND middleware.
All of these applications use the Intentional Naming System (INS) and WIND protocols
2. Self-configuring Intentional Name Resolvers (INRs)
An important design goal for WIND is the elimination of manual configuration of the network and middleware. To this end, we have been working on the design of automatically configuring INR overlay networks. This has three aspects to it:
(i) Bootstrap. In the absence of any INRs in a domain, new ones have to be automatically spawned. We have developed techniques using the Internet Domain Name System (DNS) for this.
(ii) Neighbor formation. INRs form an application-level overlay network to resolve requests and route messages to the eventual destinations. We have developed distributed algorithms to form automatically form neighborhoods and produce an overlay network without manual intervention. Currently, our algorithm performs application-level measurements and uses the resulting throughput and latency as link weights between INR nodes, and produces bandwidth- and latency-tuned spanning trees. We are actively working on algorithms to produce more redundant structures without single points of failure (trees have numerous cut-vertices, whose removal disconnects the overlay graph and caused disconnectivity).
(iii) Load balancing. INRs monitor their load and are capable of spawning instances on other nodes when they get overloaded.
3. Firewall operation
We have modified the Java kernel that WIND and INS link to so that applications and the WIND protocols can work across firewalls without any modifications. Currently, we have demonstrated our system across a SOCKS firewall, which allows TCP connections originating from inside the firewall but not always in the other direction. Since many of WIND's protocol messages and applications run over UDP, our solution was to capture UDP receive calls and transparently convert them to originating TCP connections to a proxy machine in the Internet. This proxy machine in turn acts on behalf of the machine inside the firewall, tunneling all messages to it via the established TCP connection. The advantage of our approach is that applications do not need to be modified.
4. Theses, papers, software
In May 1999, Elliot Schwartz filed his Master's thesis titled, "The Design of Intentional Names," a detailed description of the format of WIND's intentional names and its lookup algorithms.
A paper, "The Design and Implementation of an Intentional Naming System," was recently accepted for publication at the ACM Symposium on Operating Systems Principles (SOSP) 1999, one of the premier conferences in the area of computer systems. We are in the process of making revisions for the camera-ready version.
We have a preliminary alpha version available for use. At this point, it is tuned for operation within LCS, but this is relatively easy to fix. The default "browser" is the floorplan tool described above, since we believe that a geographic browser is a natural user interface for location-based context-aware applications when discovering and using services.
1. Design scaling techniques for large-scale INS desployment.
Currently, the INS design works for small to medium-sized networks, and is not intended for wide-area operation. We have starting on this problem. Our approach is to use a technique called "virtual space partitioning," where any INR only resolves for a subset of the entire namespace. We are also designing a wide-area architecture to interface with the DNS.
2. Use beaconing and triangulation techniques for automatic location discovery and map dissemination.
Currently, our "active" map dissemination relies on users to inform the system of their current location. We are working on an automatic tracking system to allow clients to automatically infer their location and have the appropriate maps downloaded to them.
3. Complete porting WIND software to Palm III to use from handheld PDAs.
This has been done partially, and we expect to finish this by December.
4. Conduct performance experiments.
We intend to conduct experiments to measure the performance of our name resolution algorithms, discovery times, and self-organization protocols (when it is implemented).