A cluster based approach for network distance embedding

Several coordinate bases embedding schemes have been proposed for scalable estimation of network distance (round trip time) among Internet hosts. These schemes may be broadly categorized into Landmark and distributed peer-to-peer based. While Landmark based approaches suffer from scalability due to the large amount of measurement loads, distributed schemes suffer from stability and accuracy issues in the presence of node churns. In this paper, we propose CSHE; a cluster based statistical approach for the network distance embedding that combines the stability of Landmark scheme and the scaling property of distributed approach. CSHE groups the nodes into a set of clusters where a new node embeds itself into the co-ordinate space by computing its distance against a set of nodes that are randomly chosen from each cluster. Using real measurement traces, we evaluate the accuracy and robustness of CSHE. We find that the accuracy of CSHE is comparable to the best known accurate embedding (GNP based embedding) and does not suffer with node churns.