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

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: Michalis Faloutsos , Petros Faloutsos , Christos Faloutsos, On power-law relationships of the Internet topology, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.251-262, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 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.
• 3: Hongsuda Tangmunarunkit , Ramesh Govindan , Sugih Jamin , Scott Shenker , Walter Willinger, Network topology generators: degree-based vs. structural, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 4: Lun Li , David Alderson , Walter Willinger , John Doyle, A first-principles approach to understanding the internet's router-level topology, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 5: T. Bu and D. Towsley, "On distinguishing between Internet power law topology generators," in IEEE INFOCOM 2002.
• 6: Sharad Jaiswal , Arnold L. Rosenberg , Don Towsley, Comparing the Structure of Power-Law Graphs and the Internet AS Graph, Proceedings of the Network Protocols, 12th IEEE International Conference on (ICNP'04), p.294-303, October 05-08, 2004
• 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/0402011
• 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.
• 9: kc claffy, T.E. Monk, and D. McRobb, "Internet tomography," Nature January 1999, http://www.caida.org/tools/measurement/skitter/.
• 10: "University of Oregon RouteViews Project," http://www.routeviews.org/.
• 11: "Internet Routing Registries," http://www.irr.net/.
• 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/.
• 13: Y. Rekhter and T. Li, A Border Gateway Protocol 4 (BGP-4)IETF, RFC 1771, 1995.
• 14: J. Hawkinson and T. Bates, Guidelines for Creation, Selection, and Registration of an Autonomous System (AS) IETF, RFC 1930, 1996.
• 15: "traceroute" http://www.traceroute.org/#source%20code
• 16: CAIDA, "Macroscopic topology AS adjacencies," http://www.caida.org/tools/measurement/skitter/as adjacencies.xml
• 17: Zhuoqing Morley Mao , Jennifer Rexford , Jia Wang , Randy H. Katz, Towards an accurate AS-level traceroute tool, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863996]
• 18: G. Siganos and M. Faloutsos, "Analyzing BGP policies:Methodology and tool," in IEEE INFOCOM 2004.
• 19: Hyunseok Chang , Ramesh Govindan , Sugih Jamin , Scott J. Shenker , Walter Willinger, Towards capturing representative AS-level Internet topologies, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.44 n.6, p.737-755, 22 April 2004 [doi>10.1016/j.comnet.2003.03.001]
• 20: A. Lakhina, J. Byers, M. Crovella, and P. Xie, "Sampling biases in IP topology measurements," in IEEE INFOCOM 2003.
• 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
• 22: M.E.J. Newman, "Assortative mixing in networks," Physical Review Letters vol. 89, no. 20, pp. 208701, 2002.
• 23: S.N. Dorogovtsev, "Networks with given correlations," http://arxiv.org/abs/cond-mat/0308336v1
• 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.
• 25: Kihong Park , Heejo Lee, On the effectiveness of route-based packet filtering for distributed DoS attack prevention in power-law internets, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.15-26, August 2001, San Diego, California, United States
• 26: CAIDA, "Visualizing Internet topology at a macroscopic scale," http://www.caida.org/analysis/topology/as core network/.
• 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/0504107
• 28: S. Tauro, C. Palmer, G. Siganos, and M. Faloutsos, "A simple conceptual model for the Internet topology," in Global Internet 2001.
• 29: J. Winick and S. Jamin, "Inet-3.0: Internet topology generator," Technical Report UM-CSE-TR-456-02, University of Michigan,2002.
• 30: B. Bollobás and O. Riordan, "Mathematical results on scale-free random graphs," in Handbook of Graphs and Networks Berlin, 2002, Wiley-VCH.
• 31: P. Fraigniaud, "A new perspective on the mall-world phenomenon: Greedy routing in tree-decomposed graphs," in ESA 2005.
• 32: S.N. Soffer and A. Vázquez, "Clustering coefficient without degree correlations biases," http://arxiv.org/abs/cond-mat/0409686
• 33: David Peleg, Distributed computing: a locality-sensitive approach, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000
• 34: D. Krioukov, K. Fall, and X. Yang, "Compact routing on Internet-like graphs," in IEEE INFOCOM 2004.
• 35: Colleen Shannon , David Moore, The Spread of the Witty Worm, IEEE Security and Privacy, v.2 n.4, p.46-50, July 2004 [doi>10.1109/MSP.2004.59]
• 36: U. Brandes, "A faster algorithm for betweenness centrality," Journal of Mathematical Sociology vol. 25, no.2, pp. 163--177, 2001.
• 37: F.K.R. Chung, Spectral Graph Theory vol. 92 of Regional Conference Series in Mathematics American Mathematical Society, Providence, RI, 1997.
• 38: Christos Gkantsidis , Milena Mihail , Amin Saberi, Conductance and congestion in power law graphs, Proceedings of the 2003 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 11-14, 2003, San Diego, CA, USA
• 39: D. Vukadinović,P. Huang, and T. Erlebach, "A spectral analysis of the Internet topology," Technical Report TIK-NR.118, ETH, 2001.
• 40: C. Gkantsidis, M. Mihail, and E. Zegura, "Spectral analysis of Internet topologies," in IEEE INFOCOM 2003.
• 41: L. Subramanian, S. Agarwal, J. Rexford, and R.H. Katz, "Characterizing the Internet hierarchy from multiple vantage points," in IEEE INFOCOM 2002.
• 42: X. Dimitropoulos, D. Krioukov, B. Huffaker, kc claffy, and G. Riley, "Inferring AS relationships: Dead end or lively beginning?," in WEA 2005.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: Internet (e.g., TCP/IP)

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems
  G.3 PROBABILITY AND STATISTICS
      Subjects: Distribution functions; Multivariate statistics; Correlation and regression analysis

General Terms:
Design, Measurement, Theory

Keywords:
internet topology