Fast local rerouting for handling transient link failures

ABSTRACT

Link failures are part of the day-to-day operation of a network due to many causes such as maintenance, faulty interfaces, and accidental fiber cuts. Commonly deployed link state routing protocols such as OSPF react to link failures through global link state advertisements and routing table recomputations causing significant forwarding discontinuity after a failure. Careful tuning of various parameters to accelerate routing convergence may cause instability when the majority of failures are transient. To enhance failure resiliency without jeopardizing routing stability, we propose a local rerouting based approach called failure insensitive routing. The proposed approach prepares for failures using interface-specific forwarding, and upon a failure, suppresses the link state advertisement and instead triggers local rerouting using a backwarding table. With this approach, when no more than one link failure notification is suppressed, a packet is guaranteed to be forwarded along a loop-free path to its destination if such a path exists. This paper demonstrates the feasibility, reliability, and stability of our approach.

REFERENCES

• 1: Gianluca Iannaccone , Chen-nee Chuah , Richard Mortier , Supratik Bhattacharyya , Christophe Diot, Analysis of link failures in an IP backbone, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637238]
• 2: [2] A. Markopulu, G. Iannaccone, S. Bhattacharya, C.-N. Chuah, and C. Diot, "Characterization of failures in an IP backbone," in Proc. IEEE INFOCOM, 2004, pp. 2307-2317.
• 3: [3] C. Alattinoglu, V. Jacobson, and H. Yu, "Towards milli-second IGP convergence," IETF Internet Draft, Nov. 2000, draft-alaettinoglu-ISIS-convergence-00.txt.
• 4: [4] C. Alattinoglu and S. Casner, "ISIS routing on the qwest backbone: A recipe for subsecond ISIS convergence," presented at the NANOG Meeting, Miami, FL, 2002.
• 5: Anindya Basu , Jon Riecke, Stability issues in OSPF routing, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.225-236, August 2001, San Diego, California, United States
• 6: Renata Teixeira , Aman Shaikh , Tim Griffin , Jennifer Rexford, Dynamics of hot-potato routing in IP networks, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA
• 7: [7] V. Sharma, "Framework for MPLS-based recovery," IETF Internet Draft, Jan. 2002, draft-ietf-mpls-recovery-frmwrk-03.txt.
• 8: [8] S. Nelakuditi, S. Lee, Y. Yu, and Z.-L. Zhang, "Failure insensitive routing for ensuring service availability," in Proc. Int. Workshop Quality Service (IWQoS), 2003, pp. 287-304.
• 9: [9] S. Lee, Y. Yu, S. Nelakuditi, Z.-L. Zhang, and C.-N. Chuah, "Proactive versus reactive approaches to failure resilient routing," in Proc. IEEE INFOCOM, 2004, pp. 176-186.
• 10: [10] "Failure inferencing based fast re-routing," Univ. South Carolina, Columbia, (2006). [Online]. Available: http://arena.cse.sc.edu/fifr.html.
• 11: [11] S. Nelakuditi, S. Lee, Y. Yu, Z.-L. Zhang, and C.-N. Chuah, "Fast local rerouting for handling transient link failures," Univ. South Carolina, Columbia, Tech. Rep. TR-2004-004, Jul. 2004.
• 12: [12] J. Medhi, Stochastic Processes. New York: Wiley, 1982.
• 13: Paolo Narvaez , Kai-Yeung Siu, Routing reconfiguration in ip networks, Massachusetts Institute of Technology, 2000
• 14: [14] B. Fortz and M. Thorup, "Optimizing OSPF/IS-IS weights in a changing world," IEEE J. Sel. Areas Commun., vol. 20, no. 4, pp. 756-767, May 2002.
• 15: [15] A. Nucci, B. Schroeder, S. Bhattacharyya, N. Taft, and C. Diot, "IGP link weight assignment for transient link failures," presented at the ITC 18, Berlin, Germany, 2003.
• 16: [16] G. Iannaccone, C.-N. Chuah, S. Bhattacharyya, and C. Diot, "Feasibility of IP restoration in a tier-1 backbone," IEEE Network, vol. 18, no. 2, pp. 13-19, Mar./Apr. 2004.
• 17: [17] A. Atlas, "U-turn alternates for IP/LDP fast-reroute," IETF Internet Draft, Feb. 2005, draft-atlas-ip-local-protect-uturn-02.txt.
• 18: [18] S. Iyer, S. Bhattacharyya, N. Taft, and C. Diot, "An approach to alleviate link overload as observed on an IP backbone," in Proc. IEEE INFOCOM, 2003, pp. 406-416.
• 19: [19] G. Schollmeier, J. Charzinski, A. Kirstadter, C. Reichert, K. Schrodi, Y. Glickman, and C. Winkler, "Improving the resilience in IP networks," in Proc. HPSR, 2003, pp. 91-96.
• 20: 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

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Store and forward networks

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

General Terms:
Algorithms, Design

Keywords:
fast rerouting, interface-specific forwarding, transient failures