2.1 Vivaldi

2.1 Vivaldi

Azureus uses the Vivaldi network coordinate update algorithm [9]. The Vivaldi algorithm calculates coordinates 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.

Figure 1: Vivaldi update algorithm.
\begin{figure}\begin{center}
\begin{algorithm}{Vivaldi}{\overrightarrow{x_{j}}, ...
...tarrow{x_{i}}-\overrightarrow{x_{j}})
\end{algorithm}
\end{center}
\end{figure}

Figure 1 shows how a new observation, consisting of a remote node's coordinate  $\overrightarrow{x_{j}}$, its confidence $w_{j}$, and a latency measurement $l_{ij}$ between the two nodes, $i$ and $j$, is used to update a local coordinate. The confidence, $w_{i}$, quantifies how accurate a coordinate is believed to be. Note that confidence increases as it approaches $0$. The algorithm first calculates the sample confidence $w_{s}$ (Line 1) and the relative error $\epsilon$ (Line 2). The relative error $\epsilon$ expresses the accuracy of the coordinate in comparison to the true network latency. Second, node $i$ updates its confidence $w_{i}$ with an exponentially-weighted moving average (EWMA) (Line 4). The weight $\alpha$ for the EWMA is set according to the sample confidence $w_{s}$ (Line 3). Also based on the sample confidence, $\delta$ dampens the change applied to the coordinate (Line 5). As a final step, the coordinate is updated in Line 6 ($u$ is the unit vector). Constants $c_{e}$ and $c_{c}$ affect the maximum impact an observation can have on the confidence and the coordinate, respectively.

Height is an alternative to a purely Euclidean distance metric. With height, the distance between nodes is measured as their Euclidean distance plus a height ``above'' the hypercube that models the latency penalty of network access links, such as DSL lines [9].

Each node successively refines its coordinate through periodic updates with other nodes in its neighbor set. In Azureus, the information used to maintain the network coordinate system is entirely piggybacked on existing messages, such as routing table heartbeats. While this does mean the coordinates induce no additional overhead (beyond 24 bytes per message for four dimensions, height, and confidence), it also means that the algorithm needed to be modified to function passively. In Section 4.2, we describe a technique we developed to incorporate information from highly transient members of the neighbor set.

Jonathan Ledlie 2007-02-23