The Inframetric Model for the Internet

Pierre Fraigniaud (1) , Emmanuelle Lebhar (1, 2) , Laurent Viennot (2)

1 LIAFA - Laboratoire d'informatique Algorithmique : Fondements et Applications
2 GANG - Networks, Graphs and Algorithms

A large amount of algorithms has recently been designed for the Internet under the assumption that the distance defined by the round-trip delay (RTT) is a metric. Moreover, many of these algorithms (\eg overlay network construction, routing scheme design, sparse spanner construction) rely on the assumption that the metric has bounded ball growth or bounded doubling dimension. This paper analyzes the validity of these assumptions and proposes a tractable model matching experimental observations. On the one hand, based on Skitter data collected by CAIDA and King matrices of Meridian and P2PSim projects, we verify that the ball growth of the Internet, as well as its doubling dimension, can actually be quite large. Nevertheless, we observed that the doubling dimension is much smaller when restricting the measures to balls of large enough radius. Moreover, by computing the number of balls of radius $r$ required to cover balls of radius $R>r$, we observed that this number grows with $R$ much slower than what is predicted by a large doubling dimension. On the other hand, based on data collected on the PlanetLab platform by the All-Sites-Pings project, we confirm that the triangle inequality does not hold for a significant fraction of the nodes. Nevertheless, we demonstrate that RTT measures satisfy a weak version of the triangle inequality: there exists a small constant $\rho$ such that for any triple $u, v, w$, we have $RTT(u,v) \leq \rho\cdot\max\{RTT(u,w), RTT(w,v)\}$. (Smaller bounds on $\rho$ can even be obtained when the triple $u,v,w$ is skewed). We call {\em inframetric} a distance function satisfying this latter inequality. Inframetrics subsume standard metrics and ultrametrics. Based on inframetrics and on our observations concerning the doubling dimension, we propose an analytical model for Internet RTT latencies. This model is tuned by a small set of parameters concerning the violation of the triangle inequality and the geometrical dimension of the network. We demonstrate the tractability of our model by designing a simple and efficient compact routing scheme with low stretch. Precisely, the scheme has constant multiplicative stretch and logarithmic additive stretch.

Domaines: Algorithme et structure de données [cs.DS]; Calcul parallèle, distribué et partagé [cs.DC]; Réseaux et télécommunications [cs.NI]; Web

Pierre Fraigniaud, Emmanuelle Lebhar, Laurent Viennot. The Inframetric Model for the Internet. 27th IEEE International Conference on Computer Communications (INFOCOM), Apr 2008, Phoenix, United States. pp.1085-1093, ⟨10.1109/INFOCOM.2008.163⟩. ⟨inria-00471723⟩