PAPER 13 PREDICTING INTERNET NETWORK DISTANCE WITH COORDINATES-BASED APPROACHES

We would like to be able to predict network distances (RTTs) for the  
internet without having to send probes each time.  One potential  
solution is to have a set of servers which maintains a simplified  
view of the network topology with RTTs.  A node can request data from  
the server and predict a desired RTT.  This however, produces a  
bottleneck at these servers, and additional latency is incurred  
requesting the data from the server.

A second solution is to use triangulated heuristic coordinates, or  
hop counts to some base stations nodes in the network.  The accuracy  
is often less than desired.

The authors propose Global Network Positioning (GNP) where there is a  
set of well known landmark nodes in the network, and the node in  
question trilaterates its position in a 3-D euclidian space relative  
to the landmark nodes.  The authors find that this scheme functions  
relatively well, although the slides do not mention how, due to  
inconsistencies in link latencies in the network, inconsistent  
localization from more than 3 landmark nodes is handled.


VIVALDI

Vivaldi, like GNP, places nodes in a virtual 3D (more precisely a 2D  
with directionless height, or 2.5D) space where euclidian distance  
between nodes is indicative of RTT.  The primary difference between  
the two is that Vivaldi does not use a set of landmark nodes like  
GNP.  Vivaldi implements a decentralized version of the following  
optimization:  Consider the network as a complete graph, with each  
edge as a spring.  The resting length of the spring is the true RTT  
between to vertices (nodes).  Nodes have been positioned optimally  
for a given virtual space when the sum of the potential energies of  
all springs is minimized (the springs will be stretched to satisfy  
low number of dimensions in the virtual space).  This in fact will  
naturally occur if the mass of nodes and springs is allowed to float  
freely in space and stabilize under it's own forces.  As potential  
energy is proportional to distortion squared for springs, this solves  
a least squares fitting problem.  It is possible to simulate this  
self-stabilization in both a centralized and decentralized manner,  
Vivaldi uses the latter.  Optimizations of the distributed simulation  
allow the system to react gracefully to the introduction of a large  
number of nodes into the network.

The authors find the system to be comparable in accuracy to GNP, a  
centralized scheme.  It is further refined by the use of a 2D +  
directionless height vector space, rather than a 3D space.


MERIDIAN

Meridian does not use a virtual coordinate system like GNP or  
Vivaldi, despite serving the same goals.  Each node keeps O(log N)  
state in the form of a set of peers organized by concentric rings of  
increasing network distance radii.  Much in the spirit of prefix  
routings ability to move exponentially closer to a target in an  
identifier space, Meridian jumps exponentially shorter distances  
towards a target.  Membership structure in these rings is loose,  
allowing a gossip protocol to be used to refresh and fill rings.

Simulation demonstrates that Meridian produces superior performance  
to GNP and Vivaldi.

