On suitability of euclidean embedding for host-based network coordinate systems

Sanghwan Lee, Zhi Li Zhang, Sambit Sahu, Debanjan Saha

Research output: Contribution to journalArticlepeer-review

27 Scopus citations

Abstract

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 two-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 seven-dimensional Euclidean embedding.

Original languageEnglish (US)
Article number5235089
Pages (from-to)27-40
Number of pages14
JournalIEEE/ACM Transactions on Networking
Volume18
Issue number1
DOIs
StatePublished - Feb 2010

Bibliographical note

Funding Information:
Manuscript received February 24, 2008; revised September 28, 2008; approved by IEEE/ACM TRANSACTIONS ON NETWORKING Editor A. Feldmann. First published September 11, 2009; current version published February 18, 2010. This work was supported in part by Research Program 2008 of Kookmin University, Korea; by the National Science Foundation under Grants ITR-0085824, CNS-0435444, CNS-0626812, and CNS-0626808; and by an IBM Faculty Partnership Award. An earlier version of this paper was presented at ACM Sigmetrics/Performance 2006 [1].

Keywords

  • Euclidean embedding
  • Suitability
  • Triangle inequality

Fingerprint

Dive into the research topics of 'On suitability of euclidean embedding for host-based network coordinate systems'. Together they form a unique fingerprint.

Cite this