Route flap damping exacerbates internet routing convergence

ABSTRACT

Route flap damping is considered to be a widely deployed mechanism in core routers that limits the widespread propagation of unstable BGP routing information. Originally designed to suppress route changes caused by link flaps, flap damping attempts to distinguish persistently unstable routes from routes that occasionally fail. It is considered to be a major contributor to the stability of the Internet routing system.We show in this paper that, surprisingly, route flap damping can significantly exacerbate the convergence times of relatively stable routes. For example, a route to a prefix that is withdrawn exactly once and re-announced can be suppressed for up to an hour (using the current RIPE recommended damping parameters). We show that such abnormal behavior fundamentally arises from the interaction of flap damping with BGP path exploration during route withdrawal. We study this interaction using a simple analytical model and understand the impact of various BGP parameters on its occurrence using simulations. Finally, we outline a preliminary proposal to modify route flap damping scheme that removes the undesired interaction in all the topologies we studied. .

REFERENCES

• 1: A. Khanna , J. Zinky, The revised ARPANET routing metric, Symposium proceedings on Communications architectures & protocols, p.45-56, September 25-27, 1989, Austin, Texas, United States
• 2: H. Yu C. Alaettinoglu, V. Jacobson, "Towards Milli-Second IGP Convergence," IETF Internet Draft: draft-alaettinoglu-ISIS-convergence-00, November 2000.
• 3: C. Villamizar, R. Chandra, and R. Govindan, "BGP Route Flap Damping," RFC 2439, 1998.
• 4: "From private email exchanges with Randy Bush," .
• 5: Geoff Huston, "Analyzing the Internet BGP Routing Table," The Internet Protocol Journal, March 2001.
• 6: 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
• 7: 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
• 8: C. Labovitz, R. Wattenhofer, S. Venkatachary, and A. Ahuja, "The Impact of Internet Policy and Topology on Delayed Routing Convergence," in Proceedings of INFOCOM 2001.
• 9: Christian Panigl, Joachim Schmitz, Philip Smith, and Cristina Vistoli, "RIPE Routing-WG Recommendations for Coordinated Route-flap Damping Parameters," October 2001, Document ID: ripe-229.
• 10: "The SSFnet Project," http://www.ssfnet.org.
• 11: Y. Rekhter and T. Li, "A Border Gateway Protocol," RFC 1771 (BGP version 4), March 1995.
• 12: B. Premore, An Experimental Analysis of BGP Convergence Time, Proceedings of the Ninth International Conference on Network Protocols, p.53, November 11-14, 2001
• 13: Z. Morley Mao, Ramesh Govindan, George Varghese, and Randy Katz, "Route flap damping exacerbates internet routing convergence," Tech. Rep. UCB//CSD-02-1184, U.C. Berkeley, June 2002.
• 14: D. Pei, X. Zhao, L. Wang, D. Massey, A. Mankin, S. F. Wu, and L. Zhang, "Improving BGP Convergence Through Consistency Assertions," .
• 15: BGP4 Inter-Domain Routing in the Internet, Addison-Wesley, 1999.
• 16: Ripe NCC, "Routing Information Service Raw Data,".
• 17: "University of Oregon Route Views Archive Project," www.routeviews.org.
• 18: Thomas L. Rodeheffer , Michael D. Schroeder, Automatic reconfiguration in Autonet, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.183-197, October 13-16, 1991, Pacific Grove, California, United States
• 19: K. Varadhan, R. Govindan, and D. Estrin, "Persistent Route Oscillations in Inter-Domain Routing," Computer Networks, March 2000.
• 20: Lixin Gao , Jennifer Rexford, Stable Internet routing without global coordination, Proceedings of the 2000 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.307-317, June 18-21, 2000, Santa Clara, California, United States
• 21: 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

INDEX TERMS

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

General Terms:
Experimentation, Performance

Keywords:
BGP, border gateway protocol, interdomain routing protocol, route flap damping, routing convergence, routing dynamics