Multiple routing configurations for fast IP network recovery

ABSTRACT

As the Internet takes an increasingly central role in our communications infrastructure, the slow convergence of routing protocols after a network failure becomes a growing problem. To assure fast recovery from link and node failures in IP networks, we present a new recovery scheme called Multiple Routing Configurations (MRC). Our proposed scheme guarantees recovery in all single failure scenarios, using a single mechanism to handle both link and node failures, and without knowing the root cause of the failure. MRC is strictly connectionless, and assumes only destination based hop-by-hop forwarding. MRC is based on keeping additional routing information in the routers, and allows packet forwarding to continue on an alternative output link immediately after the detection of a failure. It can be implemented with only minor changes to existing solutions. In this paper we present MRC, and analyze its performance with respect to scalability, backup path lengths, and load distribution after a failure. We also show how an estimate of the traffic demands in the network can be used to improve the distribution of the recovered traffic, and thus reduce the chances of congestion when MRC is used.

REFERENCES

• 1: D. Clark, The design philosophy of the DARPA internet protocols, ACM SIGCOMM Computer Communication Review, v.18 n.4, p.106-114, August 1988
• 2: 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
• 3: 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]
• 4: Catherine Boutremans , Gianluca Iannaccone , Christophe Diot, Impact of link failures on VoIP performance, Proceedings of the 12th international workshop on Network and operating systems support for digital audio and video, May 12-14, 2002, Miami, Florida, USA [doi>10.1145/507670.507680]
• 5: David Watson , Farnam Jahanian , Craig Labovitz, Experiences With Monitoring OSPF on a Regional Service Provider Network, Proceedings of the 23rd International Conference on Distributed Computing Systems, p.204, May 19-22, 2003
• 6: 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]
• 7: A. Markopoulou, G. Iannaccone, S. Bhattacharyya, C.-N. Chuah, and C. Diot, "Characterization of failures in an IP backbone network," in Proc. IEEE INFOCOM, Mar. 2004, vol. 4, pp. 2307-2317.
• 8: Srihari Nelakuditi , Sanghwan Lee , Yinzhe Yu , Zhi-Li Zhang , Chen-Nee Chuah, Fast local rerouting for handling transient link failures, IEEE/ACM Transactions on Networking (TON), v.15 n.2, p.359-372, April 2007 [doi>10.1109/TNET.2007.892851]
• 9: 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, Mar. 2003, pp. 406-416.
• 10: S. Rai, B. Mukherjee, and O. Deshpande, "IP resilience within an autonomous system: Current approaches, challenges, and future directions," IEEE Commun. Mag., vol. 43, no. 10, pp. 142-149, Oct. 2005.
• 11: S. Bryant, M. Shand, and S. Previdi, "IP fast reroute using not-via addresses," Internet Draft (work in progress), draft-ietf-rtgwg-ipfrrnotvia-addresses-01, Jun. 2007.
• 12: P. Francois, M. Shand, and O. Bonaventure, "Disruption free topology reconfiguration in OSPF networks," in Proc. IEEE INFOCOM, Anchorage, AK, May 2007, pp. 89-97.
• 13: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 14: P. Psenak, S. Mirtorabi, A. Roy, L. Nguen, and P. Pillay-Esnault, "MTOSPF: Multi Topology (MT) routing in OSPF," IETF Internet Draft (work in progress), draft-ietf-ospf-mt-07.txt, Nov. 2006.
• 15: T. Przygienda, N. Shen, and N. Sheth, "M-ISIS: Multi Topology (MT) routing in IS-IS," Internet Draft (work in progress), draft-ietf-isis-wg-multi-topology-11.txt, Oct. 2005.
• 16: M. Menth and R. Martin, "Network resilience through multitopology routing," in Proc. 5th Int. Workshop on Design of Reliable Communication Networks (DRCN), Oct. 2005, pp. 271-277.
• 17: Alberto Medina , Anukool Lakhina , Ibrahim Matta , John Byers, BRITE: An Approach to Universal Topology Generation, Proceedings of the Ninth International Symposium in Modeling, Analysis and Simulation of Computer and Telecommunication Systems, p.346, August 15-18, 2001
• 18: B. M. Waxman, "Routing of multipoint connections," IEEE J. Sel. Areas Commun., vol. 6, no. 9, pp. 1617-1622, Dec. 1988.
• 19: T. Bu and D. Towsley, "On distinguishing between internet power law topology generators," in Proc. IEEE INFOCOM, New York, Jun. 2002, pp. 638-647.
• 20: Rocketfuel Topology Mapping. [Online]. Available: http://www.cs. washington.edu
• 21: A. Atlas and A. Zinin, "Basic specification for IP fast-reroute: loop-free alternates," IETF Internet Draft (work in progress), draft-ietf-rtgwg-ipfrr-spec-base-06, Mar. 2007.
• 22: M. J. O'Mahony, "Results from the COST 239 project. Ultra-high capacity optical transmission networks," in Proc. 22nd European Conf. Optical Communication (ECOC'96), Sep. 1996, pp. 11-14.
• 23: B. Fortz and M. Thorup, "Internet traffic engineering by optimizing OSPF weights," in Proc. IEEE INFOCOM, 2000, pp. 519-528.
• 24: David S. Johnson, Approximation algorithms for combinatorial problems, Proceedings of the fifth annual ACM symposium on Theory of computing, p.38-49, April 30-May 02, 1973, Austin, Texas, United States [doi>10.1145/800125.804034]
• 25: A. Kvalbein, T. Čičic, and S. Gjessing, "Post-failure routing performance with multiple routing configurations," in Proc. IEEE INFOCOM, May 2007, pp. 98-106.
• 26: P. Pan, G. Swallow, and A. Atlas, "Fast reroute extensions to RSVPTE for LSP tunnels," RFC 4090, May 2005.
• 27: Alex Raj , Oliver C. Ibe, A survey of IP and multiprotocol label switching fast reroute schemes, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.51 n.8, p.1882-1907, June, 2007 [doi>10.1016/j.comnet.2006.09.010]
• 28: P. Narvaez, K.-Y. Siu, and H.-Y. Tzeng, "Local restoration algorithms for link-state routing protocols," in Proc. IEEE Int. Conf. Computer Communications and Networks (ICCCN'99), Oct. 1999, pp. 352-357.
• 29: Z. Zhong, S. Nelakuditi, Y. Yu, S. Lee, J. Wang, and C.-N. Chuah, "Failure inferencing based fast rerouting for handling transient link and node failures," in Proc. IEEE INFOCOM, Mar. 2005, vol. 4, pp. 2859-2863.
• 30: M. Shand and S. Bryant, "IP fast reroute framework," IETF Internet Draft (work in progress), draft-ietf-rtgwg-ipfrr-framework-07, Jun. 2007.
• 31: R. Rabbat and K.-Y. Siu, "Restoration methods for traffic engineered networks for loop-free routing guarantees," in Proc. IEEE Int. Conf. Communications (ICC'01), Helsinki, Finland, Jun. 2001, vol. 5, pp. 1566-1570.
• 32: Ingebjorg Theiss , Olav Lysne, FRoots: A Fault Tolerant and Topology-Flexible Routing Technique, IEEE Transactions on Parallel and Distributed Systems, v.17 n.10, p.1136-1150, October 2006 [doi>10.1109/TPDS.2006.140]
• 33: Audun Fosselie Hansen , Amund Kvalbein, Resilient Routing Layers for Recovery in Packet Networks, Proceedings of the 2005 International Conference on Dependable Systems and Networks, p.238-247, June 28-July 01, 2005 [doi>10.1109/DSN.2005.81]
• 34: Amund Kvalbein , Audun Fosselie Hansen, Fast Recovery from Link Failures Using Resilient Routing Layers, Proceedings of the 10th IEEE Symposium on Computers and Communications, p.554-560, June 27-30, 2005 [doi>10.1109/ISCC.2005.70]
• 35: Y. Wang, Z. Wang, and L. Zhang, "Internet traffic engineering without full mesh overlaying," in Proc. IEEE INFOCOM, Apr. 2001, pp. 565-571.
• 36: Ashwin Sridharan , Roch Guérin , Christophe Diot, Achieving near-optimal traffic engineering solutions for current OSPF/IS-IS networks, IEEE/ACM Transactions on Networking (TON), v.13 n.2, p.234-247, April 2005 [doi>10.1109/TNET.2005.845549]
• 37: A. Nucci, B. Schroeder, S. Bhattacharyya, N. Taft, and C. Diot, "IGP link weight assignment for transient link failures," in Proc. 18th Int. Teletraffic Congress, Berlin, Germany, Aug. 2003.
• 38: B. Fortz and M. Thorup, "Robust optimization of OSPF/IS-IS weights," in Proc. INOC, Oct. 2003, pp. 225-230.
• 39: A. Sridharan and R. Guerin, "Making IGP routing robust to link failures," in Proc. Networking, Waterloo, Canada, 2005.

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.2 Network Protocols

          Nouns: IP
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Reliability, availability, and serviceability; Performance attributes

General Terms:
Algorithms, Design, Performance, Reliability

Keywords:
availability, communication system fault tolerance, communication system routing, computer network reliability, protection