Dynamic landmark triangles: A simple and efficient mechanism for inter-host latency estimation

This paper describes a simple and efficient approach to estimate the network latency between arbitrary Internet hosts. We use three landmark hosts forming a triangle in two-dimensional space to estimate the distance between arbitrary hosts with simple trigonometrical calculations. To improve the accuracy of estimation, we dynamically choose the “best” triangle for a given pair of hosts using a heuristic algorithm. Experiments using several data sets of measured inter-host latencies, as well as a live Internet study, demonstrate the accuracy and efficiency of our approach.