Network Coordinates

A latency service can be constructed using a network embedding [8,12] that embeds measured latencies between nodes in a low-dimensional geometric space. Each node maintains a network coordinate (NC), with the goal that the Euclidean distance between two NCs is an estimate of physical network latency. Two classes of algorithms were proposed to compute NCs: landmark-based schemes, such as GNP [12], Lighthouses [13], and PIC [3], which use a fixed number of landmark nodes for NC calculation, and simulation-based approaches, such as Vivaldi [4] and BBS [16], which model NCs as entities in a physical system. Since one of our design goals for the latency service is scalability, we adopt a fully-decentralized, simulation-based approach for our NC service.

The Vivaldi algorithm calculates NCs as the solution to a spring relaxation problem. The measured latencies between nodes are modeled as the extensions of springs between massless bodies. A network embedding with a minimum error is found as the low-energy state of the spring system. Each node successively refines its NC through periodic updates with other nodes in its neighbor set.

Figure 1: Vivaldi update algorithm.

Figure 1 shows how a new observation, consisting of the remote node's NC $\vec{x_{j}}$, its confidence $w_{j}$, and a latency measurement $l_{ij}$ between the two nodes, $i$ and $j$, is used to update the local NC. The confidence $w_{i}$ quantifies how accurate a NC is believed to be. First, the sample confidence $w_{s}$ (Line 1) and the relative error $\epsilon$ (Line 2) are calculated. The relative error $\epsilon$ expresses the accuracy of the NC in comparison to the true network latency. Second, node $i$ updates its confidence $w_{i}$ with an exponentially-weighted moving average (Line 4). The weight $\alpha$ is set according to the sample confidence $w_{s}$ (Line 3). Also based on the sample confidence, $\delta$ dampens the change applied to the NC (Line 5). As a final step, the NC is updated in Line 6 ($u$ is the unit vector). Constants $c_{e}$$=$$c_{c}$$=$$0.25$ affect the maximum impact an observation can have on confidence and NC, respectively [6]. We define the stability of a NC as its total change over time in $\mathrm{ms/s}$.