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]