    Network Working Group                                      A. Atlas, Ed.
    Request for Comments: 5286                                            BT
    Category: Standards Track                                  A. Zinin, Ed.
                                                              Alcatel-Lucent
                                                              September 2008

         Basic Specification for IP Fast Reroute: Loop-Free Alternates

    Status of This Memo

       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

       This document describes the use of loop-free alternates to provide
       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
       link group (SRLG).  The goal of this technology is to reduce the
       packet loss that happens while routers converge after a topology
       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 until the distributed network convergence process completes.
       This simple approach does not require any support from other routers.
       The extent to which this goal can be met by this specification is
       dependent on the topology of the network.

    Atlas, et al.               Standards Track                     [Page 1]

    RFC 5286         IP Fast Reroute: Loop-Free Alternates    September 2008

    Table of Contents

       1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  3
         1.1.  Failure Scenarios  . . . . . . . . . . . . . . . . . . . .  5
         1.2.  Requirement Language . . . . . . . . . . . . . . . . . . .  8
       2.  Applicability of Described Mechanisms  . . . . . . . . . . . .  8
       3.  Alternate Next-Hop Calculation . . . . . . . . . . . . . . . .  9
         3.1.  Basic Loop-Free Condition  . . . . . . . . . . . . . . . . 10
         3.2.  Node-Protecting Alternate Next-Hops  . . . . . . . . . . . 10
         3.3.  Broadcast and Non-Broadcast Multi-Access (NBMA) Links  . . 11
         3.4.  ECMP and Alternates  . . . . . . . . . . . . . . . . . . . 12
         3.5.  Interactions with IS-IS Overload, RFC 3137, and Costed
               Out Links  . . . . . . . . . . . . . . . . . . . . . . . . 13
           3.5.1.  Interactions with IS-IS Link Attributes  . . . . . . . 14
         3.6.  Selection Procedure  . . . . . . . . . . . . . . . . . . . 14
         3.7.  LFA Types and Trade-Offs . . . . . . . . . . . . . . . . . 18
         3.8.  A Simplification: Per-Next-Hop LFAs  . . . . . . . . . . . 19
       4.  Using an Alternate . . . . . . . . . . . . . . . . . . . . . . 20
         4.1.  Terminating Use of Alternate . . . . . . . . . . . . . . . 20
       5.  Requirements on LDP Mode . . . . . . . . . . . . . . . . . . . 22
       6.  Routing Aspects  . . . . . . . . . . . . . . . . . . . . . . . 22
         6.1.  Multi-Homed Prefixes . . . . . . . . . . . . . . . . . . . 22
         6.2.  IS-IS  . . . . . . . . . . . . . . . . . . . . . . . . . . 24
         6.3.  OSPF . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
           6.3.1.  OSPF External Routing  . . . . . . . . . . . . . . . . 24
           6.3.2.  OSPF Multi-Topology  . . . . . . . . . . . . . . . . . 25
         6.4.  BGP Next-Hop Synchronization . . . . . . . . . . . . . . . 25
         6.5.  Multicast Considerations . . . . . . . . . . . . . . . . . 25
       7.  Security Considerations  . . . . . . . . . . . . . . . . . . . 25
       8.  Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 26
       9.  References . . . . . . . . . . . . . . . . . . . . . . . . . . 26
         9.1.  Normative References . . . . . . . . . . . . . . . . . . . 26
         9.2.  Informative References . . . . . . . . . . . . . . . . . . 26
       Appendix A.  OSPF Example Where LFA Based on Local Area
                    Topology Is Insufficient  . . . . . . . . . . . . . . 27

    Atlas, et al.               Standards Track                     [Page 2]

    RFC 5286         IP Fast Reroute: Loop-Free Alternates    September 2008

    1.  Introduction

       Applications for interactive multimedia services such as Voice over
       IP (VoIP) and pseudowires can be very sensitive to traffic loss, such
       as occurs 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 [FRAMEWORK], minimizing traffic loss requires a
       mechanism for the router adjacent to a failure to rapidly invoke a
       repair path, which is minimally affected by any subsequent re-
       convergence.  This specification describes such a mechanism that
       allows a router whose local link has failed to forward traffic to a
       pre-computed alternate until the router installs the new primary
       next-hops based upon the changed network topology.  The terminology
       used in this specification is given in [FRAMEWORK].  The described
       mechanism assumes that routing in the network is performed using a
       link-state routing protocol -- OSPF [RFC2328] [RFC2740] [RFC5340] or
       IS-IS [RFC1195] [RFC2966] (for IPv4 or IPv6).  The mechanism also
       assumes that both the primary path and the alternate path are in the
       same routing area.

       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
       affected prefixes, and only then install those new primary next-hops
       into the forwarding plane.  Until the new primary next-hops are
       installed, traffic directed towards the affected prefixes is
       discarded.  This process can take hundreds of milliseconds.

                              <--
                                   +-----+
                            /------|  S  |--\
                           /       +-----+   \
                          / 5               8 \
                         /                     \
                       +-----+                +-----+
                       |  E  |                | N_1 |
                       +-----+                +-----+
                          \                     /
                      \    \  4              3 /  /
                       \|   \                 / |/
                       -+    \    +-----+    /  +-
                              \---|  D  |---/
                                  +-----+

                             Figure 1: Basic Topology

    Atlas, et al.               Standards Track                     [Page 3]

    RFC 5286         IP Fast Reroute: Loop-Free Alternates    September 2008

       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.

       To clarify the behavior of IP Fast Reroute, consider the simple
       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
       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
       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
       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
       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
       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
       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
       each destination.  The process of computing an alternate next-hop
       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
       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
       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
       next-hop is dependent on the topology and the nature of the failure
       for which the alternate is calculated.

       This specification uses the terminology introduced in [FRAMEWORK].
       In particular, it uses Distance_opt(X,Y), abbreviated to D_opt(X,Y),
       to indicate the shortest distance from X to Y.  S is used to indicate
       the calculating router.  N_i is a neighbor of S; N is used as an
       abbreviation when only one neighbor is being discussed.  D is the
       destination under consideration.

    Atlas, et al.               Standards Track                     [Page 4]

    RFC 5286         IP Fast Reroute: Loop-Free Alternates    September 2008

       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)

                         Inequality 1: Loop-Free Criterion

       A subset of loop-free alternates are downstream paths that must meet
       a more restrictive condition that is applicable to more complex
       failure scenarios:

                     Distance_opt(N, D) < Distance_opt(S, D)

                      Inequality 2: Downstream Path Criterion

    1.1.  Failure Scenarios

       The alternate next-hop can protect against a single link failure, a
       single node failure, failure of one or more links within a shared
       risk link group, or a combination of these.  Whenever a failure
       occurs that is more extensive than what the alternate was intended to
       protect, there is the possibility of temporarily looping traffic
       (note again, that such a loop would only last until the next complete
       SPF calculation).  The example where a node fails when the alternate
       provided only link protection is illustrated below.  If unexpected
       simultaneous failures 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
       possible for traffic using the alternates to experience micro-
       looping.  This issue is illustrated in Figure 2.  If Link(S->E)
       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
       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
       thus causing a forwarding loop.  Such a scenario can arise because
       the key assumption, that all other routers in the network are
       forwarding based upon the shortest path, is violated because of a
       second simultaneous correlated failure -- another link connected to
       the same primary neighbor.  If there are not other protection
       mechanisms to handle node failure, a node failure is still a concern
       when only using link-protecting LFAs.

    Atlas, et al.               Standards Track                     [Page 5]

    RFC 5286         IP Fast Reroute: Loop-Free Alternates    September 2008

                                     <@@@
                               @@@>
                        +-----+       +-----+
                        |  S  |-------|  N  |
                        +-+---+   5   +-----+
                          |              |
                          | 5          4 |  |
                       |  |              | \|/
                      \|/ |              |
                          |    +-----+   |
                          +----|  E  |---+
                               +--+--+
                                  |
                                  |
                                  | 10
                                  |
                               +--+--+
                               |  D  |
                               +-----+

         Figure 2: Link-Protecting Alternates Causing Loop on Node Failure

       Micro-looping of traffic via the alternates caused when a more
       extensive failure than planned for occurs can be prevented via
       selection of only downstream paths as alternates.  A micro-loop due
       to the use of alternates can be avoided by using downstream paths
       because each succeeding router in the path to the destination must be
       closer to the destination than its predecessor (according to the
       topology prior to the failures).  Although use of downstream paths
       ensures that the micro-looping via alternates does not occur, such a
       restriction can severely limit the coverage of alternates.  In
       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
       discard the traffic, thus avoiding the micro-loop.

       As shown above, the use of either a node-protecting LFA (described in
       Section 3.2) or a downstream path provides protection against micro-
       looping in the event of node failure.  There are topologies where
       there may be either a node-protecting LFA, a downstream path, both,
       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
       neighbor node failure.  While a link-and-node-protecting LFA
       guarantees protection against either link or node failure, a
       downstream path provides protection only against a link failure and
       may or may not provide protection against a node failure depending on
       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
       path, although no looping can occur, the traffic will not be

    Atlas, et al.               Standards Track                     [Page 6]

    RFC 5286         IP Fast Reroute: Loop-Free Alternates    September 2008

       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,
       if N had a link-and-node-protecting LFA or downstream path via some
       other path (not shown), then the repair may succeed.

       Since the functionality of link-and-node-protecting LFAs is greater
       than that of link-protecting downstream paths, a router SHOULD select
       a link-and-node-protecting LFA over a link-protecting downstream
       path.  If there are any destinations for which a link-and-node-
       protecting LFA is not available, then by definition the path to all
       of those destinations from any neighbor of the computing router (S)
       must be through the node (E) being protected (otherwise there would
       be a node protecting LFA for that destination).  Consequently, if
       there exists a downstream path to the protected node as destination,
       then that downstream path may be used for all those destinations for
       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
       condition Distance_opt(N, E) < Distance_opt(S, E).

       It may be desirable to find an alternate that can protect against
       other correlated failures (of which node failure is a specific
       instance).  In the general case, these are handled by shared risk
       link groups (SRLGs) where any links in the network can belong to the
       SRLG.  General SRLGs may add unacceptably to the computational
       complexity of finding a loop-free alternate.

       However, a sub-category of SRLGs is of interest and can be applied
       only during the selection of an acceptable alternate.  This sub-
       category is to express correlated failures of links that are
       connected to the same router, for example, if there are multiple
       logical sub-interfaces on the same physical interface, such as VLANs
       on an Ethernet interface, if multiple interfaces use the same
       physical port because of channelization, or if multiple interfaces
       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
       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 that
       does not use a link in the same local-SRLG as the primary next-hop.
       The failure of local-SRLGs belonging to E can be protected against
       via node 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 IS-IS area, whose topology is used in 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.

    Atlas, et al.               Standards Track                     [Page 7]

    RFC 5286         IP Fast Reroute: Loop-Free Alternates    September 2008

    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

       IP Fast Reroute mechanisms described in this memo cover intra-domain
       routing only, with OSPF [RFC2328] [RFC2740] [RFC5340] or IS-IS
       [RFC1195] [RFC2966] as the IGP.  Specifically, Fast Reroute for BGP
       inter-domain routing is not part of this specification.

       Certain aspects of OSPF inter-area routing behavior explained in
       Section 6.3 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
       constraints 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 Area
           Border Routers (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
           Autonomous System Border Router (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.

    Atlas, et al.               Standards Track                     [Page 8]

    RFC 5286         IP Fast Reroute: Loop-Free Alternates    September 2008

    3.  Alternate Next-Hop Calculation

       In addition to the set of primary next-hops obtained through a
       shortest path tree (SPT) computation that is part of standard link-
       state routing functionality, routers supporting IP Fast Reroute also
       calculate a set of backup next-hops that are engaged when a local
       failure occurs.  These backup next-hops are calculated to provide the
       required type of protection (i.e., link-protecting and/or node-
       protecting) and to guarantee that when the expected failure occurs,
       forwarding traffic through them will not result in a loop.  Such
       next-hops are called loop-free alternates or LFAs throughout this
       specification.

       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
       information:

       o  Shortest-path distance from the calculating router to the
          destination (Distance_opt(S, D))

       o  Shortest-path distance from the router's IGP neighbors to the
          destination (Distance_opt(N, D))

       o  Shortest path distance from the router's IGP neighbors to itself
          (Distance_opt(N, S))

       o  Distance_opt(S, D) is normally available from the regular SPF
          calculation performed by the link-state routing protocols.
          Distance_opt(N, D) and Distance_opt(N, S) can be obtained by
          performing additional SPF calculations from the perspective of
          each IGP neighbor (i.e., considering the neighbor's vertex as the
          root of the SPT--called SPT(N) hereafter--rather than the
          calculating router's one, called SPT(S)).

       This specification defines a form of SRLG protection limited to those
       SRLGs that include a link to which the calculating router is directly
       connected.  Only that set of SRLGs could cause a local failure; the
       calculating router only computes alternates to handle a local
       failure.  Information about local link SRLG membership is manually
       configured.  Information about remote link SRLG membership may be
       dynamically obtained using [RFC4205] or [RFC4203].  Define
       SRLG_local(S) to be the set of SRLGs that include a link to which the
       calculating router S is directly connected Only SRLG_local(S) is of
       interest during the calculation, but the calculating router must
       correctly handle changes to SRLG_local(S) triggered by local link
       SRLG membership changes.

    Atlas, et al.               Standards Track                     [Page 9]

    RFC 5286         IP Fast Reroute: Loop-Free Alternates    September 2008

       In order to choose among all available LFAs that provide required
       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
       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
       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
       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
       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
       V.  The union of the set of SRLGs associated with a candidate
       alternate next-hop and the SRLG_set(N, D) for the neighbor reached
       via that candidate next-hop is used to determine SRLG protection.

       The following sections provide information required for calculation
       of LFAs.  Sections 3.1 through 3.4 define different types of LFA
       conditions.  Section 3.5 describes constraints imposed by the IS-IS
       overload and OSPF stub router functionality.  Section 3.6 defines the
       summarized algorithm for LFA calculation using the definitions in the
       previous sections.

    3.1.  Basic Loop-Free Condition

       Alternate next hops used by implementations following this
       specification MUST conform to at least the loop-freeness condition
       stated above in Inequality 1.  This condition guarantees that
       forwarding traffic to an LFA will not result in a loop after a link
       failure.

       Further conditions may be applied when determining link-protecting
       and/or node-protecting alternate next-hops as described in Sections
       3.2 and 3.3.

    3.2.  Node-Protecting Alternate Next-Hops

       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
       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
       neighbor providing a loop-free alternate.

             Distance_opt(N, D) < Distance_opt(N, E) + Distance_opt(E, D)

         Inequality 3: Criteria for a Node-Protecting Loop-Free Alternate

    Atlas, et al.               Standards Track                    [Page 10]

    RFC 5286         IP Fast Reroute: Loop-Free Alternates    September 2008

       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
       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
       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
       Inequality 3 is not met.

    3.3.  Broadcast and Non-Broadcast Multi-Access (NBMA) Links

       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
       link.  This is because a broadcast link is represented as a pseudo-
       node with zero-cost links connecting it to other nodes.

       Because failure of an interface attached to a broadcast segment may
       mean loss of connectivity of the whole segment, the condition
       described for broadcast link protection is pessimistic and requires
       that the alternate is loop-free with regard to the pseudo-node.
       Consider the example in Figure 3.

                           +-----+    15
                           |  S  |--------
                           +-----+       |
                              | 5        |
                              |          |
                              | 0        |
                            /----\ 0 5 +-----+
                            | PN |-----|  N  |
                            \----/     +-----+
                               | 0        |
                               |          | 8
                               | 5        |
                            +-----+ 5  +-----+
                            |  E  |----|  D  |
                            +-----+    +-----+

               Figure 3: Loop-Free Alternate That 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
       SHOULD be loop-free with respect to that link's pseudo-node (PN) to
       provide link protection.  This requirement is described in Inequality
       4 below.

                  D_opt(N, D) < D_opt(N, PN) + D_opt(PN, D)

       Inequality 4: Loop-Free Link-Protecting Criterion for Broadcast Links

    Atlas, et al.               Standards Track                    [Page 11]

    RFC 5286         IP Fast Reroute: Loop-Free Alternates    September 2008

       Because the shortest path from the pseudo-node goes through E, if a
       loop-free alternate from a neighbor N is node-protecting, the
       alternate will also be link-protecting unless the router S can only
       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-
       protecting, this implies that for point-to-point interfaces, an LFA
       that is node-protecting is always link-protecting.  Because S can
       direct the traffic away from the shortest path to use the alternate
       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 node-protecting is not automatically link-protecting for a
       broadcast or NBMA link.

       To obtain link protection, it is necessary both that the path from
       the selected alternate next-hop does not traverse the link of
       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.  To clarify, consider the
       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-
       node PN.  Second, it is necessary that the alternate next-hop
       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
       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.

       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.  S's shortest path to the
       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
       SRLG protection.

    3.4.  ECMP and Alternates

       With Equal-Cost Multi-Path (ECMP), a prefix may have multiple primary
       next-hops that are used to forward traffic.  When a particular
       primary next-hop fails, alternate next-hops should be used to
       preserve the traffic.  These alternate next-hops may themselves also
       be primary next-hops, but need not be.  Other primary next-hops are
       not guaranteed to provide protection against the failure scenarios of
       concern.

    Atlas, et al.               Standards Track                    [Page 12]

    RFC 5286         IP Fast Reroute: Loop-Free Alternates    September 2008

                               20 L1      L3  3
                           [ N ]----[ S ]--------[ E3 ]
                             |        |            |
                             |      5 | L2         |
                          20 |        |            |
                             |    ---------        | 2
                             |  5 |       | 5      |
                             |  [ E1 ]  [ E2 ]-----|
                             |     |       |
                             | 10  |    10 |
                             |---[ A ]   [ B ]
                                  |        |
                                2 |--[ D ]-| 2

         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
       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
       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
       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
       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
       next-hop L2 to E1 to obtain an alternate next-hop that provides both
       link and node protection by using L1.

       Alternate next-hops are determined for each primary next-hop
       separately.  As with alternate selection in the non-ECMP case, these
       alternate next-hops should maximize the coverage of the failure
       cases.

    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
       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.

       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
       (for OSPF) or the maximum cost (for IS-IS) or that has the overload
       bit set (for IS-IS).  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.

    Atlas, et al.               Standards Track                    [Page 13]

    RFC 5286         IP Fast Reroute: Loop-Free Alternates    September 2008

       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
       an alternate.

       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.

       This preserves the desired behavior of diverting traffic away from a
       router that is following [RFC3137], and it also preserves the desired
       behavior when an operator sets the cost of a link to LSInfinity for
       maintenance that is not permitting traffic across that link unless
       there is no other path.

       If a link or router that is costed out was the only possible
       alternate to protect traffic from a particular router S to a
       particular destination, then there should be no alternate provided
       for protection.

    3.5.1.  Interactions with IS-IS Link Attributes

       [RFC5029] describes several flags whose interactions with LFAs need
       to be defined.  A router SHOULD NOT specify the "local protection
       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
       been advertised with the attribute "link excluded from local
       protection path" or with the attribute "local maintenance required".

    3.6.  Selection Procedure

       A router supporting this specification SHOULD attempt to select at
       least one loop-free alternate next-hop for each primary next-hop used
       for a given prefix.  A router MAY decide to not use an available
       loop-free alternate next-hop.  A reason for such a decision might be
       that the loop-free alternate next-hop does not provide protection for
       the failure scenario of interest.

       The alternate selection should maximize the coverage of the failure
       cases.

       When calculating alternate next-hops, the calculating router S
       applies the following rules.

       1.  S SHOULD select a loop-free node-protecting alternate next-hop,
           if one is available.  If no loop-free node-protecting alternate
           is available, then S MAY select a loop-free link-protecting
           alternate.

    Atlas, et al.               Standards Track                    [Page 14]

    RFC 5286         IP Fast Reroute: Loop-Free Alternates    September 2008

       2.  If S has a choice between a loop-free link-and-node-protecting
           alternate and a loop-free node-protecting alternate that is not
           link-protecting, S SHOULD select a loop-free link-and-node-
           protecting alternate.  This can occur as explained in
           Section 3.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 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 link or node 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.

       5.  Implementations considering SRLGs MAY use SRLG protection to
           determine that a node-protecting or link-protecting alternate is
           not available for use.

       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
          Inequality 1 and Inequality 3.  The path avoids S, S's primary
          neighbor E, and the link from S to E.

       Loop-Free Link-Protecting Alternate -  This next-hop satisfies
          Inequality 1 but not Inequality 3.  If the primary next-hop uses a
          broadcast link, then this next-hop satisfies Inequality 4.

       An alternate path may also provide none, some, or complete SRLG
       protection as well as node and link or link protection.  For
       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
       alternate would only provide partial SRLG protection.

    Atlas, et al.               Standards Track                    [Page 15]

    RFC 5286         IP Fast Reroute: Loop-Free Alternates    September 2008

       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.  S has neighbors N_1 to N_j.  A candidate
       next-hop is indicated by (outgoing link, neighbor) and the outgoing
       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.
       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
       and H_i.neighbor refers to the neighbor of that next-hop.

       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 = {}

    Atlas, et al.               Standards Track                    [Page 16]

    RFC 5286         IP Fast Reroute: Loop-Free Alternates    September 2008

       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 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 IS-IS),
               and H_h.link is bidirectional,

            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 cand_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.link 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 20.

       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,
            then continue to the next candidate next-hop

       12.  If cand_node-protect is TRUE and P_i.alt_node-protect is FALSE,
            goto Paragraph 20.

       13.  If cand_link-protect is TRUE and P_i.alt_link-protect is FALSE,
            goto Step 20.

    Atlas, et al.               Standards Track                    [Page 17]

    RFC 5286         IP Fast Reroute: Loop-Free Alternates    September 2008

       14.  If cand_srlg-protect has a better set of SRLGs than
            P_i.alt_srlg-protect, goto Step 20.

       15.  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 Step 20.  If P_i.alt_next_hops is
            preferred, skip H_h and continue to the next candidate next-hop.

       16.  If D_opt(H_h.neighbor, D) < D_opt(P_i.neighbor, D) and
            D_opt(P_i.alt_next_hops, D) >= D_opt(P_i.neighbor, D), then H_h
            is a downstream alternate and P_i.alt_next_hops is simply an
            LFA.  Prefer H_h and goto Step 20.

       17.  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 20.

       18.  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.

       19.  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.

       20.  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.

    3.7.  LFA Types and Trade-Offs

       LFAs can provide different amounts of protection, and the decision
       about which type to prefer is dependent upon network topology and
       other techniques in use in the network.  This section describes the
       different protection levels and the trade-offs associated with each.

       1.  Primary Next-hop: When there are equal-cost primary next-hops,
           using one as an alternate is guaranteed not to cause micro-loops
           involving S.  Traffic flows across the paths that the network
           will converge to, but congestion may be experienced on the
           primary paths since traffic is sent across fewer.  All primary
           next-hops are downstream paths.

    Atlas, et al.               Standards Track                    [Page 18]

    RFC 5286         IP Fast Reroute: Loop-Free Alternates    September 2008

       2.  Downstream Paths: A downstream path, unlike an LFA, is guaranteed
           not to cause a micro-loop involving S regardless of the actual
           failure detected.  However, the expected coverage of such
           alternates in a network is expected to be poor.  All downstream
           paths are LFAs.

       3.  LFA: An LFA can have good coverage of a network, depending on
           topology.  However, it is possible to get micro-loops involving S
           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-
       protecting), NP (node-protecting), and SP (SRLG-protecting).

       a.  LP, NP, and SP: If such an alternate exists, it gives protection
           against all failures.

       b.  LP and NP only: Many networks may handle SRLG failures via
           another method or may focus on node and link failures as being
           more common.

       c.  LP only: A network may handle node failures via a high-
           availability technique and be concerned primarily about
           protecting the more common link failure case.

       d.  NP only: These only exist on interfaces that aren't point-to-
           point.  If link protection is handled in a different layer, then
           an NP alternate may be acceptable.

    3.8.  A Simplification: Per-Next-Hop LFAs

       It is possible to simplify the computation and use of LFAs when
       solely link protection is desired by considering and computing only
       one link-protecting LFA for each next-hop connected to the router.
       All prefixes that use that next-hop as a primary will use the LFA
       computed for that next-hop as its LFA.

       Even a prefix with multiple primary next-hops will have each primary
       next-hop protected individually by the primary next-hop's associated
       LFA.  That associated LFA might or might not be another of the
       primary next-hops of the prefix.

       This simplification may reduce coverage in a network.  In addition to
       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
       found for some of the prefixes that use that next-hop.

    Atlas, et al.               Standards Track                    [Page 19]

    RFC 5286         IP Fast Reroute: Loop-Free Alternates    September 2008

       For example, consider Figure 4 where S has three ECMP next-hops, E1,
       E2, and E3 to reach D.  For the prefix D, E3 can give link protection
       for the next-hops E1 and E2; E1 and E2 can give link protection for
       the next-hops E3.  However, if one uses this simplification to
       compute LFAs for E1, E2, and E3 individually, there is no link-
       protecting LFA for E1.  E3 and E2 can protect each other.

    4.  Using an Alternate

       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
       follows.

       When a next-hop failure is detected via a local interface failure or
       other failure detection mechanisms (see [FRAMEWORK]), the router
       SHOULD:

       1.  Remove the primary next-hop associated with the failure.

       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 that are
       routed according to the shortest path.  Multicast traffic is
       specifically out of scope for this specification.

    4.1.  Terminating Use of Alternate

       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
       the router will start using the new primary next-hops.  It ensures
       that all possible transient conditions are removed and the network
       converges according to the deployed routing protocol.

       There are techniques available to handle the micro-forwarding loops
       that can occur in a networking during convergence.

       A router that implements [MICROLOOP] SHOULD follow the rules given
       there for terminating the use of an alternate.

       A router that implements [ORDERED-FIB] SHOULD follow the rules given
       there for terminating the use of an alternate.

    Atlas, et al.               Standards Track                    [Page 20]

    RFC 5286         IP Fast Reroute: Loop-Free Alternates    September 2008

       It is desirable to avoid micro-forwarding loops involving S.  An
       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
       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
       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
       new topology.  This can be avoided by S delaying its installation and
       leaving traffic on the alternate next-hop.

                              +-----+
                              |  N2 |--------   |
                              +-----+   1   |  \|/
                                  |         |
                                  |     +-----+    @@>  +-----+
                                  |     |  S  |---------|  N1 |
                               10 |     +-----+   10    +-----+
                                  |        |               |
                                  |      1 |    |          |
                                  |        |   \|/    10   |
                                  |     +-----+            |  |
                                  |     |  E  |            | \|/
                                  |     +-----+            |
                                  |        |               |
                                  |      1 |  |            |
                                  |        | \|/           |
                                  |    +-----+             |
                                  |----|  D  |--------------
                                       +-----+

          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
       alternate before the failure and therefore may have been forwarding
       traffic through S.  This will occur when the path via a previously
       upstream node is shorter than the path via a loop-free alternate
       neighbor.  In these cases, it is useful to give sufficient time to
       ensure that the new primary neighbor and other nodes on the new
       primary path have switched to the new route.

       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
       wasn't dependent on the failure and therefore its path will not have
       changed.

       Given that there is an alternate providing appropriate protection and
       while the assumption of a single failure holds, it is safe to delay
       the installation of the new primaries; this will not create

    Atlas, et al.               Standards Track                    [Page 21]

    RFC 5286         IP Fast Reroute: Loop-Free Alternates    September 2008

       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
       affected by the failure.

       An implementation SHOULD continue to use the alternate next-hops for
       packet forwarding even after the new routing information is available
       based on the new network topology.  The use of the alternate next-
       hops for packet forwarding SHOULD terminate:

       a.  if the new primary next-hop was loop-free prior to the topology
           change, or

       b.  if a configured hold-down, which represents a worst-case bound on
           the length of the network convergence transition, has expired, or

       c.  if notification of an unrelated topological change in the network
           is received.

    5.  Requirements on LDP Mode

       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
       alternates indicated by the IGP.  To do so, it is necessary for LDP
       to have the appropriate labels available for the alternate so that
       the appropriate out-segments can be installed in the forwarding plane
       before the failure occurs.

       This means that a Label Switching Router (LSR) running LDP must
       distribute its labels for the Forwarding Equivalence Classes (FECs)
       it can provide to all its neighbors, regardless of whether or not
       they are upstream.  Additionally, LDP must be acting in liberal label
       retention mode so that the labels that correspond to neighbors that
       aren't currently the primary neighbor are stored.  Similarly, LDP
       should be in downstream unsolicited mode, so that the labels for the
       FEC are distributed other than along the SPT.

       If these requirements are met, then LDP can use the loop-free
       alternates without requiring any targeted sessions or signaling
       extensions for this purpose.

    6.  Routing Aspects

    6.1.  Multi-Homed Prefixes

       An SPF-like computation is run for each topology, which corresponds
       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
       for routes obtained from outside the routing domain by multiple

    Atlas, et al.               Standards Track                    [Page 22]

    RFC 5286         IP Fast Reroute: Loop-Free Alternates    September 2008

       routers, for subnets on links where the subnet is announced from
       multiple ends of the link, and for routes advertised by multiple
       routers to provide resiliency.

       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
       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
       shortest path to p, then the prefix p's alternate next-hop would be
       the link to C.  This would provide link protection, but not the node
       protection that is possible via A.

                          5   +---+  8   +---+  5  +---+
                        ------| S |------| A |-----| B |
                        |     +---+      +---+     +---+
                        |       |                    |
                        |     5 |                  5 |
                        |       |                    |
                      +---+ 5 +---+   5       7    +---+
                      | C |---| E |------ p -------| F |
                      +---+   +---+                +---+

                           Figure 6: Multi-Homed Prefix

       To determine the best protection possible, the prefix p can be
       treated in the SPF computations as a node with unidirectional links
       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
       links.

       If there exist multiple multi-homed prefixes that share the same
       connectivity and the difference in metrics to those routers, then a
       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
       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.

       A router SHOULD compute the alternate next-hop for an IGP multi-homed
       prefix by considering alternate paths via all routers that have
       announced that prefix.

       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.

    Atlas, et al.               Standards Track                    [Page 23]

    RFC 5286         IP Fast Reroute: Loop-Free Alternates    September 2008

    6.2.  IS-IS

       The applicability and interactions of LFAs with multi-topology IS-IS
       [RFC5120] is out of scope for this specification.

    6.3.  OSPF

       OSPF introduces certain complications because it is possible for the
       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.
       There are several cases where issues such as this can occur.  They
       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
       clarify, an example topology is given in Appendix A.

       a.  Virtual Links: These allow paths to leave the backbone area and
           traverse the transit area.  The path provided via the transit
           area can exit via any ABR.  The path taken is not the shortest
           path determined by doing an SPF in the backbone area.

       b.  Alternate ABR [RFC3509]: When an ABR is not connected to the
           backbone, it considers the inter-area summaries from multiple
           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.
           This can lead to scenarios similar to that illustrated in
           Figure 7.

       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
           to which area to use.  This is the example illustrated in
           Figure 7.

       d.  AS External Prefixes: A prefix may be advertised by multiple
           ASBRs in different areas and/or with multiple forwarding
           addresses that are in different areas, which are connected via at
           least one common ABR.  This presents such ABRs with a decision as
           to which area to use to reach the prefix.

       Loop-free alternates should not be used in an area where one of the
       above issues affects that area.

    6.3.1.  OSPF External Routing

       When a forwarding address is set in an OSPF AS-external Link State
       Advertisement (LSA), all routers in the network calculate their next-
       hops for the external prefix by doing a lookup for the forwarding
       address in the routing table, rather than using the next-hops

    Atlas, et al.               Standards Track                    [Page 24]

    RFC 5286         IP Fast Reroute: Loop-Free Alternates    September 2008

       calculated for the ASBR.  In this case, the alternate next-hops
       SHOULD be computed by selecting among the alternate paths to the
       forwarding link(s) instead of among alternate paths to the ASBR.

    6.3.2.  OSPF Multi-Topology

       The applicability and interactions of LFAs with multi-topology OSPF
       [RFC4915] [MT-OSPFv3] is out of scope for this specification.

    6.4.  BGP Next-Hop Synchronization

       Typically, BGP prefixes are advertised with the AS exit router's
       router-id as the BGP next-hop, and AS exit routers are reached by
       means of IGP routes.  BGP resolves its advertised next-hop to the
       immediate next-hop by potential recursive lookups in the routing
       database.  IP Fast Reroute computes the alternate next-hops to all
       IGP destinations, which include alternate next-hops to the AS exit
       router's router-id.  BGP simply inherits the alternate next-hop from
       IGP.  The BGP decision process is unaltered; BGP continues to use the
       IGP optimal distance to find the nearest exit router.  Multicast BGP
       (MBGP) routes do not need to copy the alternate next-hops.

       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
       alternate next-hops as if the BGP route were a multi-homed prefix.
       This is for future study.

    6.5.  Multicast Considerations

       Multicast traffic is out of scope for this specification of IP Fast
       Reroute.  The alternate next-hops SHOULD NOT be used for multicast
       Reverse Path Forwarding (RPF) checks.

    7.  Security Considerations

       The mechanism described in this document does not modify any routing
       protocol messages, and hence no new threats related to packet
       modifications or replay attacks are introduced.  Traffic to certain
       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.

       In LDP, the wider distribution of FEC label information is still to
       neighbors with whom a trusted LDP session has been established.  This
       wider distribution and the recommendation of using liberal label
       retention mode are believed to have no significant security impact.

    Atlas, et al.               Standards Track                    [Page 25]

    RFC 5286         IP Fast Reroute: Loop-Free Alternates    September 2008

    8.  Acknowledgements

       The authors would like to thank Joel Halpern, Mike Shand, Stewart
       Bryant, and Stefano Previdi for their assistance and useful review.

    9.  References

    9.1.  Normative References

       [RFC2119]      Bradner, S., "Key words for use in RFCs to Indicate
                      Requirement Levels", BCP 14, RFC 2119, March 1997.

       [RFC2328]      Moy, J., "OSPF Version 2", STD 54, RFC 2328,
                      April 1998.

       [RFC2740]      Coltun, R., Ferguson, D., and J. Moy, "OSPF for IPv6",
                      RFC 2740, December 1999.

       [RFC5036]      Andersson, L., Minei, I., and B. Thomas, "LDP
                      Specification", RFC 5036, October 2007.

    9.2.  Informative References

       [FRAMEWORK]    Shand, M. and S. Bryant, "IP Fast Reroute Framework",
                      Work in Progress, February 2008.

       [MICROLOOP]    Zinin, A., "Analysis and Minimization of Microloops in
                      Link-state Routing Protocols", Work in Progress,
                      October 2005.

       [MT-OSPFv3]    Mirtorabi, S. and A. Roy, "Multi-topology routing in
                      OSPFv3 (MT-OSPFv3)", Work in Progress, July 2007.

       [ORDERED-FIB]  Francois, P., "Loop-free convergence using oFIB", Work
                      in Progress, February 2008.

       [RFC1195]      Callon, R., "Use of OSI IS-IS for routing in TCP/IP
                      and dual environments", RFC 1195, December 1990.

       [RFC2966]      Li, T., Przygienda, T., and H. Smit, "Domain-wide
                      Prefix Distribution with Two-Level IS-IS", RFC 2966,
                      October 2000.

       [RFC3137]      Retana, A., Nguyen, L., White, R., Zinin, A., and D.
                      McPherson, "OSPF Stub Router Advertisement", RFC 3137,
                      June 2001.

    Atlas, et al.               Standards Track                    [Page 26]

    RFC 5286         IP Fast Reroute: Loop-Free Alternates    September 2008

       [RFC3509]      Zinin, A., Lindem, A., and D. Yeung, "Alternative
                      Implementations of OSPF Area Border Routers",
                      RFC 3509, April 2003.

       [RFC4203]      Kompella, K. and Y. Rekhter, "OSPF Extensions in
                      Support of Generalized Multi-Protocol Label Switching
                      (GMPLS)", RFC 4203, October 2005.

       [RFC4205]      Kompella, K. and Y. Rekhter, "Intermediate System to
                      Intermediate System (IS-IS) Extensions in Support of
                      Generalized Multi-Protocol Label Switching (GMPLS)",
                      RFC 4205, October 2005.

       [RFC4915]      Psenak, P., Mirtorabi, S., Roy, A., Nguyen, L., and P.
                      Pillay-Esnault, "Multi-Topology (MT) Routing in OSPF",
                      RFC 4915, June 2007.

       [RFC5029]      Vasseur, JP. and S. Previdi, "Definition of an IS-IS
                      Link Attribute Sub-TLV", RFC 5029, September 2007.

       [RFC5120]      Przygienda, T., Shen, N., and N. Sheth, "M-ISIS: Multi
                      Topology (MT) Routing in Intermediate System to
                      Intermediate Systems (IS-ISs)", RFC 5120,
                      February 2008.

       [RFC5340]      Ferguson, D., Moy, J., and A. Lindem, "OSPF for IPv6",
                      RFC 5340, July 2008.

    Atlas, et al.               Standards Track                    [Page 27]

    RFC 5286         IP Fast Reroute: Loop-Free Alternates    September 2008

    Appendix A.  OSPF Example Where LFA Based on Local Area Topology Is
                 Insufficient

       This appendix provides an example scenario where the local area
       topology does not suffice to determine that an LFA is available.  As
       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
       there is at least one ABR or alternate ABR that is in both areas.
       The following Figure 7 illustrates this case.

                                   5
                         [ F ]-----------[ C ]
                           |               |
                           |               | 5
                        20 |          5    |     1
                           |   [ N ]-----[ A ]*****[ F ]
                           |     |         #         *
                           |  40 |         # 50      *  2
                           |     |    5    #    2    *
                           |   [ S ]-----[ B ]*****[ G ]
                           |     |         *
                           |   5 |         * 15
                           |     |         *
                           |   [ E ]     [ H ]
                           |     |         *
                           |   5 |         * 10**
                           |     |         *
                           |---[ X ]----[ ASBR ]
                                      5

                           ----  Link in Area 1
                           ****  Link in Area 2
                           ####  Link in Backbone Area 0

          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
       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
       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
       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
       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
       path via area 2 (cost 25).  Therefore, B uses the path from area 1
       that connects to S.

    Atlas, et al.               Standards Track                    [Page 28]

    RFC 5286         IP Fast Reroute: Loop-Free Alternates    September 2008

    Authors' Addresses

       Alia K. Atlas (editor)
       BT

       EMail: alia.atlas@bt.com

       Alex Zinin (editor)
       Alcatel-Lucent
       750D Chai Chee Rd, #06-06
       Technopark@ChaiChee
       Singapore 469004

       EMail: alex.zinin@alcatel-lucent.com

       Raveendra Torvi
       FutureWei Technologies Inc.
       1700 Alma Dr. Suite 100
       Plano, TX  75075
       USA

       EMail: traveendra@huawei.com

       Gagan Choudhury
       AT&T
       200 Laurel Avenue, Room D5-3C21
       Middletown, NJ  07748
       USA

       Phone: +1 732 420-3721
       EMail: gchoudhury@att.com

       Christian Martin
       iPath Technologies

       EMail: chris@ipath.net

    Atlas, et al.               Standards Track                    [Page 29]

    RFC 5286         IP Fast Reroute: Loop-Free Alternates    September 2008

       Brent Imhoff
       Juniper Networks
       1194 North Mathilda
       Sunnyvale, CA  94089
       USA

       Phone: +1 314 378 2571
       EMail: bimhoff@planetspork.com

       Don Fedyk
       Nortel Networks
       600 Technology Park
       Billerica, MA  01821
       USA

       Phone: +1 978 288 3041
       EMail: dwfedyk@nortelnetworks.com

    Atlas, et al.               Standards Track                    [Page 30]

    RFC 5286         IP Fast Reroute: Loop-Free Alternates    September 2008

    Full Copyright Statement

       Copyright (C) The IETF Trust (2008).

       This document is subject to the rights, licenses and restrictions
       contained in BCP 78, and except as set forth therein, the authors
       retain all their rights.

       This document and the information contained herein are provided on an
       "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
       OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND
       THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS
       OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF
       THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
       WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.

    Intellectual Property

       The IETF takes no position regarding the validity or scope of any
       Intellectual Property Rights or other rights that might be claimed to
       pertain to the implementation or use of the technology described in
       this document or the extent to which any license under such rights
       might or might not be available; nor does it represent that it has
       made any independent effort to identify any such rights.  Information
       on the procedures with respect to rights in RFC documents can be
       found in BCP 78 and BCP 79.

       Copies of IPR disclosures made to the IETF Secretariat and any
       assurances of licenses to be made available, or the result of an
       attempt made to obtain a general license or permission for the use of
       such proprietary rights by implementers or users of this
       specification can be obtained from the IETF on-line IPR repository at
       http://www.ietf.org/ipr.

       The IETF invites any interested party to bring to its attention any
       copyrights, patents or patent applications, or other proprietary
       rights that may cover technology that may be required to implement
       this standard.  Please address the information to the IETF at
       ietf-ipr@ietf.org.

    Atlas, et al.               Standards Track                    [Page 31]