Resilient overlay networks

Abstract

A Resilient Overlay Network (RON) is an architecture that allows distributed Internet applications to detect and recover from path outages and periods of degraded performance within several seconds, improving over today's wide-area routing protocols that take at least several minutes to recover. A RON is an application-layer overlay on top of the existing Internet routing substrate. The RON nodes monitor the functioning and quality of the Internet paths among themselves, and use this information to decide whether to route packets directly over the Internet or by way of other RON nodes, optimizing application-specific routing metrics.Results from two sets of measurements of a working RON deployed at sites scattered across the Internet demonstrate the benefits of our architecture. For instance, over a 64-hour sampling period in March 2001 across a twelve-node RON, there were 32 significant outages, each lasting over thirty minutes, over the 132 measured paths. RON's routing mechanism was able to detect, recover, and route around all of them, in less than twenty seconds on average, showing that its methods for fault detection and recovery work well at discovering alternate paths in the Internet. Furthermore, RON was able to improve the loss rate, latency, or throughput perceived by data transfers; for example, about 5% of the transfers doubled their TCP throughput and 5% of our transfers saw their loss probability reduced by 0.05. We found that forwarding packets via at most one intermediate RON node is sufficient to overcome faults and improve performance in most cases. These improvements, particularly in the area of fault detection and recovery, demonstrate the benefits of moving some of the control over routing into the hands of end-systems.

References

1. 1 ANDERSEN, D. G. Resilient Overlay Networks. Master's thesis, Massachusetts Institute of Technology, May 2001.]]
2. 2 BALAKRISHNAN, H., SESHAN, S., STEMM, M., AND KATZ, R. Analyzing Stability in Wide-Area Network Performance. In Proc. ACM SIGMETRICS (Seattle, WA, June 1997), pp. 2-12.]]
3. 3 CHANDRA, B., DAHLIN, M., GAG, L., AND NAYATE, A. End-to-end WAN Service Availability. In Proc. 3rd USITS (San Francisco, CA, 2001), pp. 97-108.]]
4. 4 CLARK, D. Policy Routing in Internet Protocols. Interact Engineering Task Force, May 1989. RFC 1102.]]
5. 5 COLLINS, A. The Detour Framework for Packet Rerouting. Master's thesis, University of Washington, Oct. 1998.]]
6. 6 ERIKSSON, H. Mbone: The Multicast Backbone. Communications of the ACM 37, 8 (1994), 54-60.]]
7. 7 FLOYD, S., HANDLEY, M., PADHYE, J., AND WIDMER, J. Equation-Based Congestion Control for Unicast Applications. In Prec. ACM SIGCOMM (Stockholm, Sweden, Sept. 2000), pp. 43-54.]]
8. 8 GOYAL, M., GUERIN, R., AND RAJAN, R. Predicting TCP Throughput From Non-invasive Data. (Unpublished, http : //www. seas. upenn, edu : 8080/~guerin/publ icat ions/TCP_model. pdf).]]
9. 9 GUARDINI, I., FASANO, P., AND G1RARDI, G. IPv6 Operational Experience within the 6bone. In Prec. lnternet Society (INET) Conf. (Yokohama, Japan, July 2000). http://www.5.see.org/ inet2OOO/cdproceedings/le/le_l .htm.]]
10. 10 HAGENS, R., HALL, N., AND ROSE, M. Use of the Internet as a Subnetwork for Experimentation with the OSI Network Layer. Interact Engineering Task Force, Feb 1989. RFC 1070.]]
11. 11 KHANNA, A., AND ZINKY, J. The Revised ARPANET Routing Metric. In Prec. ACMSIGCOMM (Austin, TX, Sept. 1989), pp. 45-56.]]
12. 12 LABOVITZ, C., AHUJA, A., BOSE, A., AND JAHANIAN, F. Delayed Interact Routing Convergence. In Prec. ACM SIGCOMM (Stockholm, Sweden, September 2000), pp. 175-I 87.]]
13. 13 LABOVITZ, C., MALAN, R., AND JAHANIAN, F. Interact Routing Instability. IEEE/ACM Transactions on Networking 6, 5 (1998), 515-526.]]
14. 14 MCCANNE, S., AND JACOBSON, W. The BSD Packet Filter: A New Architecture for User-Level Packet Capture. In Prec. Winter '93 USENIX Conference (San Diego, CA, Jan. 1993), pp. 259-269.]]
15. 15 The North American Network Operators' Group mailing list archive. http : //www. cctec, com/maillists/nanog/.]]
16. 16 PADHYE, J., FIROIU, V., TOWSLEY, D., AND KUROSE, J. Modeling TCP Throughput: A Simple Model and its Empirical Validation. In Prec. ACM SIGCOMM (Vancouver, Canada, September 1998), pp. 303-323.]]
17. 17 PARTRIDGE, C. Using the Flow Label Field in 1Pv6. Internet Engineering Task Force, 1995. RFC 1809.]]
18. 18 PAXSON, V. End-to-End Routing Behavior in the Internet. In Prec. ACM SIGCOMM '96 (Stanford, CA, Aug. 1996), pp. 25-38.]]
19. 19 PAXSON, V. End-to-End Interact Packet Dynamics. In Prec. ACM SIGCOMM (Cannes, France, Sept. 1997), pp. 139-152.]]
20. 20 POSTEL, J. B. Transmission Control Protocol. Interact Engineering Task Force, September 1981. RFC 793.]]
21. 21 REKHTER, Y., AND LI, T. A Border Gateway Protocol 4 (BGP-4). Interact Engineering Task Force, 1995. RFC 1771.]]
22. 22 SAVAGE, S., ANDERSON, T., ET AL. Detour: A Case for Informed Interact Routing and Transport. IEEEMicro 19, 1 (Jan. 1999), 50-59.]]
23. 23 SAVAGE, S., COLLINS, A., HOFFMAN, E., SNELL, J., AND ANDERSON, T. The End-to-End Effects of lnternet Path Selection. In Proc. ACM SIGCOMM (Boston, MA, 1999), pp. 289-299.]]
24. 24 SESHAN, S., STEMM, M., AND KATZ, R. H. SPAND: Shared Passive Network Performance Discovery. In Proc. 1st USITS (Monterey, CA, December 1997), pp. 135-146.]]
25. 25 SHAIKH, A., KALAMPOUKAS, L., VARMA, A., AND DUBE, R. Routing Stability in Congested Networks: Experimentation and Analysis. In Proc. ACM SIGCOMM (Stockholm, Sweden, 2000), pp. 163-174.]]
26. 26 TOUCH, J., AND HOTZ, S. The X-Bone. In Proc. 3rd Global Internet Mini-Conference (Sydney, Australia, Nov. 1998), pp. 75-83.]]

Index Terms

• Networks

  • Network protocols

• Theory of computation

  • Design and analysis of algorithms

    • Approximation algorithms analysis

      • Routing and network design problems