Coordinate Systems for the Internet

该项目旨在通过探索一种新的分析方法，结合大规模网络测量，回答网络接近估计的问题，而不是直接测量。目前，用于估计网络接近度的方法非常少，这可能会在延迟和额外流量方面给应用程序和网络增加大量开销。新兴的互联网应用，如内容传递网络、点对点网络、多用户游戏、覆盖路由网络和采用动态服务器选择的应用，其最佳配置依赖于对网络接近度的精确测量。最近在网络接近估计方面的努力表明，一种有前途的方法可能是使用坐标系对网络距离进行建模；也就是说，通过将网络距离嵌入欧几里得空间。这种方法有许多吸引人的特性，但仍有许多基本问题没有得到解答：欧几里得嵌入是否普遍有效？什么是合适的维数，什么是将距离测量映射到欧几里得空间的最佳方法？最终方案的可扩展性如何？对于什么样的距离度量，这种方案是合适的？本文提出的新的分析方法是基于线性代数技术，特别是应用主成分分析来构建良好的互联网坐标系的问题。该项目将收集和分析大量网络测量数据，以评估真正具有代表性的数据上的坐标方案，并开发新的算法，用于构建准确且可扩展到数千个节点的坐标方案，并以免费分发工具的形式提供。

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.