Playing Vivaldi in Hyperbolic Space
Abstract
Internet coordinate systems have emerged as an efficient method to estimate the latency
between pairs of nodes without any communication between them. They avoid the cost of
explicit measurements by placing each node in a finite coordinate space and estimating the
latency between two nodes as the distance between their positions in the space. In this paper,
we adapt the Vivaldi algorithm to use the Hyperbolic space for embedding. Researchers have
found promise in Hyperbolic space due to its mathematical elegance and its ability to model
the structure of the Internet. We attempt to combine the elegance of the Hyperbolic space with
the practical, decentralized Vivaldi algorithm.
We evaluate both Euclidean and Hyperbolic Vivaldi on three sets of real-world latencies.
Contrary to what we expected, we find that the performance of the two versions of Vivaldi
varies with each data set. Furthermore, we show that the Hyperbolic coordinates have the
tendency to underestimate large latencies (> 100 ms) but behave better when estimating short
distances. Finally, we propose two distributed heuristics that help nodes decide whether to
choose Euclidean or Hyperbolic coordinates when estimating distances to their peers. This
is the first comparison of Euclidean and Hyperbolic embeddings using the same distributed
solver and using a data set with more than 200 nodes.