skip to main content
article

The internet AS-level topology: three data sources and one definitive metric

Published:10 January 2006Publication History
Skip Abstract Section

Abstract

We calculate an extensive set of characteristics for Internet AS topologies extracted from the three data sources most frequently used by the research community: traceroutes, BGP, and WHOIS. We discover that traceroute and BGP topologies are similar to one another but differ substantially from the WHOIS topology. Among the widely considered metrics, we find that the joint degree distribution appears to fundamentally characterize Internet AS topologies as well as narrowly define values for other important metrics. We discuss the interplay between the specifics of the three data collection mechanisms and the resulting topology views. In particular, we how how the data collection peculiarities explain differences in the resulting joint degree distributions of the respective topologies. Finally, we release to the community the input topology datasets, along with the scripts and output of our calculations. This supplement hould enable researchers to validate their models against real data and to make more informed election of topology data sources for their specific needs

References

  1. M. Faloutsos, P. Faloutsos, and C. Faloutsos, "On power-law relationships of the Internet topology," in ACM SIGCOMM 1999, pp.251--262. Google ScholarGoogle ScholarDigital LibraryDigital Library
  2. Q. Chen, H. Chang, R. Govindan, S. Jamin, S.J. Shenker, and W. Willinger, "The origin of power law in Internet topologies revisited," in IEEE INFOCOM 2002.Google ScholarGoogle Scholar
  3. H. Tangmunarunkit, R. Govindan, S. Jamin, S. Shenker, and W. Willinger, "Network topology generators: Degree-based vs.structural," in ACM SIGCOMM 2002, pp. 147--159. Google ScholarGoogle ScholarDigital LibraryDigital Library
  4. L. Li, D. Alderson, W. Willinger, and J. Doyle, "A first-principles approach to understanding the Internets router-level topology," in ACM SIGCOMM 2004. Google ScholarGoogle ScholarDigital LibraryDigital Library
  5. T. Bu and D. Towsley, "On distinguishing between Internet power law topology generators," in IEEE INFOCOM 2002.Google ScholarGoogle Scholar
  6. S. Jaiswal, A.L. Rosenberg, and D. Towsley, "Comparing the tructure of power-law graphs and the Internet AS graph," in IEEE ICNP 2004. Google ScholarGoogle ScholarDigital LibraryDigital Library
  7. S. Zhou and R.J. Mondragón, "Accurately modeling the Internet topology," Physical Review E vol. 70, pp. 066108, 2004, http://arxiv.org/abs/cs.NI/0402011Google ScholarGoogle ScholarCross RefCross Ref
  8. S.N. Dorogovtev and J.F.F. Mende, Evolution of Networks: From Biological Nets to the Internet and WWW Oxford University Press, Oxford, 2003. Google ScholarGoogle ScholarDigital LibraryDigital Library
  9. kc claffy, T.E. Monk, and D. McRobb, "Internet tomography," Nature January 1999, http://www.caida.org/tools/measurement/skitter/.Google ScholarGoogle Scholar
  10. "University of Oregon RouteViews Project," http://www.routeviews.org/.Google ScholarGoogle Scholar
  11. "Internet Routing Registries," http://www.irr.net/.Google ScholarGoogle Scholar
  12. CAIDA, "Comparative analysis of the Internet AS-level topologies extracted from different data sources: Data page," http://www.caida.org/analysis/topology/as topo comparisons/.Google ScholarGoogle Scholar
  13. Y. Rekhter and T. Li, A Border Gateway Protocol 4 (BGP-4)IETF, RFC 1771, 1995. Google ScholarGoogle ScholarDigital LibraryDigital Library
  14. J. Hawkinson and T. Bates, Guidelines for Creation, Selection, and Registration of an Autonomous System (AS) IETF, RFC 1930, 1996. Google ScholarGoogle ScholarDigital LibraryDigital Library
  15. "traceroute" http://www.traceroute.org/#source%20codeGoogle ScholarGoogle Scholar
  16. CAIDA, "Macroscopic topology AS adjacencies," http://www.caida.org/tools/measurement/skitter/as adjacencies.xmlGoogle ScholarGoogle Scholar
  17. Z.M. Mao, J. Rexford, J. Wang, and R.H. Katz, "Towards an accurate AS-level traceroute tool," in ACM SIGCOMM 2003. Google ScholarGoogle ScholarDigital LibraryDigital Library
  18. G. Siganos and M. Faloutsos, "Analyzing BGP policies:Methodology and tool," in IEEE INFOCOM 2004.Google ScholarGoogle Scholar
  19. H. Chang, R. Govindan, S. Jamin, S.J. Shenker, and W. Willinger, "Towards capturing representative AS-level Internet topologies," Computer Networks Journal vol. 44, pp. 737--755, April 2004. Google ScholarGoogle ScholarDigital LibraryDigital Library
  20. A. Lakhina, J. Byers, M. Crovella, and P. Xie, "Sampling biases in IP topology measurements," in IEEE INFOCOM 2003.Google ScholarGoogle Scholar
  21. L. Dall'Asta, I. Alvarez-Hamelin, A. Barrat, A. Vázquez, and A. Vespignani, "Exploring networks with traceroute-like probes: Theory and imulations," Theoretical Computer Science, Special Issue on Complex Networks 2005, http://arxiv.org/abs/cs.NI/0412007 Google ScholarGoogle ScholarDigital LibraryDigital Library
  22. M.E.J. Newman, "Assortative mixing in networks," Physical Review Letters vol. 89, no. 20, pp. 208701, 2002.Google ScholarGoogle ScholarCross RefCross Ref
  23. S.N. Dorogovtsev, "Networks with given correlations," http://arxiv.org/abs/cond-mat/0308336v1Google ScholarGoogle Scholar
  24. Y. Breitbart, C.-Y. Chan, M. Garofalakis, R. Rastogi, and A. Silberschatz, "Efficiently monitoring bandwidth and latency in IP networks," in IEEE INFOCOM 2001.Google ScholarGoogle Scholar
  25. K. Park and H. Lee, "On the effectiveness of route-based packet filtering for distributed DoS attack prevention in power-law internets," in ACM SIGCOMM 2001. Google ScholarGoogle ScholarDigital LibraryDigital Library
  26. CAIDA, "Visualizing Internet topology at a macroscopic scale," http://www.caida.org/analysis/topology/as core network/.Google ScholarGoogle Scholar
  27. I. Alvarez-Hamelin, L. Dall'Asta, A. Barrat, and A. Vespignani, "k -core decomposition:A tool for the visualization of large scale networks," http://arxiv.org/abs/cs.NI/0504107Google ScholarGoogle Scholar
  28. S. Tauro, C. Palmer, G. Siganos, and M. Faloutsos, "A simple conceptual model for the Internet topology," in Global Internet 2001.Google ScholarGoogle Scholar
  29. J. Winick and S. Jamin, "Inet-3.0: Internet topology generator," Technical Report UM-CSE-TR-456-02, University of Michigan,2002.Google ScholarGoogle Scholar
  30. B. Bollobás and O. Riordan, "Mathematical results on scale-free random graphs," in Handbook of Graphs and Networks Berlin, 2002, Wiley-VCH.Google ScholarGoogle Scholar
  31. P. Fraigniaud, "A new perspective on the mall-world phenomenon: Greedy routing in tree-decomposed graphs," in ESA 2005. Google ScholarGoogle ScholarDigital LibraryDigital Library
  32. S.N. Soffer and A. Vázquez, "Clustering coefficient without degree correlations biases," http://arxiv.org/abs/cond-mat/0409686Google ScholarGoogle Scholar
  33. D. Peleg, Distributed Computing: A Locality-Sensitive Approach SIAM, Philadelphia, PA, 2000. Google ScholarGoogle ScholarDigital LibraryDigital Library
  34. D. Krioukov, K. Fall, and X. Yang, "Compact routing on Internet-like graphs," in IEEE INFOCOM 2004.Google ScholarGoogle Scholar
  35. C. Shannon and D. Moore, "The spread of the witty worm," in Proceedings of IEEE Security and Privacy July 2004. Google ScholarGoogle ScholarDigital LibraryDigital Library
  36. U. Brandes, "A faster algorithm for betweenness centrality," Journal of Mathematical Sociology vol. 25, no.2, pp. 163--177, 2001.Google ScholarGoogle ScholarCross RefCross Ref
  37. F.K.R. Chung, Spectral Graph Theory vol. 92 of Regional Conference Series in Mathematics American Mathematical Society, Providence, RI, 1997.Google ScholarGoogle Scholar
  38. C. Gkantsidis, M. Mihail, and A. Saberi, "Conductance and congestion in power law graphs," in ACM SIGMETRICS 2003. Google ScholarGoogle ScholarDigital LibraryDigital Library
  39. D. Vukadinović,P. Huang, and T. Erlebach, "A spectral analysis of the Internet topology," Technical Report TIK-NR.118, ETH, 2001.Google ScholarGoogle Scholar
  40. C. Gkantsidis, M. Mihail, and E. Zegura, "Spectral analysis of Internet topologies," in IEEE INFOCOM 2003.Google ScholarGoogle Scholar
  41. L. Subramanian, S. Agarwal, J. Rexford, and R.H. Katz, "Characterizing the Internet hierarchy from multiple vantage points," in IEEE INFOCOM 2002.Google ScholarGoogle Scholar
  42. X. Dimitropoulos, D. Krioukov, B. Huffaker, kc claffy, and G. Riley, "Inferring AS relationships: Dead end or lively beginning?," in WEA 2005. Google ScholarGoogle ScholarDigital LibraryDigital Library

Index Terms

  1. The internet AS-level topology: three data sources and one definitive metric

                    Recommendations

                    Comments

                    Login options

                    Check if you have access through your login credentials or your institution to get full access on this article.

                    Sign in

                    Full Access

                    • Published in

                      cover image ACM SIGCOMM Computer Communication Review
                      ACM SIGCOMM Computer Communication Review  Volume 36, Issue 1
                      January 2006
                      90 pages
                      ISSN:0146-4833
                      DOI:10.1145/1111322
                      Issue’s Table of Contents

                      Copyright © 2006 Authors

                      Publisher

                      Association for Computing Machinery

                      New York, NY, United States

                      Publication History

                      • Published: 10 January 2006

                      Check for updates

                      Qualifiers

                      • article

                    PDF Format

                    View or Download as a PDF file.

                    PDF

                    eReader

                    View online with eReader.

                    eReader