GNP Overview |
Achieving high performance is a key challenge in building large-scale globally-distributed network services and applications such as distributed content hosting services, overlay network multicast, content addressable overlay networks, and peer-to-peer file sharing such as Napster and Gnutella. This is because these systems have a lot of flexibility in choosing their communication paths, and they must select these paths intelligently based on network performance as the Internet is a highly diverse place. For example, in a peer-to-peer file sharing application, a client ideally wants to know the available bandwidth between itself and all the peers that have the wanted file. Unfortunately, although dynamic network performance characteristics such as available bandwidth and latency are the most relevant to applications and can be accurately measured on-demand, the huge number of wide-area-spanning end-to-end paths that need to be considered in these distributed systems makes performing on-demand network measurements impractical because it is too costly and time-consuming.
To bridge the gap between the contradicting goals of performance optimization and scalability, we believe a promising approach is to attempt to predict the network distance (i.e., round-trip propagation and transmission delay, a relatively stable characteristic) between hosts, and use this as a first-order discriminating metric to greatly reduce or eliminate the need for on-demand network measurements. Therefore, the critical problem is to devise techniques that can predict network distance accurately, scalably, and in a timely fashion.
Global Network Positioning (GNP) is a solution designed to achieve these goals. The key idea is to represent the complex structure of the Internet by a simple geometric space (e.g. an N-dimensional Euclidean space). In this representation, each host in the Internet is characterized by its position in the geometric space with a set of geometric coordinates. If the representation is accurate, then the easily computable geometric distances between hosts in this geometric space can accurately approximate the Internet network distances, and no actual network measurements are required. In extensive Internet experiments, we have found that by using a 7-dimensional Euclidean space, in 90% of the cases, GNP can predict the Internet distances among a globally distributed set of hosts with less than 50% error. The accuracy is even higher when the hosts are restricted to within a single Autonomous System.
Key distinguishing properties:
To learn more about GNP, please see our papers and presentations.