skip to main content
article

Achieving sub-50 milliseconds recovery upon BGP peering link failures

Published: 01 October 2007 Publication History

Abstract

Recent measurements show that BGP peering links can fail as frequently as intradomain links and usually for short periods of time. We propose a new fast-reroute technique where routers are prepared to react quickly to interdomain link failures. For each of its interdomain links, a router precomputes a protection tunnel, i.e., an IP tunnel to an alternate nexthop which can reach the same destinations as via the protected link.We propose a BGP-based auto-discovery technique that allows each router to learn the candidate protection tunnels for its links. Each router selects the best protection tunnels for its links and when it detects an interdomain link failure, it immediately encapsulates the packets to send them through the protection tunnel. Our solution is applicable for the links between large transit ISPs and also for the links between multi-homed stub networks and their providers. Furthermore, we show that transient forwarding loops (and thus the corresponding packet losses) can be avoided during the routing convergence that follows the deactivation of a protection tunnel in BGP/MPLS VPNs and in IP networks using encapsulation.

References

[1]
{1} O. Bonaventure, C. Filsfils, and P. Francois, "Achieving sub-50 milliseconds recovery upon BGP peering link failures," presented at the CoNEXT 2005, Toulouse, France, Oct. 2005.
[2]
{2} E. Rosen and Y. Rekhter, "BGP/MPLS VPNs," RFC 2547, Mar. 1999.
[3]
{3} S. Bryant and P. Pate, "Pseudo Wire Emulation Edge-to-Edge (PWE3) Architecture," RFC 3985, Mar. 2005.
[4]
{4} J.-P. Vasseur, M. Pickavet, and P. Demeester, Network Recovery: Protection and Restoration of Optical, SONET-SDH, and MPLS. San Mateo, CA: Morgan Kaufmann, 2004.
[5]
{5} C. Filsfils and J. Evans, "Deploying diffserv in IP/MPLS backbone networks for tight SLA control," IEEE Internet Comput., vol. 9, no. 1, pp. 58-65, Jan.-Feb. 2005.
[6]
{6} A. Markopoulou, G. Iannaccone, S. Bhattacharyya, C. Chuah, and C. Diot, "Characterization of failures in an IP backbone," presented at the IEEE INFOCOM 2004, Hong Kong, Mar. 2004.
[7]
{7} D. Watson, F. Jahanian, and C. Labovitz, "Experiences with monitoring OSPF on a regional service provider network," in Proc. 23rd Int. Conf. Distributed Computing Systems, 2003, p. 204.
[8]
{8} N. Feamster, D. Andersen, H. Balakrishnan, and M. Kaashoek, "Measuring the effects of Internet path faults on reactive routing," presented at the ACM SIGMETRICS, San Diego, CA, Jun. 2003.
[9]
{9} K. Gummardi, H. Madhyastha, S. Gribble, H. Leby, and D. Wetherall, "Improving the reliability of internet paths with one-hop source routing," presented at the USENIX OSDI'04, San Francisco, CA, Dec. 2004.
[10]
{10} A. Feldmann, O. Maennel, M. Mao, A. Berger, and B. Maggs, "Locating internet routing instabilities," presented at the ACMSIGCOMM 2004, Portland, OR, Aug. 2004.
[11]
{11} P. Francois, C. Filsfils, J. Evans, and O. Bonaventure, "Achieving sub-second IGP convergence in large IP networks," ACM SIGCOMM Comput. Commun. Rev., vol. 35, no. 3, pp. 35-44, 2005.
[12]
{12} M. Shand and S. Bryant, "IP Fast Reroute Framework," Internet Draft, draft-ietf-rtgwg-ipfrr-framework-07.txt, work in progress, Jun. 2007.
[13]
{13} D. Pei, M. Azuma, N. Nguyen, J. Chen, D. Massey, and L. Zhang, "BGP-RCN: Improving BGP convergence through root cause notification," Comput. Networks, vol. 48, no. 2, pp. 175-194, Jun. 2005, 2005.
[14]
{14} T. Griffin and B. Presmore, "An experimental analysis of BGP convergence time," in Proc. ICNP 2001, Nov. 2001, pp. 53-61.
[15]
{15} D. Katz and D. Ward, "Bidirectional Forwarding Detection," Internet Draft, draft-ietf-bfd-base-07.txt, work in progress, Mar. 2007.
[16]
{16} C. Filsfils, "IGP and BGP fast convergence," presented at the Net-workers' 2004, Cannes, France, Dec. 2004.
[17]
{17} G. Iannaccone, C.-N. Chuah, R. Mortier, S. Bhattacharyya, and C. Diot, "Analysis of link failures over an IP backbone," presented at the ACM SIGCOMM Internet Measurement Workshop, Marseilles, France, Nov. 2002.
[18]
{18} F. Wang, L. Gao, J. Wang, and J. Qiu, "On understanding of transient interdomain routing failures," presented at the ICNP 2005, Boston, MA, Nov. 2005.
[19]
{19} D. Pei and J. V. der Merwe, "BGP convergence in virtual private networks," presented at the Internet Measurement Conf., Rio de Janeiro, Brazil, Oct. 2006.
[20]
{20} F. Wang, Z. Mao, J. Wang, L. Gao, and R. Bush, "A measurement study on the impact of routing events on end-to-end Internet path performance," in Proc. ACM SIGCOMM, Pisa, Italy, Sep. 2006, pp. 375-387.
[21]
{21} R. White, D. McPherson, and S. Sangli, Practical BGP. Reading, MA: Addison Wesley, 2004.
[22]
{22} N. Feamster, Z. Mao, and J. Rexford, "BorderGuard: Detecting cold potatoes from peers," presented at the ACM Internet Measurement Conf., Taormina, Italy, Oct. 2004.
[23]
{23} L. Gao and J. Rexford, "Stable internet routing without global coordination," presented at the ACM SIGMETRICS 2000, Santa Clara, CA, Jun. 2000.
[24]
{24} Cisco, Prefix and Tunnel Independent FRR Nov. 2004 {Online}. Available: http://www.cisco.com/en/US/products/ps5763/prod_re- lease_note09186a008033575a.html#wp98916.
[25]
{25} J. Lau, M. Townsley, and I. Goyret, "Layer Two Tunneling Protocol--Version 3 (L2TPv3)," Internet Draft, draft-ietf-l2tpext-l2tp- base-15.txt, work in progress, Dec. 2004.
[26]
{26} T. Worster, Y. Rekhter, and E. Rosen, "Encapsulating MPLS in IP or Generic Routing Encapsulation (GRE)," RFC 4023, Mar. 2005.
[27]
{27} Y. Rekhter, "Constructing intra-AS path segments for an inter-AS path," ACM SIGCOMM Comput. Commun. Rev., vol. 21, no. 1, pp. 44-57, 1991.
[28]
{28} S. Gross, "Modern L2 VPNs: Implementing network convergence," presented at the NANOG33, Las Vegas, NV, 2005.
[29]
{29} B. Greene and P. Smith, Cisco ISP Essentials. Indianapolis, IN: Cisco Press, 2002.
[30]
{30} S. Sangli, D. Tappan, and Y. Rekhter, "BGP Extended Communities Attribute," RFC 4320, Feb. 2006.
[31]
{31} J. C. Honig, D. Katz, M. Mathis, Y. Rekhter, and J. Y. Yu, "Application of the Border Gateway Protocol in the Internet," RFC 1164, Jun. 1990.
[32]
{32} Y. Rekhter and P. Gross, "Application of the Border Gateway Protocol in the Internet," RFC 1655, Jul. 1994.
[33]
{33} P. Francois and O. Bonaventure, "Avoiding transient loops during IGP convergence in IP networks," presented at the IEEE INFOCOM 2005, Miami, FL, Mar. 2005.
[34]
{34} J. Rexford, J. Wang, Z. Xiao, and Y. Zhang, "BGP routing stability of popular destinations," presented at the Internet Measurement Workshop, Marseille, France, Nov. 2002.
[35]
{35} S. Uhlig, V. Magnin, O. Bonaventure, C. Rapier, and L. Deri, "Implications of the topological properties of internet traffic on traffic engineering," presented at the ACM Symp. Applied Computing, Nicosia, Cyprus, Mar. 2004.
[36]
{36} B. Davie and Y. Rekhter, MPLS: Technology and Applications. San Mateo, CA: Morgan Kaufmann, 2000.
[37]
{37} U. Hengartner, S. Moon, R. Mortier, and C. Diot, "Detection and analysis of routing loops in packet traces," in Proc. 2nd ACM SIGCOMM Workshop on Internet Measurment, 2002, pp. 107-112.
[38]
{38} S. D. Cnodder and C. Pelsser, "Protection for Inter-AS MPLS Tunnels," draft-decnodder-ccamp-interas-protection-00.txt, work in progress, Jul. 2004, .
[39]
{39} C. Reichert, "IP-protection for fast inter-domain resilience," presented at the IDRWS'04, Amsterdam, The Netherlands, May 2004.
[40]
{40} G. Schollmeier, J. Charzinski, A. Kirstodter, C. Reichert, K. Schrodi, Y. Glickman, and C. Winkler, "Improving the resilience in IP networks," in Proc. IEEE HPSR 2003, Torino, Italy, Jun. 2003, pp. 91-96.
[41]
{41} R. Bless, G. Lichtwald, M. Schmidt, and M. Zitterbart, "Fast scoped rerouting for BGP," in Proc. IEEE Int. Conf. Networks, Sep. 2003, pp. 25-30.
[42]
{42} J. Chandrashekar, Z. Duan, Z. Zhang, and J. Krasky, "Limiting path exploration in BGP," presented at the IEEE INFOCOM 2005, Miami, FL, Mar. 2005.

