Understanding BGP misconfiguration

ABSTRACT

It is well-known that simple, accidental BGP configuration errors can disrupt Internet connectivity. Yet little is known about the frequency of misconfiguration or its causes, except for the few spectacular incidents of widespread outages. In this paper, we present the first quantitative study of BGP misconfiguration. Over a three week period, we analyzed routing table advertisements from 23 vantage points across the Internet backbone to detect incidents of misconfiguration. For each incident we polled the ISP operators involved to verify whether it was a misconfiguration, and to learn the cause of the incident. We also actively probed the Internet to determine the impact of misconfiguration on connectivity.Surprisingly, we find that configuration errors are pervasive, with 200-1200 prefixes (0.2-1.0% of the BGP table size) suffering from misconfiguration each day. Close to 3 in 4 of all new prefix advertisements were results of misconfiguration. Fortunately, the connectivity seen by end users is surprisingly robust to misconfigurations. While misconfigurations can substantially increase the update load on routers, only one in twenty five affects connectivity. While the causes of misconfiguration are diverse, we argue that most could be prevented through better router design.

REFERENCES

• 1: C. Alaettinoglu, C. Villamizar, E. Gerich, D. Kessens, D. Meyer, T. Bates, D. Karrenberg, and M. Terpstra. Routing Policy Specification Language (RPSL). RFC 2622, IETF, June 1999.
• 2: T. Bates. The CIDR Report. http://www.employees.org/tbates/cidr-report.html.
• 3: A. Brown and D. A. Patterson. Embracing Failure: A Case for Recovery-Oriented Computing (ROC). In High Performance Transaction Processing Symposium, Oct. 2001.
• 4: N. Brownlee, kc Claffy, and E. Nemeth. DNS Measurements at a Root Server. In Globecom, Nov. 2001.
• 5: E. Chen and T. Bates. An Application of the BGP Community Attribute in Multi-home Routing. RFC 1998, IETF, Aug. 1996.
• 6: J. M. Christensen and J. M. Howard. Field Experience in Maintenance. In NATO Symposium on Human Detection and Diagnosis of System Failures, 1981.
• 7: Cisco Documentation. http://www.cisco.com/univercd/cc/td/doc/cisintwk/ics/icsbgp4.htm.
• 8: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 9: J. Cowie, A. Ogielski, B. Premore, and Y. Yuan. Global Routing Instabilities during Code Red II and Nimda Worm Propagation. http://www.renesys.com/projects/bgp_instability.
• 10: Peter B. Danzig , Katia Obraczka , Anant Kumar, An analysis of wide-area name server traffic: a study of the Internet Domain Name System, Conference proceedings on Communications architectures & protocols, p.281-292, August 17-20, 1992, Baltimore, Maryland, United States
• 11: Dawson Engler , David Yu Chen , Seth Hallem , Andy Chou , Benjamin Chelf, Bugs as deviant behavior: a general approach to inferring errors in systems code, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 12: J. Farrar. C & W Routing Instability. NANOG mail archives. http://www.merit.edu/mail.archives/nanog/2001-04/msg00209.html.
• 13: A. Feldmann and J. Rexford. IP Network Configuration for Intradomain Traffic Engineering. IEEE Network Magazine, Sep. 2001.
• 14: L. Gao. On Inferring Autonomous System Relationships in the Internet. In IEEE Global Internet Symposium, Nov. 2000.
• 15: J. Gray. Why Do Computers Stop and What Can Be Done About It? Technical Report 85.7, Tandem Computers, June 1985.
• 16: J. Gray. A Census of Tandem System Availability Between 1985 and 1990. Technical Report 90.1, Tandem Computers, Jan. 1990.
• 17: B. Greene and P. Smith. Essential IOS Features Every ISP Should Consider (v 2.9), June 2001.
• 18: 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
• 19: G. Huston. BGP Table Statistics. http://www.telstra.net/ops/bgp/index.html.
• 20: IPMA Project. http://www.merit.edu/ipma/.
• 21: B. H. Kantowitz and R. D. Sorkin. Human Factors: Understanding People-System Relationships. Wiley, 1983.
• 22: S. Kent, C. Lynn, and K. Seo. Secure Border Gateway Protocol (Secure-BGP). IEEE JSAC, 18(4), Apr. 2000.
• 23: T. Kernen. Traceroute.org. http://www.traceroute.org/.
• 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: 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
• 26: C. Labovitz, G. R. Malan, and F. Jahanian. Origins of Internet Routing Instability. In IEEE INFOCOM, June 1999.
• 27: Nancy G. Leveson, Safeware: system safety and computers, ACM Press, New York, NY, 1995
• 28: 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
• 29: C. D. Marsan. Faster 'Net growth rate raises fears about routers. http://www.nwfusion.com/news/2001/0402routing.html, Apr. 2001.
• 30: D. Meyer. RouteViews Project. http://www.routeviews.org.
• 31: S. A. Misel. Wow, AS7007! NANOG mail archives. http://www.merit.edu/mail.archives/nanog/1997-04/msg00340.html.
• 32: Donald A. Norman, Design rules based on analyses of human error, Communications of the ACM, v.26 n.4, p.254-258, April 1983 [doi>10.1145/2163.358092]
• 33: J. Reason. Human Error. Cambridge University Press, 1990.
• 34: Y. Rekhter and T. Li. A Border Gateway Protocol 4 (BGP-4). RFC 1771, IETF, Mar. 1995.
• 35: Y. Rekhter, B. Moskowitz, D. Karrenberg, G. J. de Groot, and E. Lear. Address Allocation for Private Internets. RFC 1918, IETF, February 1996.
• 36: Routing registry consistency check. http://www.ripe.net/ripe/docs/rr-consistencycheck.html, Dec. 2001.
• 37: J. Senders and N. Moray. Human Error: Cause, Prediction and Reduction. LEA Publishers, 1991.
• 38: Skitter project. http://www.caida.org/tools/measurement/skitter/.
• 39: J. Stone and C. Partridge. When the Checksum and the Data Disagree. In ACM SIGCOMM, Aug. 2000.
• 40: K. Varadhan, R. Govindan, and D. Estrin. Persistent Route Oscillations in Inter-Domain Routing. Computer Networks, 32(1), 1999.
• 41: Xiaoliang Zhao , Dan Pei , Lan Wang , Dan Massey , Allison Mankin , S. Felix Wu , Lixia Zhang, An analysis of BGP multiple origin AS (MOAS) conflicts, Proceedings of the 1st ACM SIGCOMM Workshop on Internet Measurement, November 01-02, 2001, San Francisco, California, USA [doi>10.1145/505202.505207]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
          Subjects: Network management

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Reliability, availability, and serviceability

General Terms:
Human Factors, Management, Reliability