Lord of the links: a framework for discovering missing links in the internet topology

ABSTRACT

The topology of the Internet at the Autonomous System (AS) level is not yet fully discovered despite significant research activity. The community still does not know how many links are missing, where these links are and finally, whether the missing links will change our conceptual model of the Internet topology. An accurate and complete model of the topology would be important for protocol design, performance evaluation and analyses. The goal of our work is to develop methodologies and tools to identify and validate such missing links between ASes. In this work, we develop several methods and identify a significant number of missing links, particularly of the peer-to-peer type. Interestingly, most of the missing AS links that we find exist as peer-to-peer links at the Internet Exchange Points (IXPs). First, in more detail, we provide a large-scale comprehensive synthesis of the available sources of information. We cross-validate and compare BGP routing tables, Internet Routing Registries, and traceroute data, while we extract significant new information from the less-studied Internet Exchange Points (IXPs). We identify 40% more edges and approximately 300% more peer-to-peer edges compared to commonly used data sets. All of these edges have been verified by either BGP tables or traceroute. Second, we identify properties of the new edges and quantify their effects on important topological properties. Given the new peer-to-peer edges, we find that for some ASes more than 50% of their paths stop going through their ISPs assuming policy-aware routing. A surprising observation is that the degree of an AS may be a poor indicator of which ASes it will peer with.

REFERENCES

