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
- M. Faloutsos, P. Faloutsos, and C. Faloutsos, "On power-law relationships of the Internet topology," in ACM SIGCOMM 1999, pp.251--262. Google ScholarDigital Library
- 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 Scholar
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- T. Bu and D. Towsley, "On distinguishing between Internet power law topology generators," in IEEE INFOCOM 2002.Google Scholar
- 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 ScholarDigital Library
- 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 ScholarCross Ref
- 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 ScholarDigital Library
- kc claffy, T.E. Monk, and D. McRobb, "Internet tomography," Nature January 1999, http://www.caida.org/tools/measurement/skitter/.Google Scholar
- "University of Oregon RouteViews Project," http://www.routeviews.org/.Google Scholar
- "Internet Routing Registries," http://www.irr.net/.Google Scholar
- 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 Scholar
- Y. Rekhter and T. Li, A Border Gateway Protocol 4 (BGP-4)IETF, RFC 1771, 1995. Google ScholarDigital Library
- J. Hawkinson and T. Bates, Guidelines for Creation, Selection, and Registration of an Autonomous System (AS) IETF, RFC 1930, 1996. Google ScholarDigital Library
- "traceroute" http://www.traceroute.org/#source%20codeGoogle Scholar
- CAIDA, "Macroscopic topology AS adjacencies," http://www.caida.org/tools/measurement/skitter/as adjacencies.xmlGoogle Scholar
- Z.M. Mao, J. Rexford, J. Wang, and R.H. Katz, "Towards an accurate AS-level traceroute tool," in ACM SIGCOMM 2003. Google ScholarDigital Library
- G. Siganos and M. Faloutsos, "Analyzing BGP policies:Methodology and tool," in IEEE INFOCOM 2004.Google Scholar
- 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 ScholarDigital Library
- A. Lakhina, J. Byers, M. Crovella, and P. Xie, "Sampling biases in IP topology measurements," in IEEE INFOCOM 2003.Google Scholar
- 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 ScholarDigital Library
- M.E.J. Newman, "Assortative mixing in networks," Physical Review Letters vol. 89, no. 20, pp. 208701, 2002.Google ScholarCross Ref
- S.N. Dorogovtsev, "Networks with given correlations," http://arxiv.org/abs/cond-mat/0308336v1Google Scholar
- 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 Scholar
- 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 ScholarDigital Library
- CAIDA, "Visualizing Internet topology at a macroscopic scale," http://www.caida.org/analysis/topology/as core network/.Google Scholar
- 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 Scholar
- S. Tauro, C. Palmer, G. Siganos, and M. Faloutsos, "A simple conceptual model for the Internet topology," in Global Internet 2001.Google Scholar
- J. Winick and S. Jamin, "Inet-3.0: Internet topology generator," Technical Report UM-CSE-TR-456-02, University of Michigan,2002.Google Scholar
- B. Bollobás and O. Riordan, "Mathematical results on scale-free random graphs," in Handbook of Graphs and Networks Berlin, 2002, Wiley-VCH.Google Scholar
- P. Fraigniaud, "A new perspective on the mall-world phenomenon: Greedy routing in tree-decomposed graphs," in ESA 2005. Google ScholarDigital Library
- S.N. Soffer and A. Vázquez, "Clustering coefficient without degree correlations biases," http://arxiv.org/abs/cond-mat/0409686Google Scholar
- D. Peleg, Distributed Computing: A Locality-Sensitive Approach SIAM, Philadelphia, PA, 2000. Google ScholarDigital Library
- D. Krioukov, K. Fall, and X. Yang, "Compact routing on Internet-like graphs," in IEEE INFOCOM 2004.Google Scholar
- C. Shannon and D. Moore, "The spread of the witty worm," in Proceedings of IEEE Security and Privacy July 2004. Google ScholarDigital Library
- U. Brandes, "A faster algorithm for betweenness centrality," Journal of Mathematical Sociology vol. 25, no.2, pp. 163--177, 2001.Google ScholarCross Ref
- F.K.R. Chung, Spectral Graph Theory vol. 92 of Regional Conference Series in Mathematics American Mathematical Society, Providence, RI, 1997.Google Scholar
- C. Gkantsidis, M. Mihail, and A. Saberi, "Conductance and congestion in power law graphs," in ACM SIGMETRICS 2003. Google ScholarDigital Library
- D. Vukadinović,P. Huang, and T. Erlebach, "A spectral analysis of the Internet topology," Technical Report TIK-NR.118, ETH, 2001.Google Scholar
- C. Gkantsidis, M. Mihail, and E. Zegura, "Spectral analysis of Internet topologies," in IEEE INFOCOM 2003.Google Scholar
- L. Subramanian, S. Agarwal, J. Rexford, and R.H. Katz, "Characterizing the Internet hierarchy from multiple vantage points," in IEEE INFOCOM 2002.Google Scholar
- X. Dimitropoulos, D. Krioukov, B. Huffaker, kc claffy, and G. Riley, "Inferring AS relationships: Dead end or lively beginning?," in WEA 2005. Google ScholarDigital Library
Index Terms
The internet AS-level topology: three data sources and one definitive metric
Recommendations
Collecting the internet AS-level topology
At the inter-domain level, the Internet topology can be represented by a graph with Autonomous Systems (ASes) as nodes and AS peerings as links. This AS-level topology graph has been widely used in a variety of research efforts. Conventionally this ...
Towards an accurate AS-level traceroute tool
SIGCOMM '03: Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communicationsTraceroute is widely used to detect routing problems, characterize end-to-end paths, and discover the Internet topology. Providing an accurate list of the Autonomous Systems (ASes) along the forwarding path would make traceroute even more valuable to ...
Towards capturing representative AS-level Internet topologies
Recent studies on AS-level Internet connectivity have attracted considerable attention. These studies exclusively relied on BGP data from the Oregon route-views [University of Oregon Route Views Project, http:// www.routeviews.org] to derive some ...
Comments