Quantifying path exploration in the internet

ABSTRACT

Previous measurement studies have shown the existence of path exploration and slow convergence in the global Internet routing system, and a number of protocol enhancements have been proposed to remedy the problem. However, existing measurements were conducted only over a small number of testing prefixes. There has been no systematic study to quantify the pervasiveness of Border Gateway Protocol (BGP) slow convergence in the operational Internet, nor any known effort to deploy any of the proposed solutions.

In this paper, we present our measurement results that identify BGP slow convergence events across the entire global routing table. Our data shows that the severity of path exploration and slow convergence varies depending on where prefixes are originated and where the observations are made in the Internet routing hierarchy. In general, routers in tier-1 Internet service providers (ISPs) observe less path exploration, hence they experience shorter convergence delays than routers in edge ASs; prefixes originated from tier-1 ISPs also experience less path exploration than those originated from edge ASs. Furthermore, our data show that the convergence time of route fail-over events is similar to that of new route announcements and is significantly shorter than that of route failures. This observation is contrary to the widely held view from previous experiments but confirms our earlier analytical results. Our effort also led to the development of a path-preference inference method based on the path usage time, which can be used by future studies of BGP dynamics.

REFERENCES

• 1: Craig Labovitz , Abha Ahuja , Abhijit Bose , Farnam Jahanian, Delayed Internet routing convergence, IEEE/ACM Transactions on Networking (TON), v.9 n.3, p.293-306, June 2001 [doi>10.1109/90.929852]
• 2: C. Labovitz, A. Ahuja, R. Wattenhofer, and S. Venkatachary, "The impact of Internet policy and topology on delayed routing convergence," in Proc. IEEE INFOCOM, Anchorage, AK, Apr. 2001, pp. 537-546.
• 3: Z. Morley Mao , Randy Bush , Timothy G. Griffin , Matthew Roughan, BGP beacons, Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, October 27-29, 2003, Miami Beach, FL, USA [doi>10.1145/948205.948207]
• 4: "The RouteViews project," 2005 [Online]. Available: http://www. routeviews.org/
• 5: "The RIPE routing information services," 2008 [Online]. Available: http://www.ris.ripe.net
• 6: Dan Pei , Beichuan Zhang , Daniel Massey , Lixia Zhang, An analysis of convergence delay in path vector routing protocols, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.50 n.3, p.398-421, 22 Febraury 2006 [doi>10.1016/j.comnet.2005.04.013]
• 7: "PSG beacon list," [Online]. Available: http://www.psg.com/~zmao/ BGPBeacon.html
• 8: "RIPE beacon list," [Online]. Available: http://www.ripe.net/ris/docs/ beaconlist.html
• 9: Beichuan Zhang , Vamsi Kambhampati , Mohit Lad , Daniel Massey , Lixia Zhang, Identifying BGP routing table transfers, Proceedings of the 2005 ACM SIGCOMM workshop on Mining network data, August 26-26, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080173.1080188]
• 10: Jennifer Rexford , Jia Wang , Zhen Xiao , Yin Zhang, BGP routing stability of popular destinations, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637232]
• 11: 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
• 12: 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
• 13: 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]
• 14: Wolfgang Mühlbauer , Steve Uhlig , Bingjie Fu , Mickael Meulle , Olaf Maennel, In search for an appropriate granularity to model routing policies, Proceedings of the 2007 conference on Applications, technologies, architectures, and protocols for computer communications, August 27-31, 2007, Kyoto, Japan
• 15: A. Markopoulou, G. Iannaccone, S. Bhattacharyya, C.-N. Chuah, and C. Diot, "Characterization of failures in an IP backbone network," in Proc. IEEE INFOCOM, Hong Kong, Mar. 2004, Sprint ATL Research Report.
• 16: Y. Rekhter, T. Li, and S. Hares, "Border gateway protocol 4," Internet Engineering Task Force, RFC 4271, Jan. 2006.
• 17: B. Premore, An Experimental Analysis of BGP Convergence Time, Proceedings of the Ninth International Conference on Network Protocols, p.53, November 11-14, 2001
• 18: 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]
• 19: J. Xia and L. Gao, "On the evaluation of AS relationship inferences," in Proc. IEEE GLOBECOM, Dec. 2004, vol. 3, pp. 1373-1377.
• 20: Xiaoqiao Meng , Zhiguo Xu , Beichuan Zhang , Geoff Huston , Songwu Lu , Lixia Zhang, IPv4 address allocation and the BGP routing table evolution, ACM SIGCOMM Computer Communication Review, v.35 n.1, January 2005 [doi>10.1145/1052812.1052827]
• 21: Nate Kushman , Srikanth Kandula , Dina Katabi, Can you hear me now?!: it must be BGP, ACM SIGCOMM Computer Communication Review, v.37 n.2, April 2007 [doi>10.1145/1232919.1232927]
• 22: 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
• 23: C. Labovitz, R. Malan, and F. Jahanian, "Origins of Internet routing instability," in Proc. IEEE INFOCOM, New York, NY, Mar. 1999, pp. 218-226.
• 24: Craig Labovitz , Abha Ahuja , Farnam Jahanian, Experimental Study of Internet Stability and Backbone Failures, Proceedings of the Twenty-Ninth Annual International Symposium on Fault-Tolerant Computing, p.278, June 15-18, 1999
• 25: Lan Wang , Xiaoliang Zhao , Dan Pei , Randy Bush , Daniel Massey , Allison Mankin , S. Felix Wu , Lixia Zhang, Observation and analysis of BGP behavior under stress, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637231]
• 26: 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]
• 27: Olaf Maennel , Anja Feldmann, Realistic BGP traffic for test labs, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 28: Jian Wu , Zhuoqing Morley Mao , Jennifer Rexford , Jia Wang, Finding a needle in a haystack: pinpointing significant BGP routing changes in an IP network, Proceedings of the 2nd conference on Symposium on Networked Systems Design & Implementation, p.1-14, May 02-04, 2005

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: Measurement techniques; Performance attributes

General Terms:
Algorithms, Design, Measurement, Performance

Keywords:
AS topology completeness, border gateway protocol (BGP), inter-domain routing, internet topology