Title:	On the Internet Delay Space Dimensionality
Authors:	Abrahao, Bruno Kleinberg, Robert
Keywords:	Internet Positioning Systems Metric Embeddings Delay Space
Issue Date:	14-Mar-2008
Abstract:	We investigate the dimensionality properties of the Internet delay space, i.e., the matrix of measured round-trip latencies between Internet hosts. Previous work on network coordinates has indicated that this matrix can be embedded, with reasonably low distortion, in a low-dimensional Euclidean space. Our work addresses the question: to what extent is the dimensionality an intrinsic property of the distance matrix, defined without reference to a host metric such as Euclidean space? Does the intrinsic dimensionality of the Internet delay space match the dimension determined using embedding techniques? if not, what explain the discrepancy? What properties of the network contribute to its overall dimensionality? Using a dataset obtained via the King method, we compare three intrinsically-defined measures of dimensionality with the dimension obtained using network embedding techniques to establish the following conclusions. First, the structure of the delay space is best described by fractal measures of dimension rather than by integer-valued parameters, such as the embedding dimension. Second, the intrinsic dimension is inherently than the embedding dimension; in fact by some measures it is less than 2. Third, the Internet dimensionality can be reduced by decomposing its delay space into pieces consisting of hosts which share an upstream Tier-1 autonomous system in common. Finally, we argue that fractal dimensionality measures and non-linear embedding algorithms are capable of detecting subtle features of the delay space geometry which are not detected by other embedding techniques.
URI:	http://hdl.handle.net/1813/10169
Appears in Collections:	Computing and Information Science Technical Reports

Files in This Item: File Description Size Format podc.pdf 177.22 kB Adobe PDF View/Open

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.