Building an AS-topology model that captures route diversity

ABSTRACT

An understanding of the topological structure of the Internet is needed for quite a number of networking tasks, e. g., making decisions about peering relationships, choice of upstream providers, inter-domain traffic engineering. One essential component of these tasks is the ability to predict routes in the Internet. However, the Internet is composed of a large number of independent autonomous systems (ASes) resulting in complex interactions, and until now no model of the Internet has succeeded in producing predictions of acceptable accuracy.We demonstrate that there are two limitations of prior models: (i) they have all assumed that an Autonomous System (AS) is an atomic structure - it is not, and (ii) models have tended to oversimplify the relationships between ASes. Our approach uses multiple quasi-routers to capture route diversity within the ASes, and is deliberately agnostic regarding the types of relationships between ASes. The resulting model ensures that its routing is consistent with the observed routes. Exploiting a large number of observation points, we show that our model provides accurate predictions for unobserved routes, a first step towards developing structural mod-els of the Internet that enable real applications.

REFERENCES

• 1: 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
• 2: Lun Li , David Alderson , Walter Willinger , John Doyle, A first-principles approach to understanding the internet's router-level topology, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 3: Barath Raghavan , Alex C. Snoeren, A system for authenticated policy-compliant routing, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 4: O. Bonaventure and B. Quoitin, "Common utilizations of the BGP community attribute, "2003, Internet Draft
• 5: Nick Feamster , Jay Borkenhagen , Jennifer Rexford, Guidelines for interdomain traffic engineering, ACM SIGCOMM Computer Communication Review, v.33 n.5, October 2003 [doi>10.1145/963985.963988]
• 6: Nick Feamster , Jared Winick , Jennifer Rexford, A model of BGP routing for network engineering, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA
• 7: Z. Morley Mao , Lili Qiu , Jia Wang , Yin Zhang, On AS-level path inference, Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 06-10, 2005, Banff, Alberta, Canada
• 8: 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]
• 9: 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.
• 10: Renata Teixeira , Aman Shaikh , Tim Griffin , Jennifer Rexford, Dynamics of hot-potato routing in IP networks, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA
• 11: R. Teixeira, N. Duffield, J. Rexford, and M. Roughan, "Traffic matrix reloaded: impact of routing changes, "in Proc. ACM PAM, 2005.
• 12: Renata Teixeira , Keith Marzullo , Stefan Savage , Geoffrey M. Voelker, In search of path diversity in ISP networks, Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, October 27-29, 2003, Miami Beach, FL, USA [doi>10.1145/948205.948247]
• 13: "University of Oregon RouteViews project, "http://www.routeviews.org/.
• 14: Timothy G. Griffin , F. Bruce Shepherd , Gordon Wilfong, The stable paths problem and interdomain routing, IEEE/ACM Transactions on Networking (TON), v.10 n.2, April 2002
• 15: L. Subramanian, S. Agarwal, J. Rexford, and R. Katz, "Characterizing the Internet hierarchy from multiple vantage points, "in Proc. IEEE INFOCOM, 2002.
• 16: L. Gao, "On Inferring Autonomous System Relationships in the Internet, "Proc. IEEE Global Internet, 2000.
• 17: Feng Wang , Lixin Gao, On inferring and characterizing internet routing policies, Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, October 27-29, 2003, Miami Beach, FL, USA [doi>10.1145/948205.948208]
• 18: G. Battista, M. Patrignani, and M. Pizzonia, "Computing the types of the relationships between autonomous systems, "in Proc. IEEE INFOCOM, 2003.
• 19: Ratul Mahajan , Neil Spring , David Wetherall , Tom Anderson, Inferring link weights using end-to-end measurements, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637237]
• 20: 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]
• 21: B. Quoitin and S. Uhlig, "Modeling the routing of an Autonomous System with C-BGP, "IEEE Network Magazine, 2005.
• 22: "RIPE's routing information service, "http://data.ris.ripe.net/.
• 23: Timothy G. Griffin , Gordon Wilfong, An analysis of BGP convergence properties, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.277-288, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 24: Craig Labovitz , Abha Ahuja , Abhijit Bose , Farnam Jahanian, Delayed Internet routing convergence, Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, p.175-187, August 28-September 01, 2000, Stockholm, Sweden
• 25: C. Labovitz, R. Malan, and F. Jahanian, "Origins of Internet routing instability, "in Proc. IEEE INFOCOM, 1999.
• 26: H. Tangmunarunkit, R. Govindan, S. Shenker, and D. Estrin, "The impact of Internet policy on Internet paths, "in Proc. IEEE INFOCOM, 2001.
• 27: Anja Feldmann , Olaf Maennel , Z. Morley Mao , Arthur Berger , Bruce Maggs, Locating internet routing instabilities, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 28: David G. Andersen , Nick Feamster , Steve Bauer , Hari Balakrishnan, Topology inference from BGP routing dynamics, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637239]
• 29: Renata Teixeira , Aman Shaikh , Tim Griffin , Geoffrey M. Voelker, Network sensitivity to hot-potato disruptions, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 30: B. Quoitin, "C-BGP, an efficient BGP simulator, "http://cbgp.info.ucl.ac.be/, 2003.
• 31: Sam Halabi , Danny McPherson, Internet Routing Architectures, Second Edition, Cisco Systems, 2000
• 32: Intel-DANTE, "Intel-DANTE monitoring project, "http://www.cambridge.intel-research.net/monitoring/dante/.
• 33: Abilene, "The Abilene Observatory: Abilene routing data, "http://abilene.internet2.edu/observatory/.
• 34: 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]
• 35: W. B. Norton, "The art of peering: the peering playbook, "2002.
• 36: G. Siganos and M. Faloutsos, "Analyzing BGP Policies: Methodology and Tool, "in Proc. IEEE INFOCOM, 2004.
• 37: Timothy G. Griffin , F. Bruce Shepherd , Gordon Wilfong, Policy Disputes in Path-Vector Protocols, Proceedings of the Seventh Annual International Conference on Network Protocols, p.21, October 31-November 03, 1999
• 38: Timothy G. Griffin , Gordon Wilfong, On the correctness of IBGP configuration, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 39: Nick Feamster , Zhuoqing Morley Mao , Jennifer Rexford, BorderGuard: detecting cold potatoes from peers, Proceedings of the 4th ACM SIGCOMM conference on Internet measurement, October 25-27, 2004, Taormina, Sicily, Italy [doi>10.1145/1028788.1028815]
• 40: Craig Labovitz , G. Robert Malan , Farnam Jahanian, Internet routing instability, Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication, p.115-126, September 14-18, 1997, Cannes, France
• 41: G. Siganos and M. Faloutsos, "BGP Routing: A Study at Large Time Scale, "in Proc. IEEE Global Internet, 2002.
• 42: Di-Fa Chang , Ramesh Govindan , John Heidemann, The Temporal and Topological Characteristics of BGP Path Changes, Proceedings of the 11th IEEE International Conference on Network Protocols, p.190, November 04-07, 2003
• 43: Anindya Basu , Chih-Hao Luke Ong , April Rasala , F. Bruce Shepherd , Gordon Wilfong, Route oscillations in I-BGP with route reflection, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 44: R. Musunuri and J. A. Cobb, "An Overview of Solutions to Avoid Persistent BGP Divergence, "IEEE Network Magazine, 2005.
• 45: Sharad Agarwal , Chen-Nee Chuah , Supratik Bhattacharyya , Christophe Diot, The impact of BGP dynamics on intra-domain traffic, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA
• 46: M. Caesar and J. Rexford, "BGP Routing Policies in ISP Networks, "IEEE Network Magazine, 2005.
• 47: 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]
• 48: Timothy G. Griffin , Joäo Luís Sobrinho, Metarouting, Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, August 22-26, 2005, Philadelphia, Pennsylvania, USA

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.5 Local and Wide-Area Networks
          Subjects: Internet (e.g., TCP/IP)

General Terms:
Algorithms, Experimentation, Measurement

Keywords:
BGP, inter-domain routing, policies, route diversity, routing