Observation and analysis of BGP behavior under stress

ABSTRACT

Despite BGP's critical importance as the de-facto Internet inter-domain routing protocol, there is little understanding of how BGP actually performs under stressful conditions when dependable routing is most needed. In this paper, we examine BGP's behavior during one stressful period, the Code Red/Nimda attack on September 18, 2001. The attack was correlated with a 30-fold increase in the BGP update messages at a monitoring point which peers with a number of Internet service providers. Our examination of BGP's behavior during the event concludes that BGP exhibited no significant abnormality, and that over 40% of the observed updates can be attributed to the monitoring artifact in current BGP measurement settings. Our analysis, however, does reveal several weak points in both the protocol and its implementation, such as BGP's sensitivity to the transport session reliability, its inability to avoid the global propagation of small local changes, and its certain implementation features whose otherwise benign effects only get amplified under stressful conditions. We also identify areas for improvement in the current network measurement and monitoring effort.

References

1. Y. Rekhter and T. Li, "Border Gateway Protocol 4," RFC 1771, July 1995.
2. J. Cowie, A. Ogielski, B. J. Premore, and Y. Yuan, "Global routing instabilities triggered by Code Red II and Nimda worm attacks," Tech. Rep., Renesys Corporation, Dec 2001.
3. Networking System Adminisration and Security Institute (SANS), "Nimda worm/virus report," http://www.incidents.org/react/nimda.pdf.
4. RIPE, "Routing Information Service Project," http://www.ripe.net/ripencc/pub-services/np/ris-index.html.
5. C. Labovitz, A. Ahuja, A. Bose, and E Jahanian, "Delayed Internet routing convergence," in Proceedings of the ACM SIGCOMM, August/September 2000.
6. C. Labovitz, G. R. Malan, and F. Jahanian, "Origins of internet routing instability," in Proceedings of the IEEE INFOCOM "99, New York, NY, March 1999, pp. 218--26.
7. Cisco Systems, "Dealing with mallocfail and high cpu utilization resulting from the "code red" worm," http://www.cisco.com/warp/public/63/ts_codred_worm.shtml.
8. D. Pei, X. Zhao, L. Wang, D. Massey, A. Mankin, S. Wu, and L. Zhang, "Improving BGP convergence through consistency assertions," in Proceedings of the IEEE INFOCOM, June 2002.
9. C. Labovitz, G. R. Malan, and F. Jahanian, "Internet routing instability," in Proceedings of the ACM SIGCOMM '97, Cannes, France, September 1997, pp. 115--26.
10. G.R. Malan and F. Jahanian, "An extensible probe architecture for network protocol performance measurement," in Proceedings of the ACM SIGCOMM '98, Vancouver, BC, Canada, September 1998.
11. A. Shaikh, A. Varma, L. Kalampoukas, and R. Dube, "Routing stability in congested networks: Experimentation and analysis," in Proceedings of the ACM SIGCOMM 2000, Stockholm, Sweden, September 2000, pp. 163--74.
12. D.-F. Chang, R. Govindan, and J. Heidemann, "An empirical study of router response to large BGP routing table load," Tech. Rep. ISI-TR-2001-552, USC/Information Sciences Institute, December 2001.
13. S. Ramachandra, Y. Rekhter, R. Fernando, J. Scudder, and E. Chen, "Graceful restart mechanism for BGP," lnternet Draft October 2000.
14. University of Oregon, "The Route Views Project," http://www.antc.uoregon.edu/route-views/.

Index Terms

• Networks

  • Network protocols

    • Network layer protocols

      • Routing protocols

  • Network services

    • Network management

    • Network monitoring