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:

  • Peer-to-peer architecture friendly: GNP can naturally be incorporated into peer-to-peer applications since end hosts can easily maintain geometric coordinates that characterize their locations in the Internet.

  • High prediction accuracy: To the best of our knowledge, GNP has the highest accuracy among proposed Internet distance prediction methods, including Triangulated Heuristics and IDMaps, when a light-weight infrastructure is used (i.e. when the number of Landmarks/Tracers/Base nodes used is on the order of 10). GNP prediction error in most cases is less than 50%.

  • Extremely fast: When an end host discovers the identities of other end hosts in a peer-to-peer application, their pre-computed coordinates can be piggybacked, thus network distances can essentially be computed instantaneously by the end host. There is no additional communication delay whatsoever. The off-line computation of host coordinates is also very simple and fast.

  • Highly scalable: Another benefit of GNP is that coordinates are highly efficient in summarizing a large amount of distance information. For example, in a multi-party application, the distances of all paths between K hosts can be efficiently communicated by K sets of coordinates of D numbers each (i.e. O(KD) of data), as opposed to K(K-1)/2 individual distances (i.e., O(K^2) of data). Thus, this approach is able to trade local computations for significantly reduced communication overhead, achieving higher scalability.

  • Structured representation: The geometric coordinates of hosts generated by GNP describe a simple and yet highly structured representation of the complex Internet topology. Many algorithms can then take advantage of this structure to perform topologically aware operations on the Internet in a scalable fashion. See our applications section for some examples.

    To learn more about GNP, please see our papers and presentations.

    Back to GNP Home