skip to main content
article

The (in)completeness of the observed internet AS-level structure

Published: 01 February 2010 Publication History

Abstract

Despite significant efforts to obtain an accurate picture of the Internet's connectivity structure at the level of individual autonomous systems (ASes), much has remained unknown in terms of the quality of the inferred AS maps that have been widely used by the research community. In this paper, we assess the quality of the inferred Internet maps through case studies of a sample set of ASes. These case studies allow us to establish the ground truth of connectivity between this set of ASes and their directly connected neighbors. A direct comparison between the ground truth and inferred topology maps yield insights into questions such as which parts of the actual topology are adequately captured by the inferred maps, which parts are missing and why, and what is the percentage of missing links in these parts. This information is critical in assessing, for each class of real-world networking problems, whether the use of currently inferred AS maps or proposed AS topology models is, or is not, appropriate. More importantly, our newly gained insights also point to new directions towards building realistic and economically viable Internet topology maps.

References

[1]
AOL Peering Requirements, {Online}. Available: http://www.atdn.net/ settlement_free_int.shtml
[2]
AT&T Peering Requirements, {Online}. Available: http://www.corp.att. com/peering/
[3]
CERNET BGP Feeds, {Online}. Available: http://bgpview.6test.edu.cn/ bgp-view/
[4]
European Internet Exchange Association, {Online}. Available: http:// www.euro-ix.net
[5]
Geant2 Looking Glass, {Online}. Available: http://stats.geant2.net/lg/
[6]
Good Practices in Internet Exchange Points, {Online}. Available: http://www.pch.net/resources/papers/ix-documentation-bcp/ix-documentation-bcp-v14en.pdf
[7]
Internet Routing Registry, {Online}. Available: http://www.irr.net/
[8]
Packet Clearing House IXP Directory, {Online}. Available: http://www.pch.net/ixpdir/Main.pl
[9]
PeeringDB Website, {Online}. Available: http://www.peeringdb.com/
[10]
Personal Communication with Bill Woodcock at PCH.
[11]
RIPE Routing Information Service Project, {Online}. Available: http:// www.ripe.net/
[12]
RouteViews Routing Table Archive, {Online}. Available: http://www. routeviews.org/
[13]
Skitter AS Adjacency List, {Online}. Available: http://www.caida.org/ tools/measurement/skitter/as_adjacencies.xml
[14]
The Abilene Observatory Data Collections, {Online}. Available: http:// abilene.internet2.edu/observatory/data-collections.html
[15]
H. Ballani, P. Francis, and X. Zhang, "A study of prefix hijacking and interception in the Internet," in Proc. ACM SIGCOMM, 2007, pp. 265-276.
[16]
H. Chang, "An economic-based empirical approach to modeling the Internet inter-domain topology and traffic matrix," Ph.D. dissertation, Univ. Michigan, Ann Arbor, MI, 2006.
[17]
H. Chang, R. Govindan, S. Jamin, S. J. Shenker, and W.Willinger, "Towards capturing representative AS-level Internet topologies," Comput. Netw. J., vol. 44, no. 6, pp. 737-755, 2004.
[18]
H. Chang, S. Jamin, and W. Willinger, "Inferring AS-level Internet topology from router-level path traces," in SPIE ITCom, 2001.
[19]
H. Chang and W. Willinger, "Difficulties measuring the Internet's AS-level ecosystem," in Proc. Annu. CISS, 2006, pp. 1479-1483.
[20]
X. Dimitropoulos, D. Krioukov, M. Fomenkov, B. Huffaker, Y. Hyun, kc claffy, and G. Riley, "AS relationships: Inference and validation," Comput. Commun. Rev., vol. 37, no. 1, pp. 29-40, 2007.
[21]
D. Dolev, S. Jamin, O. Mokryn, and Y. Shavitt, "Internet resiliency to attacks and failures under BGP policy routing," Comput. Netw., vol. 50, no. 16, pp. 3183-3196, 2006.
[22]
L. Gao, "On inferring autonomous system relationships in the Internet," IEEE/ACM Trans. Netw., vol. 9, no. 6, pp. 733-745, Dec. 2001.
[23]
B. Hummel and S. Kosub, "Acyclic type-of-relationship problems on the internet: An experimental analysis," in Proc. ACM IMC, 2007, pp. 221-226.
[24]
Y. Hyun, A. Broido, and kc claffy, "On third-party addresses in traceroute paths," presented at the PAM Workshop, 2003.
[25]
M. Lad, R. Oliveira, B. Zhang, and L. Zhang, "Understanding the resiliency of Internet topology against false origin attacks," presented at the IEEE DSN, 2007.
[26]
H. Madhyastha, T. Isdal, M. Piatek, C. Dixon, T. Anderson, A. Krishnamurthy, and A. Venkataramani, "iPlane: An information plane for distributed services," in Proc. OSDI, 2006, pp. 367-380.
[27]
R. Mahajan, D. Wetherall, and T. Anderson, "Understanding BGP misconfiguration," in Proc. ACM SIGCOMM, 2002, pp. 3-16.
[28]
Z. M. Mao, L. Qiu, J. Wang, and Y. Zhang, "On AS-level path inference," in Proc. SIGMETRICS, 2005, pp. 339-349.
[29]
Z. M. Mao, J. Rexford, J. Wang, and R. H. Katz, "Towards an accurate AS-level traceroute tool," in Proc. ACM SIGCOMM, 2003, pp. 365-378.
[30]
W. Mühlbauer, A. Feldmann, O. Maennel, M. Roughan, and S. Uhlig, "Building an AS-topology model that captures route diversity," in Proc. ACM SIGCOMM, 2006, pp. 195-206.
[31]
W. Mühlbauer, S. Uhlig, B. Fu, M. Meulle, and O. Maennel, "In search for an appropriate granularity to model routing policies," in Proc. ACM SIGCOMM, 2007, pp. 145-156.
[32]
R. Oliveira, B. Zhang, D. Pei, R. Izhak-Ratzin, and L. Zhang, "Quantifying path exploration in the Internet," in Proc. ACM IMC, Oct. 2006, pp. 269-282.
[33]
R. Oliveira, B. Zhang, and L. Zhang, "Observing the evolution of Internet AS topology," in Proc. ACM SIGCOMM, 2007, pp. 313-324.
[34]
D. Raz and R. Cohen, "The Internet dark matter: On the missing links in the AS connectivity map," in Proc. IEEE INFOCOM, 2006, pp. 1-12.
[35]
Y. Rekhter, T. Li, and S. Hares, "Border Gateway Protocol 4," Internet Engineering Task Force, 2006, RFC 4271.
[36]
M. Roughan, S. J. Tuke, and O. Maennel, "Bigfoot, sasquatch, the yeti and other missing links: What we don't know about the as graph," in Proc. ACM IMC, 2008, pp. 325-330.
[37]
Y. Shavitt and E. Shir, "DIMES: Let the Internet measure itself," Comput. Commun. Rev., vol. 35, no. 5, pp. 71-74, 2005.
[38]
G. Siganos and M. Faloutsos, "Analyzing BGP policies: Methodology and tool," in Proc. IEEE INFOCOM, 2004, pp. 1640-1651.
[39]
L. Subramanian, S. Agarwal, J. Rexford, and R. Katz, "Characterizing the Internet hierarchy from multiple vantage points," in Proc. IEEE INFOCOM, 2002, pp. 618-627.
[40]
L. Subramanian, M. Caesar, C. T. Ee, M. Handley, M. Mao, S. Shenker, and I. Stoica, "HLP: A next generation inter-domain routing protocol," in Proc. ACM SIGCOMM, 2005, pp. 13-24.
[41]
L. Wang, M. Saranu, J. M. Gottlieb, and D. Pei, "Understanding BGP session failures in a large ISP," in Proc. IEEE INFOCOM, 2007, pp. 348-356.
[42]
J. Wu, Y. Zhang, Z. Mao, and K. Shin, "Internet routing resilience to failures: Analysis and implications," in Proc. ACM CoNEXT, 2007, Article No. 25.
[43]
Y. He, G. Siganos, M. Faloutsos, and S. V. Krishnamurthy, "A systematic framework for unearthing the missing links: Measurements and impact," presented at the NSDI, 2007.
[44]
B. Zhang, R. Liu, D. Massey, and L. Zhang, "Collecting the Internet AS-level topology," Comput. Commun. Rev., vol. 35, no. 1, pp. 53-61, Jan. 2005.
[45]
C. Zheng, L. Ji, D. Pei, J. Wang, and P. Francis, "A light-weight distributed scheme for detecting IP prefix hijacks in real-time," in Proc. ACM SIGCOMM, 2007, pp. 277-288.

