Analysis of Varying AS Path Lengths on End-to-End Latency
Each Autonomous System (AS) (e.g., ISPs) in the Internet is connected to a group of one or more network operators with their own set of routing rules and policies. Further, the Border Gateway Protocol (BGP) is implemented to impose such rules. BGP allows ASs almost complete freedom in adopting their routing preferences. Unfortunately, due to the diverse set of uncontrolled routing policies and rules from each AS, packets belonging to a certain end-to-end connection may traverse different ASs. From the end user’s perspective, some AS paths may be optimal and some sub-optimal. However, the sub-optimal AS paths are not always easily distinguished. Furthermore, there is not a unique definition for sub-optimality as it may be reflected with various measures (e.g., latency) depending on the application requirements and expectations.
Our study analyzes varying AS path lengths (ASPLs) and investigates their impact on the end-to-end latency over the Internet at a greater scale than previous studies. We use Scriptroute, (a public Internet measurement and debugging tool) to probe various PlanetLab nodes. Our results show that all of the source nodes experienced some AS path differences and the ASPL values that the sources use greatly vary. At worst, some nodes experienced over 70% different paths during our measurements. We observed the largest difference in ASPLs to the same destination was as high as 6 with an average of 2.5. Also, from the analysis of the individual end-to-end pairings, we show that a lower ASPL does not always yield lower latency. Specifically, we present real cases where ASPL and latency values are related, inversely related, and not related at all. Furthermore, we provide a simple definition for sub-optimality and analyze the collected data against this definition. We show that overall 82% of the fluctuating paths and 9% of all the traces between sourcedestination pairs faced sub-optimal AS paths.
- A.Selcuk Uluagac, Roma Kane, Siddharth Joshi, R. A. Beyah, and J. A. Copeland, “Analysis of Varying AS Path Lengths from the Edge of the Network,” in Proceedings of the IEEE International Communications Conference (ICC), Cape Town, South Africa, May 2010, [bibtex],[pdf]
Please send us an e-mail if you are interested in the DataSet-I and DataSet-II used in this study.