PAPER 14 The topic of this lecture is network positioning: determining the  
location, by some metric, of Internet objects to improve performance  
in several applications such as finding the closest node to a  
client.  Traditional methods for accomplishing this generally assign  
each node a set of virtual coordinates that ideally represent the  
node's position relative to other nodes in the system.  Such  
coordinates are often computed by collecting a large number of  
metrics for each node and compressing them into a two-dimensional  
space.  Taking the image of all the data to such a low dimension  
loses a lot of data, and researchers have invented other techniques  
for positioning nodes in a distributed system.

The first paper, by Dabek, et al., presents a system called Vivaldi,  
which attempts to remedy the problems presented above.  While Vivaldi  
also uses virtual coordinates to maintain relative node distances, it  
does not rely on an inaccurate dimension compression.  Instead, it  
uses an insight from physics to to continually shift nodes around by  
adjusting and readjusting their coordinates based on current network  
conditions.  In physics, Hooke's Law describes the behavior of  
perfectly elastic springs and their interactions with each other.   
Vivaldi conceptually inserts springs into the network between nodes,  
which push and pull on each other based on measured statistics  
between the nodes.  Because nodes have spring relations with multiple  
neighboring nodes, adjusting the distance between a pair of nodes  
will cause other springs connected to those nodes to adjust as well,  
propagating network measurements throughout the network to maintain  
the relative distances.

One problem with virtual coordinates is that they often require O(N)  
time to update, and even when they are relatively accurate, they lead  
to suboptimal results.  Furthermore, because Internet links do not  
abide by the triangle inequality, it is impossible for virtual  
coordinates to accurately model node distances even in the best case,  
placing an inherent restriction on the accuracy of the system.  Wong,  
et al., introduces a network location system called Meridian that  
does not rely on virtual coordinates.  Each Meridian node maintains a  
constant number of concentric rings of exponentially increasing  
radii.  For each ring, the node maintains a constant number of nodes  
whose distances are proportional to the exponential distance  
represented by that ring.  Thus, each node keeps track of more close  
nodes than far away nodes.  When a node receives a query for its  
closest node, it forwards the request to the nodes in the appropriate  
ring, based on the distance of the client machine.  Thus, each  
forwarding hop gets exponentially closer to the target closest node,  
akin to an O(log N) lookup in Choord or Pastry.  As the network  
changes, Meridian nodes swap nodes in and out of the rings, replacing  
old nodes either with ones from a backup set of nodes for each ring  
or with new nodes from the network.  Each node only keeps track of a  
constant number of nodes, so system maintenance time is reduced  
without sacrificing accuracy.

Ryan

