Rights statement: © ACM, 2013. This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in IMC '13 Proceedings of the 2013 conference on Internet measurement conference http://dx.doi.org/10.1145/2504730.2504735
Accepted author manuscript, 382 KB, PDF document
Available under license: CC BY-NC: Creative Commons Attribution-NonCommercial 4.0 International License
Final published version
Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Conference contribution/Paper › peer-review
Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Conference contribution/Paper › peer-review
}
TY - GEN
T1 - AS relationships, customer cones, and validation
AU - Luckie, Matthew
AU - Huffaker, Bradley
AU - Dhamdhere, Amogh
AU - Giotsas, Vasileios
AU - Claffy, Kc
N1 - © ACM, 2013. This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in IMC '13 Proceedings of the 2013 conference on Internet measurement conference http://dx.doi.org/10.1145/2504730.2504735
PY - 2013
Y1 - 2013
N2 - Business relationships between ASes in the Internet are typically confidential, yet knowledge of them is essential to understand many aspects of Internet structure, performance, dynamics, and evolution. We present a new algorithm to infer these relationships using BGP paths. Unlike previous approaches, our algorithm does not assume the presence (or seek to maximize the number) of valley-free paths, instead relying on three assumptions about the Internet's inter-domain structure: (1) an AS enters into a provider relationship to become globally reachable; and (2) there exists a peering clique of ASes at the top of the hierarchy, and (3) there is no cycle of p2c links. We assemble the largest source of validation data for AS-relationship inferences to date, validating 34.6% of our 126,082 c2p and p2p inferences to be 99.6% and 98.7% accurate, respectively. Using these inferred relationships, we evaluate three algorithms for inferring each AS's customer cone, defined as the set of ASes an AS can reach using customer links. We demonstrate the utility of our algorithms for studying the rise and fall of large transit providers over the last fifteen years, including recent claims about the flattening of the AS-level topology and the decreasing influence of "tier-1" ASes on the global Internet.
AB - Business relationships between ASes in the Internet are typically confidential, yet knowledge of them is essential to understand many aspects of Internet structure, performance, dynamics, and evolution. We present a new algorithm to infer these relationships using BGP paths. Unlike previous approaches, our algorithm does not assume the presence (or seek to maximize the number) of valley-free paths, instead relying on three assumptions about the Internet's inter-domain structure: (1) an AS enters into a provider relationship to become globally reachable; and (2) there exists a peering clique of ASes at the top of the hierarchy, and (3) there is no cycle of p2c links. We assemble the largest source of validation data for AS-relationship inferences to date, validating 34.6% of our 126,082 c2p and p2p inferences to be 99.6% and 98.7% accurate, respectively. Using these inferred relationships, we evaluate three algorithms for inferring each AS's customer cone, defined as the set of ASes an AS can reach using customer links. We demonstrate the utility of our algorithms for studying the rise and fall of large transit providers over the last fifteen years, including recent claims about the flattening of the AS-level topology and the decreasing influence of "tier-1" ASes on the global Internet.
KW - ASL relationships
KW - Customer cones
KW - Routing policies
U2 - 10.1145/2504730.2504735
DO - 10.1145/2504730.2504735
M3 - Conference contribution/Paper
AN - SCOPUS:84890050382
SN - 9781450319539
SP - 243
EP - 256
BT - IMC '13 Proceedings of the 2013 conference on Internet measurement conference
PB - ACM
CY - New York
T2 - 13th ACM Internet Measurement Conference, IMC 2013
Y2 - 23 October 2013 through 25 October 2013
ER -