Coping with network failures: routing strategies for optimal demand oblivious restoration

ABSTRACT

Link and node failures in IP networks pose a challenge for network control algorithms. Routing restoration, which computes new routes that avoid failed links, involves fundamental tradeoffs between efficient use of network resources, complexity of the restoration strategy and disruption to network traffic. In order to achieve a balance between these goals, obtaining routings that provide good performance guarantees under failures is desirable.In this paper, building on previous work that provided performance guarantees under uncertain (and potentially unknown) traffic demands, we develop algorithms for computing optimal restoration paths and a methodology for evaluating the performance guarantees of routing under failures. We then study the performance of route restoration on a diverse collection of ISP networks. Our evaluation uses a competitive analysis type framework, where performance of routing with restoration paths under failures is compared to the best possible performance on the failed network. We conclude that with careful selection of restoration paths one can obtain restoration strategies that retain nearly optimal performance on the failed network while minimizing disruptions to traffic flows that did not traverse the failed parts of the network.

REFERENCES

• 1: R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network flows. Prentice-Hall, Inc., Englewood Cliffs, NJ, 1993.
• 2: J. Anderson, B. T. Doshi, S. Dravida, and P. Harshavardhana. Fast restoration of ATM networks. IEEE journal on selected areas in communications, 12:128--138, 1994.
• 3: D. Applegate and E. Cohen. Making routing robust to changing traffic demands: Algorithms and evaluation. Manuscript.
• 4: David Applegate , Edith Cohen, Making intra-domain routing robust to changing and uncertain traffic demands: understanding fundamental tradeoffs, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863991]
• 5: D. Awduche, A. Chiu, A. Elwalid, I. Widjaja, and X. Xiao. RFC 2702: Requirements for Traffic Engineering over MPLS, September 1999.
• 6: D. Awduche, A. Chiu, A. Elwalid, I. Widjaja, and X. Xiao. RFC 3272: Overview and Principles of Internet Traffic Engineering, May 2002.
• 7: S. Bhattacharya, C. Diot, J. Jetcheva, and N. Taft. Geographical and temporal characteristics of inter-POP flows: view from a single POP. In European transactions on telecommunications, 2002.
• 8: J. Cao, D. Davis, S.V. Wiel, and B.Yu. Time-varying network tomography: router link data. J. Amer. Statist. Assoc., 95:1063--1075, 2000.
• 9: N. G. Duffield , Matthias Grossglauser, Trajectory sampling for direct traffic observation, IEEE/ACM Transactions on Networking (TON), v.9 n.3, p.280-292, June 2001 [doi>10.1109/90.929851]
• 10: Anja Feldmann , Albert Greenberg , Carsten Lund , Nick Reingold , Jennifer Rexford , Fred True, Deriving traffic demands for operational IP networks: methodology and experience, IEEE/ACM Transactions on Networking (TON), v.9 n.3, p.265-280, June 2001 [doi>10.1109/90.929850]
• 11: B. Fortz and M. Thorup. Internet traffic engineering by optimizing OSPF weights. In Proceedings of INFOCOM, pages 519--528. IEEE, 2000.
• 12: B. Fortz and M. Thorup. Optimizing OSPF/IS-IS weights in a changing world. IEEE journal on selected areas in communications, 20(4), 2002.
• 13: B. Grötschel, L. Lovasz, and A. Schrijver. Geometric algorithms and combinatorial optimization. Springer-Verlag, New York, 1988.
• 14: Ratul Mahajan , Neil Spring , David Wetherall , Tom Anderson, Inferring link weights using end-to-end measurements, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637237]
• 15: A. Medina , N. Taft , K. Salamatian , S. Bhattacharyya , C. Diot, Traffic matrix estimation: existing techniques and new directions, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 16: D. Mitra and K. G. Ramakrishna. A case study of multiservice, multipriority traffic engineering design for data networks. In Proceedings of IEEE GLOBECOM, pages 1077--1083. IEEE, 1999.
• 17: J. Moy. RFC 1583: OSPF version 2, 1994.
• 18: Kazutaka Murakami , Hyong S. Kim, Optimal capacity and flow assignment for self-healing ATM networks based on line and end-to-end restoration, IEEE/ACM Transactions on Networking (TON), v.6 n.2, p.207-221, April 1998 [doi>10.1109/90.664269]
• 19: E. C. Rosen, A. Viswanathan, and R. Callon. RFC 3031: Multi Protocol Label Switching architectures, 2001.
• 20: Matthew Roughan , Albert Greenberg , Charles Kalmanek , Michael Rumsewicz , Jennifer Yates , Yin Zhang, Experience in measuring backbone traffic variability: models, metrics, measurements and meaning, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637213]
• 21: Internet Traffic Engineering Working Group, 2003. http://www.ietf.org/html.charters/tewg-charter.html.
• 22: Yijun Xiong , Lorne G. Mason, Restoration strategies and spare capacity requirements in self-healing ATM networks, IEEE/ACM Transactions on Networking (TON), v.7 n.1, p.98-110, Feb. 1999 [doi>10.1109/90.759330]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
      C.2.3 Network Operations

General Terms:
Algorithms, Design, Management, Performance, Reliability

Keywords:
demand-oblivious routing, restoration, routing