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.

Papers

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

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

People