This project seeks to answer the questions of network proximity estimation, other than direct measurement, by exploring a new analysis approach, combined with large-scale network measurement. Currently, there are very few methods for estimating network proximity, which can add significant overhead to both application and network in terms of delays and additional traffic. Newly emerging Internet applications, e.g. content delivery networks, peer-to-peer networks, multiuser games, overlay routing networks, and applications employing dynamic server selection, depend for its optimal configuration on accurate measures of network proximity. Recent effort in network proximity estimation has suggested that a promising approach may be to model network distances using coordinate systems; that is, via an embedding of network distances into Euclidean space. This approach has many appealing properties, but many fundamental questions remain unanswered: Is a Euclidean embedding effective in general? What is the appropriate dimension to use, and what is the best method for mapping distance measurements into a Euclidean space? How scalable are the resulting schemes? For what sorts of distance metrics are such schemes appropriate? The new analytic approaches proposed here are based on linear algebraic techniques, in particular the application of Principal Component Analysis to the problem of constructing good coordinate systems for the Internet. This project will collect and analyze a large set of network measurements to assess coordinate schemes on truly representative data and develop new algorithms for constructing coordinate schemes that are accurate and yet scalable to thousands of nodes, made available in the form of freely distributed tools.
