draft-ietf-rtgwg-ipfrr-notvia-addresses-11.txt   rfc6981.txt 
Network Working Group S. Bryant Internet Engineering Task Force (IETF) S. Bryant
Internet-Draft S. Previdi Request for Comments: 6981 S. Previdi
Intended status: Informational Cisco Systems Category: Informational Cisco Systems
Expires: November 25, 2013 M. Shand ISSN: 2070-1721 M. Shand
Individual Contributor Individual Contributor
May 24, 2013 August 2013
A Framework for IP and MPLS Fast Reroute Using Not-via Addresses A Framework for IP and MPLS Fast Reroute Using Not-Via Addresses
draft-ietf-rtgwg-ipfrr-notvia-addresses-11
Abstract Abstract
This document presents an illustrative framework for providing fast This document presents an illustrative framework for providing fast
reroute in an IP or MPLS network through encapsulation and forwarding reroute in an IP or MPLS network through encapsulation and forwarding
to "not-via" addresses. The general approach described uses a single to "not-via" addresses. The general approach described here uses a
level of encapsulation and could be used to protect unicast, single level of encapsulation and could be used to protect unicast,
multicast, and LDP traffic against link, router, and shared risk multicast, and LDP traffic against link, router, and shared risk
group failure, regardless of network topology and metrics. group failure, regardless of network topology and metrics.
The mechanisms presented in this document are purely illustrative of The mechanisms presented in this document are purely illustrative of
the general approach and do not constitute a protocol specification. the general approach and do not constitute a protocol specification.
The document represents a snapshot of the work of the Routing Area The document represents a snapshot of the work of the Routing Area
Working Group at the time of publication and is published as a Working Group at the time of publication and is published as a
document of record. Further work is needed before implementation or document of record. Further work is needed before implementation or
deployment. deployment.
Requirements Language
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC2119 [RFC2119].
Status of This Memo Status of This Memo
This Internet-Draft is submitted in full conformance with the This document is not an Internet Standards Track specification; it is
provisions of BCP 78 and BCP 79. published for informational purposes.
Internet-Drafts are working documents of the Internet Engineering This document is a product of the Internet Engineering Task Force
Task Force (IETF). Note that other groups may also distribute (IETF). It represents the consensus of the IETF community. It has
working documents as Internet-Drafts. The list of current Internet- received public review and has been approved for publication by the
Drafts is at http://datatracker.ietf.org/drafts/current/. Internet Engineering Steering Group (IESG). Not all documents
approved by the IESG are a candidate for any level of Internet
Standard; see Section 2 of RFC 5741.
Internet-Drafts are draft documents valid for a maximum of six months Information about the current status of this document, any errata,
and may be updated, replaced, or obsoleted by other documents at any and how to provide feedback on it may be obtained at
time. It is inappropriate to use Internet-Drafts as reference http://www.rfc-editor.org/info/rfc6981.
material or to cite them other than as "work in progress."
This Internet-Draft will expire on November 25, 2013.
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
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. The Purpose of this Document . . . . . . . . . . . . . . . . 3 1. Introduction ....................................................4
2. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1. The Purpose of This Document ...............................4
3. Overview of Not-via Repairs . . . . . . . . . . . . . . . . . 4 1.2. Overview ...................................................4
3.1. Use of Equal Cost Multi-Path . . . . . . . . . . . . . . 5 2. Requirements Language ...........................................5
3.2. Use of LFA repairs . . . . . . . . . . . . . . . . . . . 5 3. Overview of Not-Via Repairs .....................................5
4. Not-via Repair Path Computation . . . . . . . . . . . . . . . 6 3.1. Use of Equal-Cost Multi-Path ...............................6
4.1. Computing not-via repairs in distance and path vector 3.2. Use of LFA Repairs .........................................6
routing protocols . . . . . . . . . . . . . . . . . . . . 7 4. Not-Via Repair Path Computation .................................7
5. Operation of Repairs . . . . . . . . . . . . . . . . . . . . 7 4.1. Computing Not-Via Repairs in Distance and Path
5.1. Node Failure . . . . . . . . . . . . . . . . . . . . . . 7 Vector Routing Protocols ...................................8
5.2. Link Failure . . . . . . . . . . . . . . . . . . . . . . 8 5. Operation of Repairs ............................................8
5.2.1. Loop Prevention Under Node Failure . . . . . . . . . 8 5.1. Node Failure ...............................................8
5.3. Multi-homed Prefixes . . . . . . . . . . . . . . . . . . 8 5.2. Link Failure ...............................................9
5.4. Installation of Repair Paths . . . . . . . . . . . . . . 10 5.2.1. Loop Prevention under Node Failure ..................9
6. Compound Failures . . . . . . . . . . . . . . . . . . . . . . 11 5.3. Multi-Homed Prefixes .......................................9
6.1. Shared Risk Link Groups . . . . . . . . . . . . . . . . . 11 5.4. Installation of Repair Paths ..............................11
6.2. Local Area Networks . . . . . . . . . . . . . . . . . . . 16 6. Compound Failures ..............................................12
6.2.1. Simple LAN Repair . . . . . . . . . . . . . . . . . . 16 6.1. Shared Risk Link Groups ...................................12
6.2.2. LAN Component Repair . . . . . . . . . . . . . . . . 17 6.2. Local Area Networks .......................................17
6.2.3. LAN Repair Using Diagnostics . . . . . . . . . . . . 18 6.2.1. Simple LAN Repair ..................................18
6.3. Multiple Independent Failures . . . . . . . . . . . . . . 18 6.2.2. LAN Component Repair ...............................19
6.3.1. Looping Repairs . . . . . . . . . . . . . . . . . . . 19 6.2.3. LAN Repair Using Diagnostics .......................19
6.3.2. Outline Solution . . . . . . . . . . . . . . . . . . 20 6.3. Multiple Independent Failures .............................20
6.3.3. Looping Repairs . . . . . . . . . . . . . . . . . . . 21 6.3.1. Looping Repairs ....................................20
6.3.3.1. Dropping Looping Packets . . . . . . . . . . . . 21 6.3.2. Outline Solution ...................................21
6.3.3.2. Computing non-looping Repairs of Repairs . . . . 22 6.3.3. Mutually Looping Repairs ...........................22
6.3.4. Mixing LFAs and Not-via . . . . . . . . . . . . . . . 24 6.3.3.1. Dropping Looping Packets ..................23
7. Optimizing not-via computations using LFAs . . . . . . . . . 25 6.3.3.2. Computing Non-looping Repairs of Repairs ..23
8. Multicast . . . . . . . . . . . . . . . . . . . . . . . . . . 25 6.3.4. Mixing LFAs and Not-Via ............................25
9. Fast Reroute in an MPLS LDP Network. . . . . . . . . . . . . 26 7. Optimizing Not-Via Computations Using LFAs .....................26
10. Encapsulation . . . . . . . . . . . . . . . . . . . . . . . . 26 8. Multicast ......................................................27
11. Routing Extensions . . . . . . . . . . . . . . . . . . . . . 27 9. Fast Reroute in an MPLS LDP Network ............................27
12. Incremental Deployment . . . . . . . . . . . . . . . . . . . 27 10. Encapsulation .................................................28
13. Manageability Considerations . . . . . . . . . . . . . . . . 27 11. Routing Extensions ............................................28
13.1. Pre-failure configuration . . . . . . . . . . . . . . . 28 12. Incremental Deployment ........................................28
13.2. Pre-failure Monitoring and operational support . . . . . 28 13. Manageability Considerations ..................................29
13.3. Failure action monitoring . . . . . . . . . . . . . . . 29 13.1. Pre-failure Configuration ................................29
14. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 29 13.2. Pre-failure Monitoring and Operational Support ...........29
15. Security Considerations . . . . . . . . . . . . . . . . . . . 29 13.3. Failure Action Monitoring ................................30
16. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 30 14. Security Considerations .......................................30
17. References . . . . . . . . . . . . . . . . . . . . . . . . . 30 15. Acknowledgements ..............................................31
17.1. Normative References . . . . . . . . . . . . . . . . . . 30 16. References ....................................................31
17.2. Informative References . . . . . . . . . . . . . . . . . 30 16.1. Normative References .....................................31
Appendix A. Q-Space . . . . . . . . . . . . . . . . . . . . . . 31 16.2. Informative References ...................................31
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 31 Appendix A. Q-Space ...............................................33
1. The Purpose of this Document 1. Introduction
1.1. The Purpose of This Document
This document presents an illustrative framework for providing fast This document presents an illustrative framework for providing fast
re-route around a failure in an IP or MPLS network based on the reroute around a failure in an IP or MPLS network based on the
concept of tunnelling or encapsulating packets via an IP address that concept of tunneling or encapsulating packets via an IP address that
is known to avoid the failure. The general approach described uses a is known to avoid the failure. The general approach described here
single level of encapsulation and could be used to protect unicast, uses a single level of encapsulation and could be used to protect
multicast, and LDP traffic against link, router, and shared risk unicast, multicast, and LDP traffic against link, router, and shared
group failure, regardless of network topology and metrics. risk group failure, regardless of network topology and metrics.
At the time of publication there is no demand to deploy this At the time of publication, there is no demand to deploy this
technology, however in view of the subtleties involved in the design technology; however, in view of the subtleties involved in the design
of routing protocol extensions to provide IP Fast Reroute (IPFRR) the of routing protocol extensions to provide IP Fast Reroute (IPFRR)
Routing Area Working Group considered it desirable to publish this [RFC5714], the Routing Area Working Group considered it desirable to
document to place on record the design consideration of the not-via publish this document to place on record the design considerations of
address approach. the not-via address approach.
The mechanisms presented in this document are purely illustrative of The mechanisms presented in this document are purely illustrative of
the general approach and do not constitute a protocol specification. the general approach and do not constitute a protocol specification.
The document represents a snapshot of the work of the working group 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. at the time of publication and is published as a document of record.
Additional work is needed to specify the necessary routing protocol Additional work is needed to specify the necessary routing protocol
extensions necessary to support this IPFRR method before extensions necessary to support this IPFRR method before
implementation or deployment. implementation or deployment.
2. Introduction 1.2. Overview
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 IPFRR [RFC5714], the routers that are the neighbors of the
neighbors of the failure repair the failure. These repairing routers failure repair the failure. These repairing routers have to steer
have to steer packets to their destinations despite the fact that packets to their destinations despite the fact that most other
most other routers in the network are unaware of the nature and routers in the network are unaware of the nature and location of the
location of the failure. 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 explicitly steer the
repaired packet round the failure. The extent to which this repaired packet around 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 that, 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.
3. Overview of Not-via Repairs 2. Requirements Language
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC 2119 [RFC2119].
3. Overview of 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
| |
S----------P----------B. . . . . . . . . .D S----------P----------B. . . . . . . . . .D
\ | Bp^ \ | Bp^
\ | | \ | |
\ | | \ | |
\ 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 of not being
reachable from node P, i.e. the notation Bp means "an address of 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 node B that is only reachable not via node P". We later show how to
install the path from S to Bp such that it is the shortest path from install the path from S to Bp such that it is the shortest path from
S to B not going via P. If the network contains a path from S to B S to B not going via P. If the network contains a path from S to B
that does not transit router P, i.e. the network is not partitioned that does not transit router P, i.e., the network is not partitioned
by the failure of P and the path from S to Bp has been installed, by the failure of P and the path from S to Bp has been installed,
then the packet will be successfully delivered to B. In the example then the packet will be successfully delivered to B. In the example
we are considering this is the path S-X-Y-Z-B. When the packet in Figure 1, this is the path S-X-Y-Z-B. When the packet addressed
addressed to Bp arrives at B, B removes the encapsulation and to Bp arrives at B, B removes the encapsulation and forwards the
forwards the repaired packet towards its final destination. 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
track after the encapsulation is removed. However, because the backtrack 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
not-via address (one for each neighbor) allowing traffic to be not-via addresses (one for each neighbor) allowing traffic to be
directed to P without traversing each of those neighbors. directed to P without traversing each of those neighbors.
The not-via addresses are advertised in the routing protocol in a way The not-via addresses are advertised in the routing protocol in a way
that clearly identifies them as not-via addresses and not 'ordinary' that clearly identifies them as not-via addresses and not 'ordinary'
addresses. addresses.
A A
|Ap |Ap
| |
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
3.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
ECMP. to ECMP.
3.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 (LFAs) 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.
LFAs are computed on a per destination basis and in general, only a LFAs are computed on a per-destination basis, and in general only a
subset of the destinations requiring repair will have a suitable LFA subset of the destinations requiring repair will have a suitable LFA
repair. In this case, those destinations which are repairable by repair. In this case, those destinations that are repairable by LFAs
LFAs are so repaired and the remainder of the destinations are are so repaired, and the remainder of the destinations are repaired
repaired using the not-via encapsulation. On the other hand, the using the not-via encapsulation. On the other hand, the path taken
path taken by an LFA repair may be less optimal than that of the by an LFA repair may be less optimal than that of the equivalent
equivalent not-via repair for traffic destined to nodes close to the not-via repair for traffic destined to nodes close to the far end of
far end of the failure, but may be more optimal for some other the failure, but it may be more optimal for some other traffic. This
traffic. The description in this document assumes that LFAs will be document assumes that LFAs will be used where available, but the
used where available, but the distribution of repairs between the two distribution of repairs between the two mechanisms is a local
mechanisms is a local implementation choice. implementation choice.
4. 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 (SPF) algorithm, 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
in the network, one at a time, and calculates its own best route to in the network, one at a time, and calculates its own best route to
each of the neighbors of that router. In other words, with reference each of the neighbors of that router. In other words, with reference
to Figure 1, routers A, B, C, X, Y, Z and P will consider each router to Figure 1, routers A, B, C, X, Y, Z, and P will consider each
in turn, assume that router has failed, and then calculate its own router in turn, assume that the router has failed, and then calculate
route to each of the not-via addresses advertised by the neighbors of its own route to each of the not-via addresses advertised by the
that router. In other words in the case of a presumed failure of P, neighbors of that router. In other words, in the case of a presumed
ALL routers (in this case S, A, B, C, X, Y and Z) calculate their failure of P, ALL routers (S, A, B, C, X, Y, and Z in this case)
routes to Sp, Ap, Bp, and Cp, in each case, not via P. calculate their routes to Sp, Ap, Bp, and Cp -- in each case,
not via P.
To calculate the repair paths a router has to calculate n-1 SPFs To calculate the repair paths, a router has to calculate n-1 SPFs
where n is the number of routers in the network. This is expensive where n is the number of routers in the network. This is expensive
to compute. However, the problem is amenable to a solution in which to compute. However, the problem is amenable to a solution in which
each router (X) proceeds as follows. X first calculates the base each router (X) proceeds as follows. X first calculates the base
topology with all routers functional and determines its normal path topology with all routers functional and determines its normal path
to all not-via addresses. This can be performed as part of the to all not-via addresses. This can be performed as part of the
normal SPF computation. For each router P in the topology, X then normal SPF computation. For each router P in the topology, X then
performs the following actions:- performs the following actions:
1. Removes router P from the topology. 1. Removes router P from the topology.
2. Performs an incremental SPF (iSPF) [ISPF] on the modified 2. Performs an incremental SPF (iSPF) [ISPF] on the modified
topology. The iSPF process involves detaching the sub-tree topology. The iSPF process involves detaching the sub-tree
affected by the removal of router P, and then re-attaching the affected by the removal of router P and then reattaching the
detached nodes. However, it is not necessary to run the iSPF to detached nodes. However, it is not necessary to run the iSPF
completion. It is sufficient to run the iSPF up to the point to completion. It is sufficient to run the iSPF up to the point
where all of the nodes advertising not-via P addresses have been where all of the nodes advertising not-via P addresses have
re-attached to the SPT, and then terminate it. been reattached to the Shortest Path Tree (SPT), and then
terminate it.
3. Reverts to the base topology. 3. Reverts to the base topology.
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.
4.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 that 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 needs to be suppressed not is some neighbor, the advertisement of Np needs to be suppressed not
only across the link N->P, but also across any link to P. The only across the link N-P but also across any link to P. The simplest
simplest way of achieving this is for P itself to perform the way of achieving this is for P itself to perform the suppression of
suppression of any address of the form Xp. any address of the form Xp.
5. 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.
5.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
on the shortest path to Bp. S follows the same procedure for routers the shortest path to Bp. S follows the same procedure for routers A
A and C in Figure 2. The packet is decapsulated at the repair target 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.
5.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 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 the 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 neighbors 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 failed. S could therefore give the packet to any of its neighbors
(except, of course, P). However, S SHOULD send the encapsulated (except, of course, P). However, S SHOULD send the encapsulated
packet on the shortest available path to P. This path is calculated packet on the shortest available path to P. This path is calculated
by running an SPF with the link SP failed. Note that this may again by running an SPF with the link S-P removed. Note that this may
be an incremental calculation, which can terminate when address Ps again be an incremental calculation, which can terminate when address
has been reattached. Ps has been reattached.
5.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 6.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 A-P 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.
5.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 that is still able to reach X.
X X X X X X
| | | | | |
| | | | | |
| Sp |Pb | | Sp |Pb |
Z...............S----------P----------B...............Y Z...............S----------P----------B...............Y
Ps|Pc Bp Ps|Pc Bp
| |
Cp| Cp|
C C
Figure 3: Multi-homed Prefixes Figure 3: Multi-Homed Prefixes
S SHOULD choose the closest router that can reach X during the S SHOULD choose the closest router that can reach X during the
failure as the alternate router. S determines which router to use as failure as the alternate router. S determines which router to use as
the alternate while running the SPF with P failed. This is the alternate while running the SPF with P removed. This is
accomplished by the normal process of re-attaching a leaf node to the accomplished by the normal process of reattaching a leaf node to the
core topology (this is sometimes known as a "partial SPF"). core topology (this is sometimes known as a "partial SPF").
First, consider the case where the shortest alternate path to X is First, consider the case where the shortest alternate path to X is
via Z. S can reach Z without using the failed router P. However, S via Z. S can reach Z without using the removed router P. However, S
cannot just send the packet towards Z, because the other routers in cannot just send the packet towards Z, because the other routers in
the network will not be aware of the failure of P, and may loop the the network will not be aware of the failure of P and may loop the
packet back to S. S therefore encapsulates the packet to Z (using a packet back to S. S therefore encapsulates the packet to Z (using a
normal address for Z). When Z receives the encapsulated packet it normal address for Z). When Z receives the encapsulated packet, it
removes the encapsulation and forwards the packet to X. removes the encapsulation and forwards the packet to X.
Now consider the case where the shortest alternate path to X is via Now consider the case where the shortest alternate path to X is via
Y, which S reaches via P and B. To reach Y, S must first repair the Y, which S reaches via P and B. To reach Y, S must first repair the
packet to B using the normal not-via repair mechanism. To do this S packet to B using the normal not-via repair mechanism. To do this, S
encapsulates the packet for X to Bp. When B receives the packet it encapsulates the packet for X to Bp. When B receives the packet, it
removes the encapsulation and discovers that the packet is intended removes the encapsulation and discovers that the packet is intended
for MHP X. The situation now reverts to the previous case, in which for MHP X. The situation now reverts to the previous case, in which
the shortest alternate path does not require traversal of the the shortest alternate path does not require traversal of the
failure. B therefore follows the algorithm above and encapsulates failure. B therefore follows the algorithm above and encapsulates
the packet to Y (using a normal address for Y). Y removes the the packet to Y (using a normal address for Y). Y removes the
encapsulation and forwards the packet to X. encapsulation and forwards the packet to X.
It may be that the cost of reaching X using local delivery from the It may be that the cost of reaching X using local delivery from the
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.
5.4. Installation of Repair Paths 5.4. Installation of Repair Paths
The following algorithm is used by node S (Figure 3) to pre-calculate The following algorithm is used by node S (Figure 3) to pre-calculate
and install repair paths in the Forwarding Information Base (FIB), and install repair paths in the Forwarding Information Base (FIB),
ready for immediate use in the event of a failure. It is assumed ready for immediate use in the event of a failure. It is assumed
that the not-via repair paths have already been calculated as that the not-via repair paths have already been calculated as
skipping to change at page 10, line 19 skipping to change at page 11, line 17
needed to repair MHPs to the alternate router. needed to repair MHPs to the alternate router.
5.4. Installation of Repair Paths 5.4. Installation of Repair Paths
The following algorithm is used by node S (Figure 3) to pre-calculate The following algorithm is used by node S (Figure 3) to pre-calculate
and install repair paths in the Forwarding Information Base (FIB), and install repair paths in the Forwarding Information Base (FIB),
ready for immediate use in the event of a failure. It is assumed ready for immediate use in the event of a failure. It is assumed
that the not-via repair paths have already been calculated as that the not-via repair paths have already been calculated as
described above. described above.
For each neighbor P, consider all destinations which are reachable For each neighbor P, consider all destinations that are reachable via
via P in the current topology:- 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
during the normal SPF run by recording the additional during the normal SPF run by recording the additional
information. If S has a path to the not-via address Hp (H not information. If S has a path to the not-via address Hp (H not
via P), install a not-via repair to Hp for the destination DR. via P), install a not-via repair to Hp for the destination DR.
3. Identify all remaining destinations (M) which can still be 3. Identify all remaining destinations (M) that can still be reached
reached when node P fails. These will be multi-homed prefixes when node P fails. These will be multi-homed prefixes that are
that are not repairable by LFA, for which the normal attachment not repairable by LFA, and for which the normal attachment node
node is P, or a router for which P is a single point of failure, is P (or a router for which P is a single point of failure), and
and have an alternative attachment point that is reachable after that have an alternative attachment point that is reachable after
P has failed. One way of determining these destinations would be P has failed. One way of determining these destinations would be
to run an SPF rooted at S with node P removed, but an to run an SPF rooted at S with node P removed, but an
implementation may record alternative attachment points during implementation may record alternative attachment points during
the normal SPF run. In either case, the next best point of the normal SPF run. In either case, the next-best point of
attachment can also be determined for use in step (4) below. attachment can also be determined for use in step (4) below.
4. For each multi-homed prefix (M) identified in step (3):- 4. For each multi-homed prefix (M) identified in step (3):
a. Identify the new attachment node (as shown in Figure 3). A. Identify the new attachment node (as shown in Figure 3).
This may be:- This may be:
a. Y, where the next hop towards Y is P, or o Y, where the next hop towards Y is P, or
b. Z, where the next hop towards Z is not P. o Z, where the next hop towards Z is not P.
If the attachment node is Z, install the repair for M as a If the attachment node is Z, install the repair for M as a
tunnel to Z' (where Z' is the address of Z that is used to tunnel to Z' (where Z' is the address of Z that is used to
force local forwarding). force local forwarding).
b. For the subset of prefixes (M) that remain (having attachment B. For the subset of prefixes (M) that remain (having attachment
point Y), install the repair path previously installed for point Y), install the repair path previously installed for
destination Y. destination Y.
For each destination (DS) that remains, install a not-via repair For each destination (DS) that remains, install a not-via repair
to Ps (P not via S). Note, these are destinations for which node to Ps (P not via S). Note that these are destinations for which
P is a single point of failure, and can only be repaired by node P is a single point of failure, and they can only be
assuming that the apparent failure of node P was simply a failure repaired by assuming that the apparent failure of node P was
of the S-P link. Note that, if available, a downstream path to P simply a failure of the S-P link. Note that, if available, a
MAY be used for such a repair. This cannot generate a persistent downstream path to P MAY be used for such a repair. This cannot
loop in the event of the failure of node P, but if one neighbor generate a persistent loop in the event of the failure of node P,
of P uses a not-via repair and another uses a downstream path, it but if one neighbor of P uses a not-via repair and another uses a
is possible for a packet sent on the downstream path to be downstream path, it is possible for a packet sent on the
returned to the sending node inside a not-via encapsulation. downstream path to be returned to the sending node inside a
Since packets destined to not-via addresses are not repaired, the not-via encapsulation. Since packets destined to not-via
packet will be dropped after executing a single turn loop. addresses are not repaired, the packet will be dropped after
executing a single turn of the loop.
Note that where multiple next-next-hops are available to reach DR, Note that where multiple next-next hops are available to reach DR,
any or several of them may be chosen from a routing correctness point any or several of them may be chosen from a routing correctness point
of view. Unless other factors require consideration the closest of view. Unless other factors require consideration, the closest
next-next-hop to the repairing router would be the normal choice. next-next hop to the repairing router would be the normal choice.
6. 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
skipping to change at page 11, line 51 skipping to change at page 12, line 48
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.
6.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
needs to be computed to avoid not only the adjacent link, but also needs to be computed to avoid not only the adjacent link but also all
all the links which are members of the same SRLG. the links that 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
"a". The semantics of the not-via address Ps changes from simply "P "a". The semantics of the not-via address Ps changes from simply "P
not-via the link S-P" to be "P not-via the link S-P or any other link not via the link S-P" to be "P not via the link S-P or any other link
with which S-P shares an SRLG" In Figure 4 this is the links that are with which S-P shares an SRLG". In Figure 4, these are the links
members of SRLG "a". I.e. links S-P and A-B. Since the information that are members of SRLG "a", i.e., links S-P and A-B. Since the
about SRLG membership of all links is available in the Link State information about SRLG membership of all links is available in the
Database, all nodes computing routes to the not-via address Ps can link-state database, all nodes computing routes to the not-via
infer these semantics, and perform the computation by failing all the address Ps can infer these semantics and perform the computation by
links in the SRLG when running the iSPF. failing all the links in the SRLG when running the iSPF.
Note that it is not necessary for S to consider repairs to any other Note that it is not necessary for S to consider repairs to any other
nodes attached to members of the SRLG (such as B). It is sufficient nodes attached to members of the SRLG (such as B). It is sufficient
for S to repair to the other end of the adjacent link (P in this for S to repair to the other end of the adjacent link (P in this
case). case).
a Ps a Ps
S----------P---------D S----------P---------D
| | | |
| a | | a |
A----------B A----------B
| | | |
| | | |
C----------E C----------E
Figure 4: Shared Risk Link Group Figure 4: Shared Risk Link Group
In some cases, it may be that the links comprising the SRLG occur in In some cases, it may be that the links comprising the SRLG occur in
series on the path from S to the destination D, as shown in Figure 5. series on the path from S to the destination D, as shown in Figure 5.
In this case, multiple consecutive repairs may be necessary. S will In this case, multiple consecutive repairs may be necessary. S will
first repair to Ps, then P will repair to Dp. In both cases, because first repair to Ps, then P will repair to Dp. In both cases, because
the links concerned are members of SRLG "a" the paths are computed to the links concerned are members of SRLG "a", the paths are computed
avoid all members of SRLG "a". to avoid all members of SRLG "a".
a Ps a Dp a Ps a Dp
S----------P---------D S----------P---------D
| | | | | |
| a | | | a | |
A----------B | A----------B |
| | | | | |
| | | | | |
C----------E---------F C----------E---------F
Figure 5: Shared Risk Link Group members in series Figure 5: Shared Risk Link Group Members in Series -
Decapsulation and Re-encapsulation by One Node
While the use of multiple repairs in series introduces some While the use of multiple repairs in series introduces some
additional overhead, these semantics avoid the potential additional overhead, these semantics avoid the potential
combinatorial explosion of not-via addresses that could otherwise combinatorial explosion of not-via addresses that could otherwise
occur. occur.
Note that although multiple repairs are used, only a single level of Note that although multiple repairs are used, only a single level of
encapsulation is required. This is because the first repair packet encapsulation is required. This is because the first repair packet
is decapsulated before the packet is re-encapsulated using the not- is decapsulated before the packet is re-encapsulated using the
via address corresponding to the far side of the next link which is a not-via address corresponding to the far side of the next link that
member of the same SRLG. In some cases the decapsulation and re- is a member of the same SRLG. In some cases, the decapsulation and
encapsulation takes place (at least notionally) at a single node, re-encapsulation take place (at least notionally) at a single node,
while in other cases, these functions may be performed by different while in other cases, these functions may be performed by different
nodes. This scenario is illustrated in Figure 6 below. nodes. This scenario is illustrated in Figure 6 below.
a Ps a Dg a Ps a Dg
S----------P---------G--------D S----------P---------G--------D
| | | | | | | |
| a | | | | a | | |
A----------B | | A----------B | |
| | | | | | | |
| | | | | | | |
C----------E---------F--------H C----------E---------F--------H
Figure 6: Shared Risk Link Group members in series Figure 6: Shared Risk Link Group Members in Series -
Decapsulation and Re-encapsulation by Different Nodes
In this case, S first encapsulates to Ps, and node P decapsulates the In this case, S first encapsulates to Ps, and node P decapsulates the
packet and forwards it "native" to G using its normal FIB entry for packet and forwards it "native" to G using its normal FIB entry for
destination D. G then repairs the packet to Dg. destination D. G then repairs the packet to Dg.
It can be shown that such multiple repairs can never form a loop It can be shown that such multiple repairs can never form a loop,
because each repair causes the packet to move closer to its because each repair causes the packet to move closer to its
destination. destination.
It is often the case that a single link may be a member of multiple It is often the case that a single link may be a member of multiple
SRLGs, and those SRLGs may not be isomorphic. This is illustrated in SRLGs, and those SRLGs may not be isomorphic. This is illustrated in
Figure 7 below. Figure 7 below.
ab Ps a Dg ab Ps a Dg
S----------P---------G--------D S----------P---------G--------D
| | | | | | | |
| a | | | | a | | |
A----------B | | A----------B | |
| | | | | | | |
| b | | b | | b | | b |
C----------E---------F--------H C----------E---------F--------H
| | | |
| | | |
J----------K J----------K
Figure 7: Multiple Shared Risk Link Groups Figure 7: Multiple Shared Risk Link Groups
The link SP is a member of SRLGs "a" and "b". When a failure of the The link S-P is a member of SRLGs "a" and "b". When a failure of the
link SP is detected, it MUST be assumed that BOTH SRLGs have failed. link S-P is detected, it MUST be assumed that BOTH SRLGs have failed.
Therefore, the not-via path to Ps needs to be computed by failing all
Therefore the not-via path to Ps needs to be computed by failing all links that are members of SRLG "a" or SRLG "b", i.e., the semantics
links which are members of SRLG "a" or SRLG "b". I.e. the semantics of Ps is now "P not via any links that are members of any of the
of Ps is now "P not-via any links which are members of any of the SRLGs of which link S-P is a member". This is illustrated in
SRLGs of which link SP is a member". This is illustrated in Figure 8 Figure 8 below.
below.
ab Ps a Dg ab Ps a Dg
S----/-----P---------G---/----D S----/-----P---------G---/----D
| | | | | | | |
| a | | | | a | | |
A----/-----B | | A----/-----B | |
| | | | | | | |
| b | | b | | b | | b |
C----/-----E---------F---/----H C----/-----E---------F---/----H
| | | |
| | | |
J----------K J----------K
Figure 8: Topology used for repair computation for link S-P Figure 8: Topology Used for Repair Computation for Link S-P
In this case, the repair path to Ps will be S-A-C-J-K-E-B-P. It may In this case, the repair path to Ps will be S-A-C-J-K-E-B-P. It may
appear that there is no path to D because GD is a member of SRLG "a" appear that there is no path to D because G-D is a member of SRLG "a"
and FH is a member of SRLG "b". This is true if BOTH SRLGs "a" and and F-H is a member of SRLG "b". This is true if BOTH SRLGs "a" and
"b" have in fact failed, which would be an instance of multiple "b" have in fact failed, which would be an instance of multiple
independent failures. In practice, it is likely that there is only a independent failures. In practice, it is likely that there is only a
single failure, i.e. either SRLG "a" or SRLG "b" has failed, but not single failure, i.e., either SRLG "a" or SRLG "b" has failed but not
both. These two possibilities are indistinguishable from the point both. These two possibilities are indistinguishable from the point
of view of the repairing router S and so it needs to repair on the of view of the repairing router S, and so it needs to repair on the
assumption that both are unavailable. However, each link repair is assumption that both are unavailable. However, each link repair is
considered independently. The repair to Ps delivers the packet to P considered independently. The repair to Ps delivers the packet to P,
which then forwards the packet to G. When the packet arrives at G, which then forwards the packet to G. When the packet arrives at G,
if SRLG "a" has failed it will be repaired around the path G-F-H-D. if SRLG "a" has failed, it will be repaired around the path G-F-H-D.
This is illustrated in Figure 9 below. If, on the other hand, SRLG This is illustrated in Figure 9 below. If, on the other hand, SRLG
"b" has failed, link GD will still be available. In this case the "b" has failed, link G-D will still be available. In this case, the
packet will be delivered as normal across the link GD. packet will be delivered as normal across the link G-D.
ab Ps a Dg ab Ps a Dg
S----/-----P---------G---/----D S----/-----P---------G---/----D
| | | | | | | |
| a | | | | a | | |
A----/-----B | | A----/-----B | |
| | | | | | | |
| b | | b | | b | | b |
C----------E---------F--------H C----------E---------F--------H
| | | |
| | | |
J----------K J----------K
Figure 9: Topology used for repair computation for link G-D Figure 9: Topology Used for Repair Computation for Link G-D
If both SRLG a and SRLG b had failed, the packet would be repaired as If both SRLG "a" and SRLG "b" had failed, the packet would be
far as P by S, and would be forwarded by P to G. G would encapsulate repaired as far as P by S and would be forwarded by P to G. G would
the packet to D using the not-via address Dg and forward it to F. F encapsulate the packet to D using the not-via address Dg and forward
would recognise that the its next hop to Dg (H) was unreachable due it to F. F would recognize that its next hop to Dg (H) was
to the failure of link FH (part of SRLG b) and would drop the packet, unreachable due to the failure of link F-H (part of SRLG "b") and
because packets addressed to a not-via address are not repaired in would drop the packet, because packets addressed to a not-via address
basic not-via IPFRR. are not repaired in basic not-via IPFRR.
The repair of multiple independent failures is not provided by the The repair of multiple independent failures is not provided by the
basic not-via IPFRR method described so far in this memo. basic not-via IPFRR method described so far in this memo.
A repair strategy that assumes the worst-case failure for each link A repair strategy that assumes the worst-case failure for each link
can often result in longer repair paths than necessary. In cases can often result in longer repair paths than necessary. In cases
where only a single link fails, rather than the full SRLG, this where only a single link fails rather than the full SRLG, this
strategy may occasionally fail to identify a repair even though a strategy may occasionally fail to identify a repair even though a
viable repair path exists in the network. The use of sub-optimal viable repair path exists in the network. The use of suboptimal
repair paths is an inevitable consequence of this compromise repair paths is an inevitable consequence of this compromise
approach. The failure to identify any repair is a serious approach. The failure to identify any repair is a serious deficiency
deficiency, but is a rare occurrence in a robustly designed network. but is a rare occurrence in a robustly designed network. This
This problem can be addressed by:- 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
[RFC5880] over alternate repair paths) to determine which SRLG Bidirectional Forwarding Detection (BFD) [RFC5880] over alternate
member(s) has actually failed and using this information to repair paths) to determine which SRLG member(s) have actually
select an appropriate pre-computed repair path. However, aside failed and using this information to select an appropriate
from the complexity of performing the diagnostics, this requires pre-computed repair path. However, aside from the complexity of
multiple not-via addresses per interface, which has poor scaling performing the diagnostics, this requires multiple not-via
properties. addresses per interface, which has poor scaling properties.
4. Using the mechanism described in Section 6.3 4. Using the mechanism described in Section 6.3.
6.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.
+--------------Q------C +--------------Q------C
| |
| |
| |
A--------S-------(N)-------------P------B A--------S-------(N)-------------P------B
| |
| |
| |
+--------------R------D +--------------R------D
Figure 10: Local Area Networks Figure 10: Local Area Networks
Consider the LAN shown in Figure 10. For connectivity purposes, we Consider the LAN shown in Figure 10. For connectivity purposes, we
consider that the LAN is represented by the pseudonode (N). To consider that the LAN is represented by the pseudonode (N). To
provide IPFRR protection, S needs to run a connectivity check to each provide IPFRR protection, S needs to run a connectivity check to each
of its protected LAN adjacencies P, Q, and R, using, for example BFD of its protected LAN adjacencies P, Q, and R, using, for example, BFD
[RFC5880]. [RFC5880].
When S discovers that it has lost connectivity to P, it is unsure When S discovers that it has lost connectivity to P, it is unsure
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
6.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
| |
As Sl | Pl Bl As Sl | Pl Bl
A--------S-------(N)------------P--------B A--------S-------(N)------------P--------B
Sa | Pb Sa | Pb
| |
| Rl Dl | Rl Dl
+-------------R--------D +-------------R--------D
Rd Rd
Figure 11: Local Area Networks - LAN SRLG Figure 11: Local Area Networks - LAN SRLG
In this case, when S detected that P had failed it would send traffic In this case, if S detected that P had failed, it would send traffic
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 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 would be addressed to P not via the LAN or any router attached to the
LAN (except of course P). LAN (except, of course, P).
Whilst this approach is simple, it assumes that a large portion of While this approach is simple, it assumes that a large portion of the
the network adjacent to the failure has also failed. This will network adjacent to the failure has also failed. This will result in
result in the use of sub-optimal repair paths and in some cases the the use of suboptimal repair paths and, in some cases, the inability
inability to identify a viable repair. to identify a viable repair.
6.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 needs to repair traffic sent through P and B, to B the failure, it needs to repair traffic sent through P and B, to an
not- via P,N (i.e. not via P and not via N), on the conservative address Bpn (B not-via P,N, i.e., B not via P and not via N), on the
assumption that both the entire LAN and P have failed. Destinations conservative assumption that both the entire LAN and P have failed.
for which P is a single point of failure MUST as usual be sent to P Destinations for which P is a single point of failure MUST, as usual,
using an address that avoids the interface by which P is reached from be sent to P using an address that avoids the interface by which P is
S, i.e. to P not-via N. Similarly for routers Q and R. reached from S, i.e., to P not via N. A similar process would also
apply for routers Q and R.
Notice that each router that is connected to a LAN MUST, as usual, Notice that each router that is connected to a LAN MUST, as usual,
advertise one not-via address for each neighbor. In addition, each advertise one not-via address for each neighbor. In addition, each
router on the LAN MUST advertise an extra address not via the router on the LAN MUST advertise an extra address not via the
pseudonode (N). pseudonode (P).
Notice also that each neighbor of a router connected to a LAN needs Notice also that each neighbor of a router connected to a LAN needs
to advertise two not-via addresses, the usual one not via the to advertise two not-via addresses: the usual one not via the
neighbor and an additional one, not via either the neighbor or the neighbor, and an additional one not via either the neighbor or the
pseudonode. The required set of LAN address assignments is shown in pseudonode. The required set of LAN address assignments is shown in
Figure 12 below. Each router on the LAN, and each of its neighbors, Figure 12 below. Each router on the LAN, and each of its neighbors,
is advertising exactly one address more than it would otherwise have are advertising exactly one address more than they would otherwise
advertised if this degree of connectivity had been achieved using have advertised if this degree of connectivity had been achieved
point-to-point links. using point-to-point links.
Qs Qp Qc Cqn Qs Qp Qc Cqn
+--------------Q---------C +--------------Q---------C
| Qr Qn Cq | Qr Qn Cq
| |
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 - Component Repair
6.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.
6.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 that 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 5.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 that are not part of an
anticipated group are detected, repairs are abandoned and the network anticipated group are detected, repairs are abandoned, and the
reverts to normal convergence. Although safe, this approach is network reverts to normal convergence. Although safe, this approach
somewhat draconian, since there are many circumstances were multiple is somewhat draconian, since there are many circumstances where
repairs do not induce loops. multiple 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.
6.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 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
\ / \ /
\ / \ /
X------//------Y X------//------Y
Figure 13: The General Case of Multiple Failures Figure 13: The General Case of Multiple Failures
The essential case is as illustrated in Figure 13. Note that The essential case is as illustrated in Figure 13. Note that,
depending on the repair case under consideration, there may be paths depending on the repair case under consideration, there may be other
present in Figure 13, that are in addition to those shown in the paths present in Figure 13, in addition to those shown in the figure.
figure. For example there may be paths between A and B, and/or For example, there may be paths between A and B, and/or between X
between X and Y. These paths are omitted for graphical clarity. and Y. These paths are omitted for graphical clarity.
There are three cases to consider: There are three cases to consider:
1) Consider the general case of a pair of protected links A-B and 1. Consider the general case of a pair of protected links A-B and
X-Y as shown in the network fragment shown Figure 13. If the X-Y, as shown in the network fragment shown in Figure 13. If the
repair path for A-B does not traverse X-Y and the repair path for repair path for A-B does not traverse X-Y and the repair path for
X-Y does not traverse A-B, this case is completely safe and will X-Y does not traverse A-B, this case is completely safe and will
not cause looping or packet loss. not cause looping or packet loss.
A more common variation of this case is shown in Figure 14, which A more common variation of this case is shown in Figure 14, which
shows two failures in different parts of the network in which a shows two failures in different parts of the network in which a
packet from A to D traverses two concatenated repairs. packet from A to D traverses two concatenated repairs.
A------//------B------------X------//------Y------D A------//------B------------X------//------Y------D
| | | | | | | |
| | | | | | | |
M--------------+ N--------------+ M--------------+ N--------------+
Figure 14: Concatenated Repairs Figure 14: Concatenated Repairs
2) In Figure 13, the repair for A-B traverses X-Y, but the repair 2. In Figure 13, the repair for A-B traverses X-Y, but the repair
for X-Y does not traverse A-B. This case occurs when the not-via for X-Y does not traverse A-B. This case occurs when the not-via
path from A to B traverses link X-Y, but the not-via path from X path from A to B traverses link X-Y but the not-via path from X
to Y traverses some path not shown in Figure 13. Without the to Y traverses some path not shown in Figure 13. Without the
multi-failure mechanism described in this section the repaired multi-failure mechanism described in this section, the repaired
packet for A-B would be dropped when it reached X-Y, since the packet for A-B would be dropped when it reached X-Y, since the
repair of repaired packets would be forbidden. However, if this repair of repaired packets would be forbidden. However, if this
packet were allowed to be repaired, the path to D would be packet were allowed to be repaired, the path to D would be
complete and no harm would be done, although two levels of complete and no harm would be done, although two levels of
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
traverses A-B. In this case unrestricted repair would result in A-B. In this case, unrestricted repair would result in looping
looping packets and increasing levels of encapsulation. 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.
6.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 that 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
traffic addressed to any not-via address arriving at A would be traffic addressed to any not-via address arriving at A would be
dropped. The new procedure modifies this such that any traffic for a dropped. The new procedure modifies this such that any traffic for a
not-via address normally reachable over A-B is also encapsulated to not-via address normally reachable over A-B is also encapsulated to
Ba unless the not-via address is one of those previously identified Ba, unless the not-via address is one of those previously identified
as being on the path to Ba, for example Yx, in which case the packet as being on the path to Ba -- for example, Yx, in which case the
is dropped. packet is dropped.
The above procedure allows cases 1 and 2 above to be repaired, while The above procedure allows cases 1 and 2 above to be repaired while
preventing the loop which would result from case 3. preventing the loop that would result from case 3.
Note that this is accomplished by pre-computing the required FIB Note that this is accomplished by pre-computing the required FIB
entries, and does not require any detailed packet inspection. The entries and does not require any detailed packet inspection. The
same result could be achieved by checking for multiple levels of same result could be achieved by checking for multiple levels of
encapsulation and dropping any attempt to triple encapsulate. encapsulation and dropping any attempt to triple encapsulate.
However, this would require more detailed inspection of the packet, However, this would require more detailed inspection of the packet
and causes difficulties when more than 2 "simultaneous" failures are and causes difficulties when more than 2 "simultaneous" failures are
contemplated. contemplated.
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 maximum at different nodes. There is, however, the issue of the maximum
transmission unit (MTU) impact of multiple encapsulations. transmission unit (MTU) impact of 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.
6.3.3. Looping Repairs 6.3.3. Mutually 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 apply the "Abandoning All Hope" (AAH) mechanism ([RFC6976],
(Appendix A) and immediately invoke normal re-convergence. Appendix A) and immediately invoke normal reconvergence.
Note that it is not sufficient to expedite the issuance of an LSP Note that it is not sufficient to expedite the issuance of a Link
reporting the failure, since this may be treated as a permitted State Packet (LSP) reporting the failure, since this may be treated
simultaneous failure by the ordered FIB (oFIB) algorithm as a permitted simultaneous failure by the ordered FIB (oFIB)
[I-D.ietf-rtgwg-ordered-fib]. It is therefore necessary to algorithm [RFC6976]. It is therefore necessary to explicitly trigger
explicitly trigger an oFIB AAH. an oFIB AAH.
6.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 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 X-Y). When the repairing node A, which has precomputed that X-Y
failures are mutually incompatible with its own repairs receives this failures are mutually incompatible with its own repairs, receives
LSP it can then issue the AAH. This has the disadvantage that it this LSP, it can then issue the AAH. This has the disadvantage
does not overcome the hold-down delay, but it requires no "data- that it does not overcome the hold-down delay, but it requires no
driven" operation, and it still has the required effect of abandoning "data-driven" operation, and it still has the required effect of
the oFIB which is probably the longer of the delays (although with abandoning the oFIB, which is probably the longer of the delays
signalled oFIB this should be sub-second). (although with signaled oFIB this should be sub-second).
Whilst both of the experimental approaches described above are While 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. predetermination that has been applied to existing IPFRR solutions.
6.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 pre-compute the With a link-state routing protocol, it is possible to pre-compute 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.
This approach requires us to identify the mutually incompatible This approach requires us to identify the mutually incompatible
failures, and advertise them as "secondary SRLGs". When computing failures and advertise them as "secondary SRLGs". When computing the
the repair paths for the affected not-via addresses these links are repair paths for the affected not-via addresses, these links are
simultaneously failed. Note that the assumed simultaneous failure simultaneously removed. Note that the assumed simultaneous failure
and resulting repair path only applies to the repair path computed and resulting repair path only apply to the repair path computed for
for the conflicting not-via addresses, and is not used for normal the conflicting not-via addresses and are not used for normal
addresses. This implies that although there will be a longer repair addresses. This implies that although there will be a longer repair
path when there is more than one failure, if there is a single path when there is more than one failure, if there is a single
failure the repair path length will be "normal". failure the repair path length will be "normal".
Ideally we would wish to only invoke secondary SRLG computation when Ideally, we would wish to only invoke secondary SRLG computation when
we are sure that the repair paths are mutually incompatible. we are sure that the repair paths are mutually incompatible.
Consider the case of node A in Figure 13. A first identifies that Consider the case of node A in Figure 13. Node A first identifies
the repair path for A-B is via F-X-Y-G-B. It then explores this path that the repair path for A-B is via F-X-Y-G-B. It then explores this
determining the repair path for each link in the path. Thus, for path, determining the repair path for each link in the path. Thus,
example, it performs a check at X by running an SPF rooted at X with for example, it performs a check at X by running an SPF rooted at X
the X-Y link removed to determine whether A-B is indeed on X's repair with the X-Y link removed to determine whether A-B is indeed on X's
path for packets addressed to Yx. repair path for packets addressed to Yx.
Some optimizations are possible in this calculation, which appears at Some optimizations are possible in this calculation, which appears at
first sight to be order hk (where h is the average hop length of first sight to be order hk (where h is the average hop length of
repair paths and k is the average number of neighbours of a router). repair paths and k is the average number of neighbors of a router).
When A is computing its set of repair paths, it does so for all its k When A is computing its set of repair paths, it does so for all its k
neighbours. In each case it identifies a list of node pairs neighbors. In each case, it identifies a list of node pairs
traversed by each repair. These lists may often have one or more traversed by each repair. These lists may often have one or more
node pairs in common, so the actual number of link failures which node pairs in common, so the actual number of link failures that
require investigation is the union of these sets. It is then require investigation is the union of these sets. It is then
necessary to run an SPF rooted at the first node of each pair (the necessary to run an SPF rooted at the first node of each pair (the
first node because the pairings are ordered representing the first node, because the pairings are ordered representing the
direction of the path), with the link to the second node removed. direction of the path), with the link to the second node removed.
This SPF, while not an incremental, can be terminated as soon as the This SPF, while not an incremental, can be terminated as soon as the
not-via address is reached. For example, when running the SPF rooted not-via address is reached. For example, when running the SPF rooted
at X, with the link X-Y removed, the SPF can be terminated when Yx is at X, with the link X-Y removed, the SPF can be terminated when Yx is
reached. Once the path has been found, the path is checked to reached. Once the path has been found, the path is checked to
determine if it traverses any of A's links in the direction away from determine if it traverses any of A's links in the direction away from
A. Note that, because the node pair XY may exist in the list for A. Note that because the node pair X-Y may exist in the list for
more than one of A's links (i.e. it lies on more than one repair more than one of A's links (i.e., it lies on more than one repair
path), it is necessary to identify the correct list, and hence link path), it is necessary to identify the correct list, and hence link,
which has a mutually looping repair path. That link of A is then that has a mutually looping repair path. That link of A is then
advertised by A as a secondary SRLG paired with the link X-Y. Also advertised by A as a secondary SRLG paired with the link X-Y. Also
note that X will be running this algorithm as well, and will identify note that X will be running this algorithm as well, and will identify
that XY is paired with A-B and so advertise it. This could perhaps that X-Y is paired with A-B and so advertise it. This could perhaps
be used as a further check. be used as a further check.
The ordering of the pairs in the lists is important. i.e. X-Y and The ordering of the pairs in the lists is important, i.e., X-Y and
Y-X are dealt with separately. If and only if the repairs are Y-X are dealt with separately. If and only if the repairs are
mutually incompatible, we need to advertise the pair of links as a mutually incompatible, we need to advertise the pair of links as a
secondary SRLG, and then ALL nodes compute repair paths around both secondary SRLG, and then ALL nodes compute repair paths around both
failures using an additional not-via address with the semantics not- failures using an additional not-via address with the semantics
via A-B AND not-via X-Y. not-via A-B AND not-via X-Y.
A further possibility is that because we are going to the trouble of A further possibility is that because we are going to the trouble of
advertising these SRLG sets, we could also advertise the new repair advertising these SRLG sets, we could also advertise the new repair
path and only get the nodes on that path to perform the necessary path and only get the nodes on that path to perform the necessary
computation. Note also that once we have reached Q-space Appendix A computation. Note also that once we have reached Q-space
with respect to the two failures we need no longer continue the (Appendix A) with respect to the two failures, we need no longer
computation, so we only need to notify the nodes on the path that are continue the computation, so we only need to notify the nodes on the
not in Q-space. path that are not in Q-space.
One cause of mutually looping repair paths is the existence of nodes One cause of mutually looping repair paths is the existence of nodes
with only two links, or sections of the network which are only bi- with only two links, or sections of the network that are only
connected. In these cases, repair is clearly impossible - the bi-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.
6.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 practice 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 that 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 that 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
the well known node repair problem with LFAs [RFC5286]. If one link the well-known node repair problem with LFAs [RFC5286]. If one link
is using a downstream route, while the other is using a not-via is using a downstream route while the other is using a not-via
tunnel, the potential mechanism described above would work provided tunnel, the potential mechanism described above would work, provided
it were possible to determine the nodes on the path of the downstream it were possible to determine the nodes on the path of the downstream
route. Some methods of computing downstream routes do not provide route. Some methods of computing downstream routes do not provide
this path information. If the path information is however available, this path information. However, if the path information is
the link using a downstream route will have a discard FIB entry for available, the link using a downstream route will have a discard FIB
the not-via address of the other link. The consequence is that entry for the not-via address of the other link. The consequence is
potentially looping packets will be discarded when they attempt to that potentially looping packets will be discarded when they attempt
cross this link. to cross this link.
In the case where the mutual repairs are both using not-via repairs, In the case where the mutual repairs are both using not-via repairs,
the loop will be broken when the packet arrives at the second the loop will be broken when the packet arrives at the second
failure. However packets are unconditionally repaired by means of a failure. However, packets are unconditionally repaired by means of a
downstream routes, and thus when the mutual pair consists of a downstream routes, and thus when the mutual pair consists of a
downstream route and a not-via repair, the looping packet will only downstream route and a not-via repair, the looping packet will only
be dropped when it gets back to the first failure. i.e. it will be dropped when it gets back to the first failure, i.e., it will
execute a single turn of the loop before being dropped. execute a single turn of the loop before being dropped.
There is a further complication with downstream routes, since There is a further complication with downstream routes, since
although the path may be computed to the far side of the failure, the although the path may be computed to the far side of the failure, the
packet may "peel off" to its destination before reaching the far side packet may "peel off" to its destination before reaching the far side
of the failure. In this case it may traverse some other link which of the failure. In this case, it may traverse some other link that
has failed and was not accounted for on the computed path. If the has failed and was not accounted for on the computed path. If the
A-B repair (Figure 13) is a downstream route and the X-Y repair is a A-B repair (Figure 13) is a downstream route and the X-Y repair is a
not-via repair, we can have the situation where the X-Y repair not-via repair, we can have the situation where the X-Y repair
packets encapsulated to Yx follow a path which attempts to traverse packets encapsulated to Yx follow a path that attempts to traverse
A-B. If the A-B repair path for "normal" addresses is a downstream A-B. If the A-B repair path for "normal" addresses is a downstream
route, it cannot be assumed that the repair path for packets route, it cannot be assumed that the repair path for packets
addressed to Yx can be sent to the same neighbour. This is because addressed to Yx can be sent to the same neighbor. This is because
the validity of a downstream route MUST be ascertained in the the validity of a downstream route MUST be ascertained in the
topology represented by Yx, i.e. that with the link X-Y failed. topology represented by Yx, i.e., that with the link X-Y removed.
This is not the same topology that was used for the normal downstream This is not the same topology that was used for the normal downstream
calculation, and use of the normal downstream route for the calculation, and use of the normal downstream route for the
encapsulated packets may result in an undetected loop. If it is encapsulated packets may result in an undetected loop. If it is
computationally feasible to check the downstream route in this computationally feasible to check the downstream route in this
topology (i.e. for any not-via address Qp which traverses A-B we topology (i.e., for any not-via address Qp that traverses A-B, we
must perform the downstream calculation for that not-via address in must perform the downstream calculation for that not-via address in
the topology with link Q-P failed.), then the downstream repair for the topology with link Q-P removed), then the downstream repair for
Yx can safely be used. These packets cannot re-visit X-Y, since by Yx can safely be used. These packets cannot revisit 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).
7. 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. S-P 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 Link
associated with each LFA protected link. Routers computing not-via State Advertisement (LSA) associated with each link protected by an
routes can then omit the running of the iSPF for links with this bit LFA. Routers computing not-via routes can then omit the running of
set. the iSPF for links with this bit set.
When running the iSPF for a particular link AB, the calculating When running the iSPF for a particular link A-B, the calculating
router first checks whether the link AB is present in the existing router first checks whether the link A-B is present in the existing
SPT. If the link is not present in the SPT, no further work is SPT. If the link is not present in the SPT, no further work is
required. This check is a normal part of the iSPF computation. required. This check is a normal part of the iSPF computation.
If the link is present in the SPT, this optimization introduces a If the link is present in the SPT, this optimization introduces a
further check to determine whether the link is marked as protected by further check to determine whether the link is marked as protected by
an LFA in the direction in which the link appears in the SPT. If so an LFA in the direction in which the link appears in the SPT. If so,
the iSPF need not be performed. For example, if the link appears in the iSPF need not be performed. For example, if the link appears in
the SPT in the direction A->B and A has indicated that the link AB is the SPT in the direction A->B and A has indicated that the link A-B
protected by an LFA no further action is required for this link. is protected by an LFA, no further action is required for this link.
If the receipt of this information is delayed, the correct operation If the receipt of this information is delayed, the correct operation
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 S-P for which S-P is in the path to P, there is a significant
reduction in the computation required. reduction in the computation required.
8. Multicast 8. Multicast
Multicast traffic can be repaired in a similar way to unicast. The
Multicast traffic can be repaired in a way similar 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 Reverse receive interface and hence to correctly run the required Reverse
Path Forwarding (RPF) check. 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: 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 left for
study. further study.
9. 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 reroute in an MPLS network by first
first pushing the label which the repair endpoint uses to forward the pushing the label that the repair endpoint uses to forward the packet
packet, and then pushing the label corresponding to the not-via and then pushing the label corresponding to the not-via address
address needed to effect the repair. Referring once again to Figure needed to effect the repair. Referring once again to Figure 1, if S
1, if S has a packet destined for D that it must reach via P and B, S has a packet destined for D that it must reach via P and B, S first
first pushes B's label for D. S then pushes the label that its next pushes B's label for D. S then pushes the label that its next hop to
hop to Bp needs to reach Bp. 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 [NNHL].
[I-D.shen-mpls-ldp-nnhop-label].
10. 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
via repair. IP in IP [RFC2003], GRE [RFC1701] and L2TPv3 [RFC3931], not-via repair. IP in IP [RFC2003], Generic Routing Encapsulation
all have the necessary and sufficient properties. The requirement is (GRE) [RFC1701], and the Layer 2 Tunneling Protocol (L2TPv3)
that both the encapsulating router and the router to which the [RFC3931] all have the necessary and sufficient properties. The
encapsulated packet is addressed have a common ability to process the requirement is that both the encapsulating router and the router to
chosen encapsulation type. When an MPLS LDP network is being which the encapsulated packet is addressed have a common ability to
protected, the encapsulation would normally be an additional MPLS process the chosen encapsulation type. When an MPLS LDP network is
label. In an MPLS enabled IP network an MPLS label may be used in being protected, the encapsulation would normally be an additional
place of an IP in IP encapsulation in the case above. MPLS 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.
Care needs to be taken to ensure that the encapsulation used to Care needs to be taken to ensure that the encapsulation used to
provide a repair tunnel does not result in the packet exceeding the provide a repair tunnel does not result in the packet exceeding the
MTU of the links traversed by that repair. MTU of the links traversed by that repair.
11. 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 routers capable of supporting not-via routes
that they will calculate not-via routes. advertise in the IGP 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 7 is to be used, then the use If the optimization proposed in Section 7 is to be used, then the use
of the LFA in place of the not-via repair MUST also be signalled in of the LFA in place of the not-via repair MUST also be signaled in
the routing protocol. the routing protocol.
12. 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.
13. Manageability Considerations 13. Manageability Considerations
[RFC5714] outlines the general set of manageability consideration [RFC5714] outlines the general set of manageability considerations
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 of
manageability consideration: manageability considerations:
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
13.1. Pre-failure configuration 3. Failure action monitoring
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.
o Configuration of failure detection mechanisms. o Configuration of failure detection mechanisms.
o Setting a preference concerning the use of LFA. o Setting a preference concerning the use of LFAs.
o Configuring not-via address (per interface), or not-via address o Configuring a 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. The selection of the
the method to be used is outside the scope of this document. method to be used is outside the scope of this document.
13.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 include:
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.
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 traceroute 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. The selection of
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.
13.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]. IP Flow Information Export (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; this
not a well developed IETF technology. technique is not a well-developed IETF technology.
14. IANA Considerations
There are no IANA considerations that arise from this draft.
15. Security Considerations 14. 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 [RFC6169]. The primary method of protection SHOULD be network [RFC6169]. The primary method of protection SHOULD be
through the use of a private address space for the not-via addresses through the use of a private address space for the not-via addresses
[RFC1918],[RFC4193] . Repair endpoint addresses MUST NOT be [RFC1918] [RFC4193]. Repair endpoint addresses MUST NOT be
advertised outside the area, and MUST be filtered at the network advertised outside the routing domain over which not-via is deployed
entry points. In addition, a mechanism might be developed that and MUST be filtered at the network entry points. In addition, a
allowed the use of the mild security available through the use of a mechanism might be developed that allows the use of the mild security
key [RFC1701] [RFC3931]. With the deployment of such mechanisms, the available through the use of a key [RFC1701] [RFC3931]. With the
repair endpoints would not increase the security risk beyond that of deployment of such mechanisms, the repair endpoints would not
existing IP tunnel mechanisms. An attacker may attempt to overload a increase the security risk beyond that of existing IP tunnel
router by addressing an excessive traffic load to the de-capsulation mechanisms. An attacker may attempt to overload a router by
endpoint. Typically, routers take a 50% performance penalty in addressing an excessive traffic load to the decapsulation endpoint.
decapsulating a packet. The attacker could not be certain that the Typically, routers take a 50% performance penalty in decapsulating a
router would be impacted, and the extremely high volume of traffic packet. The attacker could not be certain that the router would be
needed, would easily be detected as an anomaly. If an attacker were impacted, and the extremely high volume of traffic needed would
able to influence the availability of a link, they could cause the easily be detected as an anomaly. If an attacker were able to
network to invoke the not-via repair mechanism. A network protected influence the availability of a link, they could cause the network to
by not-via IPFRR is less vulnerable to such an attack than a network invoke the not-via repair mechanism. A network protected by not-via
that undertook a full convergence in response to a link up/down IPFRR is less vulnerable to such an attack than a network that
event. undertook a full convergence in response to a link up/down event.
16. Acknowledgements 15. 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.
17. References 16. References
17.1. Normative References 16.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.
17.2. Informative References 16.2. Informative References
[I-D.ietf-rtgwg-ordered-fib] [ISPF] McQuillan, J., Richer, I., and E. Rosen, "ARPANET
Shand, M., Bryant, S., Previdi, S., Filsfils, C., Routing Algorithm Improvements", BBN Technical
Francois, P., and O. Bonaventure, "Framework for Loop-free Report 3803, 1978.
convergence using oFIB", draft-ietf-rtgwg-ordered-fib-09
(work in progress), January 2013.
[I-D.ietf-rtgwg-remote-lfa] [NNHL] Shen, N., Chen, E., and A. Tian, "Discovering LDP Next-
Bryant, S., Filsfils, C., Previdi, S., Shand, M., and S. Nexthop Labels", Work in Progress, May 2005.
Ning, "Remote LFA FRR", draft-ietf-rtgwg-remote-lfa-02
(work in progress), May 2013.
[I-D.shen-mpls-ldp-nnhop-label] [REMOTE-LFA] Bryant, S., Filsfils, C., Previdi, S., Shand, M., and
Shen, N., "Discovering LDP Next-Nexthop Labels", draft- N. So, "Remote LFA FRR", Work in Progress, May 2013.
shen-mpls-ldp-nnhop-label-02 (work in progress), May 2005.
[ISPF] McQuillan, J., Richer, I., and E. Rosen, "ARPANET Routing [RFC1701] Hanks, S., Li, T., Farinacci, D., and P. Traina,
Algorithm Improvements"", BBN Technical Report 3803, 1978. "Generic Routing Encapsulation (GRE)", RFC 1701,
October 1994.
[RFC1701] Hanks, S., Li, T., Farinacci, D., and P. Traina, "Generic [RFC1918] Rekhter, Y., Moskowitz, R., Karrenberg, D., Groot, G.,
Routing Encapsulation (GRE)", RFC 1701, October 1994. and E. Lear, "Address Allocation for Private
Internets", BCP 5, RFC 1918, February 1996.
[RFC1918] Rekhter, Y., Moskowitz, R., Karrenberg, D., Groot, G., and [RFC2003] Perkins, C., "IP Encapsulation within IP", RFC 2003,
E. Lear, "Address Allocation for Private Internets", BCP October 1996.
5, RFC 1918, February 1996.
[RFC2003] Perkins, C., "IP Encapsulation within IP", RFC 2003, [RFC3931] Lau, J., Townsley, M., and I. Goyret, "Layer Two
October 1996. Tunneling Protocol - Version 3 (L2TPv3)", RFC 3931,
March 2005.
[RFC3931] Lau, J., Townsley, M., and I. Goyret, "Layer Two Tunneling [RFC4193] Hinden, R. and B. Haberman, "Unique Local IPv6 Unicast
Protocol - Version 3 (L2TPv3)", RFC 3931, March 2005. Addresses", RFC 4193, October 2005.
[RFC4193] Hinden, R. and B. Haberman, "Unique Local IPv6 Unicast [RFC5036] Andersson, L., Minei, I., and B. Thomas, "LDP
Addresses", RFC 4193, October 2005. Specification", RFC 5036, October 2007.
[RFC5036] Andersson, L., Minei, I., and B. Thomas, "LDP [RFC5101] Claise, B., "Specification of the IP Flow Information
Specification", RFC 5036, October 2007. Export (IPFIX) Protocol for the Exchange of IP Traffic
Flow Information", RFC 5101, January 2008.
[RFC5101] Claise, B., "Specification of the IP Flow Information [RFC5286] Atlas, A. and A. Zinin, "Basic Specification for IP
Export (IPFIX) Protocol for the Exchange of IP Traffic Fast Reroute: Loop-Free Alternates", RFC 5286,
Flow Information", RFC 5101, January 2008. September 2008.
[RFC5286] Atlas, A. and A. Zinin, "Basic Specification for IP Fast [RFC5714] Shand, M. and S. Bryant, "IP Fast Reroute Framework",
Reroute: Loop-Free Alternates", RFC 5286, September 2008. RFC 5714, January 2010.
[RFC5714] Shand, M. and S. Bryant, "IP Fast Reroute Framework", RFC [RFC5880] Katz, D. and D. Ward, "Bidirectional Forwarding
5714, January 2010. Detection (BFD)", RFC 5880, June 2010.
[RFC5880] Katz, D. and D. Ward, "Bidirectional Forwarding Detection [RFC6169] Krishnan, S., Thaler, D., and J. Hoagland, "Security
(BFD)", RFC 5880, June 2010. Concerns with IP Tunneling", RFC 6169, April 2011.
[RFC6169] Krishnan, S., Thaler, D., and J. Hoagland, "Security [RFC6976] Shand, M., Bryant, S., Previdi, S., Filsfils, C.,
Concerns with IP Tunneling", RFC 6169, April 2011. Francois, P., and O. Bonaventure, "Framework for Loop-
Free Convergence Using the Ordered Forwarding
Information Base (oFIB) Approach", RFC 6976, July 2013.
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 described fully in
[I-D.ietf-rtgwg-remote-lfa]. [REMOTE-LFA].
S---E S---Eq
/ \ / \
A D A Dq
\ / \ /
B---C B---Cq
Figure 15 Figure 15: The Q Space of E with Respect to the Link S-E
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
which the node E can be reached, by normal forwarding, without which the node E can be reached, by normal forwarding, without
traversing the link S-E is termed the Q-space of E with respect to 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 computing a reverse the link S-E. The Q-space can be obtained by computing a reverse
shortest path tree (rSPT) rooted at E, with the sub-tree which Shortest Path Tree (rSPT) rooted at E, with the sub-tree that
traverses the failed link excised (including those which are members traverses the failed link excised (including those that are members
of an ECMP). The rSPT uses the cost towards the root rather than of an ECMP). The rSPT uses the cost towards the root rather than
from it and yields the best paths towards the root from other nodes from it and yields the best paths towards the root from other nodes
in the network. In the case of Figure 15 the Q-space comprises nodes in the network. In the case of Figure 15, the Q-space comprises
C and D only. nodes E, D, and C only.
Authors' Addresses Authors' Addresses
Stewart Bryant Stewart Bryant
Cisco Systems Cisco Systems
250, Longwater Avenue. 10 New Square, Bedfont Lakes
Reading, Berks RG2 6GB Feltham, Middlesex TW18 8HA
UK UK
Email: stbryant@cisco.com EMail: stbryant@cisco.com
Stefano Previdi Stefano Previdi
Cisco Systems Cisco Systems
Via Del Serafico, 200 Via Del Serafico, 200
00142 Rome 00142 Rome
Italy Italy
Email: sprevidi@cisco.com EMail: sprevidi@cisco.com
Mike Shand Mike Shand
Individual Contributor Individual Contributor
Email: imc.shand@googlemail.com EMail: imc.shand@googlemail.com
 End of changes. 264 change blocks. 
717 lines changed or deleted 723 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/