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. Andersen, D. G., Balakrishnan, H., Kaashoek, M. F., and Morris, R. Resilient Overlay Networks. In Proc. 18th ACM SOSP(Banff, Canada, Oct. 2001), pp. 131--145.
3. Bremler-Barr, A., Cohen, E., Kaplan, H., and Mansour, Y. Predicting and bypassing end-to-end Internet service degradations. In Proc. ACM SIGCOMM Internet Measurement Workshop (Marseille, France, November 2002).
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. Gao, L. On inferring automonous system relationships in the Internet. IEEE/ACM Transactions on Networking 9, 6 (December 2001), 733--745.
11. Labovitz, C., Ahuja, A., Bose, A., and Jahanian, F. Delayed Internet Routing Convergence. IEEE/ACM Transactions on Networking 9, 3 (June 2001), 293--306.
12. Labovitz, C., Ahuja, A., and Jahanian, F. Experimental Study of Internet Stability and Wide-Area Backbone Failures. In Proc. 29th International Symposium on Fault-Tolerant Computing (June 1999).
13. Mahajan, R., Wetherall, D., and Anderson, T. Understanding BGP misconfiguration. In Proc. ACM SIGCOMM (Aug. 2002). (to appear) http://www.cs.washington.edu/homes/ratul/bgp/bgp-misconfigs.ps.
14. Mao, Z. M., Govindan, R., Varghese, G., and Katz, R. Route Flap Damping Exacerbates Internet Routing Convergence. In Prof. ACM SIGCOMM 2002 (Pittsburgh, PA, August 2002).
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. Paxson, V. End-to-End Routing Behavior in the Internet. IEEE/ACM Transactions on Networking 5, 5 (1997), 601--615.
19. MIT RON Project. http://nms.lcs.mit.edu/ron/.
20. RouteScience. http://www.routescience.com/.
21. Sockeye. http://www.sockeye.com/.
22. Spring, N., Mahajan, R., and Wetherall, D. Measuring ISP topologies with Rocketfuel. In Proc. ACM SIGCOMM (Aug. 2002).
23. Wang, L., et al. Observation and analysis of BGP behavior under stress. In Proc. ACM SIGCOMM Internet Measurement Workshop (Marseille, France, November 2002).
24. Gnu Zebra. http://www.zebra.org/.
25. Zhang, Y., Duffield, N., Paxson, V., and Shenker, S. On the constancy of Internet path properties. In Proc. ACM SIGCOMM Internet Measurement Workshop (San Francisco, CA, November 2001).

Index Terms

• General and reference

  • Cross-computing tools and techniques

    • Measurement

    • Metrics

• Networks

  • Network components

  • Network types

    • Public Internet