Computer Science Colloquium
Thursday, March 27,  2003
4:15 PM
B17 Upson Hall

 Eugene Ng
Carnegie Mellon University

Global Network Positioning

The Internet is a highly complex engineering artifact globally connecting hundreds of millions of hosts through multiple layers of networking technologies. This global infrastructure creates a huge opportunity for a new generation of Internet-scale distributed systems to harness the collective power of the computation, storage, and communication resources of Internet hosts. Systems such as overlay multimedia broadcasting networks and peer-to-peer file systems are being researched and prototyped and are showing great promise. A crucial requirement common to these systems is that communications among hosts must be carefully organized because hosts far apart in the Internet cannot communicate efficiently, and an arbitrary organization may lead to failing performance. Given the scale and complexity of the Internet, discovering and managing the all-to-all network distance relationship among hosts seems like a formidable challenge.

In this talk, I will present a surprising discovery that the network distance relationship resulting from the complex Internet structure can be accurately modeled in a low-dimensional Euclidean space, and this model can be obtained by a simple technique called Global Network Positioning (GNP). With GNP, hosts can be assigned positions represented by coordinates, and the O(N^2) network distance relationship can be reduced to O(N) host positions. Accurate network distance estimates can be rapidly computed based on positions, thus removing a major scalability and performance bottleneck of Internet-scale distributed systems. To realize this potential, we have designed and implemented a GNP-based positioning service that enables every Internet host to independently determine its position. I will show that the service is scalable to the size of the Internet, is reliable, and can self-adapt to changes in the network topology. Our work is already being applied to the design of several distributed systems. We believe GNP may also provide a new angle to study the topology and the evolution of the Internet.