Cited By

View all
  • (2024)Uncovering BGP Action Communities and Community Squatters in the WildProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/37004318:3(1-23)Online publication date: 10-Dec-2024
  • (2024)What is the next hop to more granular routing models?Proceedings of the 23rd ACM Workshop on Hot Topics in Networks10.1145/3696348.3696859(343-351)Online publication date: 18-Nov-2024
  • (2024)Investigating Location-aware Advertisements in Anycast IP NetworksProceedings of the 2024 Applied Networking Research Workshop10.1145/3673422.3674885(15-22)Online publication date: 23-Jul-2024
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking
IEEE/ACM Transactions on Networking  Volume 18, Issue 1
February 2010
332 pages

Publisher

IEEE Press

Publication History

Published: 01 February 2010
Revised: 13 January 2009
Received: 03 September 2008
Published in TON Volume 18, Issue 1

Author Tags

  1. border gateway protocol (BGP)
  2. interdomain routing
  3. internet topology

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)1
  • Downloads (Last 6 weeks)0
Reflects downloads up to 15 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Uncovering BGP Action Communities and Community Squatters in the WildProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/37004318:3(1-23)Online publication date: 10-Dec-2024
  • (2024)What is the next hop to more granular routing models?Proceedings of the 23rd ACM Workshop on Hot Topics in Networks10.1145/3696348.3696859(343-351)Online publication date: 18-Nov-2024
  • (2024)Investigating Location-aware Advertisements in Anycast IP NetworksProceedings of the 2024 Applied Networking Research Workshop10.1145/3673422.3674885(15-22)Online publication date: 23-Jul-2024
  • (2024)metAScritic: Reframing AS-Level Topology Discovery as a Recommendation SystemProceedings of the 2024 ACM on Internet Measurement Conference10.1145/3646547.3688429(337-364)Online publication date: 4-Nov-2024
  • (2023)Replication: 20 Years of Inferring Interdomain Routing PoliciesProceedings of the 2023 ACM on Internet Measurement Conference10.1145/3618257.3624799(16-29)Online publication date: 24-Oct-2023
  • (2023)Pareto-optimal Defenses for the Web Infrastructure: Theory and PracticeACM Transactions on Privacy and Security10.1145/356759526:2(1-36)Online publication date: 13-Mar-2023
  • (2022)ISP Probing Reduction with Passive and Active Measurement10.1007/978-3-030-98785-5_20(441-469)Online publication date: 28-Mar-2022
  • (2022)Peering Only? Analyzing the Reachability Benefits of Joining Large IXPs TodayPassive and Active Measurement10.1007/978-3-030-98785-5_15(338-366)Online publication date: 28-Mar-2022
  • (2022)RouteInfer: Inferring Interdomain Paths by Capturing ISP Routing Behavior Diversity and GeneralityPassive and Active Measurement10.1007/978-3-030-98785-5_10(216-244)Online publication date: 28-Mar-2022
  • (2021)The parallel lives of autonomous systemsProceedings of the 21st ACM Internet Measurement Conference10.1145/3487552.3487838(593-611)Online publication date: 2-Nov-2021
  • Show More Cited By

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media