Measuring the effects of internet path faults on reactive routing

ABSTRACT

Empirical evidence suggests that reactive routing systems improve resilience to Internet path failures. They detect and route around faulty paths based on measurements of path performance. This paper seeks to understand why and under what circumstances these techniques are effective.To do so, this paper correlates end-to-end active probing experiments, loss-triggered traceroutes of Internet paths, and BGP routing messages. These correlations shed light on three questions about Internet path failures: (1) Where do failures appear? (2) How long do they last? (3) How do they correlate with BGP routing instability?Data collected over 13 months from an Internet testbed of 31 topologically diverse hosts suggests that most path failures last less than fifteen minutes. Failures that appear in the network core correlate better with BGP instability than failures that appear close to end hosts. On average, most failures precede BGP messages by about four minutes, but there is often increased BGP traffic both before and after failures. Our findings suggest that reactive routing is most effective between hosts that have multiple connections to the Internet. The data set also suggests that passive observations of BGP routing messages could be used to predict about 20% of impending failures, allowing re-routing systems to react more quickly to failures.

REFERENCES

• 1: Amini, L., Shaikh, A., and Schulzrinne, H. Issues with inferring Internet topological attributes. In Proc. SPIE ITCOM (Boston, MA, August 2002), vol. 4685, pp. 80--90.
• 2: David Andersen , Hari Balakrishnan , Frans Kaashoek , Robert Morris, Resilient overlay networks, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 3: Anat Bremler-Barr , Edith Cohen , Haim Kaplan , Yishay Mansour, Predicting and bypassing end-to-end internet service degradations, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637248]
• 4: CAIDA's Skitter project, 2002. http://www.caida.org/tools/measurement/skitter/.
• 5: Chandra, B., Dahlin, M., Gao, L., and Nayate, A. End-to-end WAN Service Availability. In Proc. 3rd USITS (San Francisco, CA, 2001), pp. 97--108.
• 6: Chang, D.-F., Govindan, R., and Heidemann, J. An empirical study of router response to large BGP routing table load. Tech. Rep. ISI-TR-2001-552, USC/Information Sciences Institute, December 2001.
• 7: Donelan, S. Update: CSX train derailment. http://www.merit.edu/mail.archives/nanog/2001-07/msg00351.html.
• 8: Egan, J. Signal Detection Theory and ROC Analysis. Academic Press, New York, 1975.
• 9: Freedman, A. Active UDP and TCP performance during BGP update activity. In Proc. Internet Statistics Metrics and Analysis Workshop (Leiden, The Netherlands, October 2002). http://www.caida.org/outreach/isma/0210/ISMAagenda.xml.
• 10: 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]
• 11: 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]
• 12: 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
• 13: Ratul Mahajan , David Wetherall , Tom Anderson, Understanding BGP misconfiguration, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 14: 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
• 15: Miller, G. Overlay routing networks (akarouting), Apr. 2002.
• 16: Nichol, D. Detecting behavior propagation in BGP trace data. In Proc. Internet Statistics Metrics and Analysis Workshop (Leiden, The Netherlands, October 2002). http://www.caida.org/outreach/isma/0210/talks/david.pdf.
• 17: Opnix. Orbit: Routing Intelligence System. http://www.opnix.com/newsroom/OrbitWhitePaper_July_2001.pdf, 2002.
• 18: Vern Paxson, End-to-end routing behavior in the Internet, IEEE/ACM Transactions on Networking (TON), v.5 n.5, p.601-615, Oct. 1997 [doi>10.1109/90.649563]
• 19: MIT RON Project. http://nms.lcs.mit.edu/ron/.
• 20: RouteScience. http://www.routescience.com/.
• 21: Sockeye. http://www.sockeye.com/.
• 22: Neil Spring , Ratul Mahajan , David Wetherall, Measuring ISP topologies with rocketfuel, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 23: 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]
• 24: Gnu Zebra. http://www.zebra.org/.
• 25: Yin Zhang , Nick Duffield, On the constancy of internet path properties, Proceedings of the 1st ACM SIGCOMM Workshop on Internet Measurement, November 01-02, 2001, San Francisco, California, USA [doi>10.1145/505202.505228]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.6 Internetworking

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Measurement techniques

General Terms:
Experimentation, Measurement, Performance, Reliability