Optimizing Dimensionality and Accelerating Landmark Positioning for Coordinates Based RTT Predictions

In this paper we analyze the positioning of landmarks in coordinates-based Internet distance prediction approaches with focus on Global Network Positioning (GNP). We show that one of the major drawbacks of GNP is its computational overhead for a large number of landmarks and dimensions. In our work we identify two factors, which have a great impact on the computational overhead. The first one is being able to determine the optimal number of dimensions for embedding a given set of landmarks into a Euclidean space. The second factor is the selection of a good starting point for minimizing the total error of embedding. We propose an algorithm based on the simplex inequality (a generalized form of the triangle inequality) to extract the optimal number of dimensions based on distance measurements between landmarks. We also provide methods to compute a good starting point for the minimization problem and to reduce the number of variables involved in the minimization. We performed experiments with data obtained from the PlanetLab all-sites-pings experiment to verify the correctness and performance gains of our algorithm. The experimental results show that our enhancements to GNP landmark positioning are able to find the optimal number of dimensions for embedding the landmarks. These enhancements also accelerate the function minimization.