Computing the types of the relationships between autonomous systems

ABSTRACT

We investigate the problem of computing the types of the relationships between Internet Autonomous Systems. We refer to the model introduced by Gao [IEEE/ACM TRANSACTIONS ON NETWORKING, 9(6):733-645, 2001] and Subramanian et al. (IEEE Infocom, 2002) that bases the discovery of such relationships on the analysis of the AS paths extracted from the BGP routing tables. We characterize the time complexity of the above problem, showing both NP-completeness results and efficient algorithms for solving specific cases. Motivated by the hardness of the general problem, we propose approximation algorithms and heuristics based on a novel paradigm and show their effectiveness against publicly available data sets. The experiments provide evidence that our algorithms perform significantly better than state-of-the-art heuristics.

REFERENCES

• 1: John W. Stewart, III, BGP4: Inter-Domain Routing in the Internet, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
• 2: [2] C. Alaettinoglu, "Scalable router configuration for the internet," presented at the IEEE IC3N 1996, Washington, DC, Oct. 1996.
• 3: [3] G. Huston, "Interconnection, peering, and settlements," presented at the INET 1999, San Jose, CA, Jun. 1999.
• 4: R. Govindan , A. Reddy, An Analysis of Internet Inter-Domain Topology and Route Stability, Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, p.850, April 09-11, 1997
• 5: [5] R. Govindan and H. Tangmunarunkit, "Heuristics for internet map discovery," presented at the IEEE INFOCOM 2000, Tel Aviv, Israel, Mar. 2000.
• 6: [6] W. Theilmann and K. Rothermel, "Dynamic distance maps of the internet," presented at the IEEE INFOCOM 2000, Tel Aviv, Israel, Mar. 2000.
• 7: 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]
• 8: [8] Z. Ge, D. R. Figueiredo, S. Jaiswal, and L. Gao, "On the hierarchical structure of the logical internet graph," presented at the SPIE ITCom 2001, Denver, CO, 2001.
• 9: [9] L. Subramanian, S. Agarwal, J. Rexford, and R. Katz, "Characterizing the internet hierarchy from multiple vantage points," presented at the IEEE INFOCOM 2002, New York, NY, Jun. 2002.
• 10: [10] G. Siganos and M. Faloutsos, "Analyzing BGP policies: Methodology and tool," presented at the IEEE INFOCOM 2003, San Francisco, CA, Mar. 2003.
• 11: [11] J. Håstad, "Clique is hard to approximate within n^1-ε," Acta Math., vol. 182, pp. 105-142, 1999.
• 12: [12] T. Erlebach, A. Hall, and T. Schank, "Classifying customer-provider relationships in the internet," in Proc. IASTED Int. Conf. Communications and Computer Networks, 2002, pp. 538-545.
• 13: [13] G. Di Battista, M. Patrignani, and M. Pizzonia, "Computing the types of the relationships between autonomous systems," presented at the IEEE INFOCOM 2003, San Francisco, CA, Mar. 2003.
• 14: [14] L. Gao, T. G. Griffin, and J. Rexford, "Inherently safe backup routing with BGP," in Proc. IEEE INFOCOM, Apr. 2001, pp. 547-556.
• 15: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 16: [16] B. Aspvall, M. F. Plass, and R. E. Tarjan, "A linear-time algorithm for testing the truth of certain quantified boolean formulas," Inf. Process. Lett., vol. 8, no. 3, pp. 121-123, 1979.
• 17: [17] K. Mehlhorn, Data Structures and Algorithms. New York: Springer, 1984, vol. 1-3.
• 18: Kurt Mehlhorn , Stefan Näher, LEDA: a platform for combinatorial and geometric computing, Cambridge University Press, New York, NY, 1999
• 19: [19] "Characterizing the internet hierarchy from multiple vantage points," [Online]. Available: http://www.cs.berkeley.edu/~sagarwal/research/ BGP-hierarchy/
• 20: [20] Univ. Oregon RouteViews project. [Online]. Available: http://www. routeviews.org
• 21: Johan Håstad, Some optimal inapproximability results, Journal of the ACM (JACM), v.48 n.4, p.798-859, July 2001 [doi>10.1145/502090.502098]
• 22: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 23: Michel X. Goemans , David P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM (JACM), v.42 n.6, p.1115-1145, Nov. 1995 [doi>10.1145/227683.227684]
• 24: Michael Lewin , Dror Livnat , Uri Zwick, Improved Rounding Techniques for the MAX 2-SAT and MAX DI-CUT Problems, Proceedings of the 9th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.67-82, May 27-29, 2002
• 25: Approximating the value of two power proof systems, with applications to MAX 2SAT and MAX DICUT, Proceedings of the 3rd Israel Symposium on the Theory of Computing Systems (ISTCS'95), p.182, January 04-06, 1995
• 26: [26] S. Benson, Semidefinite Programming Solver DSDP 4.5. 2002 [On-line]. Available: http://www-unix.mcs.anl.gov/~benson/
• 27: [27] D. R. Figueiredo, Z. Ge, and S. Jaiswal, Algorithm implementation. 2002 [Online]. Available: http://www-net.cs.umass.edu/~ratton/AS/
• 28: [28] L. Subramanian, personal communication.
• 29: [29] A. Carmignani, G. Di Battista, W. Didimo, F. Matera, and M. Pizzonia, "Visualization of the high level structure of the internet with Hermes," J. Graph Algorithms Appl., vol. 6, no. 3, pp. 281-311, 2002.

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

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms, Design

Keywords:
algorithms, internet, routing