Cited By

View all
  • (2021)What You Need to Know About (Smart) Network Interface CardsPassive and Active Measurement10.1007/978-3-030-72582-2_19(319-336)Online publication date: 29-Mar-2021
  • (2019)PURR: a primitive for reconfigurable fast rerouteProceedings of the 15th International Conference on Emerging Networking Experiments And Technologies10.1145/3359989.3365410(1-14)Online publication date: 3-Dec-2019
  • (2011)On reducing the impact of interdomain route changesProceedings of the 12th international conference on Passive and active measurement10.5555/1987510.1987526(153-162)Online publication date: 20-Mar-2011
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking
IEEE/ACM Transactions on Networking  Volume 15, Issue 5
October 2007
235 pages

Publisher

IEEE Press

Publication History

Published: 01 October 2007
Published in TON Volume 15, Issue 5

Author Tags

  1. BGP
  2. computer network reliability
  3. fast recovery
  4. routing

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)4
  • Downloads (Last 6 weeks)0
Reflects downloads up to 19 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2021)What You Need to Know About (Smart) Network Interface CardsPassive and Active Measurement10.1007/978-3-030-72582-2_19(319-336)Online publication date: 29-Mar-2021
  • (2019)PURR: a primitive for reconfigurable fast rerouteProceedings of the 15th International Conference on Emerging Networking Experiments And Technologies10.1145/3359989.3365410(1-14)Online publication date: 3-Dec-2019
  • (2011)On reducing the impact of interdomain route changesProceedings of the 12th international conference on Passive and active measurement10.5555/1987510.1987526(153-162)Online publication date: 20-Mar-2011
  • (2011)Local restoration with multiple spanning trees in metro ethernet networksIEEE/ACM Transactions on Networking10.1109/TNET.2010.207994519:2(602-614)Online publication date: 1-Apr-2011
  • (2010)Providing scalable NH-diverse iBGP route re-distribution to achieve sub-second switch-over timeComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2010.04.00754:14(2492-2505)Online publication date: 1-Oct-2010
  • (2010)IP fast reroute in networks with shared risk linksProceedings of the 9th IFIP TC 6 international conference on Networking10.1007/978-3-642-12963-6_17(213-226)Online publication date: 11-May-2010
  • (2009)Fast network failure recovery using multiple BGP routing planesProceedings of the 28th IEEE conference on Global telecommunications10.5555/1811982.1812020(3841-3846)Online publication date: 30-Nov-2009
  • (2009)Scalable support of interdomain routes in a single ASProceedings of the 28th IEEE conference on Global telecommunications10.5555/1811681.1811843(2785-2792)Online publication date: 30-Nov-2009
  • (2009)OSPF-based fast reroute for BGP link failuresProceedings of the 28th IEEE conference on Global telecommunications10.5555/1811380.1811578(1199-1205)Online publication date: 30-Nov-2009
  • (2009)Load balancing inbound traffic in multihomed stub autonomous systemsProceedings of the First international conference on COMmunication Systems And NETworks10.5555/1702135.1702200(522-531)Online publication date: 5-Jan-2009
  • Show More Cited By

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media