Overview

Routing 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.

At right is a triangle inequality violation (59<62) that in the embedding is given very different predictions. This is a real triple extracted from Vivaldi on King data.

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.

Mutual Advantage

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.

Data Sets

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)

Papers

Cristian Lumezanu, Randy Baden, Neil Spring, Bobby Bhattacharjee
Triangle Inequality Variations in the Internet pdf
IMC, 2009

Cristian Lumezanu, Randy Baden, Dave Levin, Neil Spring, Bobby Bhattacharjee
Symbiotic Relationships in Internet Routing Overlays pdf
NSDI, 2009

Cristian Lumezanu, Randy Baden, Neil Spring, Bobby Bhattacharjee
Triangle Inequality and Routing Policy Violations in the Internet pdf
PAM, 2009

Dave Levin, Randy Baden, Cristian Lumezanu, Neil Spring, and Bobby Bhattacharjee
Motivating Participation in Internet Routing Overlays pdf
NetEcon, 2008

Cristian Lumezanu, Neil Spring
Measurement Manipulation and Space Selection in Network Coordinates pdf
ICDCS, 2008

Cristian Lumezanu, Dave Levin, and Neil Spring
PeerWise Discovery and Negotiation of Faster Paths pdf
HotNets, 2007

People