On the Treeness of Internet Latency and Bandwidth

Venugopalan Ramasubramanian, Dahlia Malkhi, Fabian Kuhn, Mahesh Balakrishnan, and Aditya Akella


Describing a complex and large network such as the Internet in a concise way, that brings out its fundamental properties, is a task that has challenged researchers for many years. Existing work on internet structure – and empirical reasoning -- indicates that it is tree-like. This works quantifies the degree to which at least two important internet measures---latency and bandwidth---approximate tree metrics. We evaluate our ability to model end-to-end path attributes using a tree embedding by actually building tree representations. In addition to being simple and intuitive models, these trees provide a range of commonly required functionality beyond simple attribute modeling.

The benefits of our study are twofold. First, we investigate
the ability to portray the inherent hierarchical structure of
internets using the most pure and compact topology, trees.
Second, trees obviate many natural tasks, such as shortest path
routing and selection of multicast spanners. Our study shows
that these tasks can be done with high degree of success and
little overhead.


Publication typeInproceedings
PublisherAssociation for Computing Machinery, Inc.
> Publications > On the Treeness of Internet Latency and Bandwidth