David Applegate
Edith Cohen
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.
- R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network flows. Prentice-Hall, Inc., Englewood Cliffs, NJ, 1993.]]Google Scholar
- 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.]]Google Scholar
- D. Applegate and E. Cohen. Making routing robust to changing traffic demands: Algorithms and evaluation. Manuscript.]]Google Scholar
- D. Applegate and E. Cohen. Making intra-domain routing robust to changing and uncertain traffic demands: understanding fundamental tradeoffs. In Proceedings of the ACM SIGCOMM'03 Conference, 2003.]] Google ScholarDigital Library
- D. Awduche, A. Chiu, A. Elwalid, I. Widjaja, and X. Xiao. RFC 2702: Requirements for Traffic Engineering over MPLS, September 1999.]] Google ScholarDigital Library
- D. Awduche, A. Chiu, A. Elwalid, I. Widjaja, and X. Xiao. RFC 3272: Overview and Principles of Internet Traffic Engineering, May 2002.]] Google ScholarDigital Library
- 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.]]Google Scholar
- 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.]]Google ScholarCross Ref
- N. G. Duffield and M. Grossglauser. Trajectory sampling for direct traffic observation. IEEE/ACM Transactions on Networking, 9:280--292, 2001.]] Google ScholarDigital Library
- A. Feldmann, A. Greenberg, C. Lund, N. Reingold, J. Rexford, and F. True. Deriving traffic demands for operational IP networks: methodology and experience. IEEE/ACM Transactions on Networking, 9:265--279, 2001.]] Google ScholarDigital Library
- B. Fortz and M. Thorup. Internet traffic engineering by optimizing OSPF weights. In Proceedings of INFOCOM, pages 519--528. IEEE, 2000.]]Google ScholarCross Ref
- B. Fortz and M. Thorup. Optimizing OSPF/IS-IS weights in a changing world. IEEE journal on selected areas in communications, 20(4), 2002.]] Google ScholarDigital Library
- B. Grötschel, L. Lovasz, and A. Schrijver. Geometric algorithms and combinatorial optimization. Springer-Verlag, New York, 1988.]]Google ScholarCross Ref
- R. Mahajan, N. Spring, D. Wetherall, and T. Anderson. Inferring link weights using end-to-end measurements. In Proceedings of the 2nd Internet Measurement Workshop. ACM, 2002.]] Google ScholarDigital Library
- A. Medina, N. Taft, K. Salamatian, S. Bhattacharyya, and C. Diot. Traffic matrix estimation: Existing techniques and new directions. In Proceedings of the ACM SIGCOMM'02 Conference. ACM, 2002.]] Google ScholarDigital Library
- 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.]]Google ScholarCross Ref
- J. Moy. RFC 1583: OSPF version 2, 1994.]]Google Scholar
- K. Murukami and H. Kim. Optimal capacity and flow assignment for self-healing ATM networks bsed on line and end-to-end restoration. IEEE/ACM Transactions on Networking, 6(2):207--221, 1998.]] Google ScholarDigital Library
- E. C. Rosen, A. Viswanathan, and R. Callon. RFC 3031: Multi Protocol Label Switching architectures, 2001.]] Google ScholarDigital Library
- M. Roughan, A. Greenberg, C. Kalmanek, M. Rumsewicz, J. Yates, and Y. Zhang. Experience in measuring backbone traffic variability: models, metrics, measurements, and meaning. In Proceedings of the 2nd Internet Measurement Workshop. ACM, 2002.]] Google ScholarDigital Library
- Internet Traffic Engineering Working Group, 2003. http://www.ietf.org/html.charters/tewg-charter.html.]]Google Scholar
- Y. Xiong and L. G. Mason. Restoration strategies and spare capacity requirements in self healing ATM networks. IEEE/ACM Transactions on Networking, 7(1):98--110, 1999.]] Google ScholarDigital Library
Index Terms
- Coping with network failures: routing strategies for optimal demand oblivious restoration
Recommendations
Making intra-domain routing robust to changing and uncertain traffic demands: understanding fundamental tradeoffs
SIGCOMM '03: Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communicationsIntra-domain traffic engineering can significantly enhance the performance of large IP backbone networks. Two important components of traffic engineering are understanding the traffic demandsand configuring the routing protocols. These two components ...
Coping with network failures: routing strategies for optimal demand oblivious restoration
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 ...
Routing restorable bandwidth guaranteed connections using maximum 2-route flows
Routing with service restorability is of much importance in Multi-Protocol Label Switched (MPLS) networks, and is a necessity in optical networks. For restoration, each connection has an active path and a link-disjoint backup path. The backup path ...
Comments