Acyclic type-of-relationship problems on the internet: an experimental analysis

ABSTRACT

An experimental study of the feasibility and accuracy of the acyclicity approach introduced in [14] for the inference of business relationships among autonomous systems (ASes) is provided. We investigate the maximum acyclic type-of-relationship problem: on a given set of AS paths, find a maximum-cardinality subset which allows an acyclic and valley-free orientation. Inapproximability and NP-hardness results for this problem are presented and a heuristic is designed. The heuristic is experimentally compared to most of the state-of-the-art algorithms on a reliable data set. It turns out that the proposed heuristic produces the least number of misclassified customer-to-provider relationships among the tested algorithms. Moreover, it is flexible in handling pre-knowledge in the sense that already a small amount of correct relationships is enough to produce a high-quality relationship classification. Furthermore, the reliable data set is used to validate the acyclicity assumptions. The findings demonstrate that acyclicity notions should be an integral part of models of AS relationships.

REFERENCES

• 1: C. Alaettinouglu. Scalable router configuration for the Internet. In ICCCN'96. IEEE, 1996.
• 2: Giorgio Ausiello , M. Protasi , A. Marchetti-Spaccamela , G. Gambosi , P. Crescenzi , V. Kann, Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, Springer-Verlag New York, Inc., Secaucus, NJ, 1999
• 3: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 4: Giuseppe Di Battista , Thomas Erlebach , Alexander Hall , Maurizio Patrignani , Maurizio Pizzonia , Thomas Schank, Computing the types of the relationships between autonomous systems, IEEE/ACM Transactions on Networking (TON), v.15 n.2, p.267-280, April 2007 [doi>10.1109/TNET.2007.892878]
• 5: Giuseppe Di Battista , Tiziana Refice , Massimo Rimondini, How to extract BGP peering information from the internet routing registry, Proceedings of the 2006 SIGCOMM workshop on Mining network data, p.317-322, September 11-15, 2006, Pisa, Italy [doi>10.1145/1162678.1162685]
• 6: Xenofontas Dimitropoulos , Dmitri Krioukov , Marina Fomenkov , Bradley Huffaker , Young Hyun , kc claffy , George Riley, AS relationships: inference and validation, ACM SIGCOMM Computer Communication Review, v.37 n.1, January 2007 [doi>10.1145/1198255.1198259]
• 7: X. A. Dimitriopoulos, D. V. Krioukov, B. Huffaker, K. C. Claffy, G. F. Riley. Inferring AS relationships: Dead end or lively beginning? In WEA'05, LNCS #3503, pp. 113--125. Springer, 2005.
• 8: Lixin Gao, On inferring autonomous system relationships in the internet, IEEE/ACM Transactions on Networking (TON), v.9 n.6, p.733-745, December 2001 [doi>10.1109/90.974527]
• 9: Timothy G. Griffin , Gordon Wilfong, An analysis of BGP convergence properties, ACM SIGCOMM Computer Communication Review, v.29 n.4, p.277-288, Oct. 1999
• 10: J. Hawkinson , T. Bates, Guidelines for creation, selection, and registration of an Autonomous System (AS), RFC Editor, 1996
• 11: B. Hummel, S. Kosub. Acyclic type-of-relationship problems on the Internet: An experimental analysis. Technical Report TUM-I0709, Fakultät für Informatik, TU München, February 2007.
• 12: G. Huston. Interconnection, peering and settlements - Part II. The Internet Protocol Journal, 2(2):2--23, 1999.
• 13: T. Kernen. traceroute.org web site. http://www.traceroute.org.
• 14: S. Kosub, MG. Maaß, H. Täubig. Acyclic type-of-relationship problems on the Internet. In CAAN'06, LNCS #4235, pp. 98--111. Springer, 2006.
• 15: Merit Network Inc. Internet Routing Registry. http://www.irr.net.
• 16: Y. Rekhter , T. Li, A Border Gateway Protocol 4 (BGP-4), RFC Editor, 1995
• 17: RIPE NCC. Routing Information Service (RIS). http://www.ripe.net/ris/.
• 18: G. Siganos, M. Faloutsos. Analyzing BGP policies: Methodology and tool. In INFOCOM'04, pp. 1640--1651. IEEE, 2004.
• 19: L. Subramanian, S. Agarwal, J. Rexford, R. H. Katz. Characterizing the Internet hierarchy from multiple vantage points. In INFOCOM'02, pp. 618--627. IEEE, 2002.
• 20: P. Traina, R. Chandra, T. Li. BGP community attribute. RFC 1997, The Internet Society, 1996.
• 21: University of Oregon. Route Views project page. http://www.routeviews.org.
• 22: Peer Iljitsch Beijnum , Iljitsch Van Beijnum, Bgp, O'Reilly & Associates, Inc., Sebastopol, CA, 2002
• 23: J. Xia, L. Gao. On the evaluation of AS relationship inferences. In Globecom'04, vol. 3, pp. 1373--1377. IEEE, 2004.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms, Measurement

Keywords:
algorithms, as relationships, inter-domain routing