Network Working Group M. Menth Internet-Draft M. Hartmann Intended status: Experimental D. Hock Expires: January 6, 2011 University of Wuerzburg July 5, 2010 Routing Optimization with IP Fast Reroute draft-menth-ipfrr-routing-optimization-00 Abstract This draft gives a summary of findings about routing optimization of not-via addresses [I-D.ietf-rtgwg-ipfrr-notvia-addresses] and LFAs [RFC5286] in IP networks. The optimization is done only by tuning IP link costs. Optimization goals for both IP FRR techniques is the maximum link utilization in the failure-free scenario and for a set of failure scenarios such as all single link (and node) failures as well as the failure coverage by LFAs. For LFAs, the failure coverage is another optimization goal. Status of this Memo This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet- Drafts is at http://datatracker.ietf.org/drafts/current/. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." This Internet-Draft will expire on January 6, 2011. Copyright Notice Copyright (c) 2010 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect Menth, et al. Expires January 6, 2011 [Page 1] Internet-Draft Routing Optimization with IP Fast Reroute July 2010 to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Table of Contents 1. Unique Shortest Paths for IP Networks with Not-Via Addresses . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Routing Optimization of Loop-Free Alternates (LFAs): Minimizing Maximum Link Utilization and Maximizing Failure Coverage . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 3. IANA Considerations . . . . . . . . . . . . . . . . . . . . . . 4 4. Security Considerations . . . . . . . . . . . . . . . . . . . . 4 5. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 4 6. References . . . . . . . . . . . . . . . . . . . . . . . . . . 5 6.1. Normative References . . . . . . . . . . . . . . . . . . . 5 6.2. Informative References . . . . . . . . . . . . . . . . . . 5 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 5 Menth, et al. Expires January 6, 2011 [Page 2] Internet-Draft Routing Optimization with IP Fast Reroute July 2010 1. Unique Shortest Paths for IP Networks with Not-Via Addresses Routes in IP networks are determined by administrative IP link costs, i.e., traffic is forwarded on the least-cost paths from source to destination. When the equal-cost paths option is enabled, traffic is equally distributed over all interfaces leading to a least-cost path towards the destination. If the equal-cost path option is not enabled, only a single interface towards a least-cost path is chosen to forward traffic to a specific destination even though multiple least-cost paths may exist. However, it is not clear which interface is chosen in that case. As a consequence, traffic loads and link utilization are difficult to predict in such networks. As paths cannot be predicted, routing optimization is difficult. We studied this problem in [HoHa10]. We optimized routing in example networks for the failure-free scenario and for a set of failure scenarios, i.e., we chose link costs that minimize the maximum link utilization. We assumed some tie-breaker function to choose next- hops in case of equal-cost paths and showed how much more traffic than expected can occur on some links when routers choose different next-hops than predicted. We proposed to fix this problem by choosing link costs such that equal-cost paths are avoided for the failure-free case and for the set of considered failure scenarios. We call this type of paths "unique shortest paths (USPs)". It is possible to find USPs and to minimize the maximum link utilization without any performance loss compared to unconstraint routing optimization. In IP networks, equal-cost paths is another option to avoid the presented problem. However, with not-via addresses [I-D.ietf-rtgwg-ipfrr-notvia-addresses], traffic is forwarded around non-reachable nodes only on a single interface as the traffic tunnelled by the point of local repair to the next-next-hop has the same source and destination so that it cannot be distributed equally over multiple equal-cost tunnels. Hence, the load on not-via paths in failure cases cannot be predicted in spite of ECMP when multiple equal-cost paths exist. USP is a solution to make traffic distribution in not-via networks predictable and allows to optimize routing. 2. Routing Optimization of Loop-Free Alternates (LFAs): Minimizing Maximum Link Utilization and Maximizing Failure Coverage We used link cost optimization to maximize the coverage of LFAs [RFC5286] in several example networks. We defined three different requirements. Destinations need to be protected at least by Menth, et al. Expires January 6, 2011 [Page 3] Internet-Draft Routing Optimization with IP Fast Reroute July 2010 a. link-protecting LFAs b. node-protecting LFAs (do not cause loops in case of node failures) c. downstream LFAs (do not cause loops in case of multiple failures) ad a) In most networks, 100% of all destinations could be protected after optimization. In some networks with a special structure, only a slightly lower coverage could be achieved. ad b) Even after optimization, less than 100% coverage could be achieved in any network. ad c) After optimization, it was not possible to achieve 100% coverage. This is obvious since the closest node to a specific destination does not have a downstream LFA for that destination. When only the coverage is optimized, the maximum link utilization in failure cases can become extremely high. Optimizing the coverage as primary goal and the link utilization as secondary goal does not lead to low link utilizations. However, changing the order of the optimization goals leads to low utilization and relatively high coverage. When optimizing for coverage and link utilization, the maximum link utilization in failure cases is quite high if only the maximum link utilization in the failure-free scenario is optimized. Optimizing the maximum link utilization for a set of failure scenarios and optimizing the coverage leads to low maximum link utilization and to high failure coverage. 3. IANA Considerations This document makes no request to IANA. 4. Security Considerations This document makes no security considerations. 5. Acknowledgements The authors thank Christian Schwartz, Tim Neubert, and Michael Menth, et al. Expires January 6, 2011 [Page 4] Internet-Draft Routing Optimization with IP Fast Reroute July 2010 Hoefling for their contributions and efforts. 6. References 6.1. Normative References [RFC5286] Atlas, A. and A. Zinin, "Basic Specification for IP Fast Reroute: Loop-Free Alternates", RFC 5286, September 2008. 6.2. Informative References [HoHa10] Hock, D., Hartmann, M., Menth, M., and C. Schwartz, "Optimizing Unique Shortest Paths for Resilient Routing and Fast Reroute in IP-Based Networks", in Proceedings of the 12th IEEE/IFIP Network Operations and Management Symposium (NOMS), Osaka, Japan, preprint available at: http://www.menth.net/Publications/papers/Menth10g.pdf, April 2010. [I-D.ietf-rtgwg-ipfrr-notvia-addresses] Shand, M., Bryant, S., and S. Previdi, "IP Fast Reroute Using Not-via Addresses", draft-ietf-rtgwg-ipfrr-notvia-addresses-05 (work in progress), March 2010. Authors' Addresses Michael Menth University of Wuerzburg room B206, Institute of Computer Science Am Hubland Wuerzburg 97074 Germany Phone: +49 931 31 86644 Email: menth@informatik.uni-wuerzburg.de Menth, et al. Expires January 6, 2011 [Page 5] Internet-Draft Routing Optimization with IP Fast Reroute July 2010 Matthias Hartmann University of Wuerzburg room A208, Institute of Computer Science Am Hubland Wuerzburg 97074 Germany Phone: +49 931 31 83381 Email: hartmann@informatik.uni-wuerzburg.de David Hock University of Wuerzburg room A208, Institute of Computer Science Am Hubland Wuerzburg 97074 Germany Phone: +49 931 31 88523 Email: david.hock@informatik.uni-wuerzburg.de Menth, et al. Expires January 6, 2011 [Page 6]