draft-ietf-rtgwg-remote-lfa-03.txt   draft-ietf-rtgwg-remote-lfa-04.txt 
Network Working Group S. Bryant Network Working Group S. Bryant
Internet-Draft C. Filsfils Internet-Draft C. Filsfils
Intended status: Standards Track S. Previdi Intended status: Standards Track S. Previdi
Expires: May 08, 2014 Cisco Systems Expires: May 26, 2014 Cisco Systems
M. Shand M. Shand
Independent Contributor Independent Contributor
N. So N. So
Tata Communications Tata Communications
November 04, 2013 November 22, 2013
Remote LFA FRR Remote LFA FRR
draft-ietf-rtgwg-remote-lfa-03 draft-ietf-rtgwg-remote-lfa-04
Abstract Abstract
This draft describes an extension to the basic IP fast re-route This draft describes an extension to the basic IP fast re-route
mechanism described in RFC5286 that provides additional backup mechanism described in RFC5286 that provides additional backup
connectivity for link failures when none can be provided by the basic connectivity for link failures when none can be provided by the basic
mechanisms. mechanisms.
Requirements Language Requirements Language
skipping to change at page 1, line 44 skipping to change at page 1, line 44
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet- working documents as Internet-Drafts. The list of current Internet-
Drafts is at http://datatracker.ietf.org/drafts/current/. Drafts is at http://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
This Internet-Draft will expire on May 08, 2014. This Internet-Draft will expire on May 26, 2014.
Copyright Notice Copyright Notice
Copyright (c) 2013 IETF Trust and the persons identified as the Copyright (c) 2013 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
skipping to change at page 2, line 26 skipping to change at page 2, line 26
1. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 2 1. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 2
2. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3
3. Repair Paths . . . . . . . . . . . . . . . . . . . . . . . . 5 3. Repair Paths . . . . . . . . . . . . . . . . . . . . . . . . 5
3.1. Tunnels as Repair Paths . . . . . . . . . . . . . . . . . 5 3.1. Tunnels as Repair Paths . . . . . . . . . . . . . . . . . 5
3.2. Tunnel Requirements . . . . . . . . . . . . . . . . . . . 5 3.2. Tunnel Requirements . . . . . . . . . . . . . . . . . . . 5
4. Construction of Repair Paths . . . . . . . . . . . . . . . . 6 4. Construction of Repair Paths . . . . . . . . . . . . . . . . 6
4.1. Identifying Required Tunneled Repair Paths . . . . . . . 6 4.1. Identifying Required Tunneled Repair Paths . . . . . . . 6
4.2. Determining Tunnel End Points . . . . . . . . . . . . . . 6 4.2. Determining Tunnel End Points . . . . . . . . . . . . . . 6
4.2.1. Computing Repair Paths . . . . . . . . . . . . . . . 7 4.2.1. Computing Repair Paths . . . . . . . . . . . . . . . 7
4.2.2. Extended P-space . . . . . . . . . . . . . . . . . . 8 4.2.2. Selecting Repair Paths . . . . . . . . . . . . . . . 9
4.2.3. Selecting Repair Paths . . . . . . . . . . . . . . . 9 4.3. A Cost Based RLFA Algorithm . . . . . . . . . . . . . . . 10
4.3. A Cost Based RLFA Algorithm . . . . . . . . . . . . . . . 9 5. Example Application of Remote LFAs . . . . . . . . . . . . . 14
5. Example Application of Remote LFAs . . . . . . . . . . . . . 13 6. Node Failures . . . . . . . . . . . . . . . . . . . . . . . . 15
6. Node Failures . . . . . . . . . . . . . . . . . . . . . . . . 14 7. Operation in an LDP environment . . . . . . . . . . . . . . . 16
7. Operation in an LDP environment . . . . . . . . . . . . . . . 15 8. Analysis of Real World Topologies . . . . . . . . . . . . . . 17
8. Analysis of Real World Topologies . . . . . . . . . . . . . . 16 8.1. Topology Details . . . . . . . . . . . . . . . . . . . . 17
8.1. Topology Details . . . . . . . . . . . . . . . . . . . . 16 8.2. LFA only . . . . . . . . . . . . . . . . . . . . . . . . 18
8.2. LFA only . . . . . . . . . . . . . . . . . . . . . . . . 17
8.3. RLFA . . . . . . . . . . . . . . . . . . . . . . . . . . 18 8.3. RLFA . . . . . . . . . . . . . . . . . . . . . . . . . . 18
8.4. Comparison of LFA an RLFA results . . . . . . . . . . . . 19 8.4. Comparison of LFA an RLFA results . . . . . . . . . . . . 20
9. Management Considerations . . . . . . . . . . . . . . . . . . 20 9. Management Considerations . . . . . . . . . . . . . . . . . . 21
10. Historical Note . . . . . . . . . . . . . . . . . . . . . . . 20 10. Historical Note . . . . . . . . . . . . . . . . . . . . . . . 21
11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 21 11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 21
12. Security Considerations . . . . . . . . . . . . . . . . . . . 21 12. Security Considerations . . . . . . . . . . . . . . . . . . . 21
13. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 21 13. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 22
14. Informative References . . . . . . . . . . . . . . . . . . . 21 14. Informative References . . . . . . . . . . . . . . . . . . . 22
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 23 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 24
1. Terminology 1. Terminology
This draft uses the terms defined in [RFC5714]. This section defines This draft uses the terms defined in [RFC5714]. This section defines
additional terms used in this draft. additional terms used in this draft.
Extended P-space Extended P-space
The union of the P-space of the neighbours of a The union of the P-space of the neighbours of a
specific router with respect to the protected link specific router with respect to the protected link
(see Section 4.2.2). (see Section 4.2.1.2).
P-space P-space is the set of routers reachable from a P-space P-space is the set of routers reachable from a
specific router without any path (including equal cost specific router without any path (including equal cost
path splits) transiting the protected link. path splits) transiting the protected link.
For example, the P-space of S, is the set of routers For example, the P-space of S, is the set of routers
that S can reach without using the protected link S-E. that S can reach without using the protected link S-E.
PQ node A node which is a member of both the (extended) PQ node A node which is a member of both the (extended)
P-space and the Q-space. In remote LFA this is used P-space and the Q-space. In remote LFA this is used
as the repair tunnel endpoint. as the repair tunnel endpoint.
Q-space Q-space is the set of routers from which a specific Q-space Q-space is the set of routers from which a specific
router can be reached without any path (including router can be reached without any path (including
equal cost path splits) transiting the protected link. equal cost path splits) transiting the protected link.
Repair tunnel A tunnel established for the purpose of providing a Repair tunnel A tunnel established for the purpose of providing a
virtual neighbor which is a Loop Free Alternate. virtual neighbor which is a Loop Free Alternate.
Remote LFA The use of a PQ node rather than a neighbour of the Remote LFA (RLFA) The use of a PQ node rather than a neighbour of
repairing node as the next hop in an LFA repair. the repairing node as the next hop in an LFA repair.
In this document we use the notation X-Y to mean the path from X to Y In this document we use the notation X-Y to mean the path from X to Y
over the link directly connecting X and Y, whilst the notation X->Y over the link directly connecting X and Y, whilst 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. Introduction 2. Introduction
RFC 5714 [RFC5714] describes a framework for IP Fast Re-route and RFC 5714 [RFC5714] describes a framework for IP Fast Re-route and
skipping to change at page 5, line 21 skipping to change at page 5, line 21
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 assumed that, in the absence of multiple network from which it is assumed that, in the absence of multiple
failures, it will travel to its destination using normal forwarding failures, it will travel to its destination using normal forwarding
without looping back. This is equivalent to providing a virtual without looping back. This is equivalent to providing a virtual
loop-free alternate to supplement the physical loop-free alternates. loop-free alternate to supplement the physical loop-free alternates.
Hence the name "Remote LFA FRR". In its simplest form, when a link Hence the name "Remote LFA FRR". In its simplest form, when a link
cannot be entirely protected with local LFA neighbors, the protecting cannot be entirely protected with local LFA neighbors, the protecting
router seeks the help of a remote LFA staging point. Network router seeks the help of a remote LFA staging point. 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 [I-D.ietf-rtgwg-lfa-manageability].]
3.1. Tunnels as Repair Paths 3.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 S 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 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 which
skipping to change at page 6, line 11 skipping to change at page 6, line 11
stack[RFC3032] may be used to provide the required repair tunnel. In stack[RFC3032] may be used to provide the required repair tunnel. In
this case the outer label is S's neighbor's label for the repair this case the outer label is S's neighbor's label for the repair
tunnel end point, and the inner label is the repair tunnel end tunnel end point, and the inner label is the repair tunnel end
point's label for the packet destination. In order for S to obtain point's label for the packet destination. In order for S to obtain
the correct inner label it is necessary to establish a directed LDP the correct inner label it is necessary to establish a directed LDP
session[RFC5036] to the tunnel end point. session[RFC5036] to the tunnel end point.
The selection of the specific tunnelling mechanism (and any necessary The selection of the specific tunnelling 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 dataplane as an LDP LSP from S to the repair relatively simple in the data plane as an LDP LSP from S to the
tunnel endpoint (the selected PQ node) is readily available, and repair tunnel endpoint (the selected PQ node) is readily available,
hence does not require any new protocol extension or design change. and hence does not require any new protocol extension or design
This LSP is automatically established as a basic property of LDP change. This LSP is automatically established as a basic property of
behavior. The performance of the encapsulation and decapsulation is LDP behavior. The performance of the encapsulation and decapsulation
efficient as encapsulation is just a push of one label (like is efficient as encapsulation is just a push of one label (like
conventional MPLS TE FRR) and the decapsulation occurs naturally at conventional MPLS TE FRR) and the decapsulation occurs naturally at
the penultimate hop before the repair tunnel endpoint. In the the penultimate hop before the repair tunnel endpoint. In the
control plane, a targeted LDP (TLDP) session is needed between the control plane, a targeted LDP (TLDP) session is needed between the
repairing node and the repair tunnel endpoint, which will need to be repairing node and the repair tunnel endpoint, which will need to be
established and the labels processed before the tunnel can be used. established and the labels processed before the tunnel can be used.
The time to establish the TLDP session and acquire labels will limit The time to establish the TLDP session and acquire labels will limit
the speed at which a new tunnel can be put into service, but this the speed at which a new tunnel can be put into service, but this
will not be a problem in normal operation. will not be a problem in normal operation.
When a failure is detected, it is necessary to immediately redirect When a failure is detected, it is necessary to immediately redirect
skipping to change at page 7, line 37 skipping to change at page 7, line 37
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 4 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 cost 1, then it would not be
possible to establish a tunnel from S to C (without resorting to some possible to establish a tunnel from S to C (without resorting to some
form of source routing). form of source routing).
4.2.1. Computing Repair Paths 4.2.1. Computing Repair Paths
To compute the repair path for link S-E we need to determine the set
of routers which can be reached from S without traversing S-E, and
match this with the set of routers from which the node E can be
reached, by normal forwarding, without traversing the link S-E.
We will proceed as follows: we will describe how to compute the set
of routers which can be reached from S without traversing S-E. We
call this the S's P-space with respect to the failure of link S-E. We
will then note that S is able to use P-Space of its neighbours since
S can determine which neighbour it will use as the next hop for the
repair. We call this the S's Extended P-Space with respect to the
failure of link S-E. The use of extended P-Space allows greater
repair coverage and is the preferred approach. Finally we will show
how to compute the set of routers from which 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 link S-E. The
selection of the preferred node from the set of nodes that an in both
Extended P-Space and Q-Space is described in Section 4.2.2.
A suitable cost based algorithm to compute the set of nodes common to
both extended P-space and Q-space is provide in Section 4.3.
4.2.1.1. P-space
The set of routers which can be reached from S without traversing S-E The set of routers which can be reached from S without traversing S-E
is termed the P-space of S with respect to the link S-E. The P-space is termed the P-space of S with respect to the link S-E. The P-space
can be obtained by computing a shortest path tree (SPT) rooted at S can be obtained by computing a shortest path tree (SPT) rooted at S
and excising the sub-tree reached via the link S-E (including those and excising the sub-tree reached via the link S-E (including those
which are members of an ECMP). In the case of Figure 1 the P-space which are members of an ECMP). In the case of Figure 1 the P-space
comprises nodes A and B only. Expressed in cost terms the set of comprises nodes A and B only. Expressed in cost terms the set of
routers {P} are those for which the shortest path cost S->P is routers {P} are those for which the shortest path cost S->P is
strictly less than the shortest path cost S->E->P. strictly less than the shortest path cost S->E->P.
4.2.1.2. Extended P-space
The description in Section 4.2.1.1 calculated router S's P-space
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
hop of the repair path need not be subject to S's normal forwarding
decision process. Thus we introduce the concept of extended P-space.
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 an SPT at
each of S's neighbors (excluding E) and excising the subtree reached
via the path N->S->E. The use of extended P-space may allow router S
to reach potential repair tunnel end points that were otherwise
unreachable. In cost terms a router (P) is in extended P-space if
the shortest path cost N->P is strictly less than the shortest path
cost N->S->E->P. In other words, once the packet it forced to N by S,
it is lower cost for it to continue on to P by any path except one
that takes it back to S and then across the S->E link.
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 comprises nodes
A, B and C. Since node C is also in E's Q-space, there is now a node
common to both extended P-space and Q-space which can be used as a
repair tunnel end-point to protect the link S-E.
4.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 traverses the failed link excised (including those sub-tree which traverses the failed link excised (including those
which are members of an ECMP). The rSPT uses the cost towards the which are members of an ECMP). The rSPT uses the cost towards the
root rather than from it and yields the best paths towards the root 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 Q-space from other nodes in the network. In the case of Figure 1 the Q-space
comprises nodes C and D only. Expressed in cost terms the set of comprises nodes C and D only. Expressed in cost terms the set of
routers {Q} are those for which the shortest path cost Q->E is routers {Q} are those for which the shortest path cost Q->E is
skipping to change at page 8, line 24 skipping to change at page 9, line 26
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 which is not currently considered to be
scalable. We therefore use the Q-space of E as a proxy for the scalable. We therefore use the Q-space of E as a proxy for the
Q-space of each destination. This approximation is obviously correct Q-space of each destination. This approximation is obviously correct
since the repair is only used for the set of destinations which were, since the repair is only used for the set of destinations which were,
prior to the failure, routed through node E. This is analogous to the prior to the failure, routed through node E. This is analogous to the
use of link-LFAs rather than per-prefix LFAs. use of link-LFAs rather than per-prefix LFAs.
4.2.2. Extended P-space 4.2.2. Selecting Repair Paths
The description in Section 4.2.1 calculated router S's P-space 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 hop of
the repair path need not be subject to S's normal forwarding decision
process. Thus we introduce the concept of extended P-space. 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 an SPT at each
of S's neighbors (excluding E) and excising the subtree reached via
the path N->S->E. The use of extended P-space may allow router S to
reach potential repair tunnel end points that were otherwise
unreachable. In cost terms a router (P) is in extended P-space if
the shortest path cost N->P is strictly less than the shortest path
cost N->S->E->P. In other words, once the packet it forced to N by S,
it is lower cost for it to continue on to P by any path except one
that takes it back to S and then across the S->E link.
Another way to describe extended P-space is that it is the union of (
un-extended ) P-space and the set of destinations for which S has a
per-prefix LFA protecting the link S-E. i.e. the repair tunnel end
point can be reached either directly or using a per-prefix LFA.
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 comprises nodes
A, B and C. Since node C is also in E's Q-space, there is now a node
common to both extended P-space and Q-space which can be used as a
repair tunnel end-point to protect the link S-E.
4.2.3. 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 end points that can be used to protect a particular link. In
a well-connected network there are likely to be multiple possible a 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 end point 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 end point closest (shortest metric) to
S. Choosing the closest maximises the opportunity for the traffic to S. Choosing the closest maximises 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, is RECOMMENDED that member of the set of consistency in behavior, is RECOMMENDED that member of the set of
routers {PQ} with the lowest cost S->P be the default choice for P. 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 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
the router favours LFA repairs over RLFA repairs. An LFA repair has
the advantage of not requiring the use of tunnel, however network
manageability considerations may lead to a repair strategy that uses
a remote LFA more frequently [I-D.ietf-rtgwg-lfa-manageability].
As described in [RFC5286], always selecting a PQ node that is
downstream with respect to the repairing node, prevents the formation
of loops when the failure is worse than expected. The use of
downstream nodes reduces the repair coverage, and operators are
advised to determine whether adequate coverage is achieved before
enabling this selection feature.
4.3. A Cost Based RLFA Algorithm 4.3. A Cost Based RLFA Algorithm
The preceding text has mostly described the computation of the remote The preceding text has mostly described the computation of the remote
LFA repair target (PQ) in terms of the intersection of two LFA repair target (PQ) in terms of the intersection of two
reachability graphs computed using SPFs. This section describes a reachability graphs computed using SPFs. This section describes a
method of computing the remote LFA repair target using a cost based method of computing the remote LFA repair target using a cost based
algorithm. The pseudo-code provides in this section avoids algorithm. The pseudo-code provides in this section avoids
unnecessary SPF computations, but for the sake of readability, it unnecessary SPF computations, but for the sake of readability, it
does not otherwise try to optimize the code. Unconventionally, but does not otherwise try to optimize the code. In this description
for clarity, we provide the main algorithm followed its procedures. D_opt(a,b) is the shortest distance from node a to node b as computed
In this description D_opt(a,b) is the shortest distance from node a by the SPF.
to node b as computed by the SPF.
The following notation is used:
o D_opt(a,b) is the shortest distance from node a to node b as
computed by the SPF.
o dest is the packet destination
o fail_intf is the failed interface (S-E in the example)
o fail_intf.remote_node is the node reachable over interface
fail_intf (node E in the example)
o intf.remote_node is the node reachable over interface intf
o root is the root of the SPF calculation
o self is the node carrying out the computation
o y is the node in the network under consideration
////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////
// //
// 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.
skipping to change at page 11, line 4 skipping to change at page 11, line 41
// 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
// //
////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////
// //
// Proceedures // 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 neighbour (other
// than the neighbour reachable through the failed link) and // than the neighbour reachable through the failed link) and
// every other node in the network // every other node in the network
skipping to change at page 11, line 44 skipping to change at page 12, line 34
// 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 P space and then extend it by the P-spaces of each // Calculate extended P-space
// neighbour other than the one reachable via the link being //
// protected. Note the strictly less than operator is needed to // Note 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 // neighbours
foreach interface intf in self foreach interface intf in self
if (intf.remote_node != fail_intf.remote_node) if (intf.remote_node != fail_intf.remote_node)
if ( D_opt(intf.remote_node, y) < if ( D_opt(intf.remote_node, y) <
D_opt(intf.remote_node, self) + D_opt(intf.remote_node, self) +
D_opt(self,fail_intf.remote_node) + D_opt(self,fail_intf.remote_node) +
D_opt(fail_intf.remote_node,y) ) D_opt(fail_intf.remote_node,y) )
y.in_extended_P_space = true y.in_extended_P_space = true
///////////////////////////////////////////////////////////////// /////////////////////////////////////////////////////////////////
// //
// 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 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 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
skipping to change at page 15, line 27 skipping to change at page 16, line 14
failure in their network, and determine whether the incidence and failure in their network, and determine whether the incidence and
consequence of occurrence are acceptable. consequence of occurrence are acceptable.
This topic is further discussed in This topic is further discussed in
[I-D.psarkar-rtgwg-rlfa-node-protection]. [I-D.psarkar-rtgwg-rlfa-node-protection].
7. Operation in an LDP environment 7. 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 rthe emote LFA repair target's (PQ's) label to the stack for the emote 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 Section 2 S already has the first hop (A) label for In the example Section 2 S already has the first hop (A) label for
the remote LFA repair target (C) as a result of the ordinary the remote LFA repair target (C) as a result of the ordinary
operation of LDP. To get the remote LFA repair target's label (C's operation of LDP. To get the remote LFA repair target's label (C's
label) for the destination (D), S needs to establish a targeted LDP label) for the destination (D), S needs to establish a targeted LDP
session with C. The label stack for normal operation and RLFA session with C. The label stack for normal operation and RLFA
operation is shown below in Figure 4. operation is shown below in Figure 4.
skipping to change at page 16, line 18 skipping to change at page 17, line 16
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 that the remote LFA repair target is willing to use for
targeted LDP sessions. Ideally this is provided by the remote LFA targeted LDP sessions. Ideally this is provided by the remote LFA
repair target advertising this address in the IGP in use. Which repair target advertising this address in the IGP in use. Which
address is used, how this is advertised in the IGP, and whether this address is used, how this is advertised in the IGP, and whether this
is a special IP address or an IP address also used for some other is a special IP address or an IP address also used for some other
purpose is out of scope for this document and must be specified in an purpose 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, a tie-breaking mechanism is required. Unless otherwise targeted LDP, an LSR should attempt a targeted LDP session with the
configured, an LSR should attempt a targeted LDP session with the Router ID [RFC2328] [RFC5305] [RFC5340], unless it is configured
local IP address with the lowest numerical value advertised by the otherwise.
target LSR. To determine the lowest numerical value the address is
taken in network byte order and cast to an integer of appropriate
size.
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
not be established, an implementation SHOULD advise the operator not be established, an implementation SHOULD advise the operator
about the protection setup issue using any well known mechanism such about the protection setup issue using any well known mechanism such
as syslog or SNMP. as Syslog [RFC5424] or SNMP [RFC3411].
8. Analysis of Real World Topologies 8. Analysis of Real World Topologies
This section gives the results of analysing a number of real world This section gives the results of analysing a number of real world
service provider topologies collected between October 2012 and the service provider topologies collected between October 2012 and the
date of this draft. date of this draft.
8.1. Topology Details 8.1. Topology Details
The figure below characterises each topology (topo) studied in terms The figure below characterises each topology (topo) studied in terms
skipping to change at page 20, line 38 skipping to change at page 21, line 16
traffic between non-collocated P and Q nodes traffic between non-collocated P and Q nodes
[I-D.filsfils-rtgwg-segment-routing-use-cases], [I-D.filsfils-rtgwg-segment-routing-use-cases],
[I-D.filsfils-rtgwg-segment-routing], [I-D.filsfils-rtgwg-segment-routing],
[I-D.gredler-rtgwg-igp-label-advertisement]. [I-D.gredler-rtgwg-igp-label-advertisement].
9. Management Considerations 9. Management 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 withing the IETF[I-D.ietf-rtgwg-lfa-manageability] to which the
reader is referred. Management considerations may lead to a reader is referred. Management considerations may lead to a
preference for the use of a remote LFA over an avalaible LFA. This preference for the use of a remote LFA over an available LFA. This
preference is a matter for the network operator, and not a matter of preference is a matter for the network operator, and not a matter of
protocol correctness. protocol correctness.
10. Historical Note 10. 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 [I-D.bryant-ipfrr-tunnels], submitted in 2004.
[I-D.bryant-ipfrr-tunnels], targeted a 100% protection coverage and [I-D.bryant-ipfrr-tunnels], targeted a 100% protection coverage and
hence included additional mechanisms on top of the Remote LFA hence included additional mechanisms on top of the Remote LFA
skipping to change at page 22, line 26 skipping to change at page 22, line 50
"Advertising MPLS labels in IGPs", draft-gredler-rtgwg- "Advertising MPLS labels in IGPs", draft-gredler-rtgwg-
igp-label-advertisement-05 (work in progress), May 2013. igp-label-advertisement-05 (work in progress), May 2013.
[I-D.ietf-rtgwg-lfa-manageability] [I-D.ietf-rtgwg-lfa-manageability]
Litkowski, S., Decraene, B., Filsfils, C., and K. Raza, Litkowski, S., Decraene, B., Filsfils, C., and K. Raza,
"Operational management of Loop Free Alternates", draft- "Operational management of Loop Free Alternates", draft-
ietf-rtgwg-lfa-manageability-00 (work in progress), May ietf-rtgwg-lfa-manageability-00 (work in progress), May
2013. 2013.
[I-D.psarkar-rtgwg-rlfa-node-protection] [I-D.psarkar-rtgwg-rlfa-node-protection]
psarkar@juniper.net, p., Gredler, H., Hegde, S., and H. psarkar@juniper.net, p., Gredler, H., Hegde, S.,
Raghuveer, "Node Protecting R-LFA and Manageability", Raghuveer, H., cbowers@juniper.net, c., and S. Litkowski,
draft-psarkar-rtgwg-rlfa-node-protection-01 (work in "Remote-LFA Node Protection and Manageability", draft-
progress), July 2013. psarkar-rtgwg-rlfa-node-protection-02 (work in progress),
November 2013.
[ISOCORE2010] [ISOCORE2010]
So, N., Lin, T., and C. Chen, "LFA (Loop Free Alternates) So, N., Lin, T., and C. Chen, "LFA (Loop Free Alternates)
Case Studies in Verizon's LDP Network", 2010. Case Studies in Verizon's LDP Network", 2010.
[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.
[RFC1853] Simpson, W., "IP in IP Tunneling", RFC 1853, October 1995. [RFC1853] Simpson, W., "IP in IP Tunneling", RFC 1853, October 1995.
[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.
[RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998.
[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.
[RFC3411] Harrington, D., Presuhn, R., and B. Wijnen, "An
Architecture for Describing Simple Network Management
Protocol (SNMP) Management Frameworks", STD 62, RFC 3411,
December 2002.
[RFC5036] Andersson, L., Minei, I., and B. Thomas, "LDP [RFC5036] Andersson, L., Minei, I., and B. Thomas, "LDP
Specification", RFC 5036, October 2007. Specification", RFC 5036, October 2007.
[RFC5286] Atlas, A. and A. Zinin, "Basic Specification for IP Fast [RFC5286] Atlas, A. and A. Zinin, "Basic Specification for IP Fast
Reroute: Loop-Free Alternates", RFC 5286, September 2008. Reroute: Loop-Free Alternates", RFC 5286, September 2008.
[RFC5305] Li, T. and H. Smit, "IS-IS Extensions for Traffic
Engineering", RFC 5305, October 2008.
[RFC5340] Coltun, R., Ferguson, D., Moy, J., and A. Lindem, "OSPF
for IPv6", RFC 5340, July 2008.
[RFC5424] Gerhards, R., "The Syslog Protocol", RFC 5424, March 2009.
[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.
[RFC6571] Filsfils, C., Francois, P., Shand, M., Decraene, B., [RFC6571] Filsfils, C., Francois, P., Shand, M., Decraene, B.,
Uttaro, J., Leymann, N., and M. Horneffer, "Loop-Free 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.
Authors' Addresses Authors' Addresses
 End of changes. 29 change blocks. 
81 lines changed or deleted 148 lines changed or added

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