OverviewRouting overlays (such as RON) have the potential to circumvent Internet pathologies to construct faster and more reliable paths. However, they have yet to become ubiquitous because they do not incorporate mechanisms for finding and negotiating with mutually advantageous peers: nodes in the overlay that can benefit equally from each other. Surprisingly, mutually-advantageous peers exist in the Internet and can support a latency-reducing overlay.
To find these mutually advantageous peers, we exploit the embedding error in network coordinates. The short "detour" paths and the surprisingly long pathological paths in the Internet are not well captured by coordinates because these edges violate the triangle inequality. By remembering these edges with high embedding error, nodes can discover helpful peers.
Embedding Error in Network Coordinates
Internet coordinates like GNP and Vivaldi give each host a coordinate so that the distance between coordinates predicts the latency between hosts. Coordinate systemes use metric spaces, where the triangle inequality (AB+BC≥AC) cannot be violated. However, the policies and pathologies of Internet routing permit such violations, leading to embedding error.
We believe that links with high embedding error are those that should be used (if the actual path is shorter than predicted) or avoided (if the actual path is longer). Further, network coordinates can make the discovery of such interesting links scalable. Detour showed that better paths existed than those chosen by BGP, but not how to find them scalably or how to predict whether a detour will exist for your paths.
In the example at right, A and B have a mutually-advantageous peering: A can use B to get to C faster than the direct path and B can use A to get to D.
Our current work lies in understanding these relationships, in quantifying the potential performance and reliability advantages, and in deploying a seed system on PlanetLab.
Latency data set (with AS path information) between 1715 IP addresses
pw-1715 (58MB, 7 files, see README for description)
Latency data set between 325 PlanetLab nodes and 500 popular, multiple-IP web servers
pl-dest (0.8MB, 3 files, see README for description)
Latency data set between 325 PlanetLab nodes and 795 popular prefixes
pl-prefixes (1.4MB, 5 files, see README for description)