5 Measuring Coordinate Systems

In this section, we review metrics used to evaluate coordinate systems and other latency services.

Relative Error. Relative error, the most basic and intuitive measure of accuracy, is the difference between the expected and actual latencies between two nodes:

$$e = \frac{\mid \Vert\overrightarrow{x_{i}}-\overrightarrow{x_{j}}\Vert - l_{ij} \mid}{l_{ij}}$$

where the expected latency is the distance between the two coordinates.

Relative error comes in three forms: global, continuous, and neighbor. Global relative error is the accuracy from the viewpoint of an omniscient external viewer: at one instant, the metric is computed for all links. With the simulations that use a latency matrix, this is what we compute because we do indeed have this viewpoint. Continuous error is what a node computes on-the-fly as it receives new observations from remote notes. This error is added to a statistic, such as an EWMA, as in Vivaldi's confidence. Two disadvantages to continuous error are (a) a single measurement may result in a large change in value and (b) it can become skewed by a handful of remote nodes if the ``working set'' of active gossip is small. Instead of continuous error, we use neighbor error as a proxy for global error when live nodes are performing the computation themselves, e.g., within live Azureus clients. Neighbor error is the distribution of relative errors for a set of recently contacted nodes. With a large number of neighbors, neighbor error generally provides a close approximation of global error.

Stability. Stable coordinates are particularly important when a coordinate change triggers application activity. In our distributed streaming query system, for example, a coordinate change could initiate a cascade of events, culminating in one or more heavyweight process migrations [25]. If the systems' coordinates have not changed significantly, there is no reason to begin this process. A stable coordinate system is one in which coordinates are not changing over time, assuming that the network itself is unchanging. We use the rate of coordinate change

$$s = \frac{\sum \Delta \overrightarrow{x_{i}}}{t}$$

to quantify stability. The units for stability are ms/sec.

Descriptions of and results from other metrics are included in technical report version of this paper [17].