draft-ietf-rtgwg-ipfrr-spec-base-03.txt   draft-ietf-rtgwg-ipfrr-spec-base-04.txt 
Network Working Group A. Atlas, Ed. Network Working Group A. Atlas, Ed.
Internet-Draft Avici Systems, Inc. Internet-Draft Google Inc.
Expires: August 22, 2005 February 21, 2005 Expires: January 16, 2006 A. Zinin, Ed.
Alcatel
July 15, 2005
Basic Specification for IP Fast-Reroute: Loop-free Alternates Basic Specification for IP Fast-Reroute: Loop-free Alternates
draft-ietf-rtgwg-ipfrr-spec-base-03 draft-ietf-rtgwg-ipfrr-spec-base-04
Status of this Memo Status of this Memo
This document is an Internet-Draft and is subject to all provisions By submitting this Internet-Draft, each author represents that any
of section 3 of RFC 3667. By submitting this Internet-Draft, each applicable patent or other IPR claims of which he or she is aware
author represents that any applicable patent or other IPR claims of have been or will be disclosed, and any of which he or she becomes
which he or she is aware have been or will be disclosed, and any of aware will be disclosed, in accordance with Section 6 of BCP 79.
which he or she become aware will be disclosed, in accordance with
RFC 3668.
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as other groups may also distribute working documents as Internet-
Internet-Drafts. Drafts.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt. http://www.ietf.org/ietf/1id-abstracts.txt.
The list of Internet-Draft Shadow Directories can be accessed at The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html. http://www.ietf.org/shadow.html.
This Internet-Draft will expire on August 22, 2005. This Internet-Draft will expire on January 16, 2006.
Copyright Notice Copyright Notice
Copyright (C) The Internet Society (2005). Copyright (C) The Internet Society (2005).
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
micro-looping and packet loss that happens while routers converge micro-looping and packet loss that happens while routers converge
after a topology change due to a failure. Rapid failure repair is after a topology change due to a failure. Rapid failure repair is
achieved through use of precalculated backup next-hops that are achieved through use of precalculated backup next-hops that are loop-
loop-free and safe to use until the distributed network convergence free and safe to use until the distributed network convergence
process completes. process completes.
Table of Contents Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1 Failure Scenarios . . . . . . . . . . . . . . . . . . . . 5 1.1 Failure Scenarios . . . . . . . . . . . . . . . . . . . . 5
2. Applicability of Described Mechanisms . . . . . . . . . . . . 7 2. Applicability of Described Mechanisms . . . . . . . . . . . . 6
3. Alternate Next-Hop Calculation . . . . . . . . . . . . . . . . 7 3. Alternate Next-Hop Calculation . . . . . . . . . . . . . . . . 7
3.1 Basic Loop-free Condition . . . . . . . . . . . . . . . . 8 3.1 Basic Loop-free Condition . . . . . . . . . . . . . . . . 8
3.2 Node-Protecting Alternate Next-Hops . . . . . . . . . . . 8 3.2 Node-Protecting Alternate Next-Hops . . . . . . . . . . . 9
3.3 Broadcast and NBMA Links . . . . . . . . . . . . . . . . . 9 3.3 Broadcast and NBMA Links . . . . . . . . . . . . . . . . . 9
3.4 Downstream Alternate Next-Hops . . . . . . . . . . . . . . 10 3.4 ECMP and Alternates . . . . . . . . . . . . . . . . . . . 11
3.5 ECMP and Alternates . . . . . . . . . . . . . . . . . . . 11 3.5 Interactions with ISIS Overload, RFC 3137 and Costed
3.6 Interactions with ISIS Overload, RFC 3137 and Costed Out Links . . . . . . . . . . . . . . . . . . . . . . . . 11
Out Links . . . . . . . . . . . . . . . . . . . . . . . . 12 3.6 Selection Procedure . . . . . . . . . . . . . . . . . . . 12
3.7 Selection Procedure . . . . . . . . . . . . . . . . . . . 12 4. Using an Alternate . . . . . . . . . . . . . . . . . . . . . . 16
4. Using an Alternate . . . . . . . . . . . . . . . . . . . . . . 13 4.1 Terminating Use of Alternate . . . . . . . . . . . . . . . 16
4.1 Terminating Use of Alternate . . . . . . . . . . . . . . . 14 5. Requirements on LDP Mode . . . . . . . . . . . . . . . . . . . 18
5. Requirements on LDP Mode . . . . . . . . . . . . . . . . . . . 16 6. Routing Aspects . . . . . . . . . . . . . . . . . . . . . . . 18
6. Routing Aspects . . . . . . . . . . . . . . . . . . . . . . . 16 6.1 Multi-Homed Prefixes . . . . . . . . . . . . . . . . . . . 19
6.1 Multi-Homed Prefixes . . . . . . . . . . . . . . . . . . . 16 6.2 OSPF . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
6.2 OSPF . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 6.2.1 OSPF External Routing . . . . . . . . . . . . . . . . 20
6.2.1 OSPF External Routing . . . . . . . . . . . . . . . . 19 6.3 BGP Next-Hop Synchronization . . . . . . . . . . . . . . . 20
6.3 BGP Next-Hop Synchronization . . . . . . . . . . . . . . . 19 6.4 Multicast Considerations . . . . . . . . . . . . . . . . . 21
6.4 Multicast Considerations . . . . . . . . . . . . . . . . . 19 7. Security Considerations . . . . . . . . . . . . . . . . . . . 21
7. Security Considerations . . . . . . . . . . . . . . . . . . . 19 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 21
8. References . . . . . . . . . . . . . . . . . . . . . . . . . . 19 9. References . . . . . . . . . . . . . . . . . . . . . . . . . . 21
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . 20 9.1 Normative References . . . . . . . . . . . . . . . . . . . 21
9.2 Informative References . . . . . . . . . . . . . . . . . . 22
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . 23
A. OSPF Example Where LFA Based on Local Area Topology is A. OSPF Example Where LFA Based on Local Area Topology is
Insufficient . . . . . . . . . . . . . . . . . . . . . . . . . 22 Insufficient . . . . . . . . . . . . . . . . . . . . . . . . . 24
Intellectual Property and Copyright Statements . . . . . . . . 23 Intellectual Property and Copyright Statements . . . . . . . . 26
1. Introduction 1. Introduction
Applications for interactive multimedia services such as VoIP and Applications for interactive multimedia services such as VoIP and
pseudo-wires can be very sensitive to traffic loss, such as occurs pseudo-wires can be very sensitive to traffic loss, such as occurs
when a link or router in the network fails. A router's convergence when a link or router in the network fails. A router's convergence
time is generally on the order of seconds; the application traffic time is generally on the order of seconds; the application traffic
may be sensitive to losses greater than 10s of milliseconds. may be sensitive to losses greater than 10s of milliseconds.
As discussed in [FRAMEWORK], minimizing traffic loss requires a As discussed in [FRAMEWORK], minimizing traffic loss requires a
mechanism for the router adjacent to a failure to rapidly invoke a mechanism for the router adjacent to a failure to rapidly invoke a
repair path, which is minimally affected by any subsequent repair path, which is minimally affected by any subsequent re-
re-convergence. This specification describes such a mechanism which convergence. This specification describes such a mechanism which
allows a router whose local link has failed to forward traffic to a allows a router whose local link has failed to forward traffic to a
pre-computed alternate until the router installs the new primary pre-computed alternate until the router installs the new primary
next-hops based upon the changed network topology. The terminology next-hops based upon the changed network topology. The terminology
used in this specification is given in [FRAMEWORK]. The described used in this specification is given in [FRAMEWORK]. The described
mechanism assumes that routing in the network is performed using a mechanism assumes that routing in the network is performed using a
link-state routing protocol-- OSPF[RFC2328] or ISIS link-state routing protocol-- OSPF[RFC2328] or ISIS [RFC1195]
[RFC1195][RFC2966]. [RFC2966].
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 seconds. discarded. This process can take seconds.
<-- <--
+-----+ +-----+
skipping to change at page 4, line 9 skipping to change at page 4, line 9
Figure 1: Basic Topology Figure 1: Basic Topology
The goal of IP Fast-Reroute is to reduce failure reaction time to 10s The goal of IP Fast-Reroute is to reduce failure reaction time to 10s
of milliseconds by using a pre-computed alternate next-hop, in the of milliseconds by using a pre-computed alternate next-hop, in the
event that the currently selected primary next-hop fails, so that the event that the currently selected primary next-hop fails, so that the
alternate can be rapidly used when the failure is detected. A alternate can be rapidly used when the failure is detected. A
network with this feature experiences less traffic loss and less network with this feature experiences less traffic loss and less
micro-looping of packets than a network without IPFRR. There are micro-looping of packets than a network without IPFRR. There are
cases where micro-looping is still a possibility since IPFRR coverage cases where micro-looping is still a possibility since IPFRR coverage
varies but in the worst possible situation a network with IPFRR is varies but in the worst possible situation a network with IPFRR is
equivalent with respect traffic convergence to a network without equivalent with respect to traffic convergence to a network without
IPFRR. IPFRR.
To clarify the behavior of IP Fast-Reroute, consider the simple 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
skipping to change at page 4, line 35 skipping to change at page 4, line 35
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 topology dependent. next-hop is topology dependent and the nature of the failure the
alternate is calculated for.
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)
Equation 1: Loop-Free Criterion Equation 1: Loop-Free Criterion
A sub-set of loop-free alternate are downstream paths which must meet A sub-set of loop-free alternate are downstream paths which must meet
the more restrictive condition of a more restrictive condition that is applicable to more complex
failure scenarios:
Distance_opt(N, D) < Distance_opt(S, D) Distance_opt(N, D) < Distance_opt(S, D)
Equation 2: Downstream Path Criterion Equation 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, one or more shared risk link group failure, or a single node failure, one or more shared risk link group failure, or a
combination of these. Whenever a failure occurs that is more combination of these. Whenever a failure occurs that is more
extensive than what the alternate was intended to protect, there is extensive than what the alternate was intended to protect, there is
the possibility of looping traffic. The example where a node fails the possibility of temporarily looping traffic (note again, that such
when the alternate provided only link protection is illustrated a loop would only last until the next complete SPF calculation). The
below. If unexpected simultaneous failures occur, then micro-looping example where a node fails when the alternate provided only link
may occur since the alternates are not pre-computed to avoid the set protection is illustrated below. If unexpected simultaneous failures
of failed links. occur, then micro-looping may occur since the alternates are not pre-
computed to avoid the set of failed 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 possible for traffic using the alternates to experience micro-
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 a node failure is still a concern when only using link mechanisms a node failure is still a concern when only using link
skipping to change at page 6, line 24 skipping to change at page 6, line 4
| +-----+ | | +-----+ |
+----| E |---+ +----| E |---+
+--+--+ +--+--+
| |
| |
| 10 | 10
| |
+--+--+ +--+--+
| D | | D |
+-----+ +-----+
Figure 2: Link-Protecting Alternates Causing Loop on Node Failure Figure 2: Link-Protecting Alternates Causing Loop on Node Failure
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 can be prevented via selection of extensive failure than planned for can be prevented via selection of
only downstream paths as alternates. In Figure 2, S would be able to only downstream paths as alternates. In Figure 2, S would be able to
use N as an alternate, but N could not use S; therefore N would have use N as an alternate, but N could not use S; therefore N would have
no alternate and would discard the traffic, thus avoiding the no alternate and would discard the traffic, thus avoiding the micro-
micro-loop. A micro-loop due to the use of alternates can be avoided loop. A micro-loop due to the use of alternates can be avoided by
by using downstream paths because each router in the path to the using downstream paths because each router in the path to the
destination must be closer to the destination (according to the destination must be closer to the destination (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. restriction can severely limit the coverage of alternates.
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 only during the selection of an acceptable alternate. This sub-
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 which
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 The local-SRLGs belonging to E can be protected against via node-
node-protection; i.e. picking a loop-free node-protecting alternate. protection; i.e. picking a loop-free node-protecting alternate.
Where SRLG protection is provided, it is in the context of the
particular OSPF or ISIS area, whose topology is used the SPF
computations to compute the loop-free alternates. If an SRLG
contains links in multiple areas, then separate SRLG-protecting
alternates would be required in each area that is traversed by the
affected traffic.
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] or ISIS [RFC1195][RFC2966] as the
IGP. Specifically, Fast Reroute for BGP inter-domain routing is not IGP. Specifically, Fast Reroute for BGP inter-domain routing is not
part of this specification. part of this specification.
Certain aspects of OSPF inter-area routing behavior explained in
Section 6.2 and Appendix A impact the ability of the router
calculating the backup next-hops to assess traffic trajectories. In
order to avoid micro-looping and ensure required coverage, certain
constrains are applied to multi-area OSPF networks:
a. Loop-free alternates should not be used in the backbone area if
there are any virtual links configured unless, for each transit
area, there is a full mesh of virtual links between all ABRs in
that area. Loop-free alternates may be 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
an area that contains more than one alternate ABR. [RFC3509]
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
exists an ABR that is announced as an ASBR in multiple non-
backbone areas and there exists another 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
a network for AS External routes where an AS External prefix is
advertised with the same type of external metric by multiple
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 addresses in multiple non-backbone areas when an ABR
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 shortest path tree (SPT) computation that is part of standard link-
link-state routing functionality, routers supporting IP Fast Reroute state routing functionality, routers supporting IP Fast Reroute also
also calculate a set of backup next hops that are engaged when a calculate a set of backup next hops that are engaged when a local
local failure occurs. These backup next hops are calculated to failure occurs. These backup next hops are calculated to provide
provide required type of protection (i.e. link-protecting and/or required type of protection (i.e. link-protecting and/or node-
node-protecting) and to guarantee that when the expected failure protecting) and to guarantee that when the expected failure occurs,
occurs, forwarding traffic through them will not result in a loop. forwarding traffic through them will not result in a loop. Such next
Such next hops are called loop-free alternates or LFAs throughout hops are called loop-free alternates or LFAs throughout this
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 routers 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 routers 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 that the calculating router is directly
connected to. Information about local link SRLG membership is connected to. Information about local link SRLG membership is
manually configured. Information about remote link SRLG membership manually configured. Information about remote link SRLG membership
is dynamically obtained using [ISIS-SRLG] or [OSPF-SRLG]. In order is dynamically obtained using [ISIS-SRLG] or [OSPF-SRLG]. In order
to choose among all available LFAs those that provide required SRLG to choose among all available LFAs that provide required SRLG
protection for a given destination, the calculating router needs to protection for a given destination, the calculating router needs to
track the set of SRLGs that the path through a specific IGP neighbor track the set of SRLGs that the path through a specific IGP neighbor
involves. To do so, each node D in the network topology is involves. To do so, each node D in the network topology is
associated with SRLG_set(N, D), which is the set of SRLGs that would 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 calculate be crossed if traffic to D was forwarded through N. To calculate this
this set, the router initializes SRLG_set(N, N) for each of its IGP set, the router initializes SRLG_set(N, N) for each of its IGP
neighbors to be empty. During the SPT(N) calculation, when a new 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 union 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 of SRLG sets associated with its parents, and the SRLG sets
associated with the links from V's parents to V. The union of the associated with the links from V's parents to V. The union of the set
set of SRLG associated with a candidate alternate next-hop and the of SRLG associated with a candidate alternate next-hop and the
SRLG_set(N, D) for the neighbor reached via that candidate next-hop SRLG_set(N, D) for the neighbor reached via that candidate next-hop
is used to determine SRLG protection. 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.5 define different of LFAs. Sections Section 3.1 through Section 3.4 define different
types of LFA conditions. Section 3.6 describes constrains imposed by types of LFA conditions. Section 3.5 describes constrains imposed by
the IS-IS overload and OSPF stub router functionality. Section 3.7 the IS-IS overload and OSPF stub router functionality. Section 3.6
defines the summarized algorithm for LFA calculation using the defines the summarized algorithm for LFA calculation using the
definitions in the previous sections. definitions in the 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 Equation 1. This condition guarantees that stated above in Equation 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.
skipping to change at page 9, line 13 skipping to change at page 9, line 28
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)
Equation 3: Criteria for a Node-Protecting Loop-Free Alternate Equation 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 must 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
Equation 3 is not met. Equation 3 is not met.
3.3 Broadcast and NBMA Links 3.3 Broadcast and 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 of the fact that a broadcast link is link. This is because a broadcast link is represented as a pseudo-
represented as a pseudo-node with zero-cost links connecting it to node with zero-cost links connecting it to other nodes.
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 for mean loss of connectivity of the whole segment, the condition
broadcast link protection is pessimistic and requires that the described for broadcast link protection is pessimistic and requires
alternate is loop- free with regard to the pseudo-node. Consider the that the alternate is loop-free with regard to the pseudo-node.
example in Figure 3. Consider the example in Figure 3.
+-----+ 15 +-----+ 15
| S |-------- | S |--------
+-----+ | +-----+ |
| 5 | | 5 |
| | | |
| 0 | | 0 |
/----\ 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 which is link-protecting.
If the primary next-hop uses a broadcast link, then an alternate must If the primary next-hop uses a broadcast link, then an alternate
be loop-free with respect to that link's pseudo-node to provide link SHOULD be loop-free with respect to that link's pseudo-node to
protection. This requirement is described in Equation 4 below. provide link protection. This requirement is described in Equation 4
below.
D_opt(N, D) < D_opt(N, pseudo) + D_opt(pseudo, D) D_opt(N, D) < D_opt(N, pseudo) + D_opt(pseudo, D)
Equation 4: Loop-Free Link-Protecting Criterion for Broadcast Links Equation 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 neighbor N via the same pseudo-node. This can occur reach the alternate neighbor N via the same pseudo-node. This can
because S will direct traffic away from the shortest path to use an occur because S will direct traffic away from the shortest path to
alternate. Therefore link protection must be considered during the use an alternate.
alternate selection.
3.4 Downstream Alternate Next-Hops
In certain situations, described later, alternate next-hops must
comply with the stricter condition provided in Equation 2 that
defines a downstream path. The main property of the downstream paths
is that traffic is always forwarded to a node that is closer to the
destination, i.e. a node with a smaller metric. This property
guarantees that no looping occurs regardless of the type of failure
or the network architecture.
To ensure node-protection in certain scenarios, it is not sufficient
to satisfy Equation 3. Instead the stricter downstream condition
given in Equation 5 must be satisfied.
Distance_opt(N, D) < Distance_opt(E, D)
Equation 5: Criteria for a Node-Protecting Downstream Alternate
Similarly, to ensure link-protection in certain scenarios, the
stricter downstream condition given in Equation 6 must be satisfied
instead of merely Equation 4.
D_opt(N, D) < D_opt(pseudo, D)
Equation 6: Link-Protecting Downstream Criterion for Broadcast Links
The following types of alternate next-hops are defined. These
describe increasingly contrained subsets of alternates; all strict
downstream alternates are downstream alternates and all downstream
alternates are loop-free alternates.
Loop-Free Alternate (LFA): Satisfies Equation 1. Link protection
determined via Equation 4. Node protection determined via
Equation 3.
Downstream Alternate: Satisfies Equation 2. Link protection
determined via Equation 4. Node protection determined via
Equation 3.
Strict Downstream Alternate (SDA): Satisfies Equation 2. Link
protection determined via Equation 6. Node protection determined
via Equation 5.
A downstream alternate is sufficient to guarantee that no looping To obtain link protection, it is necessary both that the path from
occurs regardless of the type of failure. An SDA is necessary to the selected alternate next-hop does not traverse the link of
guarantee protection in certain scenarios described in Section 6.2. 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-
point-to-point links. Therefore, if the primary next-hop is across a
broadcast or NBMA interface, it is necessary to consider link
protection during the alternate selection. 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 also necessary for SRLG
protection.
3.5 ECMP and Alternates 3.4 ECMP and Alternates
With equal-cost multi-path, a prefix may have multiple primary With equal-cost multi-path, a prefix may have multiple primary next-
next-hops that are used to forward traffic. When a particular hops that are used to forward traffic. When a particular primary
primary next-hop fails, alternate next-hops should be used to next-hop fails, alternate next-hops should be used to preserve the
preserve the traffic. These alternate next-hops may themselves also traffic. These alternate next-hops may themselves also be primary
be primary next-hops, but need not be. Other primary next-hops are next-hops, but need not be. Other primary next-hops are not
not guaranteed to provide protection against the failure scenarios of 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 L1 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; L1 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 E3 can link protection from L3 to E3. The third primary next-hop L3 to E3
obtain link and node protection from L2 to E1, but can only get link can obtain link and node protection from L2 to E1 and from L2 to E2.
protection from L2 to E2. It is possible for both the primary It is possible for both the primary next-hop L2 to E2 and the primary
next-hop L2 to E2 and the primary next-hop L2 to E1 to obtain an next-hop L2 to E1 to obtain an alternate next-hop that provides both
alternate next-hop that provides both link and node protection by link and node protection by using L1.
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.6 Interactions with ISIS Overload, RFC 3137 and Costed Out Links 3.5 Interactions with ISIS 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 consider diverting from For computing an alternate, a router MUST NOT use an alternate next-
the SPF tree 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 whose next-hop router (for OSPF) or the maximum cost (for ISIS) or which has the overload
has the overload bit set (for ISIS). bit set (for ISIS). For a broadcast link, the reverse cost
associated with a potential alternate next-hop is the cost towards
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
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.
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 consider have a reverse cost of LSInfinity, then router S MUST NOT use N_i as
using 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 ISIS, 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 which 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 which 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 which 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 will be no alternate provided for particular destination, then there should be no alternate provided
protection. for protection.
3.7 Selection Procedure 3.6 Selection Procedure
A router supporting this specification SHOULD select at least one A router supporting this specification SHOULD attempt to select at
loop-free alternate next-hop for each primary next-hop used for a least one loop-free alternate next-hop for each primary next-hop used
given prefix. A router MAY decide to not use an available loop-free for a given prefix. A router MAY decide to not use an available
alternate next-hop. A reason for such a decision might be that the loop-free alternate next-hop. A reason for such a decision might be
loop-free alternate next-hop does not provide protection for the that the loop-free alternate next-hop does not provide protection for
failure scenario of interest. the failure scenario of interest.
The alternate selection should maximize the coverage of the failure The alternate selection should maximize the coverage of the failure
cases. cases.
S SHOULD select a loop-free node-protecting alternate next-hop, if When calculating alternate next-hops, the calculating router S
one is available. If S has a choice between a loop-free applies the following rules.
link-protecting node-protecting alternate and a loop-free
node-protecting alternate which is not link-protecting, S SHOULD 1. S SHOULD select a loop-free node-protecting alternate next-hop,
select a loop-free node-protecting alternate which is also if one is available. If no loop-free node-protecting alternate
link-protecting. This can occur as explained in Section 3.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 a loop-free
node-protecting alternate. 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.
Each next-hop can be categorized as to the type of alternate it can 2. If S has a choice between a loop-free link-protecting node-
provide to a particular destination D from router S for a particular protecting alternate and a loop-free node-protecting alternate
primary next-hop which goes to a neighbor E. A next-hop may provide which is not link-protecting, S SHOULD select a loop-free node-
one of the following types of paths: protecting alternate which is also link-protecting. This can
occur as explained in Section 3.3.
Primary Path - This is the primary next-hop. 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
a loop-free node-protecting alternate if available. If no loop-
free node-protecting alternate is available and no other primary
next-hop can provide link-protection, then S SHOULD select a
loop-free link-protecting alternate.
4. Implementations SHOULD support a mode where other primary next-
hops satisfying the basic loop-free condition and providing at
least a minimal level of protection are preferred over any non-
primary alternates. This mode is provided to allow the
administrator to preserve traffic patterns based on regular ECMP
behavior.
Following the above rules maximizes the level of protection and use
of primary (ECMP) next-hops.
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
a particular destination D, and the type of protection it can provide
relative to a specific primary next-hop E:
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
Equation 1 and Equation 3. The path avoids S, S's primary Equation 1 and Equation 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
Equation 1 but not Equation 3. If the primary next-hop uses a Equation 1 but not Equation 3. If the primary next-hop uses a
broadcast link, then this next-hop satisfies Equation 4. broadcast link, then this next-hop satisfies Equation 4.
Unavailable - This may be because the path goes through S to reach
D, because the link is costed out, etc.
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
alternate next-hops. The algorithm is given for informational
purposes and implementations are free to use any other algorithm as
long as it satisfies the rules described above.
The following procedure describes how to select an alternate next-
hop. The procedure is described to determine alternate next-hops to
use to reach each router in the topology. Prefixes that are
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
used to reach a prefix that is advertised by more than one router
when the logical topological transformation described in Section 6.1
is used.
S is the computing router and has candidate next-hops H_1 through
H_k. N_i and N_j are used to refer to neighbors of S. For a next-hop
to be a candidate, the next-hop must be associated with a bi-
directional link, as is determined by the IGP. 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), 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 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. This procedure
finds the alternate next-hop(s) for P_i.
First, initialize the alternate information for P_i as follows:
P_i.alt_next_hops = {}
P_i.alt_type = NONE P_i.alt_link-protect = FALSE
P_i.alt_node-protect = FALSE
P_i.alt_srlg-protect = {}
For each candidate next-hop H_h,
1. Initialize variables as follows:
cand_type = NONE
cand_link-protect = FALSE
cand_node-protect = FALSE
cand_srlg-protect = {}
2. If H_h is P_i, skip it and continue to the next candidate next-
hop.
3. If H_h.link is administratively allowed to be used as an
alternate,
and the cost of H_h.link 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.link is bi-directional,
then H_h can be considered as an alternate. Otherwise, skip it
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,
D), then H_h is not loop-free. Skip it and continue to the next
candidate next-hop.
5. cand_type = LOOP-FREE.
6. If H_h is a primary next-hop, set cand_type to PRIMARY.
7. If H_h.link is not P_i.link, set can_link-protect to TRUE.
8. If D_opt(H_h.neighbor, D) < D_opt(H_h.neighbor, P_i.neighbor) +
D_opt(P_i.neighbor, D), set cand_node-protect to TRUE.
9. If the router considers SRLGs, then set the cand_srlg-protect to
the set of SRLGs traversed on the path from S via P_i to
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
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
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-
hops for use as the alternate, and the P_i.alt_type is not
PRIMARY, goto Step 18.
11. If cand_node-protect is TRUE and P_i.alt_node-protect is FALSE,
goto Paragraph 18.
12. If cand_link-protect is TRUE and P_i.alt_link-protect is FALSE,
goto Step 18.
13. If cand_srlg-protect has a better set of SRLGs than
P_i.alt_srlg-protect, goto Step 18.
14. If cand_srlg-protect is different from P_i.alt_srlg-protect,
then select between H_h and P_i.alt_next_hops based upon
distance, IP addresses, or any router-local tie-breaker. If H_h
is preferred, then goto to Step 18. Otherwise, skip H_h and
continue to the next candidate next-hop.
15. Based upon the alternate types, the alternate distances, IP
addresses, or other tie-breakers, decide if H_h is preferred to
P_i.alt_next_hops. If so, goto Step 18.
16. Decide if P_i.alt_next_hops is preferred to H_h. If so, then
skip H_h and continue to the next candidate next-hop.
17. Add H_h into P_i.alt_next_hops. Set P_i.alt_type to the better
type of H_h.alt_type and P_i.alt_type. Continue to the next
candidate next-hop.
18. Replace the P_i alternate next-hop set with H_h as follows:
P_i.alt_next_hops = {H_h}
P_i.alt_type = cand_type
P_i.alt_link-protect = cand_link-protect
P_i.alt_node-protect = cand_node-protect
P_i.alt_srlg-protect = cand_srlg-protect
Continue to the next candidate next-hop.
4. Using an Alternate 4. Using an Alternate
If an alternate next-hop is available, the router SHOULD redirect If an alternate next-hop is available, the router redirects traffic
traffic to the alternate next-hop when the primary next-hop has to the alternate next-hop in case of a primary next-hop failure as
failed. follows.
When a local interface failure is detected, traffic that was destined When a next-hop failure is detected via a local interface failure or
to go out the failed interface must be redirected to the appropriate other failure detection mechanisms (see [FRAMEWORK]), the router
alternate next-hops. Other failure detection mechanisms which detect SHOULD:
the loss of a link or a node may also be used to trigger redirection
of traffic to the appropriate alternate next-hops. The mechanisms 1. Remove the primary next-hop associated with the failure.
available for failure detection are discussed in [FRAMEWORK] and are
outside the scope of this specification. 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
primary next-hop).
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,
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 which 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
NOTE: this section may be replaced with a reference to [ULOOP].
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.
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
skipping to change at page 15, line 49 skipping to change at page 18, line 14
Given that there is an alternate providing appropriate protection and Given that there is an alternate providing appropriate protection and
while the assumption of a single failure holds, it is safe to delay while the assumption of a single failure holds, it is safe to delay
the installation of the new primaries; this will not create the installation of the new primaries; this will not create
forwarding loops because the alternate's path to the destination is forwarding loops because the alternate's path to the destination is
known to not go via S or the failed element and will therefore not be known to not go via S or the failed element and will therefore not be
affected by the failure. affected by the failure.
An implementation SHOULD continue to use the alternate next-hops for An implementation SHOULD continue to use the alternate next-hops for
packet forwarding even after the new routing information is available packet forwarding even after the new routing information is available
based on the new network topology. The use of the alternate based on the new network topology. The use of the alternate next-
next-hops for packet forwarding SHOULD terminate: hops for packet forwarding SHOULD terminate:
a. if the new primary next-hop was loop-free prior to the topology a. if the new primary next-hop was loop-free prior to the topology
change, or change, or
b. if a configured hold-down, which represents a worst-case bound on b. if a configured hold-down, which represents a worst-case bound on
the length of the network convergence transition, has expired, or the length of the network convergence transition, has expired, or
c. if notification of an unrelated topological change in the network c. if notification of an unrelated topological change in the network
is received. is received.
skipping to change at page 17, line 26 skipping to change at page 19, line 41
+---+ +---+ +---+ +---+ +---+ +---+
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 uni-directional 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 exist that share the If there exist multiple multi-homed prefixes that share the same
same connectivity and the difference in metrics to those routers, connectivity and the difference in metrics to those routers, then a
then a single node can be used to represent the set. For instance, single node can be used to represent the set. For instance, if in
if in Figure 6 there were another prefix X that was connected to E Figure 6 there were another prefix X that was connected to E with a
with a metric of 1 and to F with a metric of 3, then that prefix X metric of 1 and to F with a metric of 3, then that prefix X could use
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 OSPF 6.2 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 the same route is considered 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
clarify, an example topology is given in Appendix A. clarify, an example topology is given in Appendix A.
a. Virtual Links: These allow paths to leave the backbone area and a. Virtual Links: These allow paths to leave the backbone area and
traverse the transit area. The path provided via the transit traverse the transit area. The path provided via the transit
area can exit via any ABR. The path taken is not the shortest area can exit via any ABR. The path taken is not the shortest
path determined by doing an SPF in the backbone area. path determined by doing an SPF in the backbone area.
b. Alternate ABR[RFC3509]: When an ABR is not connected to the b. Alternate ABR[RFC3509]: When an ABR is not connected to the
backbone, it considers the inter-area summaries from multiple backbone, it considers the inter-area summaries from multiple
areas. The ABR A may determine to use area 2 but that path could areas. The ABR A may determine to use area 2 but that path could
traverse another alternate ABR B that determines to use area 1. traverse another alternate ABR B that determines to use area 1.
This can lead to scenarios similar to that illustrated in Figure This can lead to scenarios similar to that illustrated in
7. Figure 7.
c. ASBR Summaries: An ASBR may itself be an ABR and can be announced c. ASBR Summaries: An ASBR may itself be an ABR and can be announced
into multiple areas. This presents other ABRs with a decision as into multiple areas. This presents other ABRs with a decision as
to which area to use. This is the example illustrated in Figure to which area to use. This is the example illustrated in
7. Figure 7.
d. AS External Prefixes: A prefix may be advertised by multiple d. AS External Prefixes: A prefix may be advertised by multiple
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.
This issue does not exist for non-backbone intra-area routes. A
candidate alternate next-hop must be an LFA. For intra-area
backbone, inter-area, and AS External routes, a candidate alternate
next-hop must be an SDA to be used.
If no virtual links exist, backbone intra-area routes can use
candidate alternate next-hops that are LFAs and not SDAs. If no
Alternate ABRs exist, then inter-area routes can use candidate
alternate next-hops that are LFAs and not SDAs.
If no ASBR exists simultaneously in multiple non-backbone areas and
no prefix is included in announcements either by two or more ASBRs
that are in different areas or in announcements associated with
multiple forwarding addresses that are in different areas, then AS
External routes can use candidate alternate next-hops that are LFAs
and not SDAs.
The inappropriate use of an LFA that isn't an SDA can cause
forwarding loops or lack of protection.
In all cases where an SDA is required, this is because the path taken
cannot be determined via the SPT in the local area. The use of an
SDA relies on the fact that any path taken will use hops with
monotonically decreasing distance to the destination. This does not
allow knowledge of the actual path the traffic will traverse.
Therefore, it is not possible, based on the computations described in
this specification, to determine whether an SDA will provide
protection against an SRLG failure.
6.2.1 OSPF External Routing 6.2.1 OSPF External Routing
An additional complication comes from forwarding addresses, where an When a forwarding address is set in an OSPF AS-external LSA, all
ASBR uses a forwarding address to indicate to all routers in the routers in the network calculate their next-hops for the external
Autonomous System to use the specified address instead of going prefix by doing a lookup for the forwarding address in the routing
through the ASBR. When a forwarding address has been indicated, all table, rather than using the next-hops calculated for the ASBR. In
routers in the topology calculate the shortest path to the link this case, the alternate next-hops SHOULD be computed by selecting
specified in the external LSA. In this case, the alternate next-hop 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 BGP Next-Hop Synchronization 6.3 BGP Next-Hop Synchronization
Typically BGP prefixes are advertised with AS exit routers router-id, Typically BGP prefixes are advertised with AS exit routers router-id,
and AS exit routers are reached by means of IGP routes. BGP resolves and AS exit routers are reached by means of IGP routes. BGP resolves
its advertised next-hop to the immediate next-hop by potential its advertised next-hop to the immediate next-hop by potential
recursive lookups in the routing database. IP Fast-Reroute computes recursive lookups in the routing database. IP Fast-Reroute computes
the alternate next-hops to all IGP destinations, which include the alternate next-hops to all IGP destinations, which include
alternate next-hops to the AS exit router's router-id. BGP simply alternate next-hops to the AS exit router's router-id. BGP simply
inherits the alternate next-hop from IGP. The BGP decision process inherits the alternate next-hop from IGP. The BGP decision process
is unaltered; BGP continues to use the IGP optimal distance to find is unaltered; BGP continues to use the IGP optimal distance to find
the nearest exit router. MBGP routes do not need to copy the the nearest exit router. MBGP routes do not need to copy the
alternate next hops. 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 selected a
IGP next-hops and allowed the IGP to determine the primary and set of IGP 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.4 Multicast Considerations 6.4 Multicast Considerations
Multicast traffic is out of scope for this specification of IP Multicast traffic is out of scope for this specification of IP Fast-
Fast-Reroute. The alternate next-hops SHOULD not used for multi-cast Reroute. The alternate next-hops SHOULD not be used for multi-cast
RPF checks. RPF checks.
7. Security Considerations 7. Security Considerations
This document does not introduce any new security issues. The The mechanism described in this document does not modify any routing
mechanisms described in this document depend upon the network protocol messages, and hence no new threats related to packet
topology distributed via an IGP, such as OSPF or ISIS. It is modifications or replay attacks are introduced. Traffic to certain
dependent upon the security associated with those protocols. destinations can be temporarily routed via next-hop routers that
would not be used with the same topology change if this mechanism
wasn't employed. However, these next-hop routers can be used anyway
when a different topological change occurs, and hence this can't be
viewed as a new security threat.
8 References 8. IANA Considerations
This document requires no IANA considerations.
9. References
9.1 Normative References
[RFC1195] Callon, R., "Use of OSI IS-IS for routing in TCP/IP and
dual environments", RFC 1195, December 1990.
[RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998.
[RFC3036] Andersson, L., Doolan, P., Feldman, N., Fredette, A., and
B. Thomas, "LDP Specification", RFC 3036, January 2001.
9.2 Informative References
[FRAMEWORK] [FRAMEWORK]
Shand, M., "IP Fast Reroute Framework", Shand, M., "IP Fast Reroute Framework",
draft-ietf-rtgwg-ipfrr-framework-02.txt (work in draft-ietf-rtgwg-ipfrr-framework-03.txt (work in
progress), October 2004. progress), June 2005.
[ISIS-SRLG] [ISIS-SRLG]
Kompella, K. and Y. Rekhter, "IS-IS Extensions in Support Kompella, K. and Y. Rekhter, "IS-IS Extensions in Support
of Generalized MPLS", draft-ietf-isis-gmpls-extensions-19 of Generalized MPLS", draft-ietf-isis-gmpls-extensions-19
(work in progress), October 2003. (work in progress), October 2003.
[OSPF-SRLG] [OSPF-SRLG]
Kompella, K. and Y. Rekhter, "OSPF Extensions in Support Kompella, K. and Y. Rekhter, "OSPF Extensions in Support
of Generalized Multi-Protocol Label Switching", of Generalized Multi-Protocol Label Switching",
draft-ietf-ccamp-ospf-gmpls-extensions-12 (work in draft-ietf-ccamp-ospf-gmpls-extensions-12 (work in
progress), October 2003. progress), October 2003.
[RFC1195] Callon, R., "Use of OSI IS-IS for routing in TCP/IP and [RFC2966] Li, T., Przygienda, T., and H. Smit, "Domain-wide Prefix
dual environments", RFC 1195, December 1990. Distribution with Two-Level IS-IS", RFC 2966,
October 2000.
[RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998.
[RFC2966] Li, T., Przygienda, T. and H. Smit, "Domain-wide Prefix
Distribution with Two-Level IS-IS", RFC 2966, October
2000.
[RFC3036] Andersson, L., Doolan, P., Feldman, N., Fredette, A. and
B. Thomas, "LDP Specification", RFC 3036, January 2001.
[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.
[RFC3209] Awduche, D., Berger, L., Gan, D., Li, T., Srinivasan, V. [RFC3209] Awduche, D., Berger, L., Gan, D., Li, T., Srinivasan, V.,
and G. Swallow, "RSVP-TE: Extensions to RSVP for LSP and G. Swallow, "RSVP-TE: Extensions to RSVP for LSP
Tunnels", RFC 3209, December 2001. Tunnels", RFC 3209, December 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", RFC 3509,
April 2003. April 2003.
[ULOOP] Zinin, A., "Analysis and Minimization of Microloops in
Link-state Routing Protocols",
draft-zinin-microloop-analysis-01.txt (work in progress),
May 2005.
Authors' Addresses Authors' Addresses
Alia K. Atlas (editor) Alia K. Atlas (editor)
Avici Systems, Inc. Google Inc.
101 Billerica Avenue 1600 Amphitheatre Parkway
N. Billerica, MA 01862 Mountain View, CA 94043
USA USA
Phone: +1 978 964 2070 Email: akatlas@alum.mit.edu
EMail: aatlas@avici.com
Alex Zinin (editor)
Alcatel
701 E Middlefield Rd.
Mountain View, CA 94043
USA
Email: zinin@psg.com
Raveendra Torvi Raveendra Torvi
Avici Systems, Inc. Avici Systems, Inc.
101 Billerica Avenue 101 Billerica Avenue
N. Billerica, MA 01862 N. Billerica, MA 01862
USA USA
Phone: +1 978 964 2026 Phone: +1 978 964 2026
EMail: rtorvi@avici.com Email: rtorvi@avici.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
Verizon Verizon
1880 Campus Commons Drive 1880 Campus Commons Drive
Reston, VA 20191 Reston, VA 20191
USA USA
Brent Imhoff Brent Imhoff
LightCore LightCore
14567 North Outer Forty Rd. 14567 North Outer Forty Rd.
Chesterfield, MO 63017 Chesterfield, MO 63017
USA USA
Phone: +1 314 880 1851 Phone: +1 314 880 1851
EMail: brent@lightcore.net Email: brent@lightcore.net
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
Appendix A. OSPF Example Where LFA Based on Local Area Topology is 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.2, one problem scenario is for ASBR summaries described in Section 6.2, 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.
 End of changes. 

This html diff was produced by rfcdiff 1.25, available from http://www.levkowetz.com/ietf/tools/rfcdiff/