TY - CONF
T1 - Triangle inequality variations in the internet
T2 - Proceedings of the 9th ACM SIGCOMM conference on Internet measurement conference
Y1 - 2009
A1 - Lumezanu,Cristian
A1 - Baden,Randy
A1 - Spring, Neil
A1 - Bhattacharjee, Bobby
KW - latency
KW - tiv
KW - triangle inequality violation
KW - variation
AB - 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.
JA - Proceedings of the 9th ACM SIGCOMM conference on Internet measurement conference
T3 - IMC '09
PB - ACM
CY - New York, NY, USA
SN - 978-1-60558-771-4
UR - http://doi.acm.org/10.1145/1644893.1644914
M3 - 10.1145/1644893.1644914
ER -