On suitability of Euclidean embedding of internet hosts
Sanghwan Lee, Zhi-Li Zhang, Sambit Sahu, Debanjan Saha · ACM SIGMETRICS Performance Evaluation Review · 2006
In this paper, we investigate the suitability of embedding Internet hosts into a Euclidean space given their pairwise distances (as measured by round-trip time). Using the classical scaling and matrix perturbation theories, we first establish the (sum of the) magnitude of negative eigenvalues of the (doubly-centered, squared) distance matrix as a measure of suitability of Euclidean embedding. We then show that the distance matrix among Internet hosts contains negative eigenvalues of large magnitude , implying that embedding the Internet hosts in a Euclidean space would incur relatively large errors. Motivated by earlier studies, we demonstrate that the inaccuracy of Euclidean embedding is caused by a large degree of triangle inequality violation (TIV) in the Internet distances, which leads to negative eigenvalues of large magnitude. Moreover, we show that the TIVs are likely to occur locally , hence, the distances among these close-by hosts cannot be estimated accurately using a global Euclidean embedding, in addition, increasing the dimension of embedding does not reduce the embedding errors. Based on these insights, we propose a new hybrid model for embedding the network nodes using only a 2-dimensional Euclidean coordinate system and small error adjustment terms . We show that the accuracy of the proposed embedding technique is as good as, if not better, than that of a 7-dimensional Euclidean embedding.