Triangle inequality variations in the internet

TitleTriangle inequality variations in the internet
Publication TypeConference Papers
Year of Publication2009
AuthorsLumezanu C, Baden R, Spring N, Bhattacharjee B
Conference NameProceedings of the 9th ACM SIGCOMM conference on Internet measurement conference
Date Published2009///
Conference LocationNew York, NY, USA
ISBN Number978-1-60558-771-4
Keywordslatency, tiv, triangle inequality violation, variation

Triangle inequality violations (TIVs) are important for latency sensitive distributed applications. On one hand, they can expose opportunities to improve network routing by finding shorter paths between nodes. On the other hand, TIVs can frustrate network embedding or positioning systems that treat the Internet as a metric space where the triangle inequality holds. Even though triangle inequality violations are both significant and curious, their study has been limited to aggregate data sets that combine measurements taken over long periods of time. The limitations of these data sets open crucial questions in the design of systems that exploit (or avoid) TIVs: are TIVs stable or transient? Or are they illusions caused by aggregating measurements taken at different times? We collect latency matrices at varying sizes and time granularities and study dynamic properties of triangle inequality violations in the Internet. We show that TIVs are not results of measurement error and that their number varies with time. We examine how latency aggregates of data measured over longer periods of time preserve TIVs. Using medians to compute violations eliminates most of the TIVs that appear sporadically during the measurement but it misses many of the ones that are present for more than five hours.