draft-ietf-rtgwg-remote-lfa-11.txt   rfc7490.txt 
Network Working Group S. Bryant Internet Engineering Task Force (IETF) S. Bryant
Internet-Draft C. Filsfils Request for Comments: 7490 C. Filsfils
Intended status: Standards Track S. Previdi Category: Standards Track S. Previdi
Expires: August 3, 2015 Cisco Systems ISSN: 2070-1721 Cisco Systems
M. Shand M. Shand
Independent Contributor Independent Contributor
N. So N. So
Vinci Systems Vinci Systems
January 30, 2015 April 2015
Remote Loop-Free Alternate (LFA) Fast Re-Route (FRR) Remote Loop-Free Alternate (LFA) Fast Reroute (FRR)
draft-ietf-rtgwg-remote-lfa-11
Abstract Abstract
This document describes an extension to the basic IP fast re-route This document describes an extension to the basic IP fast reroute
mechanism described in RFC5286, that provides additional backup mechanism, described in RFC 5286, that provides additional backup
connectivity for point to point link failures when none can be connectivity for point-to-point link failures when none can be
provided by the basic mechanisms. provided by the basic mechanisms.
Requirements Language
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC2119 [RFC2119].
Status of This Memo Status of This Memo
This Internet-Draft is submitted in full conformance with the This is an Internet Standards Track document.
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 This document is a product of the Internet Engineering Task Force
and may be updated, replaced, or obsoleted by other documents at any (IETF). It represents the consensus of the IETF community. It has
time. It is inappropriate to use Internet-Drafts as reference received public review and has been approved for publication by the
material or to cite them other than as "work in progress." Internet Engineering Steering Group (IESG). Further information on
Internet Standards is available in Section 2 of RFC 5741.
This Internet-Draft will expire on August 3, 2015. Information about the current status of this document, any errata,
and how to provide feedback on it may be obtained at
http://www.rfc-editor.org/info/rfc7490.
Copyright Notice Copyright Notice
Copyright (c) 2015 IETF Trust and the persons identified as the Copyright (c) 2015 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of (http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License. described in the Simplified BSD License.
Table of Contents Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.1. Requirements Language . . . . . . . . . . . . . . . . . . 4
3. Overview of Solution . . . . . . . . . . . . . . . . . . . . 4 3. Overview of Solution . . . . . . . . . . . . . . . . . . . . 4
4. Repair Paths . . . . . . . . . . . . . . . . . . . . . . . . 6 4. Repair Paths . . . . . . . . . . . . . . . . . . . . . . . . 6
4.1. Tunnels as Repair Paths . . . . . . . . . . . . . . . . . 6 4.1. Tunnels as Repair Paths . . . . . . . . . . . . . . . . . 6
4.2. Tunnel Requirements . . . . . . . . . . . . . . . . . . . 7 4.2. Tunnel Requirements . . . . . . . . . . . . . . . . . . . 7
5. Construction of Repair Paths . . . . . . . . . . . . . . . . 8 5. Construction of Repair Paths . . . . . . . . . . . . . . . . 8
5.1. Identifying Required Tunneled Repair Paths . . . . . . . 8 5.1. Identifying Required Tunneled Repair Paths . . . . . . . 8
5.2. Determining Tunnel End Points . . . . . . . . . . . . . . 8 5.2. Determining Tunnel Endpoints . . . . . . . . . . . . . . 8
5.2.1. Computing Repair Paths . . . . . . . . . . . . . . . 9 5.2.1. Computing Repair Paths . . . . . . . . . . . . . . . 9
5.2.2. Selecting Repair Paths . . . . . . . . . . . . . . . 11 5.2.2. Selecting Repair Paths . . . . . . . . . . . . . . . 11
5.3. A Cost Based RLFA Algorithm . . . . . . . . . . . . . . . 12 5.3. A Cost-Based RLFA Algorithm . . . . . . . . . . . . . . . 12
5.4. Interactions with IS-IS Overload, RFC6987, and Costed 5.4. Interactions with IS-IS Overload, RFC 6987, and Costed
Out Links . . . . . . . . . . . . . . . . . . . . . . . . 17 Out Links . . . . . . . . . . . . . . . . . . . . . . . . 17
6. Example Application of Remote LFAs . . . . . . . . . . . . . 18 6. Example Application of Remote LFAs . . . . . . . . . . . . . 17
7. Node Failures . . . . . . . . . . . . . . . . . . . . . . . . 18 7. Node Failures . . . . . . . . . . . . . . . . . . . . . . . . 18
8. Operation in an LDP environment . . . . . . . . . . . . . . . 20 8. Operation in an LDP Environment . . . . . . . . . . . . . . . 19
9. Analysis of Real World Topologies . . . . . . . . . . . . . . 21 9. Analysis of Real World Topologies . . . . . . . . . . . . . . 21
9.1. Topology Details . . . . . . . . . . . . . . . . . . . . 21 9.1. Topology Details . . . . . . . . . . . . . . . . . . . . 21
9.2. LFA only . . . . . . . . . . . . . . . . . . . . . . . . 22 9.2. LFA Only . . . . . . . . . . . . . . . . . . . . . . . . 22
9.3. RLFA . . . . . . . . . . . . . . . . . . . . . . . . . . 23 9.3. RLFA . . . . . . . . . . . . . . . . . . . . . . . . . . 22
9.4. Comparison of LFA an RLFA results . . . . . . . . . . . . 24 9.4. Comparison of LFA and RLFA results . . . . . . . . . . . 24
10. Management and Operational Considerations . . . . . . . . . . 25 10. Management and Operational Considerations . . . . . . . . . . 25
11. Historical Note . . . . . . . . . . . . . . . . . . . . . . . 26 11. Historical Note . . . . . . . . . . . . . . . . . . . . . . . 25
12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 26 12. Security Considerations . . . . . . . . . . . . . . . . . . . 25
13. Security Considerations . . . . . . . . . . . . . . . . . . . 26 13. References . . . . . . . . . . . . . . . . . . . . . . . . . 26
14. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 27 13.1. Normative References . . . . . . . . . . . . . . . . . . 26
15. References . . . . . . . . . . . . . . . . . . . . . . . . . 27 13.2. Informative References . . . . . . . . . . . . . . . . . 26
15.1. Normative References . . . . . . . . . . . . . . . . . . 27 Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . 28
15.2. Informative References . . . . . . . . . . . . . . . . . 27
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 29 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 29
1. Introduction 1. Introduction
RFC 5714 [RFC5714] describes a framework for IP Fast Re-route (IPFRR) RFC 5714 [RFC5714] describes a framework for IP Fast Reroute (IPFRR)
and provides a summary of various proposed IPFRR solutions. A basic and provides a summary of various proposed IPFRR solutions. A basic
mechanism using loop-free alternates (LFAs) is described in [RFC5286] mechanism using Loop-Free Alternates (LFAs) is described in [RFC5286]
that provides good repair coverage in many topologies [RFC6571], that provides good repair coverage in many topologies [RFC6571],
especially those that are highly meshed. However, some topologies, especially those that are highly meshed. However, some topologies,
notably ring based topologies are not well protected by LFAs alone notably ring-based topologies, are not well protected by LFAs alone.
because there is no neighbor of the point of local repair (PLR) that This is because there is no neighbor of the Point of Local Repair
has a cost to the destination without traversing the failure that is (PLR) that has a cost to the destination via a path that does not
cheaper than the cost to the destination via the failure. traverse the failure that is cheaper than the cost to the destination
via the failure.
The method described in this document extends LFA approach described The method described in this document extends the LFA approach
in [RFC5286] to cover many of these cases by tunneling the packets described in [RFC5286] to cover many of these cases by tunneling the
that require IPFRR to a node that is both reachable from the PLR and packets that require IPFRR to a node that is both reachable from the
can reach the destination. PLR and can reach the destination.
2. Terminology 2. Terminology
This document uses the terms defined in [RFC5714]. This section This document uses the terms defined in [RFC5714]. This section
defines additional terms that are used in this document. defines additional terms that are used in this document.
Repair tunnel A tunnel established for the purpose of providing a Repair tunnel:
virtual neighbor which is a Loop Free Alternate. A tunnel established for the purpose of providing a virtual
neighbor that is a Loop-Free Alternate.
P-space The P-space of a router with respect to a protected
link is the set of routers reachable from that
specific router using the pre-convergence shortest
paths, without any of those paths (including equal
cost path splits) transiting that protected link.
For example, the P-space of S with respect to link P-space:
S-E, is the set of routers that S can reach without The P-space of a router with respect to a protected link is the
using the protected link S-E. set of routers reachable from that specific router using the pre-
convergence shortest paths without any of those paths (including
equal-cost path splits) transiting that protected link.
Extended P-space For example, the P-space of S with respect to link S-E is the set
of routers that S can reach without using the protected link S-E.
Consider the set of neighbours of a router protecting Extended P-space:
a link. Exclude from that set of routers the router Consider the set of neighbors of a router protecting a link.
reachable over the protected link. The extended Exclude from that set of routers the router reachable over the
P-space of the protecting router with respect to the protected link. The extended P-space of the protecting router
protected link is the union of the P-spaces of the with respect to the protected link is the union of the P-spaces of
neighbours in that set of neighbours with respect to the neighbors in that set of neighbors with respect to the
the protected link (see Section 5.2.1.2). protected link (see Section 5.2.1.2).
Q-space Q-space of a router with respect to a protected link Q-space:
is the set of routers from which that specific router The Q-space of a router with respect to a protected link is the
can be reached without any path (including equal cost set of routers from which that specific router can be reached
path splits) transiting that protected link. without any path (including equal-cost path splits) transiting
that protected link.
PQ node A PQ node of a node S with respect to a protected link PQ node:
S-E is a node which is a member of both the P-space A PQ node of a node S with respect to a protected link S-E is a
(or the extended P-space) of S with respect to that node that is a member of both the P-space (or the extended
protected link S-E and the Q-space of E with respect P-space) of S with respect to that protected link S-E and the
to that protected link S-E. A repair tunnel endpoint Q-space of E with respect to that protected link S-E. A repair
is chosen from the set of PQ-nodes. tunnel endpoint is chosen from the set of PQ-nodes.
Remote LFA (RLFA) The use of a PQ node rather than a neighbour of Remote LFA (RLFA):
the repairing node as the next hop in an LFA repair The use of a PQ node rather than a neighbor of the repairing node
[RFC5286]. as the next hop in an LFA repair [RFC5286].
In this document the notation X-Y is used to mean the path from X to In this document, the notation X-Y is used to mean the path from X to
Y over the link directly connecting X and Y, whilst the notation X->Y Y over the link directly connecting X and Y while the notation X->Y
refers to the shortest path from X to Y via some set of unspecified refers to the shortest path from X to Y via some set of unspecified
nodes including the null set (i.e. Including over a link directly nodes including the null set (i.e., including over a link directly
connecting X and Y). connecting X and Y).
2.1. Requirements Language
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC 2119 [RFC2119].
3. Overview of Solution 3. Overview of Solution
The problem of LFA IPFRR reachability in some networks is illustrated The problem of LFA IPFRR reachability in some networks is illustrated
by the network fragment shown in Figure 1 below. by the network fragment shown in Figure 1 below.
S---E S---E
/ \ / \
A D A D
\ / \ /
B---C B---C
Figure 1: A simple ring topology Figure 1: A Simple Ring Topology
If all link costs are equal, traffic transiting link S-E cannot be If all link costs are equal, traffic that is transiting link S-E
fully protected by LFAs. The destination C is an ECMP from S, and so cannot be fully protected by LFAs. The destination C is an Equal-
traffic to C can be protected when S-E fails, but traffic to D and E Cost Multipath (ECMP) from S, and so traffic to C can be protected
are not protectable using LFAs. when S-E fails but traffic to D and E are not protectable using LFAs.
This document describes extensions to the basic repair mechanism in This document describes extensions to the basic repair mechanism in
which tunnels are used to provide additional logical links which can which tunnels are used to provide additional logical links that can
then be used as loop free alternates where none exist in the original then be used as loop-free alternates where none exist in the original
topology. In Figure 1 S can reach A, B, and C without going via S-E; topology. In Figure 1, S can reach A, B, and C without going via
these form S's extended P-space with respect to S-E. The routers S-E; these form S's extended P-space with respect to S-E. The
that can reach E without going through S-E will be in E's Q-space routers that can reach E without going through S-E will be in E's
with respect to link S-E; these are D and C. B has equal-cost paths Q-space with respect to link S-E; these are D and C. B has equal-
to E via B-A-S-E and B-C-D-E and so the forwarder at S might choose cost paths to E via B-A-S-E and B-C-D-E, and so the forwarder at S
to send a packet to E via link S-E. Hence B is not in the Q-space of might choose to send a packet to E via link S-E. Hence, B is not in
E with respect to link S-E. The single node in both S's extended the Q-space of E with respect to link S-E. The single node in both
P-space and E's Q-space is C; thus node C is selected as the repair S's extended P-space and E's Q-space is C; thus, node C is selected
tunnel's end-point. Thus, if a tunnel is provided between S and C as as the repair tunnel's endpoint. Thus, if a tunnel is provided
shown in Figure 2 then C, now being a direct neighbor of S would between S and C as shown in Figure 2, then C, now being a direct
become an LFA for D and E. The definition of (extended-)P space and neighbor of S, would become an LFA for D and E. The definition of
Q space are provided in Section 2 and details of the calculation of (extended) P-space and Q-space are provided in Section 2, and details
the tunnel end points is provided in Section 5.2. of the calculation of the tunnel end points are provided in
Section 5.2.
The non-failure traffic distribution is not disrupted by the The non-failure traffic distribution is not disrupted by the
provision of such a tunnel since it is only used for repair traffic provision of such a tunnel since it is only used for repair traffic
and MUST NOT be used for normal traffic. Note that Operations and and MUST NOT be used for normal traffic. Note that Operations,
Maintenance (OAM) traffic specifically to verify the viability of the Administration, and Maintenance (OAM) traffic used specifically to
repair MAY traverse the tunnel prior to a failure. verify the viability of the repair MAY traverse the tunnel prior to a
failure.
S---E S---E
/ \ \ / \ \
A \ D A \ D
\ \ / \ \ /
B---C B---C
Figure 2: The addition of a tunnel Figure 2: The Addition of a Tunnel
The use of this technique is not restricted to ring based topologies, The use of this technique is not restricted to ring-based topologies
but is a general mechanism which can be used to enhance the but it is a general mechanism that can be used to enhance the
protection provided by LFAs. A study of the protection achieved protection provided by LFAs. A study of the protection achieved
using remote LFA in typical service provider core networks is using remote LFA in typical service provider core networks is
provided in Section 9, and a side by side comparison between LFA and provided in Section 9, and a side-by-side comparison between LFA and
remote LFA is provided in Section 9.4. remote LFA is provided in Section 9.4.
Remote LFA is suitable for incremental deployment within a network, Remote LFA is suitable for incremental deployment within a network,
including a network that is already deploying LFA. Computation of including a network that is already deploying LFA. Computation of
the repair path requires acceptable CPU resources, and takes place the repair path requires acceptable CPU resources and takes place
exclusively on the repairing node. In MPLS networks the targeted LDP exclusively on the repairing node. In MPLS networks, the targeted
protocol needed to learn the label binding at the repair tunnel LDP protocol needed to learn the label binding at the repair tunnel
endpoint Section 8 is a well understood and widely deployed endpoint (Section 8) is a well understood and widely deployed
technology. technology.
The technique described in this document is directed at providing The technique described in this document is directed at providing
repairs in the case of link failures. Considerations regarding node repairs in the case of link failures. Considerations regarding node
failures are discussed in Section 7. This memo describes a solution failures are discussed in Section 7. This memo describes a solution
to the case where the failure occurs on a point to point link. It to the case where the failure occurs on a point-to-point link. It
covers the case where the repair first hop is reached via a broadcast covers the case where the repair first hop is reached via a broadcast
or non-broadcast multi-access (NBMA) link such as a LAN, and the case or non-broadcast multi-access (NBMA) link such as a LAN and the case
where the P or Q node is attached via such a link. It does not where the P or Q node is attached via such a link. It does not,
however cover the more complicated case where the failed interface is however, cover the more complicated case where the failed interface
a broadcast or non-broadcast multi-access (NBMA) link. is a broadcast or NBMA link.
This document considers the case when the repair path is confined to This document considers the case when the repair path is confined to
either a single area or to the level two routing domain. In all either a single area or to the level two routing domain. In all
other cases, the chosen PQ node should be regarded as a tunnel other cases, the chosen PQ node should be regarded as a tunnel
adjacency of the repairing node, and the considerations described in adjacency of the repairing node, and the considerations described in
Section 6 of [RFC5286] taken into account. Section 6 of [RFC5286] should be taken into account.
4. Repair Paths 4. Repair Paths
As with LFA FRR, when a router detects an adjacent link failure, it As with LFA FRR, when a router detects an adjacent link failure, it
uses one or more repair paths in place of the failed link. Repair uses one or more repair paths in place of the failed link. Repair
paths are pre-computed in anticipation of later failures so they can paths are precomputed in anticipation of later failures so they can
be promptly activated when a failure is detected. be promptly activated when a failure is detected.
A tunneled repair path tunnels traffic to some staging point in the A tunneled repair path tunnels traffic to some staging point in the
network from which it is known that, in the absence of a worse than network from which it is known that, in the absence of a worse-than-
anticipated failure, the traffic will travel to its destination using anticipated failure, the traffic will travel to its destination using
normal forwarding without looping back. This is equivalent to normal forwarding without looping back. This is equivalent to
providing a virtual loop-free alternate to supplement the physical providing a virtual loop-free alternate to supplement the physical
loop-free alternates. Hence the name "Remote LFA FRR". In its loop-free alternates; hence the name "remote LFA FRR". In its
simplest form, when a link cannot be entirely protected with local simplest form, when a link cannot be entirely protected with local
LFA neighbors, the protecting router seeks the help of a remote LFA LFA neighbors, the protecting router seeks the help of a remote LFA
staging point. Network manageability considerations may lead to a staging point. Network manageability considerations may lead to a
repair strategy that uses a remote LFA more frequently repair strategy that uses a remote LFA more frequently [LFA-MANAGE].
[I-D.ietf-rtgwg-lfa-manageability].
Examples of worse failures are node failures (see Section 7 ), the Examples of worse failures are node failures (see Section 7), the
failure of a shared risk link group (SRLG), the independent failure of a Shared Risk Link Group (SRLG), the independent
concurrent failures of multiple links, broadcast or non-broadcast concurrent failures of multiple links, or broadcast or NBMA links
multi-access (NBMA) links Section 3 ; protecting against such worse (Section 3); protecting against such failures is out of scope for
failures is out of scope for this specification. this specification.
4.1. Tunnels as Repair Paths 4.1. Tunnels as Repair Paths
Consider an arbitrary protected link S-E. In LFA FRR, if a path to Consider an arbitrary protected link S-E. In LFA FRR, if a path to
the destination from a neighbor N of S does not cause a packet to the destination from a neighbor N of S does not cause a packet to
loop back over the link S-E (i.e. N is a loop-free alternate), then loop back over the link S-E (i.e., N is a loop-free alternate), then
S can send the packet to N and the packet will be delivered to the S can send the packet to N and the packet will be delivered to the
destination using the pre-failure forwarding information. If there destination using the pre-failure forwarding information. If there
is no such LFA neighbor, then S may be able to create a virtual LFA is no such LFA neighbor, then S may be able to create a virtual LFA
by using a tunnel to carry the packet to a point in the network which by using a tunnel to carry the packet to a point in the network that
is not a direct neighbor of S from which the packet will be delivered is not a direct neighbor of S from which the packet will be delivered
to the destination without looping back to S. In this document such to the destination without looping back to S. In this document, such
a tunnel is termed a repair tunnel. The tail-end of this tunnel (the a tunnel is termed a repair tunnel. The tail end of this tunnel (the
repair tunnel endpoint) is a "PQ node" and the repair mechanism is a repair tunnel endpoint) is a "PQ node", and the repair mechanism is a
"remote LFA". This tunnel MUST NOT traverse the link S-E. "remote LFA". This tunnel MUST NOT traverse the link S-E.
Note that the repair tunnel terminates at some intermediate router Note that the repair tunnel terminates at some intermediate router
between S and E, and not E itself. This is clearly the case, since between S and E, and not E itself. This is clearly the case, since
if it were possible to construct a tunnel from S to E then a if it were possible to construct a tunnel from S to E, then a
conventional LFA would have been sufficient to effect the repair. conventional LFA would have been sufficient to effect the repair.
4.2. Tunnel Requirements 4.2. Tunnel Requirements
There are a number of IP in IP tunnel mechanisms that may be used to There are a number of IP-in-IP tunnel mechanisms that may be used to
fulfil the requirements of this design, such as IP-in-IP [RFC1853] fulfill the requirements of this design, such as IP-in-IP [RFC1853]
and GRE[RFC1701] . and Generic Routing Encapsulation (GRE) [RFC1701].
In an MPLS enabled network using LDP[RFC5036], a simple label In an MPLS-enabled network using LDP [RFC5036], a simple label stack
stack[RFC3032] may be used to provide the required repair tunnel. In [RFC3032] may be used to provide the required repair tunnel. In this
this case the outer label is S's neighbor's label for the repair case, the outer label is S's neighbor's label for the repair tunnel
tunnel end point, and the inner label is the repair tunnel end endpoint, and the inner label is the repair tunnel endpoint's label
point's label for the packet destination. In order for S to obtain for the packet destination. In order for S to obtain the correct
the correct inner label it is necessary to establish a targeted LDP inner label, it is necessary to establish a targeted LDP session
session[RFC5036] to the tunnel end point. [RFC5036] to the tunnel endpoint.
The selection of the specific tunnelling mechanism (and any necessary The selection of the specific tunneling mechanism (and any necessary
enhancements) used to provide a repair path is outside the scope of enhancements) used to provide a repair path is outside the scope of
this document. The deployment in an MPLS/LDP environment is this document. The deployment in an MPLS/LDP environment is
relatively simple in the data plane as an LDP LSP from S to the relatively simple in the data plane, as an LDP Label Switched Path
repair tunnel endpoint (the selected PQ node) is readily available, (LSP) from S to the repair tunnel endpoint (the selected PQ node) is
and hence does not require any new protocol extension or design readily available and hence does not require any new protocol
change. This LSP is automatically established as a basic property of extension or design change. This LSP is automatically established as
LDP behavior. The performance of the encapsulation and decapsulation a basic property of LDP behavior. The performance of the
is efficient as encapsulation is just a push of one label (like encapsulation and decapsulation is efficient, as encapsulation is
conventional MPLS TE FRR) and the decapsulation is normally just a push of one label (like conventional MPLS-TE FRR) and the
configured to occur at the penultimate hop before the repair tunnel decapsulation is normally configured to occur at the penultimate hop
endpoint. In the control plane, a targeted LDP (TLDP) session is before the repair tunnel endpoint. In the control plane, a Targeted
needed between the repairing node and the repair tunnel endpoint, LDP (TLDP) session is needed between the repairing node and the
which will need to be established and the labels processed before the repair tunnel endpoint, which will need to be established and the
tunnel can be used. The time to establish the TLDP session and labels processed before the tunnel can be used. The time to
acquire labels will limit the speed at which a new tunnel can be put establish the TLDP session and acquire labels will limit the speed at
into service. This is not anticipated to be a problem in normal which a new tunnel can be put into service. This is not anticipated
operation since the managed introduction and removal of links is to be a problem in normal operation since the managed introduction
relatively rare as is the incidence of failure in a well managed and removal of links is relatively rare, as is the incidence of
network. failure in a well-managed network.
When a failure is detected, it is necessary to immediately redirect When a failure is detected, it is necessary to immediately redirect
traffic to the repair path. Consequently, the repair tunnel used traffic to the repair path. Consequently, the repair tunnel used
MUST be provisioned beforehand in anticipation of the failure. Since MUST be provisioned beforehand in anticipation of the failure. Since
the location of the repair tunnels is dynamically determined it is the location of the repair tunnels is dynamically determined, it is
necessary to automatically establish the repair tunnels. Multiple necessary to automatically establish the repair tunnels. Multiple
repair tunnels may share a tunnel end point. repair tunnels may share a tunnel endpoint.
5. Construction of Repair Paths 5. Construction of Repair Paths
5.1. Identifying Required Tunneled Repair Paths 5.1. Identifying Required Tunneled Repair Paths
Not all links will require protection using a tunneled repair path. Not all links will require protection using a tunneled repair path.
Referring to Figure 1, if E can already be protected via an LFA, S-E Referring to Figure 1, if E can already be protected via an LFA, S-E
does not need to be protected using a repair tunnel, since all does not need to be protected using a repair tunnel since all
destinations normally reachable through E must therefore also be destinations normally reachable through E must therefore also be
protectable by an LFA. Such an LFA is frequently termed a "link protectable by an LFA; such an LFA is frequently termed a "link LFA".
LFA". Tunneled repair paths (which may be calculated per-prefix) are Tunneled repair paths (which may be calculated per prefix) are only
only required for links which do not have a link or per-prefix LFA. required for links that do not have a link or per-prefix LFA.
It should be noted that using the Q-space of E as a proxy for the It should be noted that using the Q-space of E as a proxy for the
Q-space of each destination can result in failing to identify valid Q-space of each destination can result in failing to identify valid
remote LFAs. The extent to which this reduces the effective remote LFAs. The extent to which this reduces the effective
protection coverage is topology dependent. protection coverage is topology dependent.
5.2. Determining Tunnel End Points 5.2. Determining Tunnel Endpoints
The repair tunnel endpoint needs to be a node in the network The repair tunnel endpoint needs to be a node in the network
reachable from S without traversing S-E. In addition, the repair reachable from S without traversing S-E. In addition, the repair
tunnel end point needs to be a node from which packets will normally tunnel endpoint needs to be a node from which packets will normally
flow towards their destination without being attracted back to the flow towards their destination without being attracted back to the
failed link S-E. failed link S-E.
Note that once released from the tunnel, the packet will be Note that once released from the tunnel, the packet will be
forwarded, as normal, on the shortest path from the release point to forwarded, as normal, on the shortest path from the release point to
its destination. This may result in the packet traversing the router its destination. This may result in the packet traversing the router
E at the far end of the protected link S-E, but this is obviously not E at the far end of the protected link S-E, but this is obviously not
required. required.
The properties that are required of repair tunnel end points are The properties that are required of repair tunnel endpoints are as
therefore: follows:
o The repair tunneled point MUST be reachable from the tunnel source o The repair tunneled point MUST be reachable from the tunnel source
without traversing the failed link; and without traversing the failed link; and
o When released from the tunnel, packets MUST proceed towards their o when released from the tunnel, packets MUST proceed towards their
destination without being attracted back over the failed link. destination without being attracted back over the failed link.
Provided both these requirements are met, packets forwarded over the Provided both these requirements are met, packets forwarded over the
repair tunnel will reach their destination, and will not loop after a repair tunnel will reach their destination and will not loop after a
single link failure. single link failure.
In some topologies it will not be possible to find a repair tunnel In some topologies it will not be possible to find a repair tunnel
endpoint that exhibits both the required properties. For example if endpoint that exhibits both the required properties. For example, if
the ring topology illustrated in Figure 1 had a cost of 4 for the the ring topology illustrated in Figure 1 had a cost of four for the
link B-C, while the remaining links were cost 1, then it would not be link B-C while the remaining links were the cost of one, then it
possible to establish a tunnel from S to C (without resorting to some would not be possible to establish a tunnel from S to C (without
form of source routing). resorting to some form of source routing).
5.2.1. Computing Repair Paths 5.2.1. Computing Repair Paths
To compute the repair path for link S-E it is necessary to determine To compute the repair path for link S-E, it is necessary to determine
the set of routers which can be reached from S without traversing the set of routers that can be reached from S without traversing S-E
S-E, and match this with the set of routers from which the node E can and match this with the set of routers from which the node E can be
be reached, by normal forwarding, without traversing the link S-E. reached by normal forwarding without traversing the link S-E.
The approach used in this memo is as follows: The approach used in this memo is as follows:
o The method of computing the set of routers which can be reached o The method of computing the set of routers that can be reached
from S on the shortest path tree without traversing S-E is from S on the shortest path tree without traversing S-E is
described. This is called the S's P-space with respect to the described. This is called the S's P-space with respect to the
failure of link S-E. failure of link S-E.
o The distance of the tunnel endpoint from the point of local repair o The distance of the tunnel endpoint from the PLR is increased by
(PLR) is increased by noting that S is able to use the P-Space of noting that S is able to use the P-space of its neighbors with
its neighbours with respect to the failure of link S-E, since S respect to the failure of link S-E since S can determine which
can determine which neighbour it will use as the next hop for the neighbor it will use as the next hop for the repair. This is
repair. This is called the S's Extended P-space with respect to called the S's extended P-space with respect to the failure of
the failure of link S-E. The use of extended P-space allows link S-E. The use of extended P-space allows greater repair
greater repair coverage and is the preferred approach. coverage and is the preferred approach.
o Finally two methods of computing the set of routers from which the o Finally, two methods of computing the set of routers from which
node E can be reached, by normal forwarding, without traversing the node E can be reached by normal forwarding without traversing
the link S-E. This is called the Q-space of E with respect to the the link S-E. This is called the Q-space of E with respect to the
link S-E. link S-E.
The selection of the preferred node from the set of nodes that an in The selection of the preferred node from the set of nodes that are in
both Extended P-Space and Q-Space with respect to the S-E is both extended P-space and Q-space with respect to the S-E is
described in Section 5.2.2. described in Section 5.2.2.
A suitable cost based algorithm to compute the set of nodes common to A suitable cost-based algorithm to compute the set of nodes common to
both extended P-space and Q-space with respect to the S-E is provided both extended P-space and Q-space with respect to the S-E is provided
in Section 5.3. in Section 5.3.
5.2.1.1. P-space 5.2.1.1. P-space
The set of routers which can be reached from S on the shortest path The set of routers that can be reached from S on the shortest path
tree without traversing S-E is termed the P-space of S with respect tree without traversing S-E is termed the P-space of S with respect
to the link S-E. This P-space can be obtained by computing a to the link S-E. This P-space can be obtained by computing a
shortest path tree (SPT) rooted at S and excising the sub-tree Shortest Path Tree (SPT) rooted at S and excising the subtree reached
reached via the link S-E (including those routers which are members via the link S-E (including those routers that are members of an ECMP
of an ECMP that includes link S-E). The exclusion of routers that includes link S-E). The exclusion of routers reachable via an
reachable via an ECMP that includes S-E prevents the forwarding ECMP that includes S-E prevents the forwarding subsystem from
subsystem from attempting to execute a repair via the failed link attempting to execute a repair via the failed link S-E. Thus, for
S-E. Thus for example, if the SPF computation stores at each node example, if the Shortest Path First (SPF) computation stores at each
the next-hops to be used to reach that node from S, then the node can node the next hops to be used to reach that node from S, then the
be added to P-space if none of its next-hops are link S-E. In the node can be added to P-space if none of its next hops are link S-E.
case of Figure 1 this P-space comprises nodes A and B only. In the case of Figure 1, this P-space comprises nodes A and B only.
Expressed in cost terms the set of routers {P} are those for which Expressed in cost terms, the set of routers {P} are those for which
the shortest path cost S->P is strictly less than the shortest path the shortest path cost S->P is strictly less than the shortest path
cost S->E->P. cost S->E->P.
5.2.1.2. Extended P-space 5.2.1.2. Extended P-space
The description in Section 5.2.1.1 calculated router S's P-space The description in Section 5.2.1.1 calculated router S's P-space
rooted at S itself. However, since router S will only use a repair rooted at S itself. However, since router S will only use a repair
path when it has detected the failure of the link S-E, the initial path when it has detected the failure of the link S-E, the initial
hop of the repair path need not be subject to S's normal forwarding hop of the repair path need not be subject to S's normal forwarding
decision process. Thus the concept of extended P-space is decision process. Thus, the concept of extended P-space is
introduced. Router S's extended P-space is the union of the P-spaces introduced. Router S's extended P-space is the union of the P-spaces
of each of S's neighbours (N). This may be calculated by computing a of each of S's neighbors (N). This may be calculated by computing an
shortest path tree (SPT) at each of S's neighbors (excluding E) and SPT at each of S's neighbors (excluding E) and excising the subtree
excising the subtree reached via the path N->S->E. Note this will reached via the path N->S->E. Note this will excise those routers
excise those routers which are reachable through all ECMPs that that are reachable through all ECMPs that include link S-E. The use
includes link S-E. The use of extended P-space may allow router S to of extended P-space may allow router S to reach potential repair
reach potential repair tunnel end points that were otherwise tunnel endpoints that were otherwise unreachable. In cost terms, a
unreachable. In cost terms a router (P) is in extended P-space if router (P) is in extended P-space if the shortest path cost N->P is
the shortest path cost N->P is strictly less than the shortest path strictly less than the shortest path cost N->S->E->P. In other
cost N->S->E->P. In other words, once the packet it forced to N by words, once the packet is forced to N by S, it is a lower cost for it
S, it is a lower cost for it to continue on to P by any path except to continue on to P by any path except one that takes it back to S
one that takes it back to S and then across the S->E link. and then across the S->E link.
Since in the case of Figure 1 node A is a per-prefix LFA for the Since in the case of Figure 1 node A is a per-prefix LFA for the
destination node C, the set of extended P-space nodes with respect to destination node C, the set of extended P-space nodes with respect to
link S-E comprises nodes A, B and C. Since node C is also in E's link S-E comprises nodes A, B, and C. Since node C is also in E's
Q-space with respect to link S-E, there is now a node common to both Q-space with respect to link S-E, there is now a node common to both
extended P-space and Q-space which can be used as a repair tunnel extended P-space and Q-space that can be used as a repair tunnel
end-point to protect the link S-E. endpoint to protect the link S-E.
5.2.1.3. Q-space 5.2.1.3. Q-space
The set of routers from which the node E can be reached, by normal The set of routers from which the node E can be reached, by normal
forwarding, without traversing the link S-E is termed the Q-space of forwarding without traversing the link S-E, is termed the Q-space of
E with respect to the link S-E. The Q-space can be obtained by E with respect to the link S-E. The Q-space can be obtained by
computing a reverse shortest path tree (rSPT) rooted at E, with the computing a reverse Shortest Path Tree (rSPT) rooted at E, with the
sub-tree which might traverse the protected link S-E excised (i.e. subtree that might traverse the protected link S-E excised (i.e.,
those nodes that would send the packet via S-E plus those nodes which those nodes that would send the packet via S-E plus those nodes that
have an ECMP set to E with one or more members of that ECMP set have an ECMP set to E with one or more members of that ECMP set
traversing the protected link S-E). The rSPT uses the cost towards traversing the protected link S-E). The rSPT uses the cost towards
the root rather than from it and yields the best paths towards the the root rather than from it and yields the best paths towards the
root from other nodes in the network. In the case of Figure 1 the root from other nodes in the network. In the case of Figure 1, the
Q-space of E with respect to S-E comprises nodes C and D only. Q-space of E with respect to S-E comprises nodes C and D only.
Expressed in cost terms, the set of routers {Q} are those for which
Expressed in cost terms the set of routers {Q} are those for which
the shortest path cost Q<-E is strictly less than the shortest path the shortest path cost Q<-E is strictly less than the shortest path
cost Q<-S<-E. In Figure 1 the intersection of the E's Q-space with cost Q<-S<-E. In Figure 1, the intersection of the E's Q-space with
respect to S-E with S's P-space with respect to S-E defines the set respect to S-E with S's P-space with respect to S-E defines the set
of viable repair tunnel end-points, known as "PQ nodes". As can be of viable repair tunnel endpoints, known as "PQ nodes". As can be
seen, for the case of Figure 1 there is no common node and hence no seen in the case of Figure 1, there is no common node and hence no
viable repair tunnel end-point. However when the extended the viable repair tunnel endpoint. However, when the extended P-space
extended P-space Section 5.2.1.2 at S with respect to S-E is (Section 5.2.1.2) at S with respect to S-E is considered, a suitable
considered, a suitable intersection is found at C. intersection is found at C.
Note that the Q-space calculation could be conducted for each Note that the Q-space calculation could be conducted for each
individual destination and a per-destination repair tunnel end point individual destination and a per-destination repair tunnel end point
determined. However this would, in the worst case, require an SPF determined. However, this would, in the worst case, require an SPF
computation per destination which is not currently considered to be computation per destination that is not currently considered to be
scalable. Therefore the Q-space of E with respect to link S-E is scalable. Therefore, the Q-space of E with respect to link S-E is
used as a proxy for the Q-space of each destination. This used as a proxy for the Q-space of each destination. This
approximation is obviously correct since the repair is only used for approximation is obviously correct since the repair is only used for
the set of destinations which were, prior to the failure, routed the set of destinations which were, prior to the failure, routed
through node E. This is analogous to the use of link-LFAs rather through node E. This is analogous to the use of link LFAs rather
than per-prefix LFAs. than per-prefix LFAs.
5.2.2. Selecting Repair Paths 5.2.2. Selecting Repair Paths
The mechanisms described above will identify all the possible repair The mechanisms described above will identify all the possible repair
tunnel end points that can be used to protect a particular link. In tunnel endpoints that can be used to protect a particular link. In a
a well-connected network there are likely to be multiple possible well-connected network, there are likely to be multiple possible
release points for each protected link. All will deliver the packets release points for each protected link. All will deliver the packets
correctly so, arguably, it does not matter which is chosen. However, correctly, so arguably, it does not matter which is chosen. However,
one repair tunnel end point may be preferred over the others on the one repair tunnel endpoint may be preferred over the others on the
basis of path cost or some other selection criteria. basis of path cost or some other selection criteria.
There is no technical requirement for the selection criteria to be There is no technical requirement for the selection criteria to be
consistent across all routers, but such consistency may be desirable consistent across all routers, but such consistency may be desirable
from an operational point of view. In general there are advantages from an operational point of view. In general, there are advantages
in choosing the repair tunnel end point closest (shortest metric) to in choosing the repair tunnel endpoint closest (shortest metric) to
S. Choosing the closest maximises the opportunity for the traffic to S. Choosing the closest maximizes the opportunity for the traffic to
be load balanced once it has been released from the tunnel. For be load balanced once it has been released from the tunnel. For
consistency in behavior, it is RECOMMENDED that the member of the set consistency in behavior, it is RECOMMENDED that the member of the set
of routers {PQ} with the lowest cost S->P be the default choice for of routers {PQ} with the lowest cost S->P be the default choice for
P. In the event of a tie the router with the lowest node identifier P. In the event of a tie, the router with the lowest node identifier
SHOULD be selected. SHOULD be selected.
It is a local matter whether the repair path selection policy used by It is a local matter whether the repair path selection policy used by
the router favours LFA repairs over RLFA repairs. An LFA repair has the router favors LFA repairs over RLFA repairs. An LFA repair has
the advantage of not requiring the use of tunnel, however network the advantage of not requiring the use of a tunnel; however, network
manageability considerations may lead to a repair strategy that uses manageability considerations may lead to a repair strategy that uses
a remote LFA more frequently [I-D.ietf-rtgwg-lfa-manageability]. a remote LFA more frequently [LFA-MANAGE].
As described in [RFC5286], always selecting a PQ node that is As described in [RFC5286], always selecting a PQ node that is
downstream to the destination with respect to the repairing node, downstream to the destination with respect to the repairing node
prevents the formation of loops when the failure is worse than prevents the formation of loops when the failure is worse than
expected. The use of downstream nodes reduces the repair coverage, expected. The use of downstream nodes reduces the repair coverage,
and operators are advised to determine whether adequate coverage is and operators are advised to determine whether adequate coverage is
achieved before enabling this selection feature. achieved before enabling this selection feature.
5.3. A Cost Based RLFA Algorithm 5.3. A Cost-Based RLFA Algorithm
The preceding text has described the computation of the remote LFA The preceding text has described the computation of the remote LFA
repair target (PQ) in terms of the intersection of two reachability repair target (PQ) in terms of the intersection of two reachability
graphs computed using a shortest path first (SPF) algorithm. This graphs computed using an SPF algorithm. This section describes a
section describes a method of computing the remote LFA repair target method of computing the remote LFA repair target for a specific
for a specific failed link using a cost based algorithm. The pseudo- failed link using a cost-based algorithm. The pseudocode provided in
code provided in this section avoids unnecessary SPF computations, this section avoids unnecessary SPF computations; for the sake of
but for the sake of readability, it does not otherwise try to readability, it does not otherwise try to optimize the code. The
optimize the code. The algorithm covers the case where the repair algorithm covers the case where the repair first hop is reached via a
first hop is reached via a broadcast or non-broadcast multi-access broadcast or NBMA link such as a LAN. It also covers the case where
(NBMA) link such as a LAN. It also covers the case where the P or Q the P or Q node is attached via such a link. It does not cover the
node is attached via such a link. It does not cover the case where case where the failed interface is a broadcast or NBMA link. To
the failed interface is a broadcast or non-broadcast multi-access address that case it is necessary to compute the Q-space of each
(NBMA) link. To address that case it is necessary to compute the Q neighbor of the repairing router reachable through the LAN, i.e., to
space of each neighbor of the repairing router reachable though the treat the pseudonode [RFC1195] as a node failure; this is because the
LAN, i.e. to treat the pseudonode [RFC1195] as a node failure. This Q-spaces of the neighbors of the pseudonode may be disjoint and
is because the Q spaces of the neighbors of the pseudonode may be require use of a neighbor-specific PQ node. The reader is referred
disjoint requiring use of a neighbor specific PQ node. The reader is to [NODE-PROTECTION] for further information on the use of RLFA for
referred to [I-D.ietf-rtgwg-rlfa-node-protection] for further node repairs.
information on the use of RLFA for node repairs.
The following notation is used: The following notation is used:
o D_opt(a,b) is the shortest distance from node a to node b as o D_opt(a,b) is the shortest distance from node a to node b as
computed by the SPF. computed by the SPF.
o dest is the packet destination o dest is the packet destination.
o fail_intf is the failed interface (S-E in the example) o fail_intf is the failed interface (S-E in the example).
o fail_intf.remote_node is the node reachable over interface o fail_intf.remote_node is the node reachable over interface
fail_intf (node E in the example) fail_intf (node E in the example).
o intf.remote_node is the set of nodes reachable over interface intf o intf.remote_node is the set of nodes reachable over interface
intf.
o root is the root of the SPF calculation o root is the root of the SPF calculation.
o self is the node carrying out the computation o self is the node carrying out the computation.
o y is the node in the network under consideration o y is the node in the network under consideration.
o y.pseudonode is true if y is a pseudonode
o y.pseudonode is true if y is a pseudonode.
////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////
// //
// Main Function // Main Function
////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////
// //
// We have already computed the forward SPF from self to all nodes // We have already computed the forward SPF from self to all nodes
// y in network and thus we know D_opt (self, y). This is needed // y in network and thus we know D_opt (self, y). This is needed
// for normal forwarding. // for normal forwarding.
// However for completeness. // However, for completeness:
Compute_and_Store_Forward_SPF(self) Compute_and_Store_Forward_SPF(self)
// To extend P-space we compute the SPF at each neighbour except // To extend P-space, we compute the SPF at each neighbor except
// the neighbour that is reached via the link being protected. // the neighbor that is reached via the link being protected.
// We will also need D_opt(fail_intf.remote_node,y) so compute // We will also need D_opt(fail_intf.remote_node,y), so we
// that at the same time. // compute that at the same time.
Compute_Neighbor_SPFs() Compute_Neighbor_SPFs()
// Compute the set of nodes {P} reachable other than via the // Compute the set of nodes {P} reachable other than via the
// failed link // failed link.
Compute_Extended_P_Space(fail_intf) Compute_Extended_P_Space(fail_intf)
// Compute the set of nodes that can reach the node on the far // Compute the set of nodes that can reach the node on the far
// side of the failed link without traversing the failed link. // side of the failed link without traversing the failed link.
Compute_Q_Space(fail_intf) Compute_Q_Space(fail_intf)
// Compute the set of candidate RLFA tunnel endpoints.
// Compute the set of candidate RLFA tunnel endpoints
Intersect_Extended_P_and_Q_Space() Intersect_Extended_P_and_Q_Space()
// Make sure that we cannot get looping repairs when the // Make sure that we cannot get looping repairs when the
// failure is worse than expected. // failure is worse than expected.
if (guarantee_no_looping_on_worse_than_protected_failure) if (guarantee_no_looping_on_worse_than_protected_failure)
Apply_Downstream_Constraint() Apply_Downstream_Constraint()
// //
skipping to change at page 14, line 4 skipping to change at page 14, line 18
// Make sure that we cannot get looping repairs when the // Make sure that we cannot get looping repairs when the
// failure is worse than expected. // failure is worse than expected.
if (guarantee_no_looping_on_worse_than_protected_failure) if (guarantee_no_looping_on_worse_than_protected_failure)
Apply_Downstream_Constraint() Apply_Downstream_Constraint()
// //
// End of Main Function // End of Main Function
// //
////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////
// //
// Procedures // Procedures
// //
///////////////////////////////////////////////////////////////// /////////////////////////////////////////////////////////////////
// //
// This computes the SPF from root, and stores the optimum // This computes the SPF from root and stores the optimum
// distance from root to each node y // distance from root to each node y.
Compute_and_Store_Forward_SPF(root) Compute_and_Store_Forward_SPF(root)
Compute_Forward_SPF(root) Compute_Forward_SPF(root)
foreach node y in network foreach node y in network
store D_opt(root,y) store D_opt(root,y)
///////////////////////////////////////////////////////////////// /////////////////////////////////////////////////////////////////
// //
// This computes the optimum distance from each neighbour (other // This computes the optimum distance from each neighbor (other
// than the neighbour reachable through the failed link) and // than the neighbor reachable through the failed link) and
// every other node in the network // every other node in the network.
// //
// Note that we compute this for all neighbours including the // Note that we compute this for all neighbors, including the
// neighbour on the far side the failure. This is done on the // neighbor on the far side the failure. This is done on the
// expectation that more than on link will be protected, and // expectation that more than one link will be protected and
// that the results are stored for later use. // that the results are stored for later use.
// //
Compute_Neighbor_SPFs() Compute_Neighbor_SPFs()
foreach interface intf in self foreach interface intf in self
Compute_and_Store_Forward_SPF(intf.remote_node) Compute_and_Store_Forward_SPF(intf.remote_node)
///////////////////////////////////////////////////////////////// /////////////////////////////////////////////////////////////////
// //
// The reverse SPF computes the cost from each remote node to // The reverse SPF computes the cost from each remote node to
// root. This is achieved by running the normal SPF algorithm, // root. This is achieved by running the normal SPF algorithm
// but using the link cost in the direction from the next hop // but using the link cost in the direction from the next hop
// back towards root in place of the link cost in the direction // back towards root in place of the link cost in the direction
// away from root towards the next hop. // away from root towards the next hop.
Compute_and_Store_Reverse_SPF(root) Compute_and_Store_Reverse_SPF(root)
Compute_Reverse_SPF(root) Compute_Reverse_SPF(root)
foreach node y in network foreach node y in network
store D_opt(y,root) store D_opt(y,root)
///////////////////////////////////////////////////////////////// /////////////////////////////////////////////////////////////////
// //
// Calculate extended P-space // Calculate Extended P-space
// //
// Note the strictly less than operator is needed to // Note that the "strictly less than" operator is needed to
// avoid ECMP issues. // avoid ECMP issues.
Compute_Extended_P_Space(fail_intf) Compute_Extended_P_Space(fail_intf)
foreach node y in network foreach node y in network
y.in_extended_P_space = false y.in_extended_P_space = false
// Extend P-space to the P-spaces of all reachable // Extend P-space to the P-spaces of all reachable
// neighbours // neighbors
foreach interface intf in self foreach interface intf in self
// Exclude failed interface, noting that // Exclude failed interface, noting that
// the node reachable via that interface may be // the node reachable via that interface may be
// reachable via another interface (parallel path) // reachable via another interface (parallel path)
if (intf != fail_intf) if (intf != fail_intf)
foreach neighbor n in intf.remote_node foreach neighbor n in intf.remote_node
// Apply RFC5286 Inequality 1 // Apply RFC 5286 Inequality 1
if ( D_opt(n, y) < if ( D_opt(n, y) <
D_opt(n,self) + D_opt(self, y)) D_opt(n,self) + D_opt(self, y))
y.in_extended_P_space = true y.in_extended_P_space = true
///////////////////////////////////////////////////////////////// /////////////////////////////////////////////////////////////////
// //
// Compute the nodes in Q-space // Compute the Nodes in Q-space
// //
Compute_Q_Space(fail_intf) Compute_Q_Space(fail_intf)
// Compute the cost from every node the network to the // Compute the cost from every node in the network to the
// node normally reachable across the failed link // node normally reachable across the failed link
Compute_and_Store_Reverse_SPF(fail_intf.remote_node) Compute_and_Store_Reverse_SPF(fail_intf.remote_node)
// Compute the cost from every node in the network to self
// Compute the cost from every node the network to self
Compute_and_Store_Reverse_SPF(self) Compute_and_Store_Reverse_SPF(self)
foreach node y in network foreach node y in network
if ( D_opt(y,fail_intf.remote_node) < D_opt(y,self) + if ( D_opt(y,fail_intf.remote_node) < D_opt(y,self) +
D_opt(self,fail_intf.remote_node) ) D_opt(self,fail_intf.remote_node) )
y.in_Q_space = true y.in_Q_space = true
else else
y.in_Q_space = false y.in_Q_space = false
///////////////////////////////////////////////////////////////// /////////////////////////////////////////////////////////////////
// //
// Compute set of nodes in both extended P-space and in Q-space // Compute Set of Nodes in Both Extended P-space and in Q-space
Intersect_Extended_P_and_Q_Space() Intersect_Extended_P_and_Q_Space()
foreach node y in network foreach node y in network
if ( y.in_extended_P_space && y.in_Q_space && if ( y.in_extended_P_space && y.in_Q_space &&
y.pseudonode == False) y.pseudonode == False)
y.valid_tunnel_endpoint = true y.valid_tunnel_endpoint = true
else else
y.valid_tunnel_endpoint = false y.valid_tunnel_endpoint = false
///////////////////////////////////////////////////////////////// /////////////////////////////////////////////////////////////////
// //
// A downstream route is one where the next hop is strictly // A downstream route is one where the next hop is strictly
// closer to the destination. By sending the packet to a // closer to the destination. By sending the packet to a
// PQ node that is downstream, we know that if the PQ node // PQ node that is downstream, we know that if the PQ node
// detects a failure, it will not loop the packet back to self. // detects a failure it will not loop the packet back to self.
// This is useful when there are two failures, or a node has // This is useful when there are two failures or when a node has
// failed rather than a link. // failed rather than a link.
Apply_Downstream_Constraint() Apply_Downstream_Constraint()
foreach node y in network foreach node y in network
if (y.valid_tunnel_endpoint) if (y.valid_tunnel_endpoint)
Compute_and_Store_Forward_SPF(y) Compute_and_Store_Forward_SPF(y)
if ((D_opt(y,dest) < D_opt(self,dest)) if ((D_opt(y,dest) < D_opt(self,dest))
y.valid_tunnel_endpoint = true y.valid_tunnel_endpoint = true
else else
y.valid_tunnel_endpoint = false y.valid_tunnel_endpoint = false
// //
///////////////////////////////////////////////////////////////// /////////////////////////////////////////////////////////////////
5.4. Interactions with IS-IS Overload, RFC6987, and Costed Out Links 5.4. Interactions with IS-IS Overload, RFC 6987, and Costed Out Links
Since normal link state routing takes into account the IS-IS overload Since normal link state routing takes into account the IS-IS overload
bit, [RFC6987], and costing out of links as described in Section 3.5 bit, OSPF stub router advertisement [RFC6987], and costed out links
of [RFC5286], the forward SPFs performed by the PLR rooted at the (as described in Section 3.5 of [RFC5286]), the forward SPFs
neighbors of the PLR also need to take this into account. A repair performed by the PLR rooted at the neighbors of the PLR also need to
tunnel path from a neighbor of the PLR to a repair tunnel endpoint take this into account. A repair tunnel path from a neighbor of the
will generally avoid the nodes and links excluded by the IGP PLR to a repair tunnel endpoint will generally avoid the nodes and
overload/costing out rules. However, there are two situations where links excluded by the IGP overload/costing-out rules. However, there
this behavior may result in a repair path traversing a link or router are two situations where this behavior may result in a repair path
that should be excluded: traversing a link or router that should be excluded:
1. When the first hop on the repair tunnel path (from the PLR to a 1. One situation is when the first hop on the repair tunnel path
direct neighbor) does not follow the IGP shortest path. In this (from the PLR to a direct neighbor) does not follow the IGP
case, the PLR MUST NOT use a repair tunnel path whose first hop shortest path. In this case, the PLR MUST NOT use a repair
is along a link whose cost or reverse cost is MaxLinkMetric (for tunnel path whose first hop is along a link that has a cost or
OSPF) or the maximum cost (for IS-IS) or, has the overload bit reverse cost equal to MaxLinkMetric (for OSPF) or the maximum
set (for IS-IS). cost (for IS-IS) or whose first hop has the overload bit set (for
IS-IS).
2. The IS-IS overload bit and the mechanism of [RFC6987] only 2. The other situation is when the IS-IS overload bit and the
prevent transit traffic from traversing a node. They do not mechanism of [RFC6987] only prevent transit traffic from
prevent traffic destined to a node. The per-neighbor forward traversing a node; they do not prevent traffic destined to a
SPFs using the standard IGP overload rules will not prevent a PLR node. The per-neighbor forward SPFs using the standard IGP
from choosing a repair tunnel endpoint that is advertising a overload rules will not prevent a PLR from choosing a repair
desire to not carry transit traffic. Therefore, the PLR MUST NOT tunnel endpoint that is advertising a desire to not carry transit
use a repair tunnel endpoint with the IS-IS overload bit set, or traffic. Therefore, the PLR MUST NOT use a repair tunnel
where all outgoing interfaces have the cost set to MaxLinkMetric endpoint with the IS-IS overload bit set or where all outgoing
for OSPF. interfaces have the cost set to MaxLinkMetric for OSPF.
6. Example Application of Remote LFAs 6. Example Application of Remote LFAs
An example of a commonly deployed topology which is not fully An example of a commonly deployed topology that is not fully
protected by LFAs alone is shown in Figure 3. PE1 and PE2 are protected by LFAs alone is shown in Figure 3. Provider Edge (PE)1
connected in the same site. P1 and P2 may be geographically and PE2 are connected in the same site. P1 and P2 may be
separated (inter-site). In order to guarantee the lowest latency geographically separated (intersite). In order to guarantee the
path from/to all other remote PEs, normally the shortest path follows lowest latency path from/to all other remote PEs, normally the
the geographical distance of the site locations. Therefore, to shortest path follows the geographical distance of the site
ensure this, a lower IGP metric (5) is assigned between PE1 and PE2. locations. Therefore, to ensure this, a lower IGP metric (5) is
A high metric (1000) is set on the P-PE links to prevent the PEs assigned between PE1 and PE2. A high metric (1000) is set on the
being used for transit traffic. The PEs are not individually dual- P-PE links to prevent the PEs being used for transit traffic. The
homed in order to reduce costs. PEs are not individually dual-homed in order to reduce costs.
This is a common topology in SP networks. This is a common topology in Service Provider (SP) networks.
When a failure occurs on the link between PE1 and P1, PE1 does not When a failure occurs on the link between PE1 and P1, PE1 does not
have an LFA for traffic reachable via P1. Similarly, by symmetry, if have an LFA for traffic reachable via P1. Similarly, by symmetry, if
the link between PE2 and P2 fails, PE2 does not have an LFA for the link between PE2 and P2 fails, PE2 does not have an LFA for
traffic reachable via P2. traffic reachable via P2.
Increasing the metric between PE1 and PE2 to allow the LFA would Increasing the metric between PE1 and PE2 to allow the LFA would
impact the normal traffic performance by potentially increasing the impact the normal traffic performance by potentially increasing the
latency. latency.
| 100 | | 100 |
-P1---------P2- -P1---------P2-
\ / \ /
1000 \ / 1000 1000 \ / 1000
PE1---PE2 PE1---PE2
5 5
Figure 3: Example SP topology Figure 3: Example SP Topology
Clearly, full protection can be provided, using the techniques Clearly, full protection can be provided using the techniques
described in this document, by PE1 choosing P2 as the remote LFA described in this document by PE1 choosing P2 as the remote LFA
repair target node, and PE2 choosing P1 as the remote LFA repair repair target node and PE2 choosing P1 as the remote LFA repair
target. target.
7. Node Failures 7. Node Failures
When the failure is a node failure rather than a point-to-point link When the failure is a node failure rather than a point-to-point link
failure there is a danger that the RLFA repair will loop. This is failure, there is a danger that the RLFA repair will loop. This is
discussed in detail in [I-D.bryant-ipfrr-tunnels]. In summary the discussed in detail in [IP-FRR]. In summary, the problem is that two
problem is that two of more of E's neighbors each with E as the next or more of E's neighbors, each with E as the next hop to some
hop to some destination D may attempt to repair a packet addressed to destination D, may attempt to repair a packet addressed to
destination D via the other neighbor and then E, thus causing a loop destination D via the other neighbor and then E, thus causing a loop
to form. A similar problem exists in the case of a shared risk link to form. A similar problem exists in the case of a shared risk link
group failure where the PLR for each failure attempts to repair via group failure where the PLR for each failure attempts to repair via
the other failure. As will be noted from [I-D.bryant-ipfrr-tunnels], the other failure. As will be noted from [IP-FRR], this can rapidly
this can rapidly become a complex problem to address. become a complex problem to address.
There are a number of ways to minimize the probability of a loop There are a number of ways to minimize the probability of a loop
forming when a node failure occurs and there exists the possibility forming when a node failure occurs, and there exists the possibility
that two of E's neighbors may form a mutual repair. that two of E's neighbors may form a mutual repair.
1. Detect when a packet has arrived on some interface I that is also 1. Detect when a packet has arrived on some interface I that is also
the interface used to reach the first hop on the RLFA path to the the interface used to reach the first hop on the RLFA path to the
remote LFA repair target, and drop the packet. This is useful in remote LFA repair target, and drop the packet. This is useful in
the case of a ring topology. the case of a ring topology.
2. Require that the path from the remote LFA repair target to 2. Require that the path from the remote LFA repair target to
destination D never passes through E (including in the ECMP destination D never passes through E (including in the ECMP
case), i.e. only use node protecting paths in which the cost from case), i.e., only use node protecting paths in which the cost
the remote LFA repair target to D is strictly less than the cost from the remote LFA repair target to D is strictly less than the
from the remote LFA repair target to E plus the cost E to D. cost from the remote LFA repair target to E plus the cost E to D.
3. Require that where the packet may pass through another neighbor 3. Require that where the packet may pass through another neighbor
of E, that node is down stream (i.e. strictly closer to D than of E, that node is down stream (i.e., strictly closer to D than
the repairing node). This means that some neighbor of E (X) can the repairing node). This means that some neighbor of E (X) can
repair via some other neighbor of E (Y), but Y cannot repair via repair via some other neighbor of E (Y), but Y cannot repair via
X. X.
Case 1 accepts that loops may form and suppresses them by dropping Case 1 accepts that loops may form and suppresses them by dropping
packets. Dropping packets may be considered less detrimental than packets. Dropping packets may be considered less detrimental than
looping packets. This approach may also lead to dropping some looping packets. This approach may also lead to dropping some
legitimate packets. Cases 2 and 3 above prevent the formation of a legitimate packets. Cases 2 and 3 above prevent the formation of a
loop, but at the expense of a reduced repair coverage and at the cost loop but at the expense of a reduced repair coverage and at the cost
of additional complexity in the algorithm to compute the repair path. of additional complexity in the algorithm to compute the repair path.
Alternatively one might choose to assume that the probability of a Alternatively, one might choose to assume that the probability of a
node failure is sufficiently rare that the issue of looping RLFA node failure is sufficiently rare that the issue of looping RLFA
repairs can be ignored. repairs can be ignored.
The probability of a node failure and the consequences of node The probability of a node failure and the consequences of node
failure in any particular topology will depend on the node design, failure in any particular topology will depend on the node design,
the particular topology in use, and the strategy adopted under node the particular topology in use, and the strategy adopted under node
failure. It is recommended that a network operator perform an failure. It is recommended that a network operator perform an
analysis of the consequences and probability of node failure in their analysis of the consequences and probability of node failure in their
network, and determine whether the incidence and consequence of network and determine whether the incidence and consequence of
occurrence are acceptable. occurrence are acceptable.
This topic is further discussed in This topic is further discussed in [NODE-PROTECTION].
[I-D.ietf-rtgwg-rlfa-node-protection].
8. Operation in an LDP environment 8. Operation in an LDP Environment
Where this technique is used in an MPLS network using LDP [RFC5036], Where this technique is used in an MPLS network using LDP [RFC5036],
and S is a transit node, S will need to swap the top label in the and S is a transit node, S will need to swap the top label in the
stack for the remote LFA repair target's (PQ's) label to the stack for the remote LFA repair target's (PQ's) label to the
destination, and to then push its own label for the remote LFA repair destination and to then push its own label for the remote LFA repair
target. target.
In the example Figure 2 S already has the first hop (A) label for the In the example, S in Figure 2 already has the first hop (A) label for
remote LFA repair target (C) as a result of the ordinary operation of the remote LFA repair target (C) as a result of the ordinary
LDP. To get the remote LFA repair target's label (C's label) for the operation of LDP. To get the remote LFA repair target's label (C's
destination (D), S needs to establish a targeted LDP session with C. label) for the destination (D), S needs to establish a targeted LDP
The label stack for normal operation and RLFA operation is shown session with C. The label stack for normal operation and RLFA
below in Figure 4. operation is shown below in Figure 4.
+-----------------+ +-----------------+ +-----------------+ +-----------------+ +-----------------+ +-----------------+
| datalink | | datalink | | datalink | | datalink | | datalink | | datalink |
+-----------------+ +-----------------+ +-----------------+ +-----------------+ +-----------------+ +-----------------+
| S's label for D | | E's label for D | | A's label for C | | S's label for D | | E's label for D | | A's label for C |
+-----------------+ +-----------------+ +-----------------+ +-----------------+ +-----------------+ +-----------------+
| Payload | | Payload | | C's label for D | | Payload | | Payload | | C's label for D |
+-----------------+ +-----------------+ +-----------------+ +-----------------+ +-----------------+ +-----------------+
X Y | Payload | X Y | Payload |
+-----------------+ +-----------------+
Z Z
X = Normal label stack packet arriving at S X = Normal label stack packet arriving at S
Y = Normal label stack packet leaving S Y = Normal label stack packet leaving S
Z = RLFA label stack to D via C as the remote LFA repair target. Z = RLFA label stack to D via C as the remote LFA repair target
Figure 4 Figure 4
To establish an targeted LDP session with a candidate remote LFA To establish a targeted LDP session with a candidate remote LFA
repair target node the repairing node (S) needs to know what IP repair target node, the repairing node (S) needs to know what IP
address that the remote LFA repair target is willing to use for address the remote LFA repair target is willing to use for targeted
targeted LDP sessions. Ideally this is provided by the remote LFA LDP sessions. Ideally, this is provided by the remote LFA repair
repair target advertising this address in the IGP in use. Which target advertising this address in the IGP in use. Which address is
address is used, how this is advertised in the IGP, and whether this used, how this is advertised in the IGP, and whether this is a
is a special IP address or an IP address also used for some other special IP address or an IP address also used for some other purpose
purpose is out of scope for this document and must be specified in an is out of scope for this document and must be specified in an
IGP specific RFC. IGP-specific RFC.
In the absence of a protocol to learn the preferred IP address for In the absence of a protocol to learn the preferred IP address for
targeted LDP, an LSR should attempt a targeted LDP session with the targeted LDP, an LSR should attempt a targeted LDP session with the
Router ID [RFC2328] [RFC5305] [RFC5340] [RFC6119] Router ID [RFC2328] [RFC5305] [RFC5340] [RFC6119] [OSPF-RI] unless it
[I-D.ietf-ospf-routable-ip-address], unless it is configured is configured otherwise.
otherwise.
No protection is available until the TLDP session has been No protection is available until the TLDP session has been
established and a label for the destination has been learned from the established and a label for the destination has been learned from the
remote LFA repair target. If for any reason the TLDP session cannot remote LFA repair target. If for any reason the TLDP session cannot
be established, an implementation SHOULD advise the operator about be established, an implementation SHOULD advise the operator about
the protection setup issue through the network management system. the protection setup issue through the network management system.
9. Analysis of Real World Topologies 9. Analysis of Real World Topologies
This section gives the results of analysing a number of real world This section gives the results of analyzing a number of real world
service provider topologies collected between the end of 2012 and service provider topologies collected between the end of 2012 and
early 2013 early 2013.
9.1. Topology Details 9.1. Topology Details
The figure below characterises each topology (topo) studied in terms The figure below characterizes each topology (topo) studied in terms
of : of:
o The number of nodes (# nodes) excluding pseudonodes. o the number of nodes (# nodes) excluding pseudonodes;
o The number of bidirectional links ( # links) including parallel o the number of bidirectional links (# links) including parallel
links and links to and from pseudonodes. links and links to and from pseudonodes;
o The number of node pairs that are connected by one or more links o the number of node pairs that are connected by one or more links
(# pairs). (# pairs);
o The number of node pairs that are connected by more than one (i.e. o the number of node pairs that are connected by more than one
parallel) link ( # para). (i.e., parallel) link (# para); and
o The number of links (excluding pseudonode links, which are by o the number of links (excluding pseudonode links, which are by
definition asymmetric) that have asymmetric metrics (#asym). definition asymmetric) that have asymmetric metrics (# asym).
+------+---------+---------+---------+--------+--------+ +------+---------+---------+---------+--------+--------+
| topo | # nodes | # links | # pairs | # para | # asym | | topo | # nodes | # links | # pairs | # para | # asym |
+------+---------+---------+---------+--------+--------+ +------+---------+---------+---------+--------+--------+
| 1 | 315 | 570 | 560 | 10 | 3 | | 1 | 315 | 570 | 560 | 10 | 3 |
| 2 | 158 | 373 | 312 | 33 | 0 | | 2 | 158 | 373 | 312 | 33 | 0 |
| 3 | 655 | 1768 | 1314 | 275 | 1195 | | 3 | 655 | 1768 | 1314 | 275 | 1195 |
| 4 | 1281 | 2326 | 2248 | 70 | 10 | | 4 | 1281 | 2326 | 2248 | 70 | 10 |
| 5 | 364 | 811 | 659 | 80 | 86 | | 5 | 364 | 811 | 659 | 80 | 86 |
| 6 | 114 | 318 | 197 | 101 | 4 | | 6 | 114 | 318 | 197 | 101 | 4 |
| 7 | 55 | 237 | 159 | 67 | 2 | | 7 | 55 | 237 | 159 | 67 | 2 |
| 8 | 779 | 1848 | 1441 | 199 | 437 | | 8 | 779 | 1848 | 1441 | 199 | 437 |
| 9 | 263 | 482 | 413 | 41 | 12 | | 9 | 263 | 482 | 413 | 41 | 12 |
| 10 | 86 | 375 | 145 | 64 | 22 | | 10 | 86 | 375 | 145 | 64 | 22 |
| 11 | 162 | 1083 | 351 | 201 | 49 | | 11 | 162 | 1083 | 351 | 201 | 49 |
| 12 | 380 | 1174 | 763 | 231 | 0 | | 12 | 380 | 1174 | 763 | 231 | 0 |
| 13 | 1051 | 2087 | 2037 | 48 | 64 | | 13 | 1051 | 2087 | 2037 | 48 | 64 |
| 14 | 92 | 291 | 204 | 64 | 2 | | 14 | 92 | 291 | 204 | 64 | 2 |
+------+---------+---------+---------+--------+--------+ +------+---------+---------+---------+--------+--------+
9.2. LFA only 9.2. LFA Only
The figure below shows the percentage of protected destinations (% The figure below shows the percentage of protected destinations (%
prot) and percentage of guaranteed node protected destinations ( % prot) and the percentage of guaranteed node protected destinations (%
gtd N) for the set of topologies characterized in Section 9.1 gtd N) for the set of topologies characterized in Section 9.1
achieved using only LFA repairs. achieved using only LFA repairs.
These statistics were generated by considering each node and then These statistics were generated by considering each node and then
considering each link to each next hop to each destination. The considering each link to each next hop to each destination. The
percentage of such links across the entire network that are protected percentage of such links across the entire network that are protected
against link failure was determined. This is the percentage of against link failure was determined. This is the percentage of
protected destinations. If a link is protected against the failure protected destinations. If a link is protected against the failure
of the next hop node, this is considered guaranteed node protecting of the next hop node, this is considered Guaranteed Node Protecting
(GNP) and percentage of guaranteed node protected destinations is (GNP) and the percentage of guaranteed node protected destinations is
calculated using the same method used for calculating the link calculated using the same method used for calculating the link
protection coverage. protection coverage.
GNP is identical to Node-protecting as defined in [RFC5714] and does GNP is identical to node-protecting as defined in [RFC6571] and does
not include the additional node protection coverage obtained by the not include the additional node protection coverage obtained by the
de facto node-protecting condition described in [RFC6571]. de facto node-protecting condition described in [RFC6571].
+------+--------+---------+ +------+--------+---------+
| topo | % prot | % gtd N | | topo | % prot | % gtd N |
+------+--------+---------+ +------+--------+---------+
| 1 | 78.5 | 36.9 | | 1 | 78.5 | 36.9 |
| 2 | 97.3 | 52.4 | | 2 | 97.3 | 52.4 |
| 3 | 99.3 | 58 | | 3 | 99.3 | 58 |
| 4 | 83.1 | 63.1 | | 4 | 83.1 | 63.1 |
skipping to change at page 23, line 27 skipping to change at page 22, line 48
| 10 | 98.5 | 14.9 | | 10 | 98.5 | 14.9 |
| 11 | 99.6 | 24.8 | | 11 | 99.6 | 24.8 |
| 12 | 99.5 | 62.4 | | 12 | 99.5 | 62.4 |
| 13 | 92.4 | 51.6 | | 13 | 92.4 | 51.6 |
| 14 | 99.3 | 48.6 | | 14 | 99.3 | 48.6 |
+------+--------+---------+ +------+--------+---------+
9.3. RLFA 9.3. RLFA
The figure below shows the percentage of protected destinations (% The figure below shows the percentage of protected destinations (%
prot) and % guaranteed node protected destinations ( % gtd N) for prot) and % guaranteed node protected destinations (% gtd N) for RLFA
RLFA protection in the topologies studies. In addition, it show the protection in the topologies studies. In addition, it shows the
percentage of destinations using an RLFA repair (% PQ) together with percentage of destinations using an RLFA repair (% PQ) together with
the total number of unidirectional RLFA targeted LDP session the total number of unidirectional RLFA targeted LDP sessions
established (# PQ), the number of PQ sessions which would be required established (# PQ), and the number of PQ sessions that would be
for complete protection, but which could not be established because required for complete protection but that could not be established
there was no PQ node, i.e. the number of cases whether neither LFA or because there was no PQ node, i.e., the number of cases whether
RLFA protection was possible (no PQ). It also shows the 50 (p50), 90 neither LFA or RLFA protection was possible (no PQ). It also shows
(p90) and 100 (p100) percentiles for the number of individual LDP the 50 (p50), 90 (p90), and 100 (p100) percentiles for the number of
sessions terminating at an individual node (whether used for TX, RX individual LDP sessions terminating at an individual node (whether
or both). used for TX, RX, or both).
For example, if there were LDP sessions required A->B, A->C, C->A, For example, if there were LDP sessions that required A->B, A->C,
C->D, these would be counted as 2, 1, 2, 1 at nodes A,B,C and D C->A, and C->D, these would be counted as 2, 1, 2, and 1 at nodes A,
respectively because:- B, C, and D respectively because:
A has two sessions (to nodes B and C) A has two sessions (to nodes B and C);
B has one session (to node A) B has one session (to node A);
C has two sessions (to nodes A and D) C has two sessions (to nodes A and D); and
D has one session (to node D) D has one session (to node D).
In this study, remote LFA is only used when necessary. i.e. when In this study, remote LFA is only used when necessary, i.e., when
there is at least one destination which is not reparable by a per there is at least one destination that is not reparable by a per
destination LFA, and a single remote LFA tunnel is used (if destination LFA and a single remote LFA tunnel is used (if available)
available) to repair traffic to all such destinations. The remote to repair traffic to all such destinations. The remote LFA repair
LFA repair target points are computed using extended P space and target points are computed using extended P-space and choosing the PQ
choosing the PQ node which has the lowest metric cost from the node that has the lowest metric cost from the repairing node.
repairing node.
+------+--------+--------+------+------+-------+-----+-----+------+ +------+--------+--------+------+------+-------+-----+-----+------+
| topo | % prot |% gtd N | % PQ | # PQ | no PQ | p50 | p90 | p100 | | topo | % prot |% gtd N | % PQ | # PQ | no PQ | p50 | p90 | p100 |
+------+--------+--------+------+------+-------+-----+-----+------+ +------+--------+--------+------+------+-------+-----+-----+------+
| 1 | 99.7 | 53.3 | 21.2 | 295 | 3 | 1 | 5 | 14 | | 1 | 99.7 | 53.3 | 21.2 | 295 | 3 | 1 | 5 | 14 |
| 2 | 97.5 | 52.4 | 0.2 | 7 | 40 | 0 | 0 | 2 | | 2 | 97.5 | 52.4 | 0.2 | 7 | 40 | 0 | 0 | 2 |
| 3 | 99.999 | 58.4 | 0.7 | 63 | 5 | 0 | 1 | 5 | | 3 | 99.999 | 58.4 | 0.7 | 63 | 5 | 0 | 1 | 5 |
| 4 | 99 | 74.8 | 16 | 1424 | 54 | 1 | 3 | 23 | | 4 | 99 | 74.8 | 16 | 1424 | 54 | 1 | 3 | 23 |
| 5 | 99.5 | 59.5 | 0.5 | 151 | 7 | 0 | 2 | 7 | | 5 | 99.5 | 59.5 | 0.5 | 151 | 7 | 0 | 2 | 7 |
| 6 | 100 | 34.9 | 13.6 | 63 | 0 | 1 | 2 | 6 | | 6 | 100 | 34.9 | 13.6 | 63 | 0 | 1 | 2 | 6 |
| 7 | 99.999 | 40.6 | 6.1 | 16 | 2 | 0 | 2 | 4 | | 7 | 99.999 | 40.6 | 6.1 | 16 | 2 | 0 | 2 | 4 |
| 8 | 99.5 | 50.2 | 4.3 | 350 | 39 | 0 | 2 | 15 | | 8 | 99.5 | 50.2 | 4.3 | 350 | 39 | 0 | 2 | 15 |
| 9 | 99.5 | 55 | 17.3 | 428 | 5 | 1 | 2 | 67 | | 9 | 99.5 | 55 | 17.3 | 428 | 5 | 1 | 2 | 67 |
| 10 | 99.6 | 14.1 | 1 | 49 | 7 | 1 | 2 | 5 | | 10 | 99.6 | 14.1 | 1 | 49 | 7 | 1 | 2 | 5 |
| 11 | 99.9 | 24.9 | 0.3 | 85 | 1 | 0 | 2 | 8 | | 11 | 99.9 | 24.9 | 0.3 | 85 | 1 | 0 | 2 | 8 |
| 12 | 99.999 | 62.8 | 0.5 | 512 | 4 | 0 | 0 | 3 | | 12 | 99.999 | 62.8 | 0.5 | 512 | 4 | 0 | 0 | 3 |
| 13 | 97.5 | 54.6 | 5.1 | 1188 | 95 | 0 | 2 | 27 | | 13 | 97.5 | 54.6 | 5.1 | 1188 | 95 | 0 | 2 | 27 |
| 14 | 100 | 48.6 | 0.7 | 79 | 0 | 0 | 2 | 4 | | 14 | 100 | 48.6 | 0.7 | 79 | 0 | 0 | 2 | 4 |
+------+--------+--------+------+------+-------+-----+-----+------+ +------+--------+--------+------+------+-------+-----+-----+------+
Another study[ISOCORE2010] confirms the significant coverage increase Another study [ISOCORE2010] confirms the significant coverage
provided by Remote LFAs. increase provided by remote LFAs.
9.4. Comparison of LFA an RLFA results 9.4. Comparison of LFA and RLFA results
The table below provides a side by side comparison the LFA and the The table below provides a side-by-side comparison of the LFA and the
remote LFA results. This shows a significant improvement in the remote LFA results. This shows a significant improvement in the
percentage of protected destinations and normally a modest percentage of protected destinations and normally a modest
improvement in the percentage of guaranteed node protected improvement in the percentage of guaranteed node protected
destinations. destinations.
+------+--------+--------+---------+---------+ +------+--------+--------+---------+---------+
| topo | LFA | RLFA | LFA | RLFA | | topo | LFA | RLFA | LFA | RLFA |
| | % prot | %prot | % gtd N | % gtd N | | | % prot | %prot | % gtd N | % gtd N |
+------+--------+--------+---------+---------+ +------+--------+--------+---------+---------+
| 1 | 78.5 | 99.7 | 36.9 | 53.3 | | 1 | 78.5 | 99.7 | 36.9 | 53.3 |
skipping to change at page 25, line 26 skipping to change at page 24, line 34
| 8 | 95.3 | 99.5 | 48.1 | 50.2 | | 8 | 95.3 | 99.5 | 48.1 | 50.2 |
| 9 | 82.2 | 99.5 | 49.5 | 55 | | 9 | 82.2 | 99.5 | 49.5 | 55 |
| 10 | 98.5 | 99.6 | 14.9 | 14.1 | | 10 | 98.5 | 99.6 | 14.9 | 14.1 |
| 11 | 99.6 | 99.9 | 24.8 | 24.9 | | 11 | 99.6 | 99.9 | 24.8 | 24.9 |
| 12 | 99.5 | 99.999 | 62.4 | 62.8 | | 12 | 99.5 | 99.999 | 62.4 | 62.8 |
| 13 | 92.4 | 97.5 | 51.6 | 54.6 | | 13 | 92.4 | 97.5 | 51.6 | 54.6 |
| 14 | 99.3 |100 | 48.6 | 48.6 | | 14 | 99.3 |100 | 48.6 | 48.6 |
+------+--------+--------+---------+---------+ +------+--------+--------+---------+---------+
As shown in the table, remote LFA provides close to 100% prefix As shown in the table, remote LFA provides close to 100% prefix
protection against link failure in 11 of the 14 topologies studied, protection against link failure in 11 of the 14 topologies studied
and provides a significant improvement in two of the remaining three and provides a significant improvement in two of the remaining three
cases. Note that in an MPLS network the tunnels to the PQ nodes are cases. Note that in an MPLS network, the tunnels to the PQ nodes are
always present as a property of an LDP-based deployment. always present as a property of an LDP-based deployment.
In the small number of cases where there is no intersection between In the small number of cases where there is no intersection between
the (extended)P-space and the Q-space, a number of solutions to the (extended) P-space and the Q-space, a number of solutions to
providing a suitable path between such disjoint regions in the providing a suitable path between such disjoint regions in the
network have been discussed in the working group. For example an network have been discussed in the working group. For example, an
explicitly routed LSP between P and Q might be set up using RSVP-TE explicitly routed LSP between P and Q might be set up using RSVP-TE
or using Segment Routing [I-D.filsfils-spring-segment-routing]. Such or using Segment Routing [SEGMENT-ROUTING]. Such extended repair
extended repair methods are outside the scope of this document. methods are outside the scope of this document.
10. Management and Operational Considerations 10. Management and Operational Considerations
The management of LFA and remote LFA is the subject of ongoing work The management of LFA and remote LFA is the subject of ongoing work
withing the IETF [I-D.ietf-rtgwg-lfa-manageability] to which the within the IETF [LFA-MANAGE], to which the reader is referred.
reader is referred. Management considerations may lead to a Management considerations may lead to a preference for the use of a
preference for the use of a remote LFA over an available LFA. This remote LFA over an available LFA. This preference is a matter for
preference is a matter for the network operator, and not a matter of the network operator and not a matter of protocol correctness.
protocol correctness.
When the network re-converges, microloops [RFC5715] can form due to When the network reconverges, micro-loops [RFC5715] can form due to
transient inconsistencies in the forwarding tables of different transient inconsistencies in the forwarding tables of different
routers. If it is determined that microloops are a significant issue routers. If it is determined that micro-loops are a significant
in the deployment, then a suitable loop free convergence methods such issue in the deployment, then a suitable loop-free convergence
as one of those described in [RFC5715], [RFC6976], or method, such as one of those described in [RFC5715], [RFC6976], or
[I-D.litkowski-rtgwg-uloop-delay] should be implemented. [ULOOP-DELAY], should be implemented.
11. Historical Note 11. Historical Note
The basic concepts behind Remote LFA were invented in 2002 and were The basic concepts behind remote LFA were invented in 2002 and were
later included in [I-D.bryant-ipfrr-tunnels], submitted in 2004. later included in [IP-FRR], submitted in 2004.
[I-D.bryant-ipfrr-tunnels], targeted a 100% protection coverage and [IP-FRR] targeted a 100% protection coverage and hence included
hence included additional mechanisms on top of the Remote LFA additional mechanisms on top of the remote LFA concept. The addition
concept. The addition of these mechanisms made the proposal very of these mechanisms made the proposal very complex and
complex and computationally intensive and it was therefore not computationally intensive, and it was therefore not pursued as a
pursued as a working group item. working group item.
As explained in [RFC6571], the purpose of the LFA FRR technology is As explained in [RFC6571], the purpose of the LFA FRR technology is
not to provide coverage at any cost. A solution for this already not to provide coverage at any cost. A solution for this already
exists with MPLS TE FRR. MPLS TE FRR is a mature technology which is exists with MPLS-TE FRR. MPLS-TE FRR is a mature technology that is
able to provide protection in any topology thanks to the explicit able to provide protection in any topology thanks to the explicit
routing capability of MPLS TE. routing capability of MPLS-TE.
The purpose of LFA FRR technology is to provide for a simple FRR The purpose of LFA FRR technology is to provide for a simple FRR
solution when such a solution is possible. The first step along this solution when such a solution is possible. The first step along this
simplicity approach was "local" LFA [RFC5286]. This specification of simplicity approach was "local" LFA [RFC5286]. This specification of
"Remote LFA" is a natural second step. "remote LFA" is a natural second step.
12. IANA Considerations
There are no IANA considerations that arise from this architectural
description of IPFRR. The RFC Editor may remove this section on
publication.
13. Security Considerations 12. Security Considerations
The security considerations of [RFC5286] also apply. The security considerations of [RFC5286] also apply.
Targeted LDP sessions and MPLS tunnels are normal features of an MPLS Targeted LDP sessions and MPLS tunnels are normal features of an MPLS
network and their use in this application raises no additional network, and their use in this application raises no additional
security concerns. security concerns.
IP repair tunnel endpoints (where used) SHOULD be assigned from a set IP repair tunnel endpoints (where used) SHOULD be assigned from a set
of addresses that are not reachable from outside the routing domain. of addresses that are not reachable from outside the routing domain;
This would prevent their use as an attack vector. this would prevent their use as an attack vector.
Other than OAM traffic, used to verify the correct operation of a Other than OAM traffic used to verify the correct operation of a
repair tunnel, only traffic that is being protected as a result of a repair tunnel, only traffic that is being protected as a result of a
link failure is placed a repair tunnel. The repair tunnel MUST NOT link failure is placed in a repair tunnel. The repair tunnel MUST
be advertised by the routing protocol as a link that may be used to NOT be advertised by the routing protocol as a link that may be used
carry normal user traffic, or routing protocol traffic. to carry normal user traffic or routing protocol traffic.
14. Acknowledgments
The authors wish to thank Levente Csikor and Chris Bowers for their
contribution to the cost based algorithm text. The authors thank
Alia Atlas, Ross Callon, Stephane Litkowski, Bharath R, Pushpasis
Sarkar and Adrian Farrel for their review of this document.
15. References 13. References
15.1. Normative References 13.1. Normative References
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997. Requirement Levels", BCP 14, RFC 2119, March 1997,
<http://www.rfc-editor.org/info/rfc2119>.
[RFC5286] Atlas, A. and A. Zinin, "Basic Specification for IP Fast [RFC5286] Atlas, A., Ed. and A. Zinin, Ed., "Basic Specification for
Reroute: Loop-Free Alternates", RFC 5286, September 2008. IP Fast Reroute: Loop-Free Alternates", RFC 5286,
September 2008, <http://www.rfc-editor.org/info/rfc5286>.
[RFC5714] Shand, M. and S. Bryant, "IP Fast Reroute Framework", RFC [RFC5714] Shand, M. and S. Bryant, "IP Fast Reroute Framework", RFC
5714, January 2010. 5714, January 2010,
<http://www.rfc-editor.org/info/rfc5714>.
15.2. Informative References
[I-D.bryant-ipfrr-tunnels] 13.2. Informative References
Bryant, S., Filsfils, C., Previdi, S., and M. Shand, "IP
Fast Reroute using tunnels", draft-bryant-ipfrr-tunnels-03
(work in progress), November 2007.
[I-D.filsfils-spring-segment-routing] [IP-FRR] Bryant, S., Filsfils, C., Previdi, S., and M. Shand, "IP
Filsfils, C., Previdi, S., Bashandy, A., Decraene, B., Fast Reroute using tunnels", Work in Progress,
Litkowski, S., Horneffer, M., Milojevic, I., Shakir, R., draft-bryant-ipfrr-tunnels-03, November 2007.
Ytti, S., Henderickx, W., Tantsura, J., and E. Crabbe,
"Segment Routing Architecture", draft-filsfils-spring-
segment-routing-04 (work in progress), July 2014.
[I-D.ietf-ospf-routable-ip-address] [ISOCORE2010]
Xu, X., Chunduri, U., and M. Bhatia, "Carrying Routable IP So, N., Lin, T., and C. Chen, "LFA (Loop Free Alternates)
Addresses in OSPF RI LSA", draft-ietf-ospf-routable-ip- Case Studies in Verizon's LDP Network", 13th Annual MPLS
address-01 (work in progress), October 2014. Conference, 2010.
[I-D.ietf-rtgwg-lfa-manageability] [LFA-MANAGE]
Litkowski, S., Decraene, B., Filsfils, C., Raza, K., Litkowski, S., Decraene, B., Filsfils, C., Raza, K.,
Horneffer, M., and P. Sarkar, "Operational management of Horneffer, M., and P. Sarkar, "Operational management of
Loop Free Alternates", draft-ietf-rtgwg-lfa- Loop Free Alternates", Work in Progress, draft-ietf-rtgwg-
manageability-07 (work in progress), January 2015. lfa-manageability-08, March 2015.
[I-D.ietf-rtgwg-rlfa-node-protection] [NODE-PROTECTION]
Sarkar, P., Gredler, H., Hegde, S., Bowers, C., Litkowski, Sarkar, P., Gredler, H., Hegde, S., Bowers, C., Litkowski,
S., and H. Raghuveer, "Remote-LFA Node Protection and S., and H. Raghuveer, "Remote-LFA Node Protection and
Manageability", draft-ietf-rtgwg-rlfa-node-protection-01 Manageability", Work in Progress, draft-ietf-rtgwg-rlfa-
(work in progress), December 2014. node-protection-01, December 2014.
[I-D.litkowski-rtgwg-uloop-delay]
Litkowski, S., Decraene, B., Filsfils, C., and P.
Francois, "Microloop prevention by introducing a local
convergence delay", draft-litkowski-rtgwg-uloop-delay-03
(work in progress), February 2014.
[ISOCORE2010] [OSPF-RI] Xu, X., Chunduri, U., and M. Bhatia, "Carrying Routable IP
So, N., Lin, T., and C. Chen, "LFA (Loop Free Alternates) Addresses in OSPF RI LSA", Work in Progress, draft-ietf-
Case Studies in Verizon's LDP Network", 2010. ospf-routable-ip-address-02, April 2015.
[RFC1195] Callon, R., "Use of OSI IS-IS for routing in TCP/IP and [RFC1195] Callon, R., "Use of OSI IS-IS for routing in TCP/IP and
dual environments", RFC 1195, December 1990. dual environments", RFC 1195, December 1990,
<http://www.rfc-editor.org/info/rfc1195>.
[RFC1701] Hanks, S., Li, T., Farinacci, D., and P. Traina, "Generic [RFC1701] Hanks, S., Li, T., Farinacci, D., and P. Traina, "Generic
Routing Encapsulation (GRE)", RFC 1701, October 1994. Routing Encapsulation (GRE)", RFC 1701, October 1994,
<http://www.rfc-editor.org/info/rfc1701>.
[RFC1853] Simpson, W., "IP in IP Tunneling", RFC 1853, October 1995. [RFC1853] Simpson, W., "IP in IP Tunneling", RFC 1853, October 1995,
<http://www.rfc-editor.org/info/rfc1853>.
[RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998. [RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998,
<http://www.rfc-editor.org/info/rfc2328>.
[RFC3032] Rosen, E., Tappan, D., Fedorkow, G., Rekhter, Y., [RFC3032] Rosen, E., Tappan, D., Fedorkow, G., Rekhter, Y.,
Farinacci, D., Li, T., and A. Conta, "MPLS Label Stack Farinacci, D., Li, T., and A. Conta, "MPLS Label Stack
Encoding", RFC 3032, January 2001. Encoding", RFC 3032, January 2001,
<http://www.rfc-editor.org/info/rfc3032>.
[RFC5036] Andersson, L., Minei, I., and B. Thomas, "LDP [RFC5036] Andersson, L., Ed., Minei, I., Ed., and B. Thomas, Ed.,
Specification", RFC 5036, October 2007. "LDP Specification", RFC 5036, October 2007,
<http://www.rfc-editor.org/info/rfc5036>.
[RFC5305] Li, T. and H. Smit, "IS-IS Extensions for Traffic [RFC5305] Li, T. and H. Smit, "IS-IS Extensions for Traffic
Engineering", RFC 5305, October 2008. Engineering", RFC 5305, October 2008,
<http://www.rfc-editor.org/info/rfc5305>.
[RFC5340] Coltun, R., Ferguson, D., Moy, J., and A. Lindem, "OSPF [RFC5340] Coltun, R., Ferguson, D., Moy, J., and A. Lindem, "OSPF
for IPv6", RFC 5340, July 2008. for IPv6", RFC 5340, July 2008,
<http://www.rfc-editor.org/info/rfc5340>.
[RFC5715] Shand, M. and S. Bryant, "A Framework for Loop-Free [RFC5715] Shand, M. and S. Bryant, "A Framework for Loop-Free
Convergence", RFC 5715, January 2010. Convergence", RFC 5715, January 2010,
<http://www.rfc-editor.org/info/rfc5715>.
[RFC6119] Harrison, J., Berger, J., and M. Bartlett, "IPv6 Traffic [RFC6119] Harrison, J., Berger, J., and M. Bartlett, "IPv6 Traffic
Engineering in IS-IS", RFC 6119, February 2011. Engineering in IS-IS", RFC 6119, February 2011,
<http://www.rfc-editor.org/info/rfc6119>.
[RFC6571] Filsfils, C., Francois, P., Shand, M., Decraene, B., [RFC6571] Filsfils, C., Ed., Francois, P., Ed., Shand, M., Decraene,
Uttaro, J., Leymann, N., and M. Horneffer, "Loop-Free B., Uttaro, J., Leymann, N., and M. Horneffer, "Loop-Free
Alternate (LFA) Applicability in Service Provider (SP) Alternate (LFA) Applicability in Service Provider (SP)
Networks", RFC 6571, June 2012. Networks", RFC 6571, June 2012,
<http://www.rfc-editor.org/info/rfc6571>.
[RFC6976] Shand, M., Bryant, S., Previdi, S., Filsfils, C., [RFC6976] Shand, M., Bryant, S., Previdi, S., Filsfils, C.,
Francois, P., and O. Bonaventure, "Framework for Loop-Free Francois, P., and O. Bonaventure, "Framework for Loop-Free
Convergence Using the Ordered Forwarding Information Base Convergence Using the Ordered Forwarding Information Base
(oFIB) Approach", RFC 6976, July 2013. (oFIB) Approach", RFC 6976, July 2013,
<http://www.rfc-editor.org/info/rfc6976>.
[RFC6987] Retana, A., Nguyen, L., Zinin, A., White, R., and D. [RFC6987] Retana, A., Nguyen, L., Zinin, A., White, R., and D.
McPherson, "OSPF Stub Router Advertisement", RFC 6987, McPherson, "OSPF Stub Router Advertisement", RFC 6987,
September 2013. September 2013, <http://www.rfc-editor.org/info/rfc6987>.
[SEGMENT-ROUTING]
Filsfils, C., Previdi, S., Bashandy, A., Decraene, B.,
Litkowski, S., Horneffer, M., Shakir, R., Tantsura, J.,
and E. Crabbe, "Segment Routing Architecture", Work in
Progress, draft-ietf-spring-segment-routing-01, February
2015.
[ULOOP-DELAY]
Litkowski, S., Decraene, B., Filsfils, C., and P.
Francois, "Microloop prevention by introducing a local
convergence delay", Work in Progress, draft-litkowski-
rtgwg-uloop-delay-03, February 2014.
Acknowledgements
The authors wish to thank Levente Csikor and Chris Bowers for their
contribution to the cost-based algorithm text. The authors thank
Alia Atlas, Ross Callon, Stephane Litkowski, Bharath R, Pushpasis
Sarkar, and Adrian Farrel for their review of this document.
Authors' Addresses Authors' Addresses
Stewart Bryant Stewart Bryant
Cisco Systems Cisco Systems
250, Longwater, Green Park, 9-11 New Square,
Reading RG2 6GB, UK Bedfont Lakes,
UK Feltham,
Middlesex TW14 8HA
United Kingdom
Email: stbryant@cisco.com EMail: stbryant@cisco.com
Clarence Filsfils Clarence Filsfils
Cisco Systems Cisco Systems
De Kleetlaan 6a De Kleetlaan 6a
1831 Diegem 1831 Diegem
Belgium Belgium
Email: cfilsfil@cisco.com EMail: cfilsfil@cisco.com
Stefano Previdi Stefano Previdi
Cisco Systems Cisco Systems
Email: sprevidi@cisco.com EMail: sprevidi@cisco.com
Mike Shand Mike Shand
Independent Contributor Independent Contributor
Email: imc.shand@gmail.com EMail: imc.shand@gmail.com
Ning So Ning So
Vinci Systems Vinci Systems
Email: ning.so@vinci-systems.com EMail: ningso@vinci-systems.com
 End of changes. 219 change blocks. 
554 lines changed or deleted 558 lines changed or added

This html diff was produced by rfcdiff 1.42. The latest version is available from http://tools.ietf.org/tools/rfcdiff/