On understanding transient interdomain routing failures

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On understanding transient interdomain routing failures

Full text

Pdf (692 KB)

Source

IEEE/ACM Transactions on Networking (TON) archive
Volume 17 , Issue 3 (June 2009) table of contents

Pages 740-751

Year of Publication: 2009

ISSN:1063-6692

Authors

Feng Wang	School of Engineering and Computational Sciences, Liberty University, Lynchburg, VA
Jian Qiu	Department of Electrical and Computer Engineering, University of Massachusetts, Amherst, MA
Lixin Gao	Department of Electrical and Computer Engineering, University of Massachusetts, Amherst, MA
Jia Wang	AT&T Labs-Research, Florham Park, NJ

Publisher

IEEE Press Piscataway, NJ, USA

Bibliometrics

Downloads (6 Weeks): 18, Downloads (12 Months): 83, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	10.1109/TNET.2008.2001952

ABSTRACT

The convergence time of the interdomain routing protocol, BGP, can last as long as 30 minutes. Yet, routing behavior during BGP route convergence is poorly understood. During route convergence, an end-to-end Internet path can experience a transient loss of reachability. We refer to this loss of reachability as transient routing failure. Transient routing failures can lead to packet losses, and prolonged packet loss bursts can make the performance of applications such as Voice-over-IP and interactive games unacceptable. In this paper, we study how routing failures can occur in the Internet. With the aid of a formal model that captures transient failures of the interdomain routing protocol, we derive the sufficient conditions that transient routing failures could occur. We further study transient routing failures in typical BGP systems where commonly used routing policies are applied. Network administrators can apply our analysis to improve their network performance and stability.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	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]
	2	Matthew Roughan , Tim Griffin , Morley Mao , Albert Greenberg , Brian Freeman, Combining routing and traffic data for detection of IP forwarding anomalies, ACM SIGMETRICS Performance Evaluation Review, v.32 n.1, June 2004
	3	Nick Feamster , David G. Andersen , Hari Balakrishnan , M. Frans Kaashoek, Measuring the effects of internet path faults on reactive routing, Proceedings of the 2003 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 11-14, 2003, San Diego, CA, USA
	4	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
	5	A. Markopoulou, G. Iannaccone, S. Bhattacharyya, C. Chuah, and C. Diot, "Characterization of failures in an IP backbone," in Proc. IEEE INFOCOM, Hong Kong, China, Mar. 2004, vol. 4, pp. 2307-2317.
	6	Sharad Agarwal , Chen-Nee Chuah , Supratik Bhattacharyya , Christophe Diot, The impact of BGP dynamics on intra-domain traffic, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA
	7	Aman Shaikh , Albert Greenberg, OSPF monitoring: architecture, design and deployment experience, Proceedings of the 1st conference on Symposium on Networked Systems Design and Implementation, p.5-5, March 29-31, 2004, San Francisco, California
	8	Pierre Francois , Clarence Filsfils , John Evans , Olivier Bonaventure, Achieving sub-second IGP convergence in large IP networks, ACM SIGCOMM Computer Communication Review, v.35 n.3, July 2005 [doi>10.1145/1070873.1070877]
	9	C. Labovitz and A. Ahuja, "The impact of Internet policy and topology on delayed routing convergence," in Proc. IEEE INFOCOM, Anchorage, AK, Apr. 2001, vol. 1, pp. 537-546.
	10	Craig Labovitz , G. Robert Malan , Farnam Jahanian, Internet routing instability, IEEE/ACM Transactions on Networking (TON), v.6 n.5, p.515-528, Oct. 1998 [doi>10.1109/90.731185]
	11	Anja Feldmann , Olaf Maennel , Z. Morley Mao , Arthur Berger , Bruce Maggs, Locating internet routing instabilities, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
	12	Di-Fa Chang , Ramesh Govindan , John Heidemann, The Temporal and Topological Characteristics of BGP Path Changes, Proceedings of the 11th IEEE International Conference on Network Protocols, p.190, November 04-07, 2003
	13	Urs Hengartner , Sue Moon , Richard Mortier , Christophe Diot, Detection and analysis of routing loops in packet traces, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637217]
	14	Dan Pei , Xiaoliang Zhao , Dan Massey , Lixia Zhang, A Study of BGP Path Vector Route Looping Behavior, Proceedings of the 24th International Conference on Distributed Computing Systems (ICDCS'04), p.720-729, March 24-26, 2004
	15	Feng Wang , Lixin Gao , Jia Wang , Jian Qiu, On Understanding of Transient Interdomain Routing Failures, Proceedings of the 13TH IEEE International Conference on Network Protocols, p.30-39, November 06-09, 2005 [doi>10.1109/ICNP.2005.29]
	16	Feng Wang , Zhuoqing Morley Mao , Jia Wang , Lixin Gao , Randy Bush, A measurement study on the impact of routing events on end-to-end internet path performance, Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, September 11-15, 2006, Pisa, Italy
	17	Lixin Gao , Jennifer Rexford, Stable internet routing without global coordination, IEEE/ACM Transactions on Networking (TON), v.9 n.6, p.681-692, December 2001 [doi>10.1109/90.974523]
	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	Nick Feamster , Jared Winick , Jennifer Rexford, A model of BGP routing for network engineering, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA
	20	Timothy G. Griffin , F. Bruce Shepherd , Gordon Wilfong, Policy Disputes in Path-Vector Protocols, Proceedings of the Seventh Annual International Conference on Network Protocols, p.21, October 31-November 03, 1999
	21	T. Griffin and G. T. Wilfong, "A safe path vector protocol," in Proc. IEEE INFOCOM, 2000, pp. 490-499.
	22	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]
	23	L. Gao, T. Griffin, and J. Rexford, "Inherently safe backup routing with BGP," in Proc. IEEE INFOCOM, Anchorage, AK, 2001, pp. 547-556.
	24	Timothy G. Griffin , F. Bruce Shepherd , Gordon Wilfong, The stable paths problem and interdomain routing, IEEE/ACM Transactions on Networking (TON), v.10 n.2, April 2002
	25	Timothy G. Griffin , Aaron D. Jaggard , Vijay Ramachandran, Design principles of policy languages for path vector protocols, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863964]
	26	João Luis Sobrinho, Network routing with path vector protocols: theory and applications, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863963]
	27	A. Feldmann, H. Kong, O. Maennel, and A. Tudor, "Measuring BGP pass-through times," in Proc. Passive and Active Measurement Conf. (PAM'04), Antibes Juan-les-Pins, France, Apr. 2004, pp. 267-277.
	28	D. Obradovic, "Real-time model and convergence time of BGP," in Proc. IEEE INFOCOM, New York, NY, 2002, vol. 2, pp. 893-901.
	29	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]
	30	R. Teixeira, N. Duffield, J. Rexford, and M. Roughan, "Traffic matrix reloaded: Impact of routing changes," in Proc. Passive and Active Measurement Conf. (PAM'05), Boston, MA, Mar. 2005, pp. 251-264.
	31	Olivier Bonaventure , Clarence Filsfils , Pierre Francois, Achieving sub-50 milliseconds recovery upon BGP peering link failures, IEEE/ACM Transactions on Networking (TON), v.15 n.5, p.1123-1135, October 2007 [doi>10.1109/TNET.2007.906045]
	32	N. Kushman, S. Kandula, D. Katabi, and B. Maggs, "R-BGP: Staying connected in a connected world," in Proc. 4th USENIX Symp. Networked Systems Design and Implementation, Cambridge, MA, 2007, pp. 341-354.
	33	F. Wang and L. Gao, "A full route aware routing protocol--Fast recovery from transient routing failures," in Proc. IEEE INFOCOM, Phoenix, AZ, Apr. 2008, pp. 2333-2341.