• 1: Sally Floyd , Vern Paxson, Difficulties in simulating the internet, IEEE/ACM Transactions on Networking (TON), v.9 n.4, p.392-403, August 2001 [doi>10.1109/90.944338]
• 2: 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]
• 3: Beichuan Zhang , Raymond Liu , Daniel Massey , Lixia Zhang, Collecting the internet AS-level topology, ACM SIGCOMM Computer Communication Review, v.35 n.1, January 2005 [doi>10.1145/1052812.1052825]
• 4: Yuval Shavitt , Eran Shir, DIMES: let the internet measure itself, ACM SIGCOMM Computer Communication Review, v.35 n.5, October 2005 [doi>10.1145/1096536.1096546]
• 5: X. Dimitropoulos, D. Krioukov, and G. Riley, "Revisiting Internet AS-level topology discovery," in Proc. Passive and Active Measurement (PAM) Workshop, Boston, MA, 2005.
• 6: Priya Mahadevan , Dmitri Krioukov , Marina Fomenkov , Xenofontas Dimitropoulos , k c claffy , Amin Vahdat, The internet AS-level topology: three data sources and one definitive metric, ACM SIGCOMM Computer Communication Review, v.36 n.1, January 2006 [doi>10.1145/1111322.1111328]
• 7: H. Chang, S. Jamin, and W. Willinger, "To peer or not to peer: Modeling the evolution of the Internet's AS-level topology," in Proc. IEEE INFOCOM, 2006, 12 pp.
• 8: Lorenzo Colitti , Giuseppe Di Battista , Maurizio Patrignani , Maurizio Pizzonia , Massimo Rimondini, Investigating prefix propagation through active BGP probing, Microprocessors & Microsystems, v.31 n.7, p.460-474, November, 2007 [doi>10.1016/j.micpro.2007.05.001]
• 9: R. Cohen and D. Raz, "The Internet dark matter--on the missing links in the AS connectivity map," in Proc. IEEE INFOCOM, 2006, 12 pp.
• 10: Internet Routing Registry. [Online]. Available: http://www.irr.net
• 11: K. Xu, Z. Duan, Z. Zhang, and J. Chandrashekar, "On properties of Internet exchange points and their impact on AS tolology and relationship," in Networking, 2004, pp. 284-295.
• 12: G. Siganos and M. Faloutsos, "Analyzing BGP policies: Methodology and tool," in Proc. IEEE INFOCOM, 2004, vol. 3, pp. 1640-1651.
• 13: Y. He, G. Siganos, M. Faloutsos, and S. Krishnamurthy, "A systematic framework for unearthing the missing links: Measurements and impact," in USENIX NSDI, Cambridge, MA, Apr. 2007.
• 14: Oregon Routeview Project. [Online]. Available: http://www.route-views.org
• 15: Ripe Route Information Service. [Online]. Available: http://www.ripe. net/ris
• 16: A. Lakhina, J. W. Byers, M. Crovella, and P. Xie, "Sampling biases in IP topology measurements," in Proc. IEEE INFOCOM, 2003, vol. 1, pp. 332-341.
• 17: Dimitris Achlioptas , Aaron Clauset , David Kempe , Cristopher Moore, On the bias of traceroute sampling: or, power-law degree distributions in regular graphs, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060693]
• 18: Ricardo V. Oliveira , Beichuan Zhang , Lixia Zhang, Observing the evolution of internet as topology, Proceedings of the 2007 conference on Applications, technologies, architectures, and protocols for computer communications, August 27-31, 2007, Kyoto, Japan
• 19: 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]
• 20: Z. M. Mao, D. Johnson, J. Rexford, J. Wang, and R. Katz, "Scalable and accurate identification of AS-level forwarding paths," in Proc. IEEE INFOCOM, 2004, vol. 3, pp. 1605-1615.
• 21: Brice Augustin , Xavier Cuvellier , Benjamin Orgogozo , Fabien Viger , Timur Friedman , Matthieu Latapy , Clémence Magnien , Renata Teixeira, Avoiding traceroute anomalies with Paris traceroute, Proceedings of the 6th ACM SIGCOMM conference on Internet measurement, October 25-27, 2006, Rio de Janeriro, Brazil [doi>10.1145/1177080.1177100]
• 22: E. Shir, Dec. 2005, Personal communication via e-mail.
• 23: Benoit Donnet , Philippe Raoult , Timur Friedman , Mark Crovella, Efficient algorithms for large-scale topology discovery, Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 06-10, 2005, Banff, Alberta, Canada
• 24: Neil Spring , Ratul Mahajan , David Wetherall , Thomas Anderson, Measuring ISP topologies with rocketfuel, IEEE/ACM Transactions on Networking (TON), v.12 n.1, p.2-16, February 2004 [doi>10.1109/TNET.2003.822655]
• 25: Sharad Jaiswal , Arnold L. Rosenberg , Don Towsley, Comparing the Structure of Power-Law Graphs and the Internet AS Graph, Proceedings of the 12th IEEE International Conference on Network Protocols, p.294-303, October 05-08, 2004
• 26: S. Jin and A. Bestavros, "An empirical study of inherent routing bias in variable-degree networks," Boston Univ., Boston, MA, Tech. Rep., 2003.
• 27: J. Xia and L. Gao, "On the evaluation of AS relationship inferences," in Proc. IEEE Globecom, 2004, vol. 3, pp. 1373-1377.
• 28: Traceroute. [Online]. Available: http://www.traceroute.org
• 29: 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
• 30: Alberto Medina , Ibrahim Matta , John Byers, On the origin of power laws in Internet topologies, ACM SIGCOMM Computer Communication Review, v.30 n.2, April 2000 [doi>10.1145/505680.505683]
• 31: Q. Chen, H. Chang, R. Govindan, S. Jamin, S. J. Shenker, and W. Willinger, "The origin of power laws in Internet topologies revisited," in Proc. IEEE INFOCOM, 2002, pp. 608-617.
• 32: L. Gao and F. Wang, "The extent of AS path inflation by routing policies," in Proc. IEEE Globecom, 2002, vol. 3, pp. 2180-2184.
• 33: Neil Spring , Ratul Mahajan , Thomas Anderson, The causes of path inflation, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863970]
• 34: M. Caesar and J. Rexford, "BGP routing policies in ISP networks," IEEE Network, vol. 19, no. 6, pp. 5-11, Nov./Dec. 2005.
• 35: Packete Cleaning House. [Online]. Available: http://www.pch.net
• 36: L. Amimi, A. Shaikh, and H. Schulzrinne, "Issues with inferring Internet topological attributes," in Proc. SPIE ITCom, 2002, vol. 4685, pp. 80-90.
• 37: Y. Hyun, A. Broido, and K. Claffy, Traceroute and BGP AS path incongruities. [Online]. Available: www.caida.org/outreach/papers/ 2003/ASP/
• 38: European Internet Exchange Assoc. [Online]. Available: http://www. euro-ix.net

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

General Terms:
Algorithms, Design, Performance

Keywords:
BGP, inter-domain, internet, measurement, missing links, routing, topology