On the internet delay space dimensionality

We investigate the dimensionality properties of the Internet delay space, i.e., the matrix of measured round-trip laten- cies between Internet hosts. Previous work on network co- ordinates has indicated that this matrix can be embedded, with reasonably low distortion, into a 4- to 9-dimensional Euclidean space. The application of Principal Component Analysis (PCA) reveals the same dimensionality values. Our work addresses the question: to what extent is the dimen- sionality an intrinsic property of the delay space, defined without reference to a host metric such as Euclidean space? Is the intrinsic dimensionality of the Internet delay space approximately equal to the dimension determined using em- bedding techniques or PCA? If not, what explains the dis- crepancy? What properties of the network contribute to its overall dimensionality? Using datasets obtained via the King (14) method, we study dierent measures of dimension- ality to establish the following conclusions. First, based on its power-law behavior, the structure of the delay space can be better characterized by fractal measures. Second, the intrinsic dimension is significantly smaller than the value predicted by the previous studies; in fact by our measures it is less than 2. Third, we demonstrate a particular way in which the AS topology is reflected in the delay space; sub- networks composed of hosts which share an upstream Tier-1 autonomous system in common possess lower dimensional- ity than the combined delay space. Finally, we observe that fractal measures, due to their sensitivity to non-linear struc- tures, display higher precision for measuring the influence of subtle features of the delay space geometry.