draft-ietf-rtgwg-ipfrr-notvia-addresses-09.txt   draft-ietf-rtgwg-ipfrr-notvia-addresses-10.txt 
Network Working Group S. Bryant Network Working Group S. Bryant
Internet-Draft S. Previdi Internet-Draft S. Previdi
Intended status: Informational Cisco Systems Intended status: Informational Cisco Systems
Expires: December 11, 2012 M. Shand Expires: June 22, 2013 M. Shand
Individual Contributor Individual Contributor
June 9, 2012 December 19, 2012
IP Fast Reroute Using Not-via Addresses A Framework for IP and MPLS Fast Reroute Using Not-via Addresses
draft-ietf-rtgwg-ipfrr-notvia-addresses-09 draft-ietf-rtgwg-ipfrr-notvia-addresses-10
Abstract Abstract
This draft describes a mechanism that provides fast reroute in an IP This document presents a framework for providing fast reroute in an
network through encapsulation to "not-via" addresses. A single level IP or MPLS network through encapsulation and forwarding to "not-via"
of encapsulation is used. The mechanism protects unicast, multicast addresses. The general approach described uses a single level of
and LDP traffic against link, router and shared risk group failure, encapsulation and could be used to protect unicast, multicast, and
LDP traffic against link, router, and shared risk group failure,
regardless of network topology and metrics. regardless of network topology and metrics.
The mechanisms presented in this document are purely illustrative of
the general approach and do not constitute a protocol specification.
The document represents a snapshot of the work of the Routing Area
Working Group at the time of publication and is published as a
document of record. Further work is needed before implementation or
deployment.
Requirements Language Requirements Language
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC2119 [RFC2119]. 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 Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79. provisions of BCP 78 and BCP 79.
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 June 22, 2013.
This Internet-Draft will expire on December 11, 2012.
Copyright Notice Copyright Notice
Copyright (c) 2012 IETF Trust and the persons identified as the Copyright (c) 2012 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 . . . . . . . . . . . . . . . . . . . . . . . . . 4 1. The Purpose of this Document . . . . . . . . . . . . . . . . . 4
2. Overview of Not-via Repairs . . . . . . . . . . . . . . . . . 4 2. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.1. Use of Equal Cost Multi-Path . . . . . . . . . . . . . . . 5 3. Overview of Not-via Repairs . . . . . . . . . . . . . . . . . 5
2.2. Use of LFA repairs . . . . . . . . . . . . . . . . . . . . 5 3.1. Use of Equal Cost Multi-Path . . . . . . . . . . . . . . . 6
3. Not-via Repair Path Computation . . . . . . . . . . . . . . . 6 3.2. Use of LFA repairs . . . . . . . . . . . . . . . . . . . . 6
3.1. Computing not-via repairs in distance and path vector 4. Not-via Repair Path Computation . . . . . . . . . . . . . . . 7
routing protocols . . . . . . . . . . . . . . . . . . . . 7 4.1. Computing not-via repairs in distance and path vector
4. Operation of Repairs . . . . . . . . . . . . . . . . . . . . . 7 routing protocols . . . . . . . . . . . . . . . . . . . . 8
4.1. Node Failure . . . . . . . . . . . . . . . . . . . . . . . 8 5. Operation of Repairs . . . . . . . . . . . . . . . . . . . . . 8
4.2. Link Failure . . . . . . . . . . . . . . . . . . . . . . . 8 5.1. Node Failure . . . . . . . . . . . . . . . . . . . . . . . 8
4.2.1. Loop Prevention Under Node Failure . . . . . . . . . . 8 5.2. Link Failure . . . . . . . . . . . . . . . . . . . . . . . 9
4.3. Multi-homed Prefixes . . . . . . . . . . . . . . . . . . . 9 5.2.1. Loop Prevention Under Node Failure . . . . . . . . . . 9
4.4. Installation of Repair Paths . . . . . . . . . . . . . . . 10 5.3. Multi-homed Prefixes . . . . . . . . . . . . . . . . . . . 9
5. Compound Failures . . . . . . . . . . . . . . . . . . . . . . 11 5.4. Installation of Repair Paths . . . . . . . . . . . . . . . 11
5.1. Shared Risk Link Groups . . . . . . . . . . . . . . . . . 11 6. Compound Failures . . . . . . . . . . . . . . . . . . . . . . 12
5.2. Local Area Networks . . . . . . . . . . . . . . . . . . . 16 6.1. Shared Risk Link Groups . . . . . . . . . . . . . . . . . 12
5.2.1. Simple LAN Repair . . . . . . . . . . . . . . . . . . 17 6.2. Local Area Networks . . . . . . . . . . . . . . . . . . . 16
5.2.2. LAN Component Repair . . . . . . . . . . . . . . . . . 17 6.2.1. Simple LAN Repair . . . . . . . . . . . . . . . . . . 17
5.2.3. LAN Repair Using Diagnostics . . . . . . . . . . . . . 18 6.2.2. LAN Component Repair . . . . . . . . . . . . . . . . . 18
5.3. Multiple Independent Failures . . . . . . . . . . . . . . 18 6.2.3. LAN Repair Using Diagnostics . . . . . . . . . . . . . 19
5.3.1. Looping Repairs . . . . . . . . . . . . . . . . . . . 19 6.3. Multiple Independent Failures . . . . . . . . . . . . . . 19
5.3.2. Outline Solution . . . . . . . . . . . . . . . . . . . 20 6.3.1. Looping Repairs . . . . . . . . . . . . . . . . . . . 20
5.3.3. Looping Repairs . . . . . . . . . . . . . . . . . . . 21 6.3.2. Outline Solution . . . . . . . . . . . . . . . . . . . 21
5.3.3.1. Dropping Looping Packets . . . . . . . . . . . . . 21 6.3.3. Looping Repairs . . . . . . . . . . . . . . . . . . . 22
5.3.3.2. Computing non-looping Repairs of Repairs . . . . . 22 6.3.3.1. Dropping Looping Packets . . . . . . . . . . . . . 22
5.3.4. Mixing LFAs and Not-via . . . . . . . . . . . . . . . 24 6.3.3.2. Computing non-looping Repairs of Repairs . . . . . 23
6. Optimizing not-via computations using LFAs . . . . . . . . . . 25 6.3.4. Mixing LFAs and Not-via . . . . . . . . . . . . . . . 25
7. Multicast . . . . . . . . . . . . . . . . . . . . . . . . . . 26 7. Optimizing not-via computations using LFAs . . . . . . . . . . 26
8. Fast Reroute in an MPLS LDP Network. . . . . . . . . . . . . . 26 8. Multicast . . . . . . . . . . . . . . . . . . . . . . . . . . 27
9. Encapsulation . . . . . . . . . . . . . . . . . . . . . . . . 26 9. Fast Reroute in an MPLS LDP Network. . . . . . . . . . . . . . 27
10. Routing Extensions . . . . . . . . . . . . . . . . . . . . . . 27 10. Encapsulation . . . . . . . . . . . . . . . . . . . . . . . . 27
11. Incremental Deployment . . . . . . . . . . . . . . . . . . . . 27 11. Routing Extensions . . . . . . . . . . . . . . . . . . . . . . 28
12. Manageability Considerations . . . . . . . . . . . . . . . . . 27 12. Incremental Deployment . . . . . . . . . . . . . . . . . . . . 28
12.1. Pre-failure configuration . . . . . . . . . . . . . . . . 28 13. Manageability Considerations . . . . . . . . . . . . . . . . . 28
12.2. Pre-failure Monitoring and operational support . . . . . . 28 13.1. Pre-failure configuration . . . . . . . . . . . . . . . . 29
12.3. Failure action monitoring . . . . . . . . . . . . . . . . 29 13.2. Pre-failure Monitoring and operational support . . . . . . 29
13. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 29 13.3. Failure action monitoring . . . . . . . . . . . . . . . . 30
14. Security Considerations . . . . . . . . . . . . . . . . . . . 29 14. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 30
15. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 30 15. Security Considerations . . . . . . . . . . . . . . . . . . . 30
16. References . . . . . . . . . . . . . . . . . . . . . . . . . . 30 16. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 31
16.1. Normative References . . . . . . . . . . . . . . . . . . . 30 17. References . . . . . . . . . . . . . . . . . . . . . . . . . . 31
16.2. Informative References . . . . . . . . . . . . . . . . . . 30 17.1. Normative References . . . . . . . . . . . . . . . . . . . 31
Appendix A. Q-Space . . . . . . . . . . . . . . . . . . . . . . . 31 17.2. Informative References . . . . . . . . . . . . . . . . . . 31
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 31 Appendix A. Q-Space . . . . . . . . . . . . . . . . . . . . . . . 32
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 32
1. Introduction 1. The Purpose of this Document
This document presents a framework for providing fast re-route around
a failure in an IP or MPLS network based on the concept tunnelling or
encapsulating packets via an IP address that is known to avoid the
failure. The general approach described uses a single level of
encapsulation and could be used to protect unicast, multicast, and
LDP traffic against link, router, and shared risk group failure,
regardless of network topology and metrics.
At the time of publication there is no demand to deploy this
technology, however in view of the subtleties involved in the design
of routing protocol extensions to provide IP Fast Reroute (IPFRR) the
Routing Area Working Group considered it desirable to publish this
document to place on record the design consideration of the not-via
address approach.
The mechanisms presented in this document are purely illustrative of
the general approach and do not constitute a protocol specification.
The document represents a snapshot of the work of the working group
at the time of publication and is published as a document of record.
Additional work is needed to specify the necessary routing protocol
extensions necessary to support this IPFRR method before
implementation or deployment.
2. Introduction
When a link or a router fails, only the neighbors of the failure are When a link or a router fails, only the neighbors of the failure are
initially aware that the failure has occurred. In a network initially aware that the failure has occurred. In a network
operating IP fast reroute [RFC5714], the routers that are the operating IP fast reroute [RFC5714], the routers that are the
neighbors of the failure repair the failure. These repairing routers neighbors of the failure repair the failure. These repairing routers
have to steer packets to their destinations despite the fact that have to steer packets to their destinations despite the fact that
most other routers in the network are unaware of the nature and most other routers in the network are unaware of the nature and
location of the failure. location of the failure.
A common limitation in most IPFRR mechanisms is an inability to A common limitation in most IPFRR mechanisms is an inability to
indicate the identity of the failure and to explicitly steer the indicate the identity of the failure and to explicitly steer the
repaired packet round the failure. The extent to which this repaired packet round the failure. The extent to which this
limitation affects the repair coverage is topology dependent. The limitation affects the repair coverage is topology dependent. The
mechanism proposed here is to encapsulate the packet to an address mechanism proposed here is to encapsulate the packet to an address
that explicitly identifies the network component that the repair must that explicitly identifies the network component that the repair must
avoid. This produces a repair mechanism, which, provided the network avoid. This produces a repair mechanism, which, provided the network
is not partitioned by the failure, will always achieve a repair. is not partitioned by the failure, will always achieve a repair.
2. Overview of Not-via Repairs 3. Overview of Not-via Repairs
This section provides a brief overview of the not-via method of This section provides a brief overview of the not-via method of
IPFRR. Consider the network fragment shown in Figure 1 below, in IPFRR. Consider the network fragment shown in Figure 1 below, in
which S has a packet for some destination D that it would normally which S has a packet for some destination D that it would normally
send via P and B, and that S suspects that P has failed. send via P and B, and that S suspects that P has failed.
A A
| Bp is the address to use to get | Bp is the address to use to get
| a packet to B not-via P | a packet to B not-via P
| |
skipping to change at page 4, line 49 skipping to change at page 5, line 30
\ C | \ C |
\ | \ |
X-------Y-------Z X-------Y-------Z
Repair to Bp Repair to Bp
Figure 1: Not-via repair of router failure Figure 1: Not-via repair of router failure
In the not-via IPFRR method, S encapsulates the packet to Bp, where In the not-via IPFRR method, S encapsulates the packet to Bp, where
Bp is an address on node B that has the property that it is not Bp is an address on node B that has the property that it is not
reachable from node P, i.e. the notation Bp means "an address of node reachable from node P, i.e. the notation Bp means "an address of node
B that is only reachable not via node P. We later show how to install B that is only reachable not via node P". We later show how to
the path from S to Bp such that it is the shortest path from S to B install the path from S to Bp such that it is the shortest path from
not going via P. If the network contains a path from S to B that does S to B not going via P. If the network contains a path from S to B
not transit router P, i.e. the network is not partitioned by the that does not transit router P, i.e. the network is not partitioned
failure of P and the path from S to Bp has been installed, then the by the failure of P and the path from S to Bp has been installed,
packet will be successfully delivered to B. In the example we are then the packet will be successfully delivered to B. In the example
considering this is the path S-X-Y-Z-B. When the packet addressed to we are considering this is the path S-X-Y-Z-B. When the packet
Bp arrives at B, B removes the encapsulation and forwards the addressed to Bp arrives at B, B removes the encapsulation and
repaired packet towards its final destination. forwards the repaired packet towards its final destination.
Note that if the path from B to the final destination includes one or Note that if the path from B to the final destination includes one or
more nodes that are included in the repair path, a packet MAY back more nodes that are included in the repair path, a packet MAY back
track after the encapsulation is removed. However, because the track after the encapsulation is removed. However, because the
decapsulating router is always closer to the packet destination than decapsulating router is always closer to the packet destination than
the encapsulating router, the packet will not loop. the encapsulating router, the packet will not loop.
For complete protection, all of P's neighbors will require a not-via For complete protection, all of P's neighbors will require a not-via
address that allows traffic to be directed to them without traversing address that allows traffic to be directed to them without traversing
P. This is shown in Figure 2. Similarly, P will require a set of P. This is shown in Figure 2. Similarly, P will require a set of
skipping to change at page 5, line 39 skipping to change at page 6, line 19
| |
Sp Pa|Pb Sp Pa|Pb
S----------P----------B S----------P----------B
Ps|Pc Bp Ps|Pc Bp
| |
Cp| Cp|
C C
Figure 2: The set of Not-via P Addresses Figure 2: The set of Not-via P Addresses
2.1. Use of Equal Cost Multi-Path 3.1. Use of Equal Cost Multi-Path
A router can use an equal cost multi-path (ECMP) repair in place of a A router can use an equal cost multi-path (ECMP) repair in place of a
not-via repair. not-via repair.
A router computing a not-via repair path MAY subject the repair to A router computing a not-via repair path MAY subject the repair to
ECMP. ECMP.
2.2. Use of LFA repairs 3.2. Use of LFA repairs
The not-via approach provides complete repair coverage and therefore The not-via approach provides complete repair coverage and therefore
MAY be used as the sole repair mechanism. There are, however, MAY be used as the sole repair mechanism. There are, however,
advantages in using not-via in combination with loop free alternates advantages in using not-via in combination with loop free alternates
(LFA) and or downstream paths as documented in [RFC5286]. In (LFA) and or downstream paths as documented in [RFC5286]. In
particular LFAs do not require the assignment and management of particular LFAs do not require the assignment and management of
additional IP addresses to nodes, they do not require nodes in the additional IP addresses to nodes, they do not require nodes in the
network to be upgraded in order to calculate not-via repair paths, network to be upgraded in order to calculate not-via repair paths,
and they do not require the use of encapsulation. and they do not require the use of encapsulation.
skipping to change at page 6, line 22 skipping to change at page 7, line 5
repair. In this case, those destinations which are repairable by repair. In this case, those destinations which are repairable by
LFAs are so repaired and the remainder of the destinations are LFAs are so repaired and the remainder of the destinations are
repaired using the not-via encapsulation. On the other hand, the repaired using the not-via encapsulation. On the other hand, the
path taken by an LFA repair may be less optimal than that of the path taken by an LFA repair may be less optimal than that of the
equivalent not-via repair for traffic destined to nodes close to the equivalent not-via repair for traffic destined to nodes close to the
far end of the failure, but may be more optimal for some other far end of the failure, but may be more optimal for some other
traffic. The description in this document assumes that LFAs will be traffic. The description in this document assumes that LFAs will be
used where available, but the distribution of repairs between the two used where available, but the distribution of repairs between the two
mechanisms is a local implementation choice. mechanisms is a local implementation choice.
3. Not-via Repair Path Computation 4. Not-via Repair Path Computation
The not-via repair mechanism requires that all routers on the path The not-via repair mechanism requires that all routers on the path
from S to B (Figure 1) have a route to Bp. They can calculate this from S to B (Figure 1) have a route to Bp. They can calculate this
by failing node P, running a Shortest Path First Algorithm (SPF), and by failing node P, running a Shortest Path First Algorithm (SPF), and
finding the shortest route to B. finding the shortest route to B.
A router has no simple way of knowing whether it is on the shortest A router has no simple way of knowing whether it is on the shortest
path for any particular repair. It is therefore necessary for every path for any particular repair. It is therefore necessary for every
router to calculate the path it would use in the event of any router to calculate the path it would use in the event of any
possible router failure. Each router therefore "fails" every router possible router failure. Each router therefore "fails" every router
skipping to change at page 7, line 26 skipping to change at page 8, line 7
This algorithm is significantly less expensive than a set of full This algorithm is significantly less expensive than a set of full
SPFs. Thus, although a router has to calculate the repair paths for SPFs. Thus, although a router has to calculate the repair paths for
n-1 failures, the computational effort is much less than n-1 SPFs. n-1 failures, the computational effort is much less than n-1 SPFs.
Experiments on a selection of real world network topologies with Experiments on a selection of real world network topologies with
between 40 and 400 nodes suggest that the worst-case computational between 40 and 400 nodes suggest that the worst-case computational
complexity using the above optimizations is equivalent to performing complexity using the above optimizations is equivalent to performing
between 5 and 13 full SPFs. Further optimizations are described in between 5 and 13 full SPFs. Further optimizations are described in
section 6. section 6.
3.1. Computing not-via repairs in distance and path vector routing 4.1. Computing not-via repairs in distance and path vector routing
protocols protocols
While this document focuses on link state routing protocols, it is While this document focuses on link state routing protocols, it is
equally possible to compute not-via repairs in distance vector (e.g. equally possible to compute not-via repairs in distance vector (e.g.
RIP) or path vector (e.g. BGP) routing protocols. This can be RIP) or path vector (e.g. BGP) routing protocols. This can be
achieved with very little protocol modification by advertising the achieved with very little protocol modification by advertising the
not-via address in the normal way, but ensuring that the information not-via address in the normal way, but ensuring that the information
about a not-via address Ps is not propagated through the node S. In about a not-via address Ps is not propagated through the node S. In
the case of link protection this simply means that the advertisement the case of link protection this simply means that the advertisement
from P to S is suppressed, with the result that S and all other nodes from P to S is suppressed, with the result that S and all other nodes
compute a route to Ps which doesn't traverse S, as required. compute a route to Ps which doesn't traverse S, as required.
In the case of node protection, where P is the protected node, and N In the case of node protection, where P is the protected node, and N
is some neighbor, the advertisement of Np MUST be suppressed not only is some neighbor, the advertisement of Np MUST be suppressed not only
across the link N->P, but also across any link to P. The simplest way across the link N->P, but also across any link to P. The simplest way
of achieving this is for P itself to perform the suppression of any of achieving this is for P itself to perform the suppression of any
address of the form Xp. address of the form Xp.
4. Operation of Repairs 5. Operation of Repairs
This section explains the basic operation of the not-via repair of This section explains the basic operation of the not-via repair of
node and link failure. node and link failure.
4.1. Node Failure 5.1. Node Failure
When router P fails (Figure 2) S encapsulates any packet that it When router P fails (Figure 2) S encapsulates any packet that it
would send to B via P to Bp, and then sends the encapsulated packet would send to B via P to Bp, and then sends the encapsulated packet
on the shortest path to Bp. S follows the same procedure for routers on the shortest path to Bp. S follows the same procedure for routers
A and C in Figure 2. The packet is decapsulated at the repair target A and C in Figure 2. The packet is decapsulated at the repair target
(A, B or C) and then forwarded normally to its destination. The (A, B or C) and then forwarded normally to its destination. The
repair target can be determined as part of the normal SPF by repair target can be determined as part of the normal SPF by
recording the "next-next-hop" for each destination in addition to the recording the "next-next-hop" for each destination in addition to the
normal next-hop. The next-next hop is the router that the next hop normal next-hop. The next-next hop is the router that the next hop
router regards as its own next hop to the destination. In Figure 1, router regards as its own next hop to the destination. In Figure 1,
B is S's next next hop to D. B is S's next-next hop to D.
Notice that with this technique only one level of encapsulation is Notice that with this technique only one level of encapsulation is
needed, and that it is possible to repair ANY failure regardless of needed, and that it is possible to repair ANY failure regardless of
link metrics and any asymmetry that may be present in the network. link metrics and any asymmetry that may be present in the network.
The only exception to this is where the failure was a single point of The only exception to this is where the failure was a single point of
failure that partitioned the network, in which case ANY repair is failure that partitioned the network, in which case ANY repair is
clearly impossible. clearly impossible.
4.2. Link Failure 5.2. Link Failure
The normal mode of operation of the network would be to assume router The normal mode of operation of the network would be to assume router
failure. However, where some destinations are only reachable through failure. However, where some destinations are only reachable through
the failed router, it is desirable that an attempt be made to repair the failed router, it is desirable that an attempt be made to repair
to those destinations by assuming that only a link failure has to those destinations by assuming that only a link failure has
occurred. occurred.
To perform a link repair, S encapsulates to Ps (i.e. it instructs the To perform a link repair, S encapsulates to Ps (i.e. it instructs the
network to deliver the packet to P not-via S). All of the neighbors network to deliver the packet to P not-via S). All of the neighbors
of S will have calculated a path to Ps in case S itself had failed. of S will have calculated a path to Ps in case S itself had failed.
S could therefore give the packet to any of its neighbors (except, of S could therefore give the packet to any of its neighbors (except, of
course, P). However, S SHOULD send the encapsulated packet on the course, P). However, S SHOULD send the encapsulated packet on the
shortest available path to P. This path is calculated by running an shortest available path to P. This path is calculated by running an
SPF with the link SP failed. Note that this may again be an SPF with the link SP failed. Note that this may again be an
incremental calculation, which can terminate when address Ps has been incremental calculation, which can terminate when address Ps has been
reattached. reattached.
4.2.1. Loop Prevention Under Node Failure 5.2.1. Loop Prevention Under Node Failure
It is necessary to consider the behavior of IPFRR solutions when a It is necessary to consider the behavior of IPFRR solutions when a
link repair is attempted in the presence of node failure. In its link repair is attempted in the presence of node failure. In its
simplest form, the not-via IPFRR solution prevents the formation of simplest form, the not-via IPFRR solution prevents the formation of
loops as a result of mutual repair, by never providing a repair path loops as a result of mutual repair, by never providing a repair path
for a not-via address. The repair of packets with not-via addresses for a not-via address. The repair of packets with not-via addresses
is considered in more detail in Section 5.3. Referring to Figure 2, is considered in more detail in Section 6.3. Referring to Figure 2,
if A was the neighbor of P that was on the link repair path from S to if A was the neighbor of P that was on the link repair path from S to
P, and P itself had failed, the repaired packet from S would arrive P, and P itself had failed, the repaired packet from S would arrive
at A encapsulated to Ps. A would have detected that the AP link had at A encapsulated to Ps. A would have detected that the AP link had
failed and would normally attempt to repair the packet. However, no failed and would normally attempt to repair the packet. However, no
repair path is provided for any not-via address, and so A would be repair path is provided for any not-via address, and so A would be
forced to drop the packet, thus preventing the formation of a loop. forced to drop the packet, thus preventing the formation of a loop.
4.3. Multi-homed Prefixes 5.3. Multi-homed Prefixes
A multi-homed Prefix (MHP) is a prefix that is reachable via more A multi-homed Prefix (MHP) is a prefix that is reachable via more
than one router in the network. Some of these may be repairable than one router in the network. Some of these may be repairable
using LFAs as described in [RFC5286]. Only those without such a using LFAs as described in [RFC5286]. Only those without such a
repair need be considered here. repair need be considered here.
When IPFRR router S (Figure 3) discovers that P has failed, it needs When IPFRR router S (Figure 3) discovers that P has failed, it needs
to send packets addressed to the MHP X, which is normally reachable to send packets addressed to the MHP X, which is normally reachable
through P, to an alternate router, which is still able to reach X. through P, to an alternate router, which is still able to reach X.
skipping to change at page 10, line 20 skipping to change at page 11, line 5
alternate router (i.e. Z or Y) is greater than the cost of reaching alternate router (i.e. Z or Y) is greater than the cost of reaching
X via P. Under those circumstances, the alternate router would X via P. Under those circumstances, the alternate router would
normally forward to X via P, which would cause the IPFRR repair to normally forward to X via P, which would cause the IPFRR repair to
loop. To prevent the repair from looping the alternate router MUST loop. To prevent the repair from looping the alternate router MUST
locally deliver a packet received via a repair encapsulation. This locally deliver a packet received via a repair encapsulation. This
may be specified by using a special address with the above semantics. may be specified by using a special address with the above semantics.
Note that only one such address is required per node. Notice that Note that only one such address is required per node. Notice that
using the not-via approach, only one level of encapsulation was using the not-via approach, only one level of encapsulation was
needed to repair MHPs to the alternate router. needed to repair MHPs to the alternate router.
4.4. Installation of Repair Paths 5.4. Installation of Repair Paths
The following algorithm is used by node S (Figure 3) to pre- The following algorithm is used by node S (Figure 3) to pre-
calculate and install repair paths in the FIB, ready for immediate calculate and install repair paths in the Forwarding Information Base
use in the event of a failure. It is assumed that the not-via repair (FIB), ready for immediate use in the event of a failure. It is
paths have already been calculated as described above. assumed that the not-via repair paths have already been calculated as
described above.
For each neighbor P, consider all destinations which are reachable For each neighbor P, consider all destinations which are reachable
via P in the current topology:- via P in the current topology:-
1. For all destinations with an ECMP or LFA repair (as described in 1. For all destinations with an ECMP or LFA repair (as described in
[RFC5286]) install that repair. [RFC5286]) install that repair.
2. For each destination (DR) that remains, identify in the current 2. For each destination (DR) that remains, identify in the current
topology the next-next-hop (H) (i.e. the neighbor of P that P topology the next-next-hop (H) (i.e. the neighbor of P that P
will use to send the packet to DR). This can be determined will use to send the packet to DR). This can be determined
skipping to change at page 11, line 35 skipping to change at page 12, line 18
assuming that the apparent failure of node P was simply a failure assuming that the apparent failure of node P was simply a failure
of the S-P link. Note that, if available, a downstream path to P of the S-P link. Note that, if available, a downstream path to P
MAY be used for such a repair. This cannot generate a persistent MAY be used for such a repair. This cannot generate a persistent
loop in the event of the failure of node P, but if one neighbor loop in the event of the failure of node P, but if one neighbor
of P uses a not-via repair and another uses a downstream path, it of P uses a not-via repair and another uses a downstream path, it
is possible for a packet sent on the downstream path to be is possible for a packet sent on the downstream path to be
returned to the sending node inside a not-via encapsulation. returned to the sending node inside a not-via encapsulation.
Since packets destined to not-via addresses are not repaired, the Since packets destined to not-via addresses are not repaired, the
packet will be dropped after executing a single turn loop. packet will be dropped after executing a single turn loop.
5. Compound Failures 6. Compound Failures
The following types of failures involve more than one component: The following types of failures involve more than one component:
1. Shared Risk Link Groups 1. Shared Risk Link Groups
2. Local Area Networks 2. Local Area Networks
3. Multiple Independent Failures 3. Multiple Independent Failures
The considerations that apply in each of the above situations are The considerations that apply in each of the above situations are
described in the following sections. described in the following sections.
5.1. Shared Risk Link Groups 6.1. Shared Risk Link Groups
A Shared Risk Link Group (SRLG) is a set of links whose failure can A Shared Risk Link Group (SRLG) is a set of links whose failure can
be caused by a single action such as a conduit cut or line card be caused by a single action such as a conduit cut or line card
failure. When repairing the failure of a link that is a member of an failure. When repairing the failure of a link that is a member of an
SRLG, it MUST be assumed that all the other links that are also SRLG, it MUST be assumed that all the other links that are also
members of the SRLG have also failed. Consequently, any repair path members of the SRLG have also failed. Consequently, any repair path
MUST be computed to avoid not just the adjacent link, but also all MUST be computed to avoid not just the adjacent link, but also all
the links which are members of the same SRLG. the links which are members of the same SRLG.
In Figure 4 below, the links S-P and A-B are both members of SRLG In Figure 4 below, the links S-P and A-B are both members of SRLG
skipping to change at page 15, line 50 skipping to change at page 16, line 27
approach. The failure to identify any repair is a serious approach. The failure to identify any repair is a serious
deficiency, but is a rare occurrence in a robustly designed network. deficiency, but is a rare occurrence in a robustly designed network.
This problem can be addressed by:- This problem can be addressed by:-
1. Reporting that the link in question is irreparable, so that the 1. Reporting that the link in question is irreparable, so that the
network designer can take appropriate action. network designer can take appropriate action.
2. Modifying the design of the network to avoid this possibility. 2. Modifying the design of the network to avoid this possibility.
3. Using some form of SRLG diagnostic (for example, by running BFD 3. Using some form of SRLG diagnostic (for example, by running BFD
over alternate repair paths) to determine which SRLG member(s) [RFC5880] over alternate repair paths) to determine which SRLG
has actually failed and using this information to select an member(s) has actually failed and using this information to
appropriate pre-computed repair path. However, aside from the select an appropriate pre-computed repair path. However, aside
complexity of performing the diagnostics, this requires multiple from the complexity of performing the diagnostics, this requires
not-via addresses per interface, which has poor scaling multiple not-via addresses per interface, which has poor scaling
properties. properties.
4. Using the mechanism described in Section 5.3 4. Using the mechanism described in Section 6.3
5.2. Local Area Networks 6.2. Local Area Networks
LANs are a special type of SRLG and are solved using the SRLG LANs are a special type of SRLG and are solved using the SRLG
mechanisms outlined above. With all SRLGs there is a trade-off mechanisms outlined above. With all SRLGs there is a trade-off
between the sophistication of the fault detection and the size of the between the sophistication of the fault detection and the size of the
SRLG. Protecting against link failure of the LAN link(s) is SRLG. Protecting against link failure of the LAN link(s) is
relatively straightforward, but as with all fast reroute mechanisms, relatively straightforward, but as with all fast reroute mechanisms,
the problem becomes more complex when it is desired to protect the problem becomes more complex when it is desired to protect
against the possibility of failure of the nodes attached to the LAN against the possibility of failure of the nodes attached to the LAN
as well as the LAN itself. as well as the LAN itself.
skipping to change at page 17, line 5 skipping to change at page 17, line 34
whether the failure is: whether the failure is:
o its own interface to the LAN, o its own interface to the LAN,
o the LAN itself, o the LAN itself,
o the LAN interface of P, o the LAN interface of P,
o the node P. o the node P.
5.2.1. Simple LAN Repair 6.2.1. Simple LAN Repair
A simple approach to LAN repair is to consider the LAN and all of its A simple approach to LAN repair is to consider the LAN and all of its
connected routers as a single SRLG. Thus, the address P not via the connected routers as a single SRLG. Thus, the address P not via the
LAN (Pl) would require P to be reached not-via any router connected LAN (Pl) would require P to be reached not-via any router connected
to the LAN. This is shown in Figure 11. to the LAN. This is shown in Figure 11.
Ql Cl Ql Cl
+-------------Q--------C +-------------Q--------C
| Qc | Qc
| |
skipping to change at page 17, line 37 skipping to change at page 18, line 30
reached via P and B to B not-via the LAN or any router attached to reached via P and B to B not-via the LAN or any router attached to
the LAN (i.e. to Bl). Any destination only reachable through P would the LAN (i.e. to Bl). Any destination only reachable through P would
be addressed to P not-via the LAN or any router attached to the LAN be addressed to P not-via the LAN or any router attached to the LAN
(except of course P). (except of course P).
Whilst this approach is simple, it assumes that a large portion of Whilst this approach is simple, it assumes that a large portion of
the network adjacent to the failure has also failed. This will the network adjacent to the failure has also failed. This will
result in the use of sub-optimal repair paths and in some cases the result in the use of sub-optimal repair paths and in some cases the
inability to identify a viable repair. inability to identify a viable repair.
5.2.2. LAN Component Repair 6.2.2. LAN Component Repair
In this approach, possible failures are considered at a finer In this approach, possible failures are considered at a finer
granularity, but without the use of diagnostics to identify the granularity, but without the use of diagnostics to identify the
specific component that has failed. Because S is unable to diagnose specific component that has failed. Because S is unable to diagnose
the failure it MUST repair traffic sent through P and B, to B not- the failure it MUST repair traffic sent through P and B, to B not-
via P,N (i.e. not via P and not via N), on the conservative via P,N (i.e. not via P and not via N), on the conservative
assumption that both the entire LAN and P have failed. Destinations assumption that both the entire LAN and P have failed. Destinations
for which P is a single point of failure MUST as usual be sent to P for which P is a single point of failure MUST as usual be sent to P
using an address that avoids the interface by which P is reached from using an address that avoids the interface by which P is reached from
S, i.e. to P not-via N. Similarly for routers Q and R. S, i.e. to P not-via N. Similarly for routers Q and R.
skipping to change at page 18, line 28 skipping to change at page 19, line 21
Asn Sa Sp Sq | Ps Pq Pb Bpn Asn Sa Sp Sq | Ps Pq Pb Bpn
A--------S-------(N)-------------P---------B A--------S-------(N)-------------P---------B
As Sr Sn | Pr Pn Bp As Sr Sn | Pr Pn Bp
| |
| Rs Rp Pd Drn | Rs Rp Pd Drn
+--------------R---------D +--------------R---------D
Rq Rn Dr Rq Rn Dr
Figure 12: Local Area Networks Figure 12: Local Area Networks
5.2.3. LAN Repair Using Diagnostics 6.2.3. LAN Repair Using Diagnostics
A more specific LAN repair can be undertaken by using diagnostics. A more specific LAN repair can be undertaken by using diagnostics.
In order to explicitly diagnose the failed network component, S In order to explicitly diagnose the failed network component, S
correlates the connectivity reports from P and one or more of the correlates the connectivity reports from P and one or more of the
other routers on the LAN, in this case, Q and R. If it lost other routers on the LAN, in this case, Q and R. If it lost
connectivity to P alone, it could deduce that the LAN was still connectivity to P alone, it could deduce that the LAN was still
functioning and that the fault lay with either P, or the interface functioning and that the fault lay with either P, or the interface
connecting P to the LAN. It would then repair to B not via P (and P connecting P to the LAN. It would then repair to B not via P (and P
not-via N for destinations for which P is a single point of failure) not-via N for destinations for which P is a single point of failure)
in the usual way. If S lost connectivity to more than one router on in the usual way. If S lost connectivity to more than one router on
the LAN, it could conclude that the fault lay only with the LAN, and the LAN, it could conclude that the fault lay only with the LAN, and
could repair to P, Q and R not-via N, again in the usual way. could repair to P, Q and R not-via N, again in the usual way.
5.3. Multiple Independent Failures 6.3. Multiple Independent Failures
IPFRR repair of multiple simultaneous failures which are not members IPFRR repair of multiple simultaneous failures which are not members
of a known SRLG is complicated by the problem that the use of of a known SRLG is complicated by the problem that the use of
multiple concurrent repairs may result in looping repair paths. As multiple concurrent repairs may result in looping repair paths. As
described in Section 4.2.1, the simplest method of preventing such described in Section 5.2.1, the simplest method of preventing such
loops, is to ensure that packets addressed to a not-via address are loops, is to ensure that packets addressed to a not-via address are
not repaired but instead are dropped. It is possible that a network not repaired but instead are dropped. It is possible that a network
may experience multiple simultaneous failures. This may be due to may experience multiple simultaneous failures. This may be due to
simple statistical effects, but the more likely cause is simple statistical effects, but the more likely cause is
unanticipated SRLGs. When multiple failures which are not part of an unanticipated SRLGs. When multiple failures which are not part of an
anticipated group are detected, repairs are abandoned and the network anticipated group are detected, repairs are abandoned and the network
reverts to normal convergence. Although safe, this approach is reverts to normal convergence. Although safe, this approach is
somewhat draconian, since there are many circumstances were multiple somewhat draconian, since there are many circumstances were multiple
repairs do not induce loops. repairs do not induce loops.
This section describes the properties of multiple unrelated failures This section describes the properties of multiple unrelated failures
and proposes some methods that may be used to address this problem. and proposes some methods that may be used to address this problem.
5.3.1. Looping Repairs 6.3.1. Looping Repairs
Let us assume that the repair mechanism is based on solely on not-via Let us assume that the repair mechanism is based on solely on not-via
repairs. LFA or downstream routes MAY be incorporated, and will be repairs. LFA or downstream routes MAY be incorporated, and will be
dealt with later. dealt with later.
A------//------B------------D A------//------B------------D
/ \ / \
/ \ / \
F G F G
\ / \ /
skipping to change at page 20, line 31 skipping to change at page 21, line 31
encapsulation would be required. encapsulation would be required.
3) The repair for A-B traverses X-Y AND the repair for X-Y 3) The repair for A-B traverses X-Y AND the repair for X-Y
traverses A-B. In this case unrestricted repair would result in traverses A-B. In this case unrestricted repair would result in
looping packets and increasing levels of encapsulation. looping packets and increasing levels of encapsulation.
The challenge in applying IPFRR to a network that is undergoing The challenge in applying IPFRR to a network that is undergoing
multiple failures is, therefore, to identify which of these cases multiple failures is, therefore, to identify which of these cases
exist in the network and react accordingly. exist in the network and react accordingly.
5.3.2. Outline Solution 6.3.2. Outline Solution
When A is computing the not-via repair path for A-B (i.e. the path When A is computing the not-via repair path for A-B (i.e. the path
for packets addressed to Ba, read as "B not-via A") it is aware of for packets addressed to Ba, read as "B not-via A") it is aware of
the list of nodes which this path traverses. This can be recorded by the list of nodes which this path traverses. This can be recorded by
a simple addition to the SPF process, and the not-via addresses a simple addition to the SPF process, and the not-via addresses
associated with each forward link can be determined. If the path associated with each forward link can be determined. If the path
were A, F, X, Y, G, B, (Figure 13) the list of not-via addresses were A, F, X, Y, G, B, (Figure 13) the list of not-via addresses
would be: Fa, Xf, Yx, Gy, Bg. Under standard not-via operation, A would be: Fa, Xf, Yx, Gy, Bg. Under standard not-via operation, A
would populate its FIB such that all normal addresses normally would populate its FIB such that all normal addresses normally
reachable via A-B would be encapsulated to Ba when A-B fails, but reachable via A-B would be encapsulated to Ba when A-B fails, but
skipping to change at page 21, line 26 skipping to change at page 22, line 24
So far we have permitted benign repairs to coexist, albeit sometimes So far we have permitted benign repairs to coexist, albeit sometimes
requiring multiple encapsulation. Note that in many cases there will requiring multiple encapsulation. Note that in many cases there will
be no performance impact since unless both failures are on the same be no performance impact since unless both failures are on the same
node, the two encapsulations or two decapsulations will be performed node, the two encapsulations or two decapsulations will be performed
at different nodes. There is however the issue of the MTU impact of at different nodes. There is however the issue of the MTU impact of
multiple encapsulations. multiple encapsulations.
In the following sub-section we consider the various strategies that In the following sub-section we consider the various strategies that
may be applied to case 3 - mutual repairs that would loop. may be applied to case 3 - mutual repairs that would loop.
5.3.3. Looping Repairs 6.3.3. Looping Repairs
In case 3, the simplest approach is to simply not install repairs for In case 3, the simplest approach is to simply not install repairs for
repair paths that might loop. In this case, although the potentially repair paths that might loop. In this case, although the potentially
looping traffic is dropped, the traffic is not repaired. If we looping traffic is dropped, the traffic is not repaired. If we
assume that a hold-down is applied before reconvergence in case the assume that a hold-down is applied before reconvergence in case the
link failure was just a short glitch, and if a loop free convergence link failure was just a short glitch, and if a loop free convergence
mechanism further delays convergence, then the traffic will be mechanism further delays convergence, then the traffic will be
dropped for an extended period. In these circumstances it would be dropped for an extended period. In these circumstances it would be
better to "abandon all hope" (AAH) [I-D.ietf-rtgwg-ordered-fib] better to "abandon all hope" (AAH) [I-D.ietf-rtgwg-ordered-fib]
(Appendix A) and immediately invoke normal re-convergence. (Appendix A) and immediately invoke normal re-convergence.
Note that it is not sufficient to expedite the issuance of an LSP Note that it is not sufficient to expedite the issuance of an LSP
reporting the failure, since this may be treated as a permitted reporting the failure, since this may be treated as a permitted
simultaneous failure by the ordered FIB (oFIB) algorithm simultaneous failure by the ordered FIB (oFIB) algorithm
[I-D.ietf-rtgwg-ordered-fib]. It is therefore necessary to [I-D.ietf-rtgwg-ordered-fib]. It is therefore necessary to
explicitly trigger an oFIB AAH. explicitly trigger an oFIB AAH.
5.3.3.1. Dropping Looping Packets 6.3.3.1. Dropping Looping Packets
One approach to case 3 is to allow the repair, and to experimentally One approach to case 3 is to allow the repair, and to experimentally
discover the incompatibility of the repairs if and when they occur. discover the incompatibility of the repairs if and when they occur.
With this method we permit the repair in case 3 and trigger AAH when With this method we permit the repair in case 3 and trigger AAH when
a packet drop count on the not-via address has been incremented. a packet drop count on the not-via address has been incremented.
Alternatively, it is possible to wait until the LSP describing the Alternatively, it is possible to wait until the LSP describing the
change is issued normally (i.e. when X announces the failure of X-Y). change is issued normally (i.e. when X announces the failure of X-Y).
When the repairing node A, which has precomputed that X-Y failures When the repairing node A, which has precomputed that X-Y failures
are mutually incompatible with its own repairs receives this LSP it are mutually incompatible with its own repairs receives this LSP it
can then issue the AAH. This has the disadvantage that it does not can then issue the AAH. This has the disadvantage that it does not
overcome the hold-down delay, but it requires no "data-driven" overcome the hold-down delay, but it requires no "data-driven"
operation, and it still has the required effect of abandoning the operation, and it still has the required effect of abandoning the
oFIB which is probably the longer of the delays (although with oFIB which is probably the longer of the delays (although with
signalled oFIB this should be sub-second). signalled oFIB this should be sub-second).
Whilst both of the experimental approaches described above are Whilst both of the experimental approaches described above are
feasible, they tend to induce AAH in the presence of otherwise feasible, they tend to induce AAH in the presence of otherwise
feasible repairs, and they are contrary to the philosophy of repair feasible repairs, and they are contrary to the philosophy of repair
pre-determination that has been applied to existing IPFRR solutions. pre-determination that has been applied to existing IPFRR solutions.
5.3.3.2. Computing non-looping Repairs of Repairs 6.3.3.2. Computing non-looping Repairs of Repairs
An alternative approach to simply dropping the looping packets, or to An alternative approach to simply dropping the looping packets, or to
detecting the loop after it has occurred, is to use secondary SRLGs. detecting the loop after it has occurred, is to use secondary SRLGs.
With a link state routing protocol it is possible to precompute the With a link state routing protocol it is possible to precompute the
incompatibility of the repairs in advance and to compute an incompatibility of the repairs in advance and to compute an
alternative SRLG repair path. Although this does considerably alternative SRLG repair path. Although this does considerably
increase the computational complexity it may be possible to compute increase the computational complexity it may be possible to compute
repair paths that avoid the need to simply drop the offending repair paths that avoid the need to simply drop the offending
packets. packets.
skipping to change at page 24, line 5 skipping to change at page 25, line 5
connected. In these cases, repair is clearly impossible - the connected. In these cases, repair is clearly impossible - the
failure of both links partitions the network. It would be failure of both links partitions the network. It would be
advantageous to be able to identify these cases, and inhibit the advantageous to be able to identify these cases, and inhibit the
fruitless advertisement of the secondary SRLG information. This fruitless advertisement of the secondary SRLG information. This
could be achieved by the node detecting the requirement for a could be achieved by the node detecting the requirement for a
secondary SRLG, first running the not-via computation with both links secondary SRLG, first running the not-via computation with both links
removed. If this does not result in a path, it is clear that the removed. If this does not result in a path, it is clear that the
network would be partitioned by such a failure, and so no network would be partitioned by such a failure, and so no
advertisement is required. advertisement is required.
5.3.4. Mixing LFAs and Not-via 6.3.4. Mixing LFAs and Not-via
So far in this section we have assumed that all repairs use not-via So far in this section we have assumed that all repairs use not-via
tunnels. However, in practise we may wish to use LFAs or downstream tunnels. However, in practise we may wish to use LFAs or downstream
routes where available. This complicates the issue, because their routes where available. This complicates the issue, because their
use results in packets which are being repaired, but NOT addressed to use results in packets which are being repaired, but NOT addressed to
not-via addresses. If BOTH links are using downstream routes there not-via addresses. If BOTH links are using downstream routes there
is no possibility of looping, since it is impossible to have a pair is no possibility of looping, since it is impossible to have a pair
of nodes which are both downstream of each other [RFC5286]. of nodes which are both downstream of each other [RFC5286].
Loops can however occur when LFAs are used. An obvious example is Loops can however occur when LFAs are used. An obvious example is
skipping to change at page 25, line 15 skipping to change at page 26, line 15
topology with link Q-P failed.), then the downstream repair for Yx topology with link Q-P failed.), then the downstream repair for Yx
can safely be used. These packets cannot re-visit X-Y, since by can safely be used. These packets cannot re-visit X-Y, since by
definition they will avoid that link. Alternatively, the packet definition they will avoid that link. Alternatively, the packet
could be always repaired in a not-via tunnel. i.e. even though the could be always repaired in a not-via tunnel. i.e. even though the
normal repair for traffic traversing A-B would be to use a downstream normal repair for traffic traversing A-B would be to use a downstream
route, we could insist that such traffic addressed to a not-via route, we could insist that such traffic addressed to a not-via
address MUST use a tunnel to Ba. Such a tunnel would only be address MUST use a tunnel to Ba. Such a tunnel would only be
installed for an address Qp if it were established that it did not installed for an address Qp if it were established that it did not
traverse Q-P (using the rules described above). traverse Q-P (using the rules described above).
6. Optimizing not-via computations using LFAs 7. Optimizing not-via computations using LFAs
If repairing node S has an LFA to the repair endpoint it is not If repairing node S has an LFA to the repair endpoint it is not
necessary for any router to perform the incremental SPF with the link necessary for any router to perform the incremental SPF with the link
SP removed in order to compute the route to the not-via address Ps. SP removed in order to compute the route to the not-via address Ps.
This is because the correct routes will already have been computed as This is because the correct routes will already have been computed as
a result of the SPF on the base topology. Node S can signal this a result of the SPF on the base topology. Node S can signal this
condition to all other routers by including a bit in its LSP or LSA condition to all other routers by including a bit in its LSP or LSA
associated with each LFA protected link. Routers computing not-via associated with each LFA protected link. Routers computing not-via
routes can then omit the running of the iSPF for links with this bit routes can then omit the running of the iSPF for links with this bit
set. set.
skipping to change at page 26, line 5 skipping to change at page 27, line 5
of the protocol is not compromised provided that the necessity to of the protocol is not compromised provided that the necessity to
perform a not-via computation is re-evaluated whenever new perform a not-via computation is re-evaluated whenever new
information arrives. information arrives.
This optimization is not particularly beneficial to nodes close to This optimization is not particularly beneficial to nodes close to
the repair since, as has been observed above, the computation for the repair since, as has been observed above, the computation for
nodes on the LFA path is trivial. However, for nodes upstream of the nodes on the LFA path is trivial. However, for nodes upstream of the
link SP for which S-P is in the path to P, there is a significant link SP for which S-P is in the path to P, there is a significant
reduction in the computation required. reduction in the computation required.
7. Multicast 8. Multicast
Multicast traffic can be repaired in a similar way to unicast. The Multicast traffic can be repaired in a similar way to unicast. The
multicast forwarder is able to use the not-via address to which the multicast forwarder is able to use the not-via address to which the
multicast packet was addressed as an indication of the expected multicast packet was addressed as an indication of the expected
receive interface and hence to correctly run the required RPF check. receive interface and hence to correctly run the required Reverse
Path Forwarding (RPF) check.
In some cases, all the destinations, including the repair endpoint, In some cases, all the destinations, including the repair endpoint,
are repairable by an LFA. In this case, all unicast traffic may be are repairable by an LFA. In this case, all unicast traffic may be
repaired without encapsulation. Multicast traffic still requires repaired without encapsulation. Multicast traffic still requires
encapsulation, but for the nodes on the LFA repair path the encapsulation, but for the nodes on the LFA repair path the
computation of the not-via forwarding entry is unnecessary since, by computation of the not-via forwarding entry is unnecessary since, by
definition, their normal path to the repair endpoint is not via the definition, their normal path to the repair endpoint is not via the
failure. failure.
A more complete description of multicast operation is for further A more complete description of multicast operation is for further
study. study.
8. Fast Reroute in an MPLS LDP Network. 9. Fast Reroute in an MPLS LDP Network.
Not-via addresses are IP addresses and LDP [RFC5036] will distribute Not-via addresses are IP addresses and LDP [RFC5036] will distribute
labels for them in the usual way. The not-via repair mechanism may labels for them in the usual way. The not-via repair mechanism may
therefore be used to provide fast re-route in an MPLS network by therefore be used to provide fast re-route in an MPLS network by
first pushing the label which the repair endpoint uses to forward the first pushing the label which the repair endpoint uses to forward the
packet, and then pushing the label corresponding to the not-via packet, and then pushing the label corresponding to the not-via
address needed to effect the repair. Referring once again to address needed to effect the repair. Referring once again to
Figure 1, if S has a packet destined for D that it must reach via P Figure 1, if S has a packet destined for D that it must reach via P
and B, S first pushes B's label for D. S then pushes the label that and B, S first pushes B's label for D. S then pushes the label that
its next hop to Bp needs to reach Bp. its next hop to Bp needs to reach Bp.
Note that in an MPLS LDP network it is necessary for S to have the Note that in an MPLS LDP network it is necessary for S to have the
repair endpoint's label for the destination. When S is effecting a repair endpoint's label for the destination. When S is effecting a
link repair it already has this. In the case of a node repair, S link repair it already has this. In the case of a node repair, S
either needs to set up a directed LDP session with each of its either needs to set up a directed LDP session with each of its
neighbor's neighbors, or it needs to use a method similar to the neighbor's neighbors, or it needs to use a method similar to the
next-next hop label distribution mechanism proposed in next-next hop label distribution mechanism proposed in
[I-D.shen-mpls-ldp-nnhop-label]. [I-D.shen-mpls-ldp-nnhop-label].
9. Encapsulation 10. Encapsulation
Any IETF specified IP in IP encapsulation may be used to carry a not- Any IETF specified IP in IP encapsulation may be used to carry a not-
via repair. IP in IP [RFC2003], GRE [RFC1701] and L2TPv3 [RFC3931], via repair. IP in IP [RFC2003], GRE [RFC1701] and L2TPv3 [RFC3931],
all have the necessary and sufficient properties. The requirement is all have the necessary and sufficient properties. The requirement is
that both the encapsulating router and the router to which the that both the encapsulating router and the router to which the
encapsulated packet is addressed have a common ability to process the encapsulated packet is addressed have a common ability to process the
chosen encapsulation type. When an MPLS LDP network is being chosen encapsulation type. When an MPLS LDP network is being
protected, the encapsulation would normally be an additional MPLS protected, the encapsulation would normally be an additional MPLS
label. In an MPLS enabled IP network an MPLS label may be used in label. In an MPLS enabled IP network an MPLS label may be used in
place of an IP in IP encapsulation in the case above. place of an IP in IP encapsulation in the case above.
10. Routing Extensions 11. Routing Extensions
IPFRR requires routing protocol extensions. Each IPFRR router that IPFRR requires routing protocol extensions. Each IPFRR router that
is directly connected to a protected network component MUST advertise is directly connected to a protected network component MUST advertise
a not-via address for that component. This MUST be advertised in a not-via address for that component. This MUST be advertised in
such a way that the association between the protected component such a way that the association between the protected component
(link, router or SRLG) and the not-via address can be determined by (link, router or SRLG) and the not-via address can be determined by
the other routers in the network. the other routers in the network.
It is necessary that not-via capable routers advertise in the IGP It is necessary that not-via capable routers advertise in the IGP
that they will calculate not-via routes. that they will calculate not-via routes.
It is necessary for routers to advertise the type of encapsulation It is necessary for routers to advertise the type of encapsulation
that they support (MPLS, GRE, L2TPv3 etc). However, the deployment that they support (MPLS, GRE, L2TPv3 etc). However, the deployment
of mixed IP encapsulation types within a network is discouraged. of mixed IP encapsulation types within a network is discouraged.
If the optimization proposed in Section 6 is to be used the use of If the optimization proposed in Section 7 is to be used the use of
the LFA in place of the not-via repair MUST also be signalled in the the LFA in place of the not-via repair MUST also be signalled in the
routing protocol. routing protocol.
11. Incremental Deployment 12. Incremental Deployment
Incremental deployment is supported by excluding routers that are not Incremental deployment is supported by excluding routers that are not
calculating not-via routes (as indicated by their capability calculating not-via routes (as indicated by their capability
information flooded with their link state information) from the base information flooded with their link state information) from the base
topology used for the computation of repair paths. In that way topology used for the computation of repair paths. In that way
repairs may be steered around islands of routers that are not IPFRR repairs may be steered around islands of routers that are not IPFRR
capable. Routers that are protecting a network component need to capable. Routers that are protecting a network component need to
have the capability to encapsulate and decapsulate packets. However, have the capability to encapsulate and decapsulate packets. However,
routers that are on the repair path only need to be capable of routers that are on the repair path only need to be capable of
calculating not-via paths and including the not-via addresses in calculating not-via paths and including the not-via addresses in
their FIB i.e. these routers do not need any changes to their their FIB i.e. these routers do not need any changes to their
forwarding mechanism. forwarding mechanism.
12. Manageability Considerations 13. Manageability Considerations
[RFC5714] outlines the general set of manageability consideration [RFC5714] outlines the general set of manageability consideration
that apply to the general case of IPFRR. We slightly expand this and that apply to the general case of IPFRR. We slightly expand this and
add details that are not-via specific. There are three classes add details that are not-via specific. There are three classes
manageability consideration: manageability consideration:
1. Pre-failure configuration 1. Pre-failure configuration
2. Pre-failure Monitoring and operational support 2. Pre-failure Monitoring and operational support
3. Failure action verification 3. Failure action verification
12.1. Pre-failure configuration 13.1. Pre-failure configuration
Pre-failure configuration for not-via includes: Pre-failure configuration for not-via includes:
o Enabling/disabling not-via IPFRR support. o Enabling/disabling not-via IPFRR support.
o Enabling/disabling protection on a per-link or per-node basis. o Enabling/disabling protection on a per-link or per-node basis.
o Expressing preferences regarding the links/nodes used for repair o Expressing preferences regarding the links/nodes used for repair
paths. paths.
skipping to change at page 28, line 34 skipping to change at page 29, line 34
o Setting a preference concerning the use of LFA. o Setting a preference concerning the use of LFA.
o Configuring not-via address (per interface), or not-via address o Configuring not-via address (per interface), or not-via address
set (per node). set (per node).
o Configuring any SRLG rules or preferences. o Configuring any SRLG rules or preferences.
Any standard configuration method may be used and the selection of Any standard configuration method may be used and the selection of
the method to be used is outside the scope of this document. the method to be used is outside the scope of this document.
12.2. Pre-failure Monitoring and operational support 13.2. Pre-failure Monitoring and operational support
Pre-failure Monitoring and operational support for not-via includes: Pre-failure Monitoring and operational support for not-via includes:
o Notification of links/nodes/destinations that cannot be protected. o Notification of links/nodes/destinations that cannot be protected.
o Notification of pre-computed repair paths. o Notification of pre-computed repair paths.
o Notification of repair type to be used (LFA or not-via). o Notification of repair type to be used (LFA or not-via).
o Notification of not-via address assignment. o Notification of not-via address assignment.
skipping to change at page 29, line 8 skipping to change at page 30, line 8
o Notification of path or address optimizations used. o Notification of path or address optimizations used.
o Testing repair paths. Note that not-via addresses look identical o Testing repair paths. Note that not-via addresses look identical
to "ordinary" addresses as far as tools such as trace route and to "ordinary" addresses as far as tools such as trace route and
ping are concerned and thus it is anticipated that these will be ping are concerned and thus it is anticipated that these will be
used to verify the established repair path. used to verify the established repair path.
Any standard IETF method may be used for the above and the selection Any standard IETF method may be used for the above and the selection
of the method to be used is outside the scope of this document. of the method to be used is outside the scope of this document.
12.3. Failure action monitoring 13.3. Failure action monitoring
Failure action monitoring for not-via includes: Failure action monitoring for not-via includes:
o Counts of failure detections, protection invocations, and packets o Counts of failure detections, protection invocations, and packets
forwarded over repair paths. forwarded over repair paths.
o Logging of the events using a sufficiently accurate and precise o Logging of the events using a sufficiently accurate and precise
timestamp. timestamp.
o Validation that the packet loss was within specification using a o Validation that the packet loss was within specification using a
suitable loss verification tool. suitable loss verification tool.
o Capture of the in-flight repair packet flows using a tool such as o Capture of the in-flight repair packet flows using a tool such as
IPFIX[RFC5101]. IPFIX[RFC5101].
Note that monitoring the repair in action requires the capture of the Note that monitoring the repair in action requires the capture of the
signatures of a short, possibly sub-second network transient which is signatures of a short, possibly sub-second network transient which is
not a well developed IETF technology. not a well developed IETF technology.
13. IANA Considerations 14. IANA Considerations
There are no IANA considerations that arise from this draft. There are no IANA considerations that arise from this draft.
14. Security Considerations 15. Security Considerations
The repair endpoints present vulnerability in that they might be used The repair endpoints present vulnerability in that they might be used
as a method of disguising the delivery of a packet to a point in the as a method of disguising the delivery of a packet to a point in the
network. The primary method of protection SHOULD be through the use network. The primary method of protection SHOULD be through the use
of a private address space for the not-via addresses. These of a private address space for the not-via addresses. These
addresses MUST NOT be advertised outside the area, and SHOULD be addresses MUST NOT be advertised outside the area, and SHOULD be
filtered at the network entry points. In addition, a mechanism might filtered at the network entry points. In addition, a mechanism might
be developed that allowed the use of the mild security available be developed that allowed the use of the mild security available
through the use of a key [RFC1701] [RFC3931]. With the deployment of through the use of a key [RFC1701] [RFC3931]. With the deployment of
such mechanisms, the repair endpoints would not increase the security such mechanisms, the repair endpoints would not increase the security
skipping to change at page 30, line 8 skipping to change at page 31, line 8
to the de-capsulation endpoint. Typically, routers take a 50% to the de-capsulation endpoint. Typically, routers take a 50%
performance penalty in decapsulating a packet. The attacker could performance penalty in decapsulating a packet. The attacker could
not be certain that the router would be impacted, and the extremely not be certain that the router would be impacted, and the extremely
high volume of traffic needed, would easily be detected as an high volume of traffic needed, would easily be detected as an
anomaly. If an attacker were able to influence the availability of a anomaly. If an attacker were able to influence the availability of a
link, they could cause the network to invoke the not-via repair link, they could cause the network to invoke the not-via repair
mechanism. A network protected by not-via IPFRR is less vulnerable mechanism. A network protected by not-via IPFRR is less vulnerable
to such an attack than a network that undertook a full convergence in to such an attack than a network that undertook a full convergence in
response to a link up/down event. response to a link up/down event.
15. Acknowledgements 16. Acknowledgements
The authors would like to acknowledge contributions made by Alia The authors would like to acknowledge contributions made by Alia
Atlas and John Harper. Atlas and John Harper.
16. References 17. References
16.1. Normative References 17.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.
16.2. Informative References 17.2. Informative References
[I-D.ietf-rtgwg-ordered-fib] [I-D.ietf-rtgwg-ordered-fib]
Shand, M., Bryant, S., Previdi, S., and C. Filsfils, Shand, M., Bryant, S., Previdi, S., Filsfils, C.,
"Loop-free convergence using oFIB", Francois, P., and O. Bonaventure, "Loop-free convergence
draft-ietf-rtgwg-ordered-fib-05 (work in progress), using oFIB", draft-ietf-rtgwg-ordered-fib-07 (work in
April 2011. progress), September 2012.
[I-D.shand-remote-lfa] [I-D.ietf-rtgwg-remote-lfa]
Bryant, S., Filsfils, C., Shand, M., and N. So, "Remote Bryant, S., Filsfils, C., Previdi, S., Shand, M., and S.
LFA FRR", draft-shand-remote-lfa-01 (work in progress), Ning, "Remote LFA FRR", draft-ietf-rtgwg-remote-lfa-01
June 2012. (work in progress), December 2012.
[I-D.shen-mpls-ldp-nnhop-label] [I-D.shen-mpls-ldp-nnhop-label]
Shen, N., "Discovering LDP Next-Nexthop Labels", Shen, N., "Discovering LDP Next-Nexthop Labels",
draft-shen-mpls-ldp-nnhop-label-02 (work in progress), draft-shen-mpls-ldp-nnhop-label-02 (work in progress),
May 2005. May 2005.
[ISPF] McQuillan, J., Richer, I., and E. Rosen, "ARPANET Routing [ISPF] McQuillan, J., Richer, I., and E. Rosen, "ARPANET Routing
Algorithm Improvements"", BBN Technical Report 3803, 1978. Algorithm Improvements"", BBN Technical Report 3803, 1978.
[RFC1701] Hanks, S., Li, T., Farinacci, D., and P. Traina, "Generic [RFC1701] Hanks, S., Li, T., Farinacci, D., and P. Traina, "Generic
skipping to change at page 31, line 26 skipping to change at page 32, line 26
RFC 5714, January 2010. RFC 5714, January 2010.
[RFC5880] Katz, D. and D. Ward, "Bidirectional Forwarding Detection [RFC5880] Katz, D. and D. Ward, "Bidirectional Forwarding Detection
(BFD)", RFC 5880, June 2010. (BFD)", RFC 5880, June 2010.
Appendix A. Q-Space Appendix A. Q-Space
Q-space is the set of routers from which a specific router can be Q-space is the set of routers from which a specific router can be
reached without any path (including equal cost path splits) reached without any path (including equal cost path splits)
transiting the protected link (or node). It is fully described in transiting the protected link (or node). It is fully described in
[I-D.shand-remote-lfa]. [I-D.ietf-rtgwg-remote-lfa].
S---E S---E
/ \ / \
A D A D
\ / \ /
B---C B---C
Figure 15 Figure 15
Consider a repair of link S-E (Figure 15). The set of routers from Consider a repair of link S-E (Figure 15). The set of routers from
 End of changes. 60 change blocks. 
127 lines changed or deleted 162 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/