Enhancing RTT Prediction Schemes Using Global Function Minimization

Numerous round trip time (RTT) prediction schemes use the least squares method to embed hosts in virtual euclidean spaces. The least squares method minimizes the residuals between measured data (measured RTTs) and their approximation (euclidean distances between the host position and fixed points, to which the distance was measured). This is achieved by minimizing an objective function, which is defined as a sum of square differences between measured distances to fixed points (landmarks) and euclidean distances to those landmarks in a virtual space. Since there is no direct way (closed form) for finding minima of the objective function, numerical function minimization must be used. In this paper we identify the problem of existence of multiple local minima of objective functions and their impact on resulting RTT predictions. To overcome this problem, we propose an algorithm for finding all local minima of the objective function. By finding all minima, we are able to identify the global minimum of the objective function, and thus ensure the optimal embedding of a host in the virtual space. To evaluate our algorithm we compare it with standard methods for function minimization using data collected by the Planet-Lab all-pings experiment.