Monitoring our PlanetLab-based coordinate service over several months revealed that coordinates migrated in a fairly constant direction. That is, the centroid of the coordinates did not move in a ``random walk,'' but instead drifted constantly and repeatedly in a vector away from the origin. This was surprising because our previous study, based on a shorter, three-day trace, had not exhibited this pattern [18].
While coordinates are meant to provide relative distance information, absolute coordinates matter too. One problem with drift is that applications that use them often need to make assumptions on maximum distances away from the ``true'' origin. For example, one could use Hilbert functions to map coordinates into a single dimension [5]. This requires an a prioriestimate of the maximum volume the coordinates may fill up. Mapping functions like Hilbert require that the current centroid not drift from the origin without bound. As Freedman et al.note, a second, more practical problem with drift is that it limits the amount of time that cached coordinates remain useful [13].
A ``strawman'' solution to drift would be to continuously redefine the origin as the centroid of the systems coordinate. Unfortunately, this would require accurate statistical sampling of the coordinate distribution and a reliable mechanism to advertise the current centroid. Our solution to drift is to apply a polynomially-increasing gravity to coordinates as they become farther away from the true origin. Gravity G is a force vector applied to the node's coordinate 
after each update:
where 
tunes G so that its pull is a small fraction of the expected diameter of the network. Hyperbolic coordinates could use a similar equation to compute gravity.
Drift does not occur in simulation if one is using a latency matrix and updating nodes randomly, because this form of simulation does not capture time-dependent RTT variability. Instead, we used a 24-hour trace of our PlanetLab service to simulate the effect of gravity; we show the effect of different strengths of gravity in Table 1. The data show that this simple technique does, in fact, keep the coordinate centroid highly stationary without affecting accuracy.
 |
To confirm the effect of gravity on a live system, we added it to our on-going PlanetLab service, which had approximately 300 participants. In Figure 13, we compare drift before and after adding gravity over two 18 day periods. The data show that gravity effectively eliminates drift. In addition, it did not reduce accuracy, which, in both cases, had a median of about 10 percent. While gravity does not actively limit rotation, we did not observe a rate greater than one full rotation per three days. Determining the cause of drift is beyond the scope of this work.
Jonathan Ledlie 2007-02-23