Triangle Inequality and Routing Policy Violations in the Internet

TitleTriangle Inequality and Routing Policy Violations in the Internet
Publication TypeBook Chapters
Year of Publication2009
AuthorsLumezanu C, Baden R, Spring N, Bhattacharjee B
EditorMoon S, Teixeira R, Uhlig S
Book TitlePassive and Active Network MeasurementPassive and Active Network Measurement
Series TitleLecture Notes in Computer Science
Pagination45 - 54
PublisherSpringer Berlin / Heidelberg
ISBN Number978-3-642-00974-7
KeywordsComputer, Science

Triangle inequality violations (TIVs) are the effect of packets between two nodes being routed on the longer direct path between them when a shorter detour path through an intermediary is available. TIVs are a natural, widespread and persistent consequence of Internet routing policies. By exposing opportunities to improve the delay between two nodes, TIVs can help myriad applications that seek to minimize end-to-end latency. However, sending traffic along the detour paths revealed by TIVs may influence Internet routing negatively. In this paper we study the interaction between triangle inequality violations and policy routing in the Internet. We use measured and predicted AS paths between Internet nodes to show that 25% of the detour paths exposed by TIVs are in fact available to BGP but are simply deemed “less efficient”. We also compare the AS paths of detours and direct paths and find that detours use AS edges that are rarely followed by default Internet paths, while avoiding others that BGP seems to prefer. Our study is important both for understanding the various interactions that occur at the routing layer as well as their effects on applications that seek to use TIVs to minimize latency.