BGP routing dynamics revisited

ABSTRACT

Understanding BGP routing dynamics is critical to the solid growth and maintenance of the Internet routing infrastructure. However, while the most extensive study on BGP dynamics is nearly a decade old, many factors that could affect BGP dynamics have changed considerably. We revisit this important topic in this paper, focusing on not only comparing with the previous results, but also issues not well explored before. We have found that, compared to almost a decade ago, although certain characteristics remain unchanged (such as some temporal properties), BGP dynamics are now “busier,” and more importantly, now have much less pathological behavior and are “healthier”; for example, forwarding dynamics are now not only dominant, but also more consistent across different days. Contributions to BGP dynamics by different BGP peers—which are not proportional to the size of a peer’s AS—are also more stable, and dynamics due to policy changes or duplicate announcements are usually from specific peers

REFERENCES

• 1: 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
• 2: Y. Rekhter, T. Li, and S. Hares, "A Border Gateway Protocol 4 (BGP-4)," RFC 4271, 2006.
• 3: Y. Rekhter and T. Li, "A Border Gateway Protocol 4 (BGP-4)," RFC 1771, 1995.
• 4: R. Chandra, P. Traina, and T. Li, "BGP Communities Attribute," RFC 1997, 1996.
• 5: C. Villamizar, R. Chandra, and R. Govindan, "BGP Route Flap Damping," RFC 2439, 1998.
• 6: T. Bu, L. Gao, and D. Towsley, "On characterizing BGP routing table growth," in Proc. IEEE Global Internet, November 2002.
• 7: G. Huston, "Analyzing the Internet's BGP routing table," The Internet Protocol Journal, vol. 4, no. 1, March 2001.
• 8: "BGP reports," http://bgp.potaroo.net/.
• 9: C. Labovitz, G. Malan, and F. Jahanian, "Origins of Internet routing instability," in Proc. IEEE INFOCOM, March 1999.
• 10: Bilal Chinoy, Dynamics of internet routing information, Conference proceedings on Communications architectures, protocols and applications, p.45-52, September 13-17, 1993, San Francisco, California, United States
• 11: 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
• 12: 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]
• 13: Vern Paxson, End-to-end routing behavior in the Internet, Conference proceedings on Applications, technologies, architectures, and protocols for computer communications, p.25-38, August 28-30, 1996, Palo Alto, California, United States
• 14: M. Caesar, L. Subramanian, and R. Katz, "Towards localizing root causes of BGP dynamics," Tech. Rep. CSD-04-1302, UC Berkeley, 2004.
• 15: 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]
• 16: 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
• 17: 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
• 18: 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
• 19: C. Labovitz, A. Ahuja, R. Wattenhofer, and V. Srinivasan, "The impact of Internet policy and topology on delayed routing convergence," in Proc. IEEE INFOCOM, April 2001.
• 20: Timothy Griffin , Gordon T. Wilfong, Analysis of the MED Oscillation Problem in BGP, Proceedings of the 10th IEEE International Conference on Network Protocols, p.90-99, November 12-15, 2002
• 21: Zhuoqing Morley Mao , Ramesh Govindan , George Varghese , Randy H. Katz, Route flap damping exacerbates internet routing convergence, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 22: J. Cowie, A. Ogielski, B. Premore, and Y. Yuan, "Internet worms and global routing instabilities," in Proc. of SPIE International symposium on Convergence of IT and Communication, July 2002.
• 23: J. Cowie, A. Ogielski, B. Premore, E. Smith, and T. Underwood, "Impact of the 2003 blackouts on Internet communications," http://www.renesys.com/news/2003-11-21/Renesys_BlackoutReport.pdf, November 2003.
• 24: Mohit Lad, Xiaoliang Zhao, Beichuan Zhang, Dan Massey, and Lixia Zhang, "An analysis of BGP update burst during Slammer worm attack," in Proceedings of 5th International Workshop on Distributed Computing, December 2003.
• 25: Jun Li , Dejing Dou , Zhen Wu , Shiwoong Kim , Vikash Agarwal, An internet routing forensics framework for discovering rules of abnormal BGP events, ACM SIGCOMM Computer Communication Review, v.35 n.5, October 2005 [doi>10.1145/1096536.1096542]
• 26: RIPE NCC, "RIPE routing information service raw data," http://data.ris.ripe.net/.
• 27: "University of Oregon Route Views Project," http://antc.uoregon.edu/route-views/.
• 28: 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]
• 29: V. A. Mandelshtam and H. S. Taylor, "Harmonic inversion of time signals," Journal of Chemical Physics, vol. 107, no. 17, 1997.
• 30: Steven G. Johnson, "harminv," http://ab-initio.mit.edu/wiki/index.php/Harminv.

INDEX TERMS

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

General Terms:
Measurement

Keywords:
BGP, analysis, network measurement, routing dynamics, routing instability