How to extract BGP peering information from the internet routing registry

ABSTRACT

We describe an on-line service, and its underlying methodology, designed to extract BGP peerings from the Internet Routing Registry. Both the method and the service are based on: a consistency manager for integrating information across different registries, an RPSL analyzer that extracts peering specifications from RPSL objects, and a peering classifier that aims at understanding to what extent such peering specifications actually contribute to fully determine a peering. A peering graph is built with different levels of confidence. We compare the effectiveness of our method with the state of the art. The comparison puts in evidence the quality of the proposed method.

REFERENCES

• 1: ARIN. http://www.arin.net/.
• 2: IRRd. http://www.irrd.net/.
• 3: IRRToolSet. http://www.isc.org/index.pl?/sw/IRRToolSet/.
• 4: Nemecis. http://ira.cs.ucr.edu:8080/Nemecis/.
• 5: Oregon Route Views Project. http://www.routeviews.org/.
• 6: Overview of the IRR. http://www.irr.net/docs/overview.html.
• 7: RADB db. ftp://ftp.radb.net/radb/dbase/.
• 8: RIPE. http://www.ripe.net/.
• 9: RIPE db. ftp://ftp.ripe.net/ripe/dbase/.
• 10: RRCC. http://www.ripe.net/projects/rrcc/.
• 11: The Internet Routing Registry: History and Purpose. http://www.ripe.net/db/irr.html.
• 12: C. Alaettinoglu , C. Villamizar , E. Gerich , D. Kessens , D. Meyer , T. Bates , D. Karrenberg , M. Terpstra, Routing Policy Specification Language (RPSL), RFC Editor, 1999
• 13: L. Blunk, J. Damas, F. Parent, and A. Robachevsky. Routing Policy Specification Language next generation (RPSLng). IETF RFC 4012, 2005.
• 14: A. Carmignani, G. D. Battista, W. Didimo, F. Matera, and M. Pizzonia. Visualization of the High Level Structure of the Internet with Hermes. J. of Graph Algorithms and Applications, 2002.
• 15: D. Karrenberg, G. Ross, P. Wilson, and L. Nobile. Development of the Regional Internet Registry System. Internet Protocol J., 2001.
• 16: S. Kerr. RIPE DB Inconsistencies. RIPE 43, 2002.
• 17: 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]
• 18: D. Meyer , J. Schmitz , C. Orange , M. Prior , C. Alaettinoglu, Using RPSL in Practice, RFC Editor, 1999
• 19: Y. Rekhter , T. Li, A Border Gateway Protocol 4 (BGP-4), RFC Editor, 1995
• 20: J. Schmitz, E. Gunduz, S. Kerr, A. Robachevsky, and J. L. S. Damas. Routing Registry Consistency Check. RIPE Document 201, 2001.
• 21: G. Siganos and M. Faloutsos. Analyzing BGP Policies: Methodology and Tool. In IEEE INFOCOM, 2004.
• 22: 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]

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems; Graph algorithms

General Terms:
Algorithms, Design

Keywords:
BGP, RPSL, interdomain routing, internet routing registry, policies