draft-ietf-rtgwg-ipfrr-spec-base-12.txt   rfc5286.txt 
Routing Area Working Group A. Atlas, Ed. Network Working Group A. Atlas, Ed.
Internet-Draft BT Request for Comments: 5286 BT
Intended status: Standards Track A. Zinin, Ed. Category: Standards Track A. Zinin, Ed.
Expires: September 28, 2008 Alcatel Alcatel-Lucent
Mar 27, 2008 September 2008
Basic Specification for IP Fast-Reroute: Loop-free Alternates
draft-ietf-rtgwg-ipfrr-spec-base-12
Status of this Memo
By submitting this Internet-Draft, each author represents that any
applicable patent or other IPR claims of which he or she is aware
have been or will be disclosed, and any of which he or she becomes
aware will be disclosed, in accordance with Section 6 of BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet-
Drafts.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt.
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
This Internet-Draft will expire on September 28, 2008. Basic Specification for IP Fast Reroute: Loop-Free Alternates
Copyright Notice Status of This Memo
Copyright (C) The IETF Trust (2008). This document specifies an Internet standards track protocol for the
Internet community, and requests discussion and suggestions for
improvements. Please refer to the current edition of the "Internet
Official Protocol Standards" (STD 1) for the standardization state
and status of this protocol. Distribution of this memo is unlimited.
Abstract Abstract
This document describes the use of loop-free alternates to provide This document describes the use of loop-free alternates to provide
local protection for unicast traffic in pure IP and MPLS/LDP networks local protection for unicast traffic in pure IP and MPLS/LDP networks
in the event of a single failure, whether link, node or shared risk in the event of a single failure, whether link, node, or shared risk
link group (SRLG). The goal of this technology is to reduce the link group (SRLG). The goal of this technology is to reduce the
packet loss that happens while routers converge after a topology packet loss that happens while routers converge after a topology
change due to a failure. Rapid failure repair is achieved through change due to a failure. Rapid failure repair is achieved through
use of precalculated backup next-hops that are loop-free and safe to use of precalculated backup next-hops that are loop-free and safe to
use until the distributed network convergence process completes. use until the distributed network convergence process completes.
This simple approach does not require any support from other routers. This simple approach does not require any support from other routers.
The extent to which this goal can be met by this specification is The extent to which this goal can be met by this specification is
dependent on the topology of the network. dependent on the topology of the network.
Table of Contents Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1. Failure Scenarios . . . . . . . . . . . . . . . . . . . . 5 1.1. Failure Scenarios . . . . . . . . . . . . . . . . . . . . 5
1.2. Requirement Language . . . . . . . . . . . . . . . . . . . 8
2. Applicability of Described Mechanisms . . . . . . . . . . . . 8 2. Applicability of Described Mechanisms . . . . . . . . . . . . 8
3. Alternate Next-Hop Calculation . . . . . . . . . . . . . . . . 9 3. Alternate Next-Hop Calculation . . . . . . . . . . . . . . . . 9
3.1. Basic Loop-free Condition . . . . . . . . . . . . . . . . 10 3.1. Basic Loop-Free Condition . . . . . . . . . . . . . . . . 10
3.2. Node-Protecting Alternate Next-Hops . . . . . . . . . . . 10 3.2. Node-Protecting Alternate Next-Hops . . . . . . . . . . . 10
3.3. Broadcast and NBMA Links . . . . . . . . . . . . . . . . . 11 3.3. Broadcast and Non-Broadcast Multi-Access (NBMA) Links . . 11
3.4. ECMP and Alternates . . . . . . . . . . . . . . . . . . . 12 3.4. ECMP and Alternates . . . . . . . . . . . . . . . . . . . 12
3.5. Interactions with ISIS Overload, RFC 3137 and Costed 3.5. Interactions with IS-IS Overload, RFC 3137, and Costed
Out Links . . . . . . . . . . . . . . . . . . . . . . . . 13 Out Links . . . . . . . . . . . . . . . . . . . . . . . . 13
3.5.1. Interactions with ISIS Link Attributes . . . . . . . . 14 3.5.1. Interactions with IS-IS Link Attributes . . . . . . . 14
3.6. Selection Procedure . . . . . . . . . . . . . . . . . . . 14 3.6. Selection Procedure . . . . . . . . . . . . . . . . . . . 14
3.7. LFA types and Trade-offs . . . . . . . . . . . . . . . . . 18 3.7. LFA Types and Trade-Offs . . . . . . . . . . . . . . . . . 18
3.8. A Simplification: Per-Next-Hop LFAs . . . . . . . . . . . 19 3.8. A Simplification: Per-Next-Hop LFAs . . . . . . . . . . . 19
4. Using an Alternate . . . . . . . . . . . . . . . . . . . . . . 20 4. Using an Alternate . . . . . . . . . . . . . . . . . . . . . . 20
4.1. Terminating Use of Alternate . . . . . . . . . . . . . . . 20 4.1. Terminating Use of Alternate . . . . . . . . . . . . . . . 20
5. Requirements on LDP Mode . . . . . . . . . . . . . . . . . . . 22 5. Requirements on LDP Mode . . . . . . . . . . . . . . . . . . . 22
6. Routing Aspects . . . . . . . . . . . . . . . . . . . . . . . 22 6. Routing Aspects . . . . . . . . . . . . . . . . . . . . . . . 22
6.1. Multi-Homed Prefixes . . . . . . . . . . . . . . . . . . . 22 6.1. Multi-Homed Prefixes . . . . . . . . . . . . . . . . . . . 22
6.2. ISIS . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 6.2. IS-IS . . . . . . . . . . . . . . . . . . . . . . . . . . 24
6.3. OSPF . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 6.3. OSPF . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
6.3.1. OSPF External Routing . . . . . . . . . . . . . . . . 24 6.3.1. OSPF External Routing . . . . . . . . . . . . . . . . 24
6.3.2. OSPF Multi-Topology . . . . . . . . . . . . . . . . . 25 6.3.2. OSPF Multi-Topology . . . . . . . . . . . . . . . . . 25
6.4. BGP Next-Hop Synchronization . . . . . . . . . . . . . . . 25 6.4. BGP Next-Hop Synchronization . . . . . . . . . . . . . . . 25
6.5. Multicast Considerations . . . . . . . . . . . . . . . . . 25 6.5. Multicast Considerations . . . . . . . . . . . . . . . . . 25
7. Security Considerations . . . . . . . . . . . . . . . . . . . 25 7. Security Considerations . . . . . . . . . . . . . . . . . . . 25
8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 26 8. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 26
9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 26 9. References . . . . . . . . . . . . . . . . . . . . . . . . . . 26
10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 26 9.1. Normative References . . . . . . . . . . . . . . . . . . . 26
10.1. Normative References . . . . . . . . . . . . . . . . . . . 26 9.2. Informative References . . . . . . . . . . . . . . . . . . 26
10.2. Informative References . . . . . . . . . . . . . . . . . . 26
Appendix A. OSPF Example Where LFA Based on Local Area Appendix A. OSPF Example Where LFA Based on Local Area
Topology is Insufficient . . . . . . . . . . . . . . 27 Topology Is Insufficient . . . . . . . . . . . . . . 27
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 28
Intellectual Property and Copyright Statements . . . . . . . . . . 31
1. Introduction 1. Introduction
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", Applications for interactive multimedia services such as Voice over
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this IP (VoIP) and pseudowires can be very sensitive to traffic loss, such
document are to be interpreted as described in RFC 2119. [RFC2119] as occurs when a link or router in the network fails. A router's
convergence time is generally on the order of hundreds of
Applications for interactive multimedia services such as VoIP and milliseconds; the application traffic may be sensitive to losses
pseudo-wires can be very sensitive to traffic loss, such as occurs greater than tens of milliseconds.
when a link or router in the network fails. A router's convergence
time is generally on the order of hundreds of milliseconds; the
application traffic may be sensitive to losses greater than tens of
milliseconds.
As discussed in [I-D.ietf-rtgwg-ipfrr-framework], minimizing traffic As discussed in [FRAMEWORK], minimizing traffic loss requires a
loss requires a mechanism for the router adjacent to a failure to mechanism for the router adjacent to a failure to rapidly invoke a
rapidly invoke a repair path, which is minimally affected by any repair path, which is minimally affected by any subsequent re-
subsequent re-convergence. This specification describes such a convergence. This specification describes such a mechanism that
mechanism which allows a router whose local link has failed to allows a router whose local link has failed to forward traffic to a
forward traffic to a pre-computed alternate until the router installs pre-computed alternate until the router installs the new primary
the new primary next-hops based upon the changed network topology. next-hops based upon the changed network topology. The terminology
The terminology used in this specification is given in used in this specification is given in [FRAMEWORK]. The described
[I-D.ietf-rtgwg-ipfrr-framework]. The described mechanism assumes mechanism assumes that routing in the network is performed using a
that routing in the network is performed using a link-state routing link-state routing protocol -- OSPF [RFC2328] [RFC2740] [RFC5340] or
protocol-- OSPF [RFC2328] [RFC2740] [I-D.ietf-ospf-ospfv3-update] or IS-IS [RFC1195] [RFC2966] (for IPv4 or IPv6). The mechanism also
ISIS [RFC1195] [RFC2966] (for IPv4 or IPv6). The mechanism also
assumes that both the primary path and the alternate path are in the assumes that both the primary path and the alternate path are in the
same routing area. same routing area.
When a local link fails, a router currently must signal the event to When a local link fails, a router currently must signal the event to
its neighbors via the IGP, recompute new primary next-hops for all its neighbors via the IGP, recompute new primary next-hops for all
affected prefixes, and only then install those new primary next-hops affected prefixes, and only then install those new primary next-hops
into the forwarding plane. Until the new primary next-hops are into the forwarding plane. Until the new primary next-hops are
installed, traffic directed towards the affected prefixes is installed, traffic directed towards the affected prefixes is
discarded. This process can take hundreds of milliseconds. discarded. This process can take hundreds of milliseconds.
skipping to change at page 4, line 22 skipping to change at page 4, line 4
| E | | N_1 | | E | | N_1 |
+-----+ +-----+ +-----+ +-----+
\ / \ /
\ \ 4 3 / / \ \ 4 3 / /
\| \ / |/ \| \ / |/
-+ \ +-----+ / +- -+ \ +-----+ / +-
\---| D |---/ \---| D |---/
+-----+ +-----+
Figure 1: Basic Topology Figure 1: Basic Topology
The goal of IP Fast Reroute (IPFRR) is to reduce failure reaction
time to 10s of milliseconds by using a pre-computed alternate next-
hop, in the event that the currently selected primary next-hop fails,
so that the alternate can be rapidly used when the failure is
detected. A network with this feature experiences less traffic loss
and less micro-looping of packets than a network without IPFRR.
There are cases where traffic loss is still a possibility since IPFRR
coverage varies, but in the worst possible situation a network with
IPFRR is equivalent with respect to traffic convergence to a network
without IPFRR.
The goal of IP Fast-Reroute is to reduce failure reaction time to 10s To clarify the behavior of IP Fast Reroute, consider the simple
of milliseconds by using a pre-computed alternate next-hop, in the
event that the currently selected primary next-hop fails, so that the
alternate can be rapidly used when the failure is detected. A
network with this feature experiences less traffic loss and less
micro-looping of packets than a network without IPFRR. There are
cases where traffic loss is still a possibility since IPFRR coverage
varies but in the worst possible situation a network with IPFRR is
equivalent with respect to traffic convergence to a network without
IPFRR.
To clarify the behavior of IP Fast-Reroute, consider the simple
topology in Figure 1. When router S computes its shortest path to topology in Figure 1. When router S computes its shortest path to
router D, router S determines to use the link to router E as its router D, router S determines to use the link to router E as its
primary next-hop. Without IP Fast-Reroute, that link is the only primary next-hop. Without IP Fast Reroute, that link is the only
next-hop that router S computes to reach D. With IP Fast-Reroute, S next-hop that router S computes to reach D. With IP Fast Reroute, S
also looks for an alternate next-hop to use. In this example, S also looks for an alternate next-hop to use. In this example, S
would determine that it could send traffic destined to D by using the would determine that it could send traffic destined to D by using the
link to router N_1 and therefore S would install the link to N_1 as link to router N_1 and therefore S would install the link to N_1 as
its alternate next-hop. At some later time, the link between router its alternate next-hop. At some later time, the link between router
S and router E could fail. When that link fails, S and E will be the S and router E could fail. When that link fails, S and E will be the
first to detect it. On detecting the failure, S will stop sending first to detect it. On detecting the failure, S will stop sending
traffic destined for D towards E via the failed link, and instead traffic destined for D towards E via the failed link, and instead
send the traffic to S's pre-computed alternate next-hop, which is the send the traffic to S's pre-computed alternate next-hop, which is the
link to N_1, until a new SPF is run and its results are installed. link to N_1, until a new SPF is run and its results are installed.
As with the primary next-hop, an alternate next-hop is computed for As with the primary next-hop, an alternate next-hop is computed for
each destination. The process of computing an alternate next-hop each destination. The process of computing an alternate next-hop
does not alter the primary next-hop computed via a standard SPF. does not alter the primary next-hop computed via a standard SPF.
If in the example of Figure 1, the link cost from N_1 to D increased If in the example of Figure 1, the link cost from N_1 to D increased
to 30 from 3, then N_1 would not be a loop-free alternate, because to 30 from 3, then N_1 would not be a loop-free alternate, because
the cost of the path from N_1 to D via S would be 17 while the cost the cost of the path from N_1 to D via S would be 17 while the cost
from N_1 directly to D would be 30. In real networks, we may often from N_1 directly to D would be 30. In real networks, we may often
face this situation. The existence of a suitable loop-free alternate face this situation. The existence of a suitable loop-free alternate
next-hop is dependent on the topology and the nature of the failure next-hop is dependent on the topology and the nature of the failure
the alternate is calculated for. for which the alternate is calculated.
This specification uses the terminology introduced in This specification uses the terminology introduced in [FRAMEWORK].
[I-D.ietf-rtgwg-ipfrr-framework]. In particular, it uses In particular, it uses Distance_opt(X,Y), abbreviated to D_opt(X,Y),
Distance_opt(X,Y), abbreviated to D_opt(X,Y), to indicate the to indicate the shortest distance from X to Y. S is used to indicate
shortest distance from X to Y. S is used to indicate the calculating the calculating router. N_i is a neighbor of S; N is used as an
router. N_i is a neighbor of S; N is used as an abbreviation when abbreviation when only one neighbor is being discussed. D is the
only one neighbor is being discussed. D is the destination under destination under consideration.
consideration.
A neighbor N can provide a loop-free alternate (LFA) if and only if A neighbor N can provide a loop-free alternate (LFA) if and only if
Distance_opt(N, D) < Distance_opt(N, S) + Distance_opt(S, D) Distance_opt(N, D) < Distance_opt(N, S) + Distance_opt(S, D)
Inequality 1: Loop-Free Criterion Inequality 1: Loop-Free Criterion
A sub-set of loop-free alternate are downstream paths which must meet A subset of loop-free alternates are downstream paths that must meet
a more restrictive condition that is applicable to more complex a more restrictive condition that is applicable to more complex
failure scenarios: failure scenarios:
Distance_opt(N, D) < Distance_opt(S, D) Distance_opt(N, D) < Distance_opt(S, D)
Inequality 2: Downstream Path Criterion Inequality 2: Downstream Path Criterion
1.1. Failure Scenarios 1.1. Failure Scenarios
The alternate next-hop can protect against a single link failure, a The alternate next-hop can protect against a single link failure, a
single node failure, failure of one or more links within a shared single node failure, failure of one or more links within a shared
risk link group failures, or a combination of these. Whenever a risk link group, or a combination of these. Whenever a failure
failure occurs that is more extensive than what the alternate was occurs that is more extensive than what the alternate was intended to
intended to protect, there is the possibility of temporarily looping protect, there is the possibility of temporarily looping traffic
traffic (note again, that such a loop would only last until the next (note again, that such a loop would only last until the next complete
complete SPF calculation). The example where a node fails when the SPF calculation). The example where a node fails when the alternate
alternate provided only link protection is illustrated below. If provided only link protection is illustrated below. If unexpected
unexpected simultaneous failures occur, then micro-looping may occur simultaneous failures occur, then micro-looping may occur since the
since the alternates are not pre-computed to avoid the set of failed alternates are not pre-computed to avoid the set of failed links.
links.
If only link protection is provided and the node fails, it is If only link protection is provided and the node fails, it is
possible for traffic using the alternates to experience micro- possible for traffic using the alternates to experience micro-
looping. This issue is illustrated in Figure 2. If Link(S->E) looping. This issue is illustrated in Figure 2. If Link(S->E)
fails, then the link-protecting alternate via N will work correctly. fails, then the link-protecting alternate via N will work correctly.
However, if router E fails, then both S and N will detect a failure However, if router E fails, then both S and N will detect a failure
and switch to their alternates. In this example, that would cause S and switch to their alternates. In this example, that would cause S
to redirect the traffic to N and N to redirect the traffic to S and to redirect the traffic to N and N to redirect the traffic to S and
thus causing a forwarding loop. Such a scenario can arise because thus causing a forwarding loop. Such a scenario can arise because
the key assumption, that all other routers in the network are the key assumption, that all other routers in the network are
forwarding based upon the shortest path, is violated because of a forwarding based upon the shortest path, is violated because of a
second simultaneous correlated failure - another link connected to second simultaneous correlated failure -- another link connected to
the same primary neighbor. If there are not other protection the same primary neighbor. If there are not other protection
mechanisms to handle node failure, a node failure is still a concern mechanisms to handle node failure, a node failure is still a concern
when only using link protecting LFAs. when only using link-protecting LFAs.
<@@@ <@@@
@@@> @@@>
+-----+ +-----+ +-----+ +-----+
| S |-------| N | | S |-------| N |
+-+---+ 5 +-----+ +-+---+ 5 +-----+
| | | |
| 5 4 | | | 5 4 | |
| | | \|/ | | | \|/
\|/ | | \|/ | |
skipping to change at page 6, line 46 skipping to change at page 6, line 37
Micro-looping of traffic via the alternates caused when a more Micro-looping of traffic via the alternates caused when a more
extensive failure than planned for occurs can be prevented via extensive failure than planned for occurs can be prevented via
selection of only downstream paths as alternates. A micro-loop due selection of only downstream paths as alternates. A micro-loop due
to the use of alternates can be avoided by using downstream paths to the use of alternates can be avoided by using downstream paths
because each succeeding router in the path to the destination must be because each succeeding router in the path to the destination must be
closer to the destination than its predecessor (according to the closer to the destination than its predecessor (according to the
topology prior to the failures). Although use of downstream paths topology prior to the failures). Although use of downstream paths
ensures that the micro-looping via alternates does not occur, such a ensures that the micro-looping via alternates does not occur, such a
restriction can severely limit the coverage of alternates. In restriction can severely limit the coverage of alternates. In
Figure 2, S would be able to use N as a downstream alternate, but N Figure 2, S would be able to use N as a downstream alternate, but N
could not use S; therefore N would have no alternate and would could not use S; therefore, N would have no alternate and would
discard the traffic, thus avoiding the micro-loop. discard the traffic, thus avoiding the micro-loop.
As shown above, the use of either a node protecting LFA (described in As shown above, the use of either a node-protecting LFA (described in
Section 3.2) or a downstream path provides protection against micro- Section 3.2) or a downstream path provides protection against micro-
looping in the event of node failure. There are topologies where looping in the event of node failure. There are topologies where
there may be either a node portecting LFA, a downstream path, both or there may be either a node-protecting LFA, a downstream path, both,
neither. A node may select either a node protecting LFA or a or neither. A node may select either a node-protecting LFA or a
downstream path without risk of causing micro-loops in the event of downstream path without risk of causing micro-loops in the event of
neighbor node failure. While a link-and-node-protecting LFA neighbor node failure. While a link-and-node-protecting LFA
guarantees protection against either link or node failure, a guarantees protection against either link or node failure, a
downstream path provides protection only against a link failure and downstream path provides protection only against a link failure and
may or may not provide protection against a node failure depending on may or may not provide protection against a node failure depending on
the protection available at the downstream node, but it cannot cause the protection available at the downstream node, but it cannot cause
a micro-loop. For example in Figure 2, if S uses N as a downstream a micro-loop. For example, in Figure 2, if S uses N as a downstream
path, although no looping can occur, the traffic will not be path, although no looping can occur, the traffic will not be
protected in the event of the failure of node E because N has no protected in the event of the failure of node E because N has no
viable repair path, and it will simply discard the packet. However, viable repair path, and it will simply discard the packet. However,
if N had a link and node protecting LFA or downstream path via some if N had a link-and-node-protecting LFA or downstream path via some
other path (not shown), then the repair may succeed. other path (not shown), then the repair may succeed.
Since the functionality of link and node protecting LFAs is greater Since the functionality of link-and-node-protecting LFAs is greater
than that of link protecting downstream paths, a router SHOULD select than that of link-protecting downstream paths, a router SHOULD select
a link and node protecting LFA over a link protecting downstream a link-and-node-protecting LFA over a link-protecting downstream
path. If there are any destinations for which a link and node path. If there are any destinations for which a link-and-node-
protecting LFA is not available, then by definition the path to all protecting LFA is not available, then by definition the path to all
of those destinations from any neighbor of the computing router (S) of those destinations from any neighbor of the computing router (S)
must be through the node (E) being protected (otherwise there would must be through the node (E) being protected (otherwise there would
be a node protecting LFA for that destination). Consequently, if be a node protecting LFA for that destination). Consequently, if
there exists a downstream path to the protected node as destination, there exists a downstream path to the protected node as destination,
then that downstream path may be used for all those destinations for then that downstream path may be used for all those destinations for
which a link and node protecting LFA is not available; the existence which a link-and-node-protecting LFA is not available; the existence
of a downstream path can be determined by a single check of the of a downstream path can be determined by a single check of the
condition Distance_opt(N, E) < Distance_opt(S, E). condition Distance_opt(N, E) < Distance_opt(S, E).
It may be desirable to find an alternate that can protect against It may be desirable to find an alternate that can protect against
other correlated failures (of which node failure is a specific other correlated failures (of which node failure is a specific
instance). In the general case, these are handled by shared risk instance). In the general case, these are handled by shared risk
link groups (SRLGs) where any links in the network can belong to the link groups (SRLGs) where any links in the network can belong to the
SRLG. General SRLGs may add unacceptably to the computational SRLG. General SRLGs may add unacceptably to the computational
complexity of finding a loop-free alternate. complexity of finding a loop-free alternate.
However, a sub-category of SRLGs is of interest and can be applied However, a sub-category of SRLGs is of interest and can be applied
only during the selection of an acceptable alternate. This sub- only during the selection of an acceptable alternate. This sub-
category is to express correlated failures of links that are category is to express correlated failures of links that are
connected to the same router. For example, if there are multiple connected to the same router, for example, if there are multiple
logical sub-interfaces on the same physical interface, such as VLANs logical sub-interfaces on the same physical interface, such as VLANs
on an Ethernet interface, if multiple interfaces use the same on an Ethernet interface, if multiple interfaces use the same
physical port because of channelization, or if multiple interfaces physical port because of channelization, or if multiple interfaces
share a correlated failure because they are on the same line-card. share a correlated failure because they are on the same line-card.
This sub-category of SRLGs will be referred to as local-SRLGs. A This sub-category of SRLGs will be referred to as local-SRLGs. A
local-SRLG has all of its member links with one end connected to the local-SRLG has all of its member links with one end connected to the
same router. Thus, router S could select a loop-free alternate which same router. Thus, router S could select a loop-free alternate that
does not use a link in the same local-SRLG as the primary next-hop. does not use a link in the same local-SRLG as the primary next-hop.
The local-SRLGs belonging to E can be protected against via node- The failure of local-SRLGs belonging to E can be protected against
protection; i.e. picking a loop-free node-protecting alternate. via node protection, i.e., picking a loop-free node-protecting
alternate.
Where SRLG protection is provided, it is in the context of the Where SRLG protection is provided, it is in the context of the
particular OSPF or ISIS area, whose topology is used in the SPF particular OSPF or IS-IS area, whose topology is used in the SPF
computations to compute the loop-free alternates. If an SRLG computations to compute the loop-free alternates. If an SRLG
contains links in multiple areas, then separate SRLG-protecting contains links in multiple areas, then separate SRLG-protecting
alternates would be required in each area that is traversed by the alternates would be required in each area that is traversed by the
affected traffic. affected traffic.
1.2. Requirement 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].
2. Applicability of Described Mechanisms 2. Applicability of Described Mechanisms
IP Fast Reroute mechanisms described in this memo cover intra-domain IP Fast Reroute mechanisms described in this memo cover intra-domain
routing only, with OSPF[RFC2328] or ISIS [RFC1195] [RFC2966] as the routing only, with OSPF [RFC2328] [RFC2740] [RFC5340] or IS-IS
IGP. Specifically, Fast Reroute for BGP inter-domain routing is not [RFC1195] [RFC2966] as the IGP. Specifically, Fast Reroute for BGP
part of this specification. inter-domain routing is not part of this specification.
Certain aspects of OSPF inter-area routing behavior explained in Certain aspects of OSPF inter-area routing behavior explained in
Section 6.3 and Appendix A impact the ability of the router Section 6.3 and Appendix A impact the ability of the router
calculating the backup next-hops to assess traffic trajectories. In calculating the backup next-hops to assess traffic trajectories. In
order to avoid micro-looping and ensure required coverage, certain order to avoid micro-looping and ensure required coverage, certain
constraints are applied to multi-area OSPF networks: constraints are applied to multi-area OSPF networks:
a. Loop-free alternates should not be used in the backbone area if a. Loop-free alternates should not be used in the backbone area if
there are any virtual links configured unless, for each transit there are any virtual links configured unless, for each transit
area, there is a full mesh of virtual links between all ABRs in area, there is a full mesh of virtual links between all Area
that area. Loop-free alternates may be used in non-backbone Border Routers (ABRs) in that area. Loop-free alternates may be
areas regardless of whether there are virtual links configured. used in non-backbone areas regardless of whether there are
virtual links configured.
b. Loop-free alternates should not be used for inter-area routes in b. Loop-free alternates should not be used for inter-area routes in
an area that contains more than one alternate ABR. [RFC3509] an area that contains more than one alternate ABR [RFC3509].
c. Loop-free alternates should not be used for AS External routes or c. Loop-free alternates should not be used for AS External routes or
ASBR routes in a non-backbone area of a network where there Autonomous System Border Router (ASBR) routes in a non-backbone
exists an ABR that is announced as an ASBR in multiple non- area of a network where there exists an ABR that is announced as
backbone areas and there exists another ABR that is in at least an ASBR in multiple non-backbone areas and there exists another
two of the same non-backbone areas. ABR that is in at least two of the same non-backbone areas.
d. Loop-free alternates should not be used in a non-backbone area of d. Loop-free alternates should not be used in a non-backbone area of
a network for AS External routes where an AS External prefix is a network for AS External routes where an AS External prefix is
advertised with the same type of external metric by multiple advertised with the same type of external metric by multiple
ASBRs, which are in different non-backbone areas, with a ASBRs, which are in different non-backbone areas, with a
forwarding address of 0.0.0.0 or by one or more ASBRs with forwarding address of 0.0.0.0 or by one or more ASBRs with
forwarding addresses in multiple non-backbone areas when an ABR forwarding addresses in multiple non-backbone areas when an ABR
exists simultaneously in two or more of those non-backbone areas. exists simultaneously in two or more of those non-backbone areas.
3. Alternate Next-Hop Calculation 3. Alternate Next-Hop Calculation
In addition to the set of primary next-hops obtained through a In addition to the set of primary next-hops obtained through a
shortest path tree (SPT) computation that is part of standard link- shortest path tree (SPT) computation that is part of standard link-
state routing functionality, routers supporting IP Fast Reroute also state routing functionality, routers supporting IP Fast Reroute also
calculate a set of backup next hops that are engaged when a local calculate a set of backup next-hops that are engaged when a local
failure occurs. These backup next hops are calculated to provide the failure occurs. These backup next-hops are calculated to provide the
required type of protection (i.e. link-protecting and/or node- required type of protection (i.e., link-protecting and/or node-
protecting) and to guarantee that when the expected failure occurs, protecting) and to guarantee that when the expected failure occurs,
forwarding traffic through them will not result in a loop. Such next forwarding traffic through them will not result in a loop. Such
hops are called loop-free alternates or LFAs throughout this next-hops are called loop-free alternates or LFAs throughout this
specification. specification.
In general, to be able to calculate the set of LFAs for a specific In general, to be able to calculate the set of LFAs for a specific
destination D, a router needs to know the following basic pieces of destination D, a router needs to know the following basic pieces of
information: information:
o Shortest-path distance from the calculating router to the o Shortest-path distance from the calculating router to the
destination (Distance_opt(S, D)) destination (Distance_opt(S, D))
o Shortest-path distance from the router's IGP neighbors to the o Shortest-path distance from the router's IGP neighbors to the
destination (Distance_opt(N, D)) destination (Distance_opt(N, D))
o Shortest path distance from the router's IGP neighbors to itself o Shortest path distance from the router's IGP neighbors to itself
(Distance_opt(N, S)) (Distance_opt(N, S))
o Distance_opt(S, D) is normally available from the regular SPF o Distance_opt(S, D) is normally available from the regular SPF
calculation performed by the link-state routing protocols. calculation performed by the link-state routing protocols.
Distance_opt(N, D) and Distance_opt(N, S) can be obtained by Distance_opt(N, D) and Distance_opt(N, S) can be obtained by
performing additional SPF calculations from the perspective of performing additional SPF calculations from the perspective of
each IGP neighbor (i.e. considering the neighbor's vertex as the each IGP neighbor (i.e., considering the neighbor's vertex as the
root of the SPT--called SPT(N) hereafter--rather than the root of the SPT--called SPT(N) hereafter--rather than the
calculating router's one, called SPT(S)). calculating router's one, called SPT(S)).
This specification defines a form of SRLG protection limited to those This specification defines a form of SRLG protection limited to those
SRLGs that include a link that the calculating router is directly SRLGs that include a link to which the calculating router is directly
connected to. Only that set of SRLGs could cause a local failure; connected. Only that set of SRLGs could cause a local failure; the
the calculating router only computes alternates to handle a local calculating router only computes alternates to handle a local
failure. Information about local link SRLG membership is manually failure. Information about local link SRLG membership is manually
configured. Information about remote link SRLG membership may be configured. Information about remote link SRLG membership may be
dynamically obtained using [RFC4205] or [RFC4203]. Define dynamically obtained using [RFC4205] or [RFC4203]. Define
SRLG_local(S) to be the set of SRLGs that include a link that the SRLG_local(S) to be the set of SRLGs that include a link to which the
calculating router S is directly connected to. Only SRLG_local(S) is calculating router S is directly connected Only SRLG_local(S) is of
of interest during the calculation, but the calculating router must interest during the calculation, but the calculating router must
correctly handle changes to SRLG_local(S) triggered by local link correctly handle changes to SRLG_local(S) triggered by local link
SRLG membership changes. SRLG membership changes.
In order to choose among all available LFAs that provide required In order to choose among all available LFAs that provide required
SRLG protection for a given destination, the calculating router needs SRLG protection for a given destination, the calculating router needs
to track the set of SRLGs in SRLG_local(S) that the path through a to track the set of SRLGs in SRLG_local(S) that the path through a
specific IGP neighbor involves. To do so, each node D in the network specific IGP neighbor involves. To do so, each node D in the network
topology is associated with SRLG_set(N, D), which is the set of SRLGs topology is associated with SRLG_set(N, D), which is the set of SRLGs
that would be crossed if traffic to D was forwarded through N. To that would be crossed if traffic to D was forwarded through N. To
calculate this set, the router initializes SRLG_set(N, N) for each of calculate this set, the router initializes SRLG_set(N, N) for each of
its IGP neighbors to be empty. During the SPT(N) calculation, when a its IGP neighbors to be empty. During the SPT(N) calculation, when a
new vertex V is added to the SPT, its SRLG_set(N, V) is set to the new vertex V is added to the SPT, its SRLG_set(N, V) is set to the
union of SRLG sets associated with its parents, and the SRLG sets in union of SRLG sets associated with its parents, and the SRLG sets in
SRLG_local(S) that are associated with the links from V's parents to SRLG_local(S) that are associated with the links from V's parents to
V. The union of the set of SRLG associated with a candidate alternate V. The union of the set of SRLGs associated with a candidate
next-hop and the SRLG_set(N, D) for the neighbor reached via that alternate next-hop and the SRLG_set(N, D) for the neighbor reached
candidate next-hop is used to determine SRLG protection. via that candidate next-hop is used to determine SRLG protection.
The following sections provide information required for calculation The following sections provide information required for calculation
of LFAs. Sections Section 3.1 through Section 3.4 define different of LFAs. Sections 3.1 through 3.4 define different types of LFA
types of LFA conditions. Section 3.5 describes constraints imposed conditions. Section 3.5 describes constraints imposed by the IS-IS
by the IS-IS overload and OSPF stub router functionality. overload and OSPF stub router functionality. Section 3.6 defines the
Section 3.6 defines the summarized algorithm for LFA calculation summarized algorithm for LFA calculation using the definitions in the
using the definitions in the previous sections. previous sections.
3.1. Basic Loop-free Condition 3.1. Basic Loop-Free Condition
Alternate next hops used by implementations following this Alternate next hops used by implementations following this
specification MUST conform to at least the loop-freeness condition specification MUST conform to at least the loop-freeness condition
stated above in Inequality 1. This condition guarantees that stated above in Inequality 1. This condition guarantees that
forwarding traffic to an LFA will not result in a loop after a link forwarding traffic to an LFA will not result in a loop after a link
failure. failure.
Further conditions may be applied when determining link-protecting Further conditions may be applied when determining link-protecting
and/or node-protecting alternate next-hops as described in Sections and/or node-protecting alternate next-hops as described in Sections
Section 3.2 and Section 3.3. 3.2 and 3.3.
3.2. Node-Protecting Alternate Next-Hops 3.2. Node-Protecting Alternate Next-Hops
For an alternate next-hop N to protect against node failure of a For an alternate next-hop N to protect against node failure of a
primary neighbor E for destination D, N must be loop-free with primary neighbor E for destination D, N must be loop-free with
respect to both E and D. In other words, N's path to D must not go respect to both E and D. In other words, N's path to D must not go
through E. This is the case if Inequality 3 is true, where N is the through E. This is the case if Inequality 3 is true, where N is the
neighbor providing a loop-free alternate. neighbor providing a loop-free alternate.
Distance_opt(N, D) < Distance_opt(N, E) + Distance_opt(E, D) Distance_opt(N, D) < Distance_opt(N, E) + Distance_opt(E, D)
skipping to change at page 10, line 48 skipping to change at page 11, line 4
For an alternate next-hop N to protect against node failure of a For an alternate next-hop N to protect against node failure of a
primary neighbor E for destination D, N must be loop-free with primary neighbor E for destination D, N must be loop-free with
respect to both E and D. In other words, N's path to D must not go respect to both E and D. In other words, N's path to D must not go
through E. This is the case if Inequality 3 is true, where N is the through E. This is the case if Inequality 3 is true, where N is the
neighbor providing a loop-free alternate. neighbor providing a loop-free alternate.
Distance_opt(N, D) < Distance_opt(N, E) + Distance_opt(E, D) Distance_opt(N, D) < Distance_opt(N, E) + Distance_opt(E, D)
Inequality 3: Criteria for a Node-Protecting Loop-Free Alternate Inequality 3: Criteria for a Node-Protecting Loop-Free Alternate
If Distance_opt(N,D) = Distance_opt(N, E) + Distance_opt(E, D), it is If Distance_opt(N,D) = Distance_opt(N, E) + Distance_opt(E, D), it is
possible that N has equal-cost paths and one of those could provide possible that N has equal-cost paths and one of those could provide
protection against E's node failure. However, it is equally possible protection against E's node failure. However, it is equally possible
that one of N's paths goes through E, and the calculating router has that one of N's paths goes through E, and the calculating router has
no way to influence N's decision to use it. Therefore, it SHOULD be no way to influence N's decision to use it. Therefore, it SHOULD be
assumed that an alternate next-hop does not offer node protection if assumed that an alternate next-hop does not offer node protection if
Inequality 3 is not met. Inequality 3 is not met.
3.3. Broadcast and NBMA Links 3.3. Broadcast and Non-Broadcast Multi-Access (NBMA) Links
Verification of the link-protection property of a next hop in the Verification of the link-protection property of a next-hop in the
case of a broadcast link is more elaborate than for a point-to-point case of a broadcast link is more elaborate than for a point-to-point
link. This is because a broadcast link is represented as a pseudo- link. This is because a broadcast link is represented as a pseudo-
node with zero-cost links connecting it to other nodes. node with zero-cost links connecting it to other nodes.
Because failure of an interface attached to a broadcast segment may Because failure of an interface attached to a broadcast segment may
mean loss of connectivity of the whole segment, the condition mean loss of connectivity of the whole segment, the condition
described for broadcast link protection is pessimistic and requires described for broadcast link protection is pessimistic and requires
that the alternate is loop-free with regard to the pseudo-node. that the alternate is loop-free with regard to the pseudo-node.
Consider the example in Figure 3. Consider the example in Figure 3.
skipping to change at page 11, line 38 skipping to change at page 11, line 41
/----\ 0 5 +-----+ /----\ 0 5 +-----+
| PN |-----| N | | PN |-----| N |
\----/ +-----+ \----/ +-----+
| 0 | | 0 |
| | 8 | | 8
| 5 | | 5 |
+-----+ 5 +-----+ +-----+ 5 +-----+
| E |----| D | | E |----| D |
+-----+ +-----+ +-----+ +-----+
Figure 3: Loop-Free Alternate that is Link-Protecting Figure 3: Loop-Free Alternate That Is Link-Protecting
In Figure 3, N offers a loop-free alternate which is link-protecting. In Figure 3, N offers a loop-free alternate that is link-protecting.
If the primary next-hop uses a broadcast link, then an alternate If the primary next-hop uses a broadcast link, then an alternate
SHOULD be loop-free with respect to that link's pseudo-node (PN) to SHOULD be loop-free with respect to that link's pseudo-node (PN) to
provide link protection. This requirement is described in provide link protection. This requirement is described in Inequality
Inequality 4 below. 4 below.
D_opt(N, D) < D_opt(N, PN) + D_opt(PN, D) D_opt(N, D) < D_opt(N, PN) + D_opt(PN, D)
Inequality 4: Loop-Free Link-Protecting Criterion for Broadcast Links Inequality 4: Loop-Free Link-Protecting Criterion for Broadcast Links
Because the shortest path from the pseudo-node goes through E, if a Because the shortest path from the pseudo-node goes through E, if a
loop-free alternate from a neighbor N is node-protecting, the loop-free alternate from a neighbor N is node-protecting, the
alternate will also be link-protecting unless the router S can only alternate will also be link-protecting unless the router S can only
reach the alternate neighbor N via the same pseudo-node. Since this reach the alternate neighbor N via the same pseudo-node. Since this
is the only case for which a node-protecting LFA is not link- is the only case for which a node-protecting LFA is not link-
protecting, this implies that for point-to-point interfaces, an LFA protecting, this implies that for point-to-point interfaces, an LFA
that is node-protecting is always link-protecting. Because S can that is node-protecting is always link-protecting. Because S can
direct the traffic away from the shortest path to use the alternate direct the traffic away from the shortest path to use the alternate
N, traffic might pass through the same broadcast link as it would N, traffic might pass through the same broadcast link as it would
when S sent the traffic to the primary E. Thus, an LFA from N that is when S sent the traffic to the primary E. Thus, an LFA from N that
node-protecting is not automatically link-protecting for a broadcast is node-protecting is not automatically link-protecting for a
or NBMA link. broadcast or NBMA link.
To obtain link protection, it is necessary both that the path from To obtain link protection, it is necessary both that the path from
the selected alternate next-hop does not traverse the link of the selected alternate next-hop does not traverse the link of
interest and that the link used from S to reach that alternate next- interest and that the link used from S to reach that alternate next-
hop is not the link of interest. The latter can only occur with non- hop is not the link of interest. The latter can only occur with non-
point-to-point links. Therefore, if the primary next-hop is across a point-to-point links. Therefore, if the primary next-hop is across a
broadcast or NBMA interface, it is necessary to consider link broadcast or NBMA interface, it is necessary to consider link
protection during the alternate selection. To clarify, consider the protection during the alternate selection. To clarify, consider the
topology in Figure 3. For N to provide link-protection, it is first topology in Figure 3. For N to provide link protection, it is first
necessary that N's shortest path to D does not traverse the pseudo- necessary that N's shortest path to D does not traverse the pseudo-
node PN. Second, it is necessary that the alternate next-hop node PN. Second, it is necessary that the alternate next-hop
selected by S does not traverse PN. In this example, S's shortest selected by S does not traverse PN. In this example, S's shortest
path to N is via the pseudo-node. Thus, to obtain link-protection, S path to N is via the pseudo-node. Thus, to obtain link protection, S
must find a next-hop to N (the point-to-point link from S to N in must find a next-hop to N (the point-to-point link from S to N in
this example) that avoids the pseudo-node PN. this example) that avoids the pseudo-node PN.
Similar consideration of the link from S to the selected alternate Similar consideration of the link from S to the selected alternate
next-hop as well as the path from the selected alternate next-hop is next-hop as well as the path from the selected alternate next-hop is
also necessary for SRLG protection. S's shortest path to the also necessary for SRLG protection. S's shortest path to the
selected neighbor N may not be acceptable as an alternate next-hop to selected neighbor N may not be acceptable as an alternate next-hop to
provide SRLG protection, even if the path from N to D can provide provide SRLG protection, even if the path from N to D can provide
SRLG protection. SRLG protection.
3.4. ECMP and Alternates 3.4. ECMP and Alternates
With equal-cost multi-path, a prefix may have multiple primary next- With Equal-Cost Multi-Path (ECMP), a prefix may have multiple primary
hops that are used to forward traffic. When a particular primary next-hops that are used to forward traffic. When a particular
next-hop fails, alternate next-hops should be used to preserve the primary next-hop fails, alternate next-hops should be used to
traffic. These alternate next-hops may themselves also be primary preserve the traffic. These alternate next-hops may themselves also
next-hops, but need not be. Other primary next-hops are not be primary next-hops, but need not be. Other primary next-hops are
guaranteed to provide protection against the failure scenarios of not guaranteed to provide protection against the failure scenarios of
concern. concern.
20 L1 L3 3 20 L1 L3 3
[ N ]----[ S ]--------[ E3 ] [ N ]----[ S ]--------[ E3 ]
| | | | | |
| 5 | L2 | | 5 | L2 |
20 | | | 20 | | |
| --------- | 2 | --------- | 2
| 5 | | 5 | | 5 | | 5 |
| [ E1 ] [ E2 ]-----| | [ E1 ] [ E2 ]-----|
| | | | | |
| 10 | 10 | | 10 | 10 |
|---[ A ] [ B ] |---[ A ] [ B ]
| | | |
2 |--[ D ]-| 2 2 |--[ D ]-| 2
Figure 4: ECMP where Primary Next-Hops Provide Limited Protection Figure 4: ECMP Where Primary Next-Hops Provide Limited Protection
In Figure 4 S has three primary next-hops to reach D; these are L2 to In Figure 4 S has three primary next-hops to reach D; these are L2 to
E1, L2 to E2 and L3 to E3. The primary next-hop L2 to E1 can obtain E1, L2 to E2, and L3 to E3. The primary next-hop L2 to E1 can obtain
link and node protection from L3 to E3, which is one of the other link and node protection from L3 to E3, which is one of the other
primary next-hops; L2 to E1 cannot obtain link protection from the primary next-hops; L2 to E1 cannot obtain link protection from the
other primary next-hop L2 to E2. Similarly, the primary next-hop L2 other primary next-hop L2 to E2. Similarly, the primary next-hop L2
to E2 can only get node protection from L2 to E1 and can only get to E2 can only get node protection from L2 to E1 and can only get
link protection from L3 to E3. The third primary next-hop L3 to E3 link protection from L3 to E3. The third primary next-hop L3 to E3
can obtain link and node protection from L2 to E1 and from L2 to E2. can obtain link and node protection from L2 to E1 and from L2 to E2.
It is possible for both the primary next-hop L2 to E2 and the primary It is possible for both the primary next-hop L2 to E2 and the primary
next-hop L2 to E1 to obtain an alternate next-hop that provides both next-hop L2 to E1 to obtain an alternate next-hop that provides both
link and node protection by using L1. link and node protection by using L1.
Alternate next-hops are determined for each primary next-hop Alternate next-hops are determined for each primary next-hop
separately. As with alternate selection in the non-ECMP case, these separately. As with alternate selection in the non-ECMP case, these
alternate next-hops should maximize the coverage of the failure alternate next-hops should maximize the coverage of the failure
cases. cases.
3.5. Interactions with ISIS Overload, RFC 3137 and Costed Out Links 3.5. Interactions with IS-IS Overload, RFC 3137, and Costed Out Links
As described in [RFC3137], there are cases where it is desirable not As described in [RFC3137], there are cases where it is desirable not
to have a router used as a transit node. For those cases, it is also to have a router used as a transit node. For those cases, it is also
desirable not to have the router used on an alternate path. desirable not to have the router used on an alternate path.
For computing an alternate, a router MUST NOT use an alternate next- For computing an alternate, a router MUST NOT use an alternate next-
hop that is along a link whose cost or reverse cost is LSInfinity hop that is along a link whose cost or reverse cost is LSInfinity
(for OSPF) or the maximum cost (for ISIS) or which has the overload (for OSPF) or the maximum cost (for IS-IS) or that has the overload
bit set (for ISIS). For a broadcast link, the reverse cost bit set (for IS-IS). For a broadcast link, the reverse cost
associated with a potential alternate next-hop is the cost towards associated with a potential alternate next-hop is the cost towards
the pseudo-node advertised by the next-hop router. For point-to- the pseudo-node advertised by the next-hop router. For point-to-
point links, if a specific link from the next-hop router cannot be point links, if a specific link from the next-hop router cannot be
associated with a particular link, then the reverse cost considered associated with a particular link, then the reverse cost considered
is that of the minimum cost link from the next-hop router back to S. is that of the minimum cost link from the next-hop router back to S.
In the case of OSPF, if all links from router S to a neighbor N_i In the case of OSPF, if all links from router S to a neighbor N_i
have a reverse cost of LSInfinity, then router S MUST NOT use N_i as have a reverse cost of LSInfinity, then router S MUST NOT use N_i as
an alternate. an alternate.
Similarly in the case of ISIS, if N_i has the overload bit set, then Similarly in the case of IS-IS, if N_i has the overload bit set, then
S MUST NOT consider using N_i as an alternate. S MUST NOT consider using N_i as an alternate.
This preserves the desired behavior of diverting traffic away from a This preserves the desired behavior of diverting traffic away from a
router which is following [RFC3137] and it also preserves the desired router that is following [RFC3137], and it also preserves the desired
behavior when an operator sets the cost of a link to LSInfinity for behavior when an operator sets the cost of a link to LSInfinity for
maintenance which is not permitting traffic across that link unless maintenance that is not permitting traffic across that link unless
there is no other path. there is no other path.
If a link or router which is costed out was the only possible If a link or router that is costed out was the only possible
alternate to protect traffic from a particular router S to a alternate to protect traffic from a particular router S to a
particular destination, then there should be no alternate provided particular destination, then there should be no alternate provided
for protection. for protection.
3.5.1. Interactions with ISIS Link Attributes 3.5.1. Interactions with IS-IS Link Attributes
[RFC5029] describes several flags whose interactions with LFAs needs [RFC5029] describes several flags whose interactions with LFAs need
to be defined. A router SHOULD NOT specify the "local protection to be defined. A router SHOULD NOT specify the "local protection
available" flag as a result of having LFAs. A router SHOULD NOT use available" flag as a result of having LFAs. A router SHOULD NOT use
an alternate next-hop that is along a link for which the link has an alternate next-hop that is along a link for which the link has
been advertised with the attribute "link excluded from local been advertised with the attribute "link excluded from local
protection path" or with the attribute "local maintenance required". protection path" or with the attribute "local maintenance required".
3.6. Selection Procedure 3.6. Selection Procedure
A router supporting this specification SHOULD attempt to select at A router supporting this specification SHOULD attempt to select at
least one loop-free alternate next-hop for each primary next-hop used least one loop-free alternate next-hop for each primary next-hop used
skipping to change at page 15, line 5 skipping to change at page 15, line 5
cases. cases.
When calculating alternate next-hops, the calculating router S When calculating alternate next-hops, the calculating router S
applies the following rules. applies the following rules.
1. S SHOULD select a loop-free node-protecting alternate next-hop, 1. S SHOULD select a loop-free node-protecting alternate next-hop,
if one is available. If no loop-free node-protecting alternate if one is available. If no loop-free node-protecting alternate
is available, then S MAY select a loop-free link-protecting is available, then S MAY select a loop-free link-protecting
alternate. alternate.
2. If S has a choice between a loop-free link-protecting node- 2. If S has a choice between a loop-free link-and-node-protecting
protecting alternate and a loop-free node-protecting alternate alternate and a loop-free node-protecting alternate that is not
which is not link-protecting, S SHOULD select a loop-free node- link-protecting, S SHOULD select a loop-free link-and-node-
protecting alternate which is also link-protecting. This can protecting alternate. This can occur as explained in
occur as explained in Section 3.3. Section 3.3.
3. If S has multiple primary next-hops, then S SHOULD select as a 3. If S has multiple primary next-hops, then S SHOULD select as a
loop-free alternate either one of the other primary next-hops or loop-free alternate either one of the other primary next-hops or
a loop-free node-protecting alternate if available. If no loop- a loop-free node-protecting alternate if available. If no loop-
free node-protecting alternate is available and no other primary free node-protecting alternate is available and no other primary
next-hop can provide link-protection, then S SHOULD select a next-hop can provide link-protection, then S SHOULD select a
loop-free link-protecting alternate. loop-free link-protecting alternate.
4. Implementations SHOULD support a mode where other primary next- 4. Implementations SHOULD support a mode where other primary next-
hops satisfying the basic loop-free condition and providing at hops satisfying the basic loop-free condition and providing at
least link or node protection are preferred over any non-primary least link or node protection are preferred over any non-primary
alternates. This mode is provided to allow the administrator to alternates. This mode is provided to allow the administrator to
preserve traffic patterns based on regular ECMP behavior. preserve traffic patterns based on regular ECMP behavior.
5. Implementations considering SRLGs MAY use SRLG-protection to 5. Implementations considering SRLGs MAY use SRLG protection to
determine that a node-protecting or link-protecting alternate is determine that a node-protecting or link-protecting alternate is
not available for use. not available for use.
Following the above rules maximizes the level of protection and use Following the above rules maximizes the level of protection and use
of primary (ECMP) next-hops. of primary (ECMP) next-hops.
Each next-hop is associated with a set of non-mutually-exclusive Each next-hop is associated with a set of non-mutually-exclusive
characteristics based on whether it is used as a primary next-hop to characteristics based on whether it is used as a primary next-hop to
a particular destination D, and the type of protection it can provide a particular destination D, and the type of protection it can provide
relative to a specific primary next-hop E: relative to a specific primary next-hop E:
skipping to change at page 15, line 46 skipping to change at page 15, line 46
Primary Path - The next-hop is used by S as primary. Primary Path - The next-hop is used by S as primary.
Loop-Free Node-Protecting Alternate - This next-hop satisfies Loop-Free Node-Protecting Alternate - This next-hop satisfies
Inequality 1 and Inequality 3. The path avoids S, S's primary Inequality 1 and Inequality 3. The path avoids S, S's primary
neighbor E, and the link from S to E. neighbor E, and the link from S to E.
Loop-Free Link-Protecting Alternate - This next-hop satisfies Loop-Free Link-Protecting Alternate - This next-hop satisfies
Inequality 1 but not Inequality 3. If the primary next-hop uses a Inequality 1 but not Inequality 3. If the primary next-hop uses a
broadcast link, then this next-hop satisfies Inequality 4. broadcast link, then this next-hop satisfies Inequality 4.
An alternate path may also provide none, some or complete SRLG An alternate path may also provide none, some, or complete SRLG
protection as well as node and link or link protection. For protection as well as node and link or link protection. For
instance, a link may belong to two SRLGs G1 and G2. The alternate instance, a link may belong to two SRLGs G1 and G2. The alternate
path might avoid other links in G1 but not G2, in which case the path might avoid other links in G1 but not G2, in which case the
alternate would only provide partial SRLG protection. alternate would only provide partial SRLG protection.
Below is an algorithm that can be used to calculate loop-free Below is an algorithm that can be used to calculate loop-free
alternate next-hops. The algorithm is given for informational alternate next-hops. The algorithm is given for informational
purposes and implementations are free to use any other algorithm as purposes, and implementations are free to use any other algorithm as
long as it satisfies the rules described above. long as it satisfies the rules described above.
The following procedure describes how to select an alternate next- The following procedure describes how to select an alternate next-
hop. The procedure is described to determine alternate next-hops to hop. The procedure is described to determine alternate next-hops to
use to reach each router in the topology. Prefixes that are use to reach each router in the topology. Prefixes that are
advertised by a single router can use the alternate next-hop computed advertised by a single router can use the alternate next-hop computed
for the router to which they are attached. The same procedure can be for the router to which they are attached. The same procedure can be
used to reach a prefix that is advertised by more than one router used to reach a prefix that is advertised by more than one router
when the logical topological transformation described in Section 6.1 when the logical topological transformation described in Section 6.1
is used. is used.
S is the computing router. S has neighbors N_1 to N_j. A candidate S is the computing router. S has neighbors N_1 to N_j. A candidate
next-hop is indicated by (outgoing link, neighbor) and the outgoing next-hop is indicated by (outgoing link, neighbor) and the outgoing
link must be bidirectionally connected, as is determined by the IGP. link must be bidirectionally connected, as is determined by the IGP.
The candidate next-hops of S are enumerated as H_1 through H_k. The candidate next-hops of S are enumerated as H_1 through H_k.
Recall that S may have multiple next hops over different interfaces Recall that S may have multiple next-hops over different interfaces
to a neighbor. H_i.link refers to the outgoing link of that next-hop to a neighbor. H_i.link refers to the outgoing link of that next-hop
and H_i.neighbor refers to the neighbor of that nexthop. and H_i.neighbor refers to the neighbor of that next-hop.
For a particular destination router D, let S have already computed For a particular destination router D, let S have already computed
D_opt(S, D), and for each neighbor N_i, D_opt(N_i, D), D_opt(N_i, S), D_opt(S, D), and for each neighbor N_i, D_opt(N_i, D), D_opt(N_i, S),
and D_opt(N_i, N_j), the distance from N_i to each other neighbor and D_opt(N_i, N_j), the distance from N_i to each other neighbor
N_j, and the set of SRLGs traversed by the path D_opt(N_i, D). S N_j, and the set of SRLGs traversed by the path D_opt(N_i, D). S
should follow the below procedure for every primary next-hop selected should follow the below procedure for every primary next-hop selected
to reach D. This set of primary next-hops is represented P_1 to P_p. to reach D. This set of primary next-hops is represented P_1 to P_p.
This procedure finds the alternate next-hop(s) for P_i. This procedure finds the alternate next-hop(s) for P_i.
First, initialize the alternate information for P_i as follows: First, initialize the alternate information for P_i as follows:
skipping to change at page 17, line 12 skipping to change at page 17, line 12
cand_node-protect = FALSE cand_node-protect = FALSE
cand_srlg-protect = {} cand_srlg-protect = {}
2. If H_h is P_i, skip it and continue to the next candidate next- 2. If H_h is P_i, skip it and continue to the next candidate next-
hop. hop.
3. If H_h.link is administratively allowed to be used as an 3. If H_h.link is administratively allowed to be used as an
alternate, alternate,
and the cost of H_h.link is less than the maximum, and the cost of H_h.link is less than the maximum,
and the reverse cost of H_h is less than the maximum, and the reverse cost of H_h is less than the maximum,
and H_h.neighbor is not overloaded (for ISIS), and H_h.neighbor is not overloaded (for IS-IS),
and H_h.link is bi-directional, and H_h.link is bidirectional,
then H_h can be considered as an alternate. Otherwise, skip it then H_h can be considered as an alternate. Otherwise, skip it
and continue to the next candidate next-hop. and continue to the next candidate next-hop.
4. If D_opt( H_h.neighbor, D) >= D_opt( H_h.neighbor, S) + D_opt(S, 4. If D_opt( H_h.neighbor, D) >= D_opt( H_h.neighbor, S) + D_opt(S,
D), then H_h is not loop-free. Skip it and continue to the next D), then H_h is not loop-free. Skip it and continue to the next
candidate next-hop. candidate next-hop.
5. cand_type = LOOP-FREE. 5. cand_type = LOOP-FREE.
skipping to change at page 17, line 43 skipping to change at page 17, line 43
P_i.neighbor. Remove the set of SRLGs to which H_h belongs from P_i.neighbor. Remove the set of SRLGs to which H_h belongs from
cand_srlg-protect. Remove from cand_srlg-protect the set of cand_srlg-protect. Remove from cand_srlg-protect the set of
SRLGs traversed on the path from H_h.neighbor to D. Now SRLGs traversed on the path from H_h.neighbor to D. Now
cand_srlg-protect holds the set of SRLGs to which P_i belongs cand_srlg-protect holds the set of SRLGs to which P_i belongs
and that are not traversed on the path from S via H_h to D. and that are not traversed on the path from S via H_h to D.
10. If cand_type is PRIMARY, the router prefers other primary next- 10. If cand_type is PRIMARY, the router prefers other primary next-
hops for use as the alternate, and the P_i.alt_type is not hops for use as the alternate, and the P_i.alt_type is not
PRIMARY, goto Step 20. PRIMARY, goto Step 20.
11. If cand_type is not PRIMARY, P_i.alt_type is PRIMARY and the 11. If cand_type is not PRIMARY, P_i.alt_type is PRIMARY, and the
router prefers other primary next-hops for use as the alternate, router prefers other primary next-hops for use as the alternate,
then continue to the next candidate next-hop then continue to the next candidate next-hop
12. If cand_node-protect is TRUE and P_i.alt_node-protect is FALSE, 12. If cand_node-protect is TRUE and P_i.alt_node-protect is FALSE,
goto Paragraph 20. goto Paragraph 20.
13. If cand_link-protect is TRUE and P_i.alt_link-protect is FALSE, 13. If cand_link-protect is TRUE and P_i.alt_link-protect is FALSE,
goto Step 20. goto Step 20.
14. If cand_srlg-protect has a better set of SRLGs than 14. If cand_srlg-protect has a better set of SRLGs than
skipping to change at page 18, line 40 skipping to change at page 18, line 40
20. Replace the P_i alternate next-hop set with H_h as follows: 20. Replace the P_i alternate next-hop set with H_h as follows:
P_i.alt_next_hops = {H_h} P_i.alt_next_hops = {H_h}
P_i.alt_type = cand_type P_i.alt_type = cand_type
P_i.alt_link-protect = cand_link-protect P_i.alt_link-protect = cand_link-protect
P_i.alt_node-protect = cand_node-protect P_i.alt_node-protect = cand_node-protect
P_i.alt_srlg-protect = cand_srlg-protect P_i.alt_srlg-protect = cand_srlg-protect
Continue to the next candidate next-hop. Continue to the next candidate next-hop.
3.7. LFA types and Trade-offs 3.7. LFA Types and Trade-Offs
LFAs can provide different amounts of protection and the decision LFAs can provide different amounts of protection, and the decision
about which type to prefer is dependent upon network topology and about which type to prefer is dependent upon network topology and
other techniques in use in the network. This section describes the other techniques in use in the network. This section describes the
different protection levels and the trade-offs associated with each. different protection levels and the trade-offs associated with each.
1. Primary Next-hop: When there are equal-cost primary next-hops, 1. Primary Next-hop: When there are equal-cost primary next-hops,
using one as an alternate is guaranteed to not cause micro-loops using one as an alternate is guaranteed not to cause micro-loops
involving S. Traffic flows across the paths that the network will involving S. Traffic flows across the paths that the network
converge to, but congestion may be experienced on the primary will converge to, but congestion may be experienced on the
paths since traffic is sent across fewer. All primary next-hops primary paths since traffic is sent across fewer. All primary
are downstream paths. next-hops are downstream paths.
2. Downstream Paths: A downstream path, unlike an LFA, is guaranteed 2. Downstream Paths: A downstream path, unlike an LFA, is guaranteed
not to cause a micro-loop involving S regardless of the actual not to cause a micro-loop involving S regardless of the actual
failure detected. However, the expected coverage of such failure detected. However, the expected coverage of such
alternates in a network is expected to be poor. All downstream alternates in a network is expected to be poor. All downstream
paths are LFAs. paths are LFAs.
3. LFA: An LFA can have good coverage of a network, depending on 3. LFA: An LFA can have good coverage of a network, depending on
topology. However, it is possible to get micro-loops involving S topology. However, it is possible to get micro-loops involving S
if a more severe failure occurs than is protected against. if an unprotected failure occurs (e.g., a node fails when the LFA
only was link-protecting).
The different types of protection are abbreviated as LP (link- The different types of protection are abbreviated as LP (link-
protecting), NP (node-protecting) and SP (SRLG-protecting). protecting), NP (node-protecting), and SP (SRLG-protecting).
a. LP, NP, and SP: If such an alternate exists, it gives protection a. LP, NP, and SP: If such an alternate exists, it gives protection
against all failures. against all failures.
b. LP and NP only: Many networks may handle SRLG failures via b. LP and NP only: Many networks may handle SRLG failures via
another method or may focus on node and link failures as being another method or may focus on node and link failures as being
more common. more common.
c. LP only: A network may handle node failures via a high c. LP only: A network may handle node failures via a high-
availability technique and be concerned primarily about availability technique and be concerned primarily about
protecting the more common link failure case. protecting the more common link failure case.
d. NP only: These only exist on interfaces that aren't point-to- d. NP only: These only exist on interfaces that aren't point-to-
point. If link protection is handled in a different layer, then point. If link protection is handled in a different layer, then
an NP alternate may be acceptable. an NP alternate may be acceptable.
3.8. A Simplification: Per-Next-Hop LFAs 3.8. A Simplification: Per-Next-Hop LFAs
It is possible to simplify the computation and use of LFAs when It is possible to simplify the computation and use of LFAs when
skipping to change at page 19, line 51 skipping to change at page 20, line 5
Even a prefix with multiple primary next-hops will have each primary Even a prefix with multiple primary next-hops will have each primary
next-hop protected individually by the primary next-hop's associated next-hop protected individually by the primary next-hop's associated
LFA. That associated LFA might or might not be another of the LFA. That associated LFA might or might not be another of the
primary next-hops of the prefix. primary next-hops of the prefix.
This simplification may reduce coverage in a network. In addition to This simplification may reduce coverage in a network. In addition to
limiting protection for multi-homed prefixes (see Section 6.1), the limiting protection for multi-homed prefixes (see Section 6.1), the
computation per next-hop may also not find an LFA when one could be computation per next-hop may also not find an LFA when one could be
found for some of the prefixes that use that next-hop. found for some of the prefixes that use that next-hop.
For example, consider Figure 4 where S has 3 ECMP next-hops, E1, E2, For example, consider Figure 4 where S has three ECMP next-hops, E1,
and E3 to reach D. For the prefix D, E3 can give link protection for E2, and E3 to reach D. For the prefix D, E3 can give link protection
the next-hops E1 and E2; E1 and E2 can give link protection for the for the next-hops E1 and E2; E1 and E2 can give link protection for
next-hops E3. However, if one uses this simplification to compute the next-hops E3. However, if one uses this simplification to
LFAs for E1, E2 and E3 individually, there is no link-protecting LFA compute LFAs for E1, E2, and E3 individually, there is no link-
for E1. E3 and E2 can protect each other. protecting LFA for E1. E3 and E2 can protect each other.
4. Using an Alternate 4. Using an Alternate
If an alternate next-hop is available, the router redirects traffic If an alternate next-hop is available, the router redirects traffic
to the alternate next-hop in case of a primary next-hop failure as to the alternate next-hop in case of a primary next-hop failure as
follows. follows.
When a next-hop failure is detected via a local interface failure or When a next-hop failure is detected via a local interface failure or
other failure detection mechanisms (see other failure detection mechanisms (see [FRAMEWORK]), the router
[I-D.ietf-rtgwg-ipfrr-framework]), the router SHOULD: SHOULD:
1. Remove the primary next-hop associated with the failure. 1. Remove the primary next-hop associated with the failure.
2. Install the loop-free alternate calculated for the failed next- 2. Install the loop-free alternate calculated for the failed next-
hop if it is not already installed (e.g. the alternate is also a hop if it is not already installed (e.g., the alternate is also a
primary next-hop). primary next-hop).
Note that the router MAY remove other next-hops if it believes (via Note that the router MAY remove other next-hops if it believes (via
SRLG analysis) that they may have been affected by the same failure, SRLG analysis) that they may have been affected by the same failure,
even if it is not visible at the time of failure detection. even if it is not visible at the time of failure detection.
The alternate next-hop MUST be used only for traffic types which are The alternate next-hop MUST be used only for traffic types that are
routed according to the shortest path. Multicast traffic is routed according to the shortest path. Multicast traffic is
specifically out of scope for this specification. specifically out of scope for this specification.
4.1. Terminating Use of Alternate 4.1. Terminating Use of Alternate
A router MUST limit the amount of time an alternate next-hop is used A router MUST limit the amount of time an alternate next-hop is used
after the primary next-hop has become unavailable. This ensures that after the primary next-hop has become unavailable. This ensures that
the router will start using the new primary next-hops. It ensures the router will start using the new primary next-hops. It ensures
that all possible transient conditions are removed and the network that all possible transient conditions are removed and the network
converges according to the deployed routing protocol. converges according to the deployed routing protocol.
There are techniques available to handle the micro-forwarding loops There are techniques available to handle the micro-forwarding loops
that can occur in a networking during convergence. that can occur in a networking during convergence.
A router that implements [I-D.ietf-rtgwg-microloop-analysis] SHOULD A router that implements [MICROLOOP] SHOULD follow the rules given
follow the rules given there for terminating the use of an alternate. there for terminating the use of an alternate.
A router that implements [I-D.francois-ordered-fib] SHOULD follow the A router that implements [ORDERED-FIB] SHOULD follow the rules given
rules given there for terminating the use of an alternate. there for terminating the use of an alternate.
It is desirable to avoid micro-forwarding loops involving S. An It is desirable to avoid micro-forwarding loops involving S. An
example illustrating the problem is given in Figure 5. If the link example illustrating the problem is given in Figure 5. If the link
from S to E fails, S will use N1 as an alternate and S will compute from S to E fails, S will use N1 as an alternate and S will compute
N2 as the new primary next-hop to reach D. If S starts using N2 as N2 as the new primary next-hop to reach D. If S starts using N2 as
soon as S can compute and install its new primary, it is probable soon as S can compute and install its new primary, it is probable
that N2 will not have yet installed its new primary next-hop. This that N2 will not have yet installed its new primary next-hop. This
would cause traffic to loop and be dropped until N2 has installed the would cause traffic to loop and be dropped until N2 has installed the
new topology. This can be avoided by S delaying its installation and new topology. This can be avoided by S delaying its installation and
leaving traffic on the alternate next-hop. leaving traffic on the alternate next-hop.
skipping to change at page 21, line 33 skipping to change at page 21, line 35
| +-----+ | | | +-----+ | |
| | E | | \|/ | | E | | \|/
| +-----+ | | +-----+ |
| | | | | |
| 1 | | | | 1 | | |
| | \|/ | | | \|/ |
| +-----+ | | +-----+ |
|----| D |-------------- |----| D |--------------
+-----+ +-----+
Figure 5: Example where Continued Use of Alternate is Desirable Figure 5: Example Where Continued Use of Alternate Is Desirable
This is an example of a case where the new primary is not a loop-free This is an example of a case where the new primary is not a loop-free
alternate before the failure and therefore may have been forwarding alternate before the failure and therefore may have been forwarding
traffic through S. This will occur when the path via a previously traffic through S. This will occur when the path via a previously
upstream node is shorter than the the path via a loop-free alternate upstream node is shorter than the path via a loop-free alternate
neighbor. In these cases, it is useful to give sufficient time to neighbor. In these cases, it is useful to give sufficient time to
ensure that the new primary neighbor and other nodes on the new ensure that the new primary neighbor and other nodes on the new
primary path have switched to the new route. primary path have switched to the new route.
If the newly selected primary was loop-free before the failure, then If the newly selected primary was loop-free before the failure, then
it is safe to switch to that new primary immediately; the new primary it is safe to switch to that new primary immediately; the new primary
wasn't dependent on the failure and therefore its path will not have wasn't dependent on the failure and therefore its path will not have
changed. changed.
Given that there is an alternate providing appropriate protection and Given that there is an alternate providing appropriate protection and
skipping to change at page 22, line 30 skipping to change at page 22, line 31
5. Requirements on LDP Mode 5. Requirements on LDP Mode
Since LDP [RFC5036] traffic will follow the path specified by the Since LDP [RFC5036] traffic will follow the path specified by the
IGP, it is also possible for the LDP traffic to follow the loop-free IGP, it is also possible for the LDP traffic to follow the loop-free
alternates indicated by the IGP. To do so, it is necessary for LDP alternates indicated by the IGP. To do so, it is necessary for LDP
to have the appropriate labels available for the alternate so that to have the appropriate labels available for the alternate so that
the appropriate out-segments can be installed in the forwarding plane the appropriate out-segments can be installed in the forwarding plane
before the failure occurs. before the failure occurs.
This means that a Label Switched Router (LSR) running LDP must This means that a Label Switching Router (LSR) running LDP must
distribute its labels for the FECs it can provide to all its distribute its labels for the Forwarding Equivalence Classes (FECs)
neighbors, regardless of whether or not they are upstream. it can provide to all its neighbors, regardless of whether or not
Additionally, LDP must be acting in liberal label retention mode so they are upstream. Additionally, LDP must be acting in liberal label
that the labels which correspond to neighbors that aren't currently retention mode so that the labels that correspond to neighbors that
the primary neighbor are stored. Similarly, LDP should be in aren't currently the primary neighbor are stored. Similarly, LDP
downstream unsolicited mode, so that the labels for the FEC are should be in downstream unsolicited mode, so that the labels for the
distributed other than along the SPT. FEC are distributed other than along the SPT.
If these requirements are met, then LDP can use the loop-free If these requirements are met, then LDP can use the loop-free
alternates without requiring any targeted sessions or signaling alternates without requiring any targeted sessions or signaling
extensions for this purpose. extensions for this purpose.
6. Routing Aspects 6. Routing Aspects
6.1. Multi-Homed Prefixes 6.1. Multi-Homed Prefixes
An SPF-like computation is run for each topology, which corresponds An SPF-like computation is run for each topology, which corresponds
to a particular OSPF area or ISIS level. The IGP needs to determine to a particular OSPF area or IS-IS level. The IGP needs to determine
loop-free alternates to multi-homed routes. Multi-homed routes occur loop-free alternates to multi-homed routes. Multi-homed routes occur
for routes obtained from outside the routing domain by multiple for routes obtained from outside the routing domain by multiple
routers, for subnets on links where the subnet is announced from routers, for subnets on links where the subnet is announced from
multiple ends of the link, and for routes advertised by multiple multiple ends of the link, and for routes advertised by multiple
routers to provide resiliency. routers to provide resiliency.
Figure 6 demonstrates such a topology. In this example, the shortest Figure 6 demonstrates such a topology. In this example, the shortest
path to reach the prefix p is via E. The prefix p will have the link path to reach the prefix p is via E. The prefix p will have the link
to E as its primary next-hop. If the alternate next-hop for the to E as its primary next-hop. If the alternate next-hop for the
prefix p is simply inherited from the router advertising it on the prefix p is simply inherited from the router advertising it on the
skipping to change at page 23, line 27 skipping to change at page 23, line 26
5 +---+ 8 +---+ 5 +---+ 5 +---+ 8 +---+ 5 +---+
------| S |------| A |-----| B | ------| S |------| A |-----| B |
| +---+ +---+ +---+ | +---+ +---+ +---+
| | | | | |
| 5 | 5 | | 5 | 5 |
| | | | | |
+---+ 5 +---+ 5 7 +---+ +---+ 5 +---+ 5 7 +---+
| C |---| E |------ p -------| F | | C |---| E |------ p -------| F |
+---+ +---+ +---+ +---+ +---+ +---+
Figure 6: Multi-homed prefix Figure 6: Multi-Homed Prefix
To determine the best protection possible, the prefix p can be To determine the best protection possible, the prefix p can be
treated in the SPF computations as a node with uni-directional links treated in the SPF computations as a node with unidirectional links
to it from those routers that have advertised the prefix. Such a to it from those routers that have advertised the prefix. Such a
node need never have its links explored, as it has no out-going node need never have its links explored, as it has no out-going
links. links.
If there exist multiple multi-homed prefixes that share the same If there exist multiple multi-homed prefixes that share the same
connectivity and the difference in metrics to those routers, then a connectivity and the difference in metrics to those routers, then a
single node can be used to represent the set. For instance, if in single node can be used to represent the set. For instance, if in
Figure 6 there were another prefix X that was connected to E with a Figure 6 there were another prefix X that was connected to E with a
metric of 1 and to F with a metric of 3, then that prefix X could use metric of 1 and to F with a metric of 3, then that prefix X could use
the same alternate next-hop as was computed for prefix p. the same alternate next-hop as was computed for prefix p.
A router SHOULD compute the alternate next-hop for an IGP multi-homed A router SHOULD compute the alternate next-hop for an IGP multi-homed
prefix by considering alternate paths via all routers that have prefix by considering alternate paths via all routers that have
announced that prefix. announced that prefix.
6.2. ISIS In all cases, a router MAY safely simplify the multi-homed prefix
(MHP) calculation by assuming that the MHP is solely attached to the
router that was its pre-failure optimal point of attachment.
However, this may result in a prefix not being considered repairable,
when the full computation would show that a repair was possible.
The applicability and interactions of LFAs with multi-topology ISIS 6.2. IS-IS
The applicability and interactions of LFAs with multi-topology IS-IS
[RFC5120] is out of scope for this specification. [RFC5120] is out of scope for this specification.
6.3. OSPF 6.3. OSPF
OSPF introduces certain complications because it is possible for the OSPF introduces certain complications because it is possible for the
traffic path to exit an area and then re-enter that area. This can traffic path to exit an area and then re-enter that area. This can
occur whenever a router considers the same route from multiple areas. occur whenever a router considers the same route from multiple areas.
There are several cases where issues such as this can occur. They There are several cases where issues such as this can occur. They
happen when another area permits a shorter path to connect two ABRs happen when another area permits a shorter path to connect two ABRs
than is available in the area where the LFA has been computed. To than is available in the area where the LFA has been computed. To
skipping to change at page 24, line 43 skipping to change at page 24, line 48
ASBRs in different areas and/or with multiple forwarding ASBRs in different areas and/or with multiple forwarding
addresses that are in different areas, which are connected via at addresses that are in different areas, which are connected via at
least one common ABR. This presents such ABRs with a decision as least one common ABR. This presents such ABRs with a decision as
to which area to use to reach the prefix. to which area to use to reach the prefix.
Loop-free alternates should not be used in an area where one of the Loop-free alternates should not be used in an area where one of the
above issues affects that area. above issues affects that area.
6.3.1. OSPF External Routing 6.3.1. OSPF External Routing
When a forwarding address is set in an OSPF AS-external LSA, all When a forwarding address is set in an OSPF AS-external Link State
routers in the network calculate their next-hops for the external Advertisement (LSA), all routers in the network calculate their next-
prefix by doing a lookup for the forwarding address in the routing hops for the external prefix by doing a lookup for the forwarding
table, rather than using the next-hops calculated for the ASBR. In address in the routing table, rather than using the next-hops
this case, the alternate next-hops SHOULD be computed by selecting calculated for the ASBR. In this case, the alternate next-hops
among the alternate paths to the forwarding link(s) instead of among SHOULD be computed by selecting among the alternate paths to the
alternate paths to the ASBR. forwarding link(s) instead of among alternate paths to the ASBR.
6.3.2. OSPF Multi-Topology 6.3.2. OSPF Multi-Topology
The applicabilty and interactions of LFAs with multi-topology OSPF The applicability and interactions of LFAs with multi-topology OSPF
[RFC4915] [I-D.ietf-ospf-mt-ospfv3] is out of scope for this [RFC4915] [MT-OSPFv3] is out of scope for this specification.
specification.
6.4. BGP Next-Hop Synchronization 6.4. BGP Next-Hop Synchronization
Typically BGP prefixes are advertised with AS exit routers router-id Typically, BGP prefixes are advertised with the AS exit router's
as the BGP next-hop, and AS exit routers are reached by means of IGP router-id as the BGP next-hop, and AS exit routers are reached by
routes. BGP resolves its advertised next-hop to the immediate next- means of IGP routes. BGP resolves its advertised next-hop to the
hop by potential recursive lookups in the routing database. IP Fast- immediate next-hop by potential recursive lookups in the routing
Reroute computes the alternate next-hops to all IGP destinations, database. IP Fast Reroute computes the alternate next-hops to all
which include alternate next-hops to the AS exit router's router-id. IGP destinations, which include alternate next-hops to the AS exit
BGP simply inherits the alternate next-hop from IGP. The BGP router's router-id. BGP simply inherits the alternate next-hop from
decision process is unaltered; BGP continues to use the IGP optimal IGP. The BGP decision process is unaltered; BGP continues to use the
distance to find the nearest exit router. MBGP routes do not need to IGP optimal distance to find the nearest exit router. Multicast BGP
copy the alternate next hops. (MBGP) routes do not need to copy the alternate next-hops.
It is possible to provide ASBR protection if BGP selected a set of It is possible to provide ASBR protection if BGP selected a set of
BGP next-hops and allowed the IGP to determine the primary and BGP next-hops and allowed the IGP to determine the primary and
alternate next-hops as if the BGP route were a multi-homed prefix. alternate next-hops as if the BGP route were a multi-homed prefix.
This is for future study. This is for future study.
6.5. Multicast Considerations 6.5. Multicast Considerations
Multicast traffic is out of scope for this specification of IP Fast- Multicast traffic is out of scope for this specification of IP Fast
Reroute. The alternate next-hops SHOULD NOT be used for multicast Reroute. The alternate next-hops SHOULD NOT be used for multicast
RPF checks. Reverse Path Forwarding (RPF) checks.
7. Security Considerations 7. Security Considerations
The mechanism described in this document does not modify any routing The mechanism described in this document does not modify any routing
protocol messages, and hence no new threats related to packet protocol messages, and hence no new threats related to packet
modifications or replay attacks are introduced. Traffic to certain modifications or replay attacks are introduced. Traffic to certain
destinations can be temporarily routed via next-hop routers that destinations can be temporarily routed via next-hop routers that
would not be used with the same topology change if this mechanism would not be used with the same topology change if this mechanism
wasn't employed. However, these next-hop routers can be used anyway wasn't employed. However, these next-hop routers can be used anyway
when a different topological change occurs, and hence this can't be when a different topological change occurs, and hence this can't be
viewed as a new security threat. viewed as a new security threat.
In LDP, the wider distribution of FEC label information is still to In LDP, the wider distribution of FEC label information is still to
neighbors with whom a trusted LDP session has been established. This neighbors with whom a trusted LDP session has been established. This
wider distribution and the recommendation of using liberal label wider distribution and the recommendation of using liberal label
retention mode are believed to have no significant security impact. retention mode are believed to have no significant security impact.
8. IANA Considerations 8. Acknowledgements
This document requires no IANA considerations.
9. Acknowledgements
The authors would like to thank Joel Halpern, Mike Shand, Stewart The authors would like to thank Joel Halpern, Mike Shand, Stewart
Bryant, and Stefano Previdi for their assistance and useful review. Bryant, and Stefano Previdi for their assistance and useful review.
10. References 9. References
10.1. Normative References 9.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.
[RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998. [RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328,
April 1998.
[RFC2740] Coltun, R., Ferguson, D., and J. Moy, "OSPF for IPv6", [RFC2740] Coltun, R., Ferguson, D., and J. Moy, "OSPF for IPv6",
RFC 2740, December 1999. RFC 2740, December 1999.
[RFC5036] Andersson, L., Minei, I., and B. Thomas, "LDP [RFC5036] Andersson, L., Minei, I., and B. Thomas, "LDP
Specification", RFC 5036, October 2007. Specification", RFC 5036, October 2007.
10.2. Informative References 9.2. Informative References
[I-D.francois-ordered-fib]
Francois, P., "Loop-free convergence using oFIB",
draft-francois-ordered-fib-02 (work in progress),
October 2006.
[I-D.ietf-ospf-mt-ospfv3] [FRAMEWORK] Shand, M. and S. Bryant, "IP Fast Reroute Framework",
Mirtorabi, S. and A. Roy, "Multi-topology routing in Work in Progress, February 2008.
OSPFv3 (MT-OSPFv3)", draft-ietf-ospf-mt-ospfv3-03 (work in
progress), July 2007.
[I-D.ietf-ospf-ospfv3-update] [MICROLOOP] Zinin, A., "Analysis and Minimization of Microloops in
Ferguson, D., "OSPF for IPv6", Link-state Routing Protocols", Work in Progress,
draft-ietf-ospf-ospfv3-update-18 (work in progress), October 2005.
November 2007.
[I-D.ietf-rtgwg-ipfrr-framework] [MT-OSPFv3] Mirtorabi, S. and A. Roy, "Multi-topology routing in
Shand, M. and S. Bryant, "IP Fast Reroute Framework", OSPFv3 (MT-OSPFv3)", Work in Progress, July 2007.
draft-ietf-rtgwg-ipfrr-framework-08 (work in progress),
February 2008.
[I-D.ietf-rtgwg-microloop-analysis] [ORDERED-FIB] Francois, P., "Loop-free convergence using oFIB", Work
Zinin, A., "Analysis and Minimization of Microloops in in Progress, February 2008.
Link-state Routing Protocols",
draft-ietf-rtgwg-microloop-analysis-01 (work in progress),
October 2005.
[RFC1195] Callon, R., "Use of OSI IS-IS for routing in TCP/IP and [RFC1195] Callon, R., "Use of OSI IS-IS for routing in TCP/IP
dual environments", RFC 1195, December 1990. and dual environments", RFC 1195, December 1990.
[RFC2966] Li, T., Przygienda, T., and H. Smit, "Domain-wide Prefix [RFC2966] Li, T., Przygienda, T., and H. Smit, "Domain-wide
Distribution with Two-Level IS-IS", RFC 2966, Prefix Distribution with Two-Level IS-IS", RFC 2966,
October 2000. October 2000.
[RFC3137] Retana, A., Nguyen, L., White, R., Zinin, A., and D. [RFC3137] Retana, A., Nguyen, L., White, R., Zinin, A., and D.
McPherson, "OSPF Stub Router Advertisement", RFC 3137, McPherson, "OSPF Stub Router Advertisement", RFC 3137,
June 2001. June 2001.
[RFC3509] Zinin, A., Lindem, A., and D. Yeung, "Alternative [RFC3509] Zinin, A., Lindem, A., and D. Yeung, "Alternative
Implementations of OSPF Area Border Routers", RFC 3509, Implementations of OSPF Area Border Routers",
April 2003. RFC 3509, April 2003.
[RFC4203] Kompella, K. and Y. Rekhter, "OSPF Extensions in Support [RFC4203] Kompella, K. and Y. Rekhter, "OSPF Extensions in
of Generalized Multi-Protocol Label Switching (GMPLS)", Support of Generalized Multi-Protocol Label Switching
RFC 4203, October 2005. (GMPLS)", RFC 4203, October 2005.
[RFC4205] Kompella, K. and Y. Rekhter, "Intermediate System to [RFC4205] Kompella, K. and Y. Rekhter, "Intermediate System to
Intermediate System (IS-IS) Extensions in Support of Intermediate System (IS-IS) Extensions in Support of
Generalized Multi-Protocol Label Switching (GMPLS)", Generalized Multi-Protocol Label Switching (GMPLS)",
RFC 4205, October 2005. RFC 4205, October 2005.
[RFC4915] Psenak, P., Mirtorabi, S., Roy, A., Nguyen, L., and P. [RFC4915] Psenak, P., Mirtorabi, S., Roy, A., Nguyen, L., and P.
Pillay-Esnault, "Multi-Topology (MT) Routing in OSPF", Pillay-Esnault, "Multi-Topology (MT) Routing in OSPF",
RFC 4915, June 2007. RFC 4915, June 2007.
[RFC5029] Vasseur, JP. and S. Previdi, "Definition of an IS-IS Link [RFC5029] Vasseur, JP. and S. Previdi, "Definition of an IS-IS
Attribute Sub-TLV", RFC 5029, September 2007. Link Attribute Sub-TLV", RFC 5029, September 2007.
[RFC5120] Przygienda, T., Shen, N., and N. Sheth, "M-ISIS: Multi [RFC5120] Przygienda, T., Shen, N., and N. Sheth, "M-ISIS: Multi
Topology (MT) Routing in Intermediate System to Topology (MT) Routing in Intermediate System to
Intermediate Systems (IS-ISs)", RFC 5120, February 2008. Intermediate Systems (IS-ISs)", RFC 5120,
February 2008.
Appendix A. OSPF Example Where LFA Based on Local Area Topology is [RFC5340] Ferguson, D., Moy, J., and A. Lindem, "OSPF for IPv6",
RFC 5340, July 2008.
Appendix A. OSPF Example Where LFA Based on Local Area Topology Is
Insufficient Insufficient
This appendix provides an example scenario where the local area This appendix provides an example scenario where the local area
topology does not suffice to determine that an LFA is available. As topology does not suffice to determine that an LFA is available. As
described in Section 6.3, one problem scenario is for ASBR summaries described in Section 6.3, one problem scenario is for ASBR summaries
where the ASBR is available in two areas via intra-area routes and where the ASBR is available in two areas via intra-area routes and
there is at least one ABR or alternate ABR that is in both areas. there is at least one ABR or alternate ABR that is in both areas.
The following Figure 7 illustrates this case. The following Figure 7 illustrates this case.
5 5
skipping to change at page 28, line 32 skipping to change at page 28, line 39
| | * | | *
| 5 | * 10** | 5 | * 10**
| | * | | *
|---[ X ]----[ ASBR ] |---[ X ]----[ ASBR ]
5 5
---- Link in Area 1 ---- Link in Area 1
**** Link in Area 2 **** Link in Area 2
#### Link in Backbone Area 0 #### Link in Backbone Area 0
Figure 7: Topology with Multi-area ASBR Causing Area Transiting Figure 7: Topology with Multi-Area ASBR Causing Area Transiting
In Figure 7, the ASBR is also an ABR and is announced into both area In Figure 7, the ASBR is also an ABR and is announced into both area
1 and area 2. A and B are both ABRs that are also connected to the 1 and area 2. A and B are both ABRs that are also connected to the
backbone area. S determines that N can provide a loop-free alternate backbone area. S determines that N can provide a loop-free alternate
to reach the ASBR. N's path goes via A. A also sees an intra-area to reach the ASBR. N's path goes via A. A also sees an intra-area
route to ASBR via Area 2; the cost of the path in area 2 is 30, which route to ASBR via area 2; the cost of the path in area 2 is 30, which
is less than 35, the cost of the path in area 1. Therefore, A uses is less than 35, the cost of the path in area 1. Therefore, A uses
the path from area 2 and directs traffic to F. The path from F in the path from area 2 and directs traffic to F. The path from F in
area 2 goes to B. B is also an ABR and learns the ASBR from both area 2 goes to B. B is also an ABR and learns the ASBR from both
areas 1 and area 2; B's path via area 1 is shorter (cost 20) than B's areas 1 and area 2; B's path via area 1 is shorter (cost 20) than B's
path via area 2 (cost 25). Therefore, B uses the path from area 1 path via area 2 (cost 25). Therefore, B uses the path from area 1
that connects to S. that connects to S.
Authors' Addresses Authors' Addresses
Alia K. Atlas (editor) Alia K. Atlas (editor)
BT BT
Email: alia.atlas@bt.com EMail: alia.atlas@bt.com
Alex Zinin (editor) Alex Zinin (editor)
Alcatel Alcatel-Lucent
701 E Middlefield Rd. 750D Chai Chee Rd, #06-06
Mountain View, CA 94043 Technopark@ChaiChee
USA Singapore 469004
Email: alex.zinin@alcatel.com EMail: alex.zinin@alcatel-lucent.com
Raveendra Torvi Raveendra Torvi
FutureWei Technologies Inc. FutureWei Technologies Inc.
1700 Alma Dr. Suite 100 1700 Alma Dr. Suite 100
Plano, TX 75075 Plano, TX 75075
USA USA
Email: traveendra@huawei.com EMail: traveendra@huawei.com
Gagan Choudhury Gagan Choudhury
AT&T AT&T
200 Laurel Avenue, Room D5-3C21 200 Laurel Avenue, Room D5-3C21
Middletown, NJ 07748 Middletown, NJ 07748
USA USA
Phone: +1 732 420-3721 Phone: +1 732 420-3721
Email: gchoudhury@att.com EMail: gchoudhury@att.com
Christian Martin Christian Martin
iPath Technologies iPath Technologies
Email: chris@ipath.net EMail: chris@ipath.net
Brent Imhoff Brent Imhoff
Juniper Networks Juniper Networks
1194 North Mathilda 1194 North Mathilda
Sunnyvale, CA 94089 Sunnyvale, CA 94089
USA USA
Phone: +1 314 378 2571 Phone: +1 314 378 2571
Email: bimhoff@planetspork.com EMail: bimhoff@planetspork.com
Don Fedyk Don Fedyk
Nortel Networks Nortel Networks
600 Technology Park 600 Technology Park
Billerica, MA 01821 Billerica, MA 01821
USA USA
Phone: +1 978 288 3041 Phone: +1 978 288 3041
Email: dwfedyk@nortelnetworks.com EMail: dwfedyk@nortelnetworks.com
Full Copyright Statement Full Copyright Statement
Copyright (C) The IETF Trust (2008). Copyright (C) The IETF Trust (2008).
This document is subject to the rights, licenses and restrictions This document is subject to the rights, licenses and restrictions
contained in BCP 78, and except as set forth therein, the authors contained in BCP 78, and except as set forth therein, the authors
retain all their rights. retain all their rights.
This document and the information contained herein are provided on an This document and the information contained herein are provided on an
skipping to change at page 31, line 44 skipping to change at line 1363
attempt made to obtain a general license or permission for the use of attempt made to obtain a general license or permission for the use of
such proprietary rights by implementers or users of this such proprietary rights by implementers or users of this
specification can be obtained from the IETF on-line IPR repository at specification can be obtained from the IETF on-line IPR repository at
http://www.ietf.org/ipr. http://www.ietf.org/ipr.
The IETF invites any interested party to bring to its attention any The IETF invites any interested party to bring to its attention any
copyrights, patents or patent applications, or other proprietary copyrights, patents or patent applications, or other proprietary
rights that may cover technology that may be required to implement rights that may cover technology that may be required to implement
this standard. Please address the information to the IETF at this standard. Please address the information to the IETF at
ietf-ipr@ietf.org. ietf-ipr@ietf.org.
Acknowledgment
Funding for the RFC Editor function is provided by the IETF
Administrative Support Activity (IASA).
 End of changes. 131 change blocks. 
315 lines changed or deleted 283 lines changed or added

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