Taming the Triangle Inequality Violations with Network Coordinate System on Real Internet

Abstract

Network Coordinate (NC) systems are efficient in scalable Internet latency estimation. While most of the focus has been put on how to distort Triangle Inequality Violation (TIV) in metric spaces to relieve the inaccuracy caused by it, TIV is a persistently and widely existing phenomenon on the Internet and thus should be embraced by future NC systems rather than being eliminated. Besides high accuracy, such an NC system can also provide the benefit of reducing the data transmission time by use of proper relay routes. With that in mind, we design an NC system with a hierarchical architecture, which is motivated by the natural idea of partitioning the three TIV links into different autonomous NC systems, in order to make as many as TIVs inherently embeddable in metric space. We implement and deploy our work, named Toread, on real Internet. Evaluation results show that Toread's metric space can well characterize more than 60% TIVs, thus Toread is highly accurate (0.54 in Toread versus 1.06 in Pyxida at 90th percentile Relative Error) and effective in searching detour paths (succeeds in 58.2% cases).