SP: Very Fine-Grained Proximity Addressing

Cornell University, Ithaca NY

Investigators

Abstract

Today host computer systems attached to the Internet have two basic identifiers: the IP address and the Domain Name. Neither identifier reliably indicates how systems are "positioned" in the Internet with respect to each other. Two IP addresses or Domain Names may be very similar, and yet the two systems they represent may be far apart in terms of latency or throughput. This lack of a proximity "address" is a serious limitation of the Internet architecture. There have been several research projects to address this limitation. The pioneering work in this area was IDMaps, which proposed an infrastructure service that could answer queries about proximity between pairs of IP addresses. A subsequent advancement proposed using Global Network Positioning (GNP)a proximity address formed from a Cartesian coordinate system super-imposed on the Internet. The primary shortcoming of these and other approaches is that they operate only at course granularity. At less than 50ms latency (a typical east-to-west coast latency!), over-estimates of 200% and 300% are common. This is entirely inadequate for applications such as networked first person shooter games and tightly-coupled grid computing applications, both of which require latencies well below 50ms. Data intensive grid computing applications and peer-to-peer applications like file sharing would reduce network load significantly if participants in the same campus network or ISP could find each other. Another shortcoming of existing approaches is that they typically require that dedicated infrastructure be deployed. While this is feasible for private corporations like Akamai, there exists no known business model for a common public proximity service. This project will design and implement a system for calculating proximity addresses at very-fine granularity (microsecond latencies and gigabit throughputs) and at global scale. By necessity this system will be distributed (peer-to-peer), requiring that all nodes be able to serve as "reference points" in the coordinate system. This is because it is impossible to represent microsecond latencies unless the reference points are within microseconds. The existence of a global fine-grained hierarchical proximity address, however, presents other tantalizing possibilities. For instance, such an address could be used as the basis for building a new type of routing overlay, which could then be used as a peer-to-peer discovery mechanism. This project presents significant new intellectual challenges comparable to those in network routing required to move from flat addressing to hierarchical addressing. The research team plans to design new forms of proximity addressing that are hierarchical rather than flat, that do not focus load on a few systems, and that are simple enough that they can be auto-configured. The researchers also must design new types of P2P networks that are customized for the problem of configuring proximity addresses. These P2P networks must be simpler than current networks so that they can truly scale to global proportion even in the face of churn (nodes joining and leaving). This project is expected to produce broad intellectual results in the structure of hierarchical proximity addresses and how they relate to network metrics, as well as in how to build very large and simple peer-to-peer networks. This project will have two forms of impact. First, any distributed application that dynamically discovers participants, and requires that participants be nearby, will benefit from very-fine grained proximity addresses. Such applications include networked games and Grid computing. Indeed the improvements in granularity may enable the creation of new applications. Second, the advances in peer-to-peer networking required for this project may serve as the basis for other types of peer-to- peer applications. Specifically, any peer-to-peer application that requires the discovery of nodes that can serve a certain role (i.e., act as reference points) will benefit from the advances in scale and efficiency required for this project.