Internet Draft                               Alia Atlas, Ed (Avici Systems)
Expires: March 2005

            Loop-Free Alternates

     Basic Specification for IP/LDP Local Protection

                draft-ietf-rtgwg-ipfrr-spec-base-00.txt IP Fast-Reroute: Loop-free Alternates

                draft-ietf-rtgwg-ipfrr-spec-base-01.txt

Status of this Memo

   This document is an Internet-Draft and is in full conformance with
   all provisions of Section 10 of RFC2026.

   By submitting this Internet-Draft, I certify that any applicable
   patent or other IPR claims of which I am aware have been disclosed,
   or will be disclosed, and any of which I become aware will be
   disclosed, in accordance with RFC 3668.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF), its areas, and its working groups.  Note that
   other groups may also distribute working documents as Internet-
   Drafts.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as ``work a "work in progress.'' progress."

   The list of current Internet-Drafts can be accessed at
   http://www.ietf.org/ietf/1id-abstracts.txt
   http://www.ietf.org/1id-abstracts.html

   The list of Internet-Draft Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html.
   http://www.ietf.org/shadow.html"

Abstract

   This document defines an architecture and selection process for
   providing describes the use of loop-free alternates to provide
   local protection for IP unicast and/or LDP traffic in the event of a
   single link or node failure until the router has
   converged. failure.  When computing the primary next-hop for a prefix, topology change occurs, a router
   S also determines for each prefix an alternate next-hop which can be used
   if the primary next-hop fails.  The  An acceptable alternate next-hop is said to must
   be a loop-free alternate, which goes to a neighbor whose shortest
   path to the prefix does not go back through the router S.

Contents

  1  Introduction  .................................................  2
  2  Terminology  ..................................................
    1.1 Failure Scenarios  .........................................  4
  3  Finding an
  2  Alternate  .........................................  5
  3.1 Next-Hop Calcuation  ................................  6
    2.1  Basic Loop-Free Alternates  ....................................... Condition  ................................  6
  3.2  Selection of an
    2.2  Node-Protecting Alternate  ..................................  7
  3.2.1  Failure Scenarios  ........................................  7
  3.2.2 Next-Hops   .....................  6
    2.3  Broadcast and NBMA Interfaces  ............................  9
  3.2.3 Links  .................................  6
    2.4  Interactions wtih ISIS Overload, RFC 3137
         and Costed Out Links  .....................................  9
  3.2.4  Characterization of Neighbors  ............................ 10
  3.2.5  7
    2.5  Selection Procedure  ...................................... 10
  4  8
  3  Using an Alternate  ........................................... 11
  5  9
    3.1  Terminating Use of Alternate  .............................  9
  4  Requirements on LDP Mode  ..................................... 11
  6
  5  Routing Aspects  .............................................. 12
  6.1 11
  5.1  Multiple-Region Routing  .................................... 12
  6.1.1
  5.1.1  Inheriting Alternate Next-Hops with One Primary Neighbor  . 14
  6.1.2
  5.1.2  OSPF Inter-Area Routes  ................................... 15
  6.1.3 14
  5.1.3  OSPF Inter-Area Routes  ................................... 15
  6.1.4
  5.1.4  ISIS Multi-Level Routing  ................................. 15
  6.2
  5.2  OSPF Virtual Links  ......................................... 15
  6.3
  5.3  BGP Next-Hop Synchronization  ............................... 16
  6.4
  5.4  Multicast Considerations  ................................... 16
  7
  6  Security Considerations  ...................................... 16
  8
  7  Full Copyright Statement  ..................................... 17
  9 16
  8  References  ................................................... 17
  10
  9  Authors Information  .......................................... 18
  11 17
  10 Editor's Information  ......................................... 19
  Appendix A  Loop-Free Alternate Proofs  .......................... 19
  Appendix A.1  Loop-Free Node-Protecting Alternate Proofs  ........ 21 18

1. Introduction

   Applications for interactive multimedia services such as VoIP and
   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
   time is generally on the order of seconds; the application traffic
   may be sensitive to losses greater than 10s of milliseconds.

   As discussed in [FRAMEWORK], minimizing traffic loss requires a
   mechanism for the router adjacent to a failure rapidly invoke a
   repair path, which is minimally affected by any subsequent re-
   convergence.  This document specification describes such a mechanism which
   allows a router whose local link has failed to forward traffic to a pre-
   computed
   pre-computed alternate until the router installs the new primary next-
   hops
   next-hops based upon the changed network topology.  The terminology
   used in this specification is given in [FRAMEWORK].

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

                              /__
                              \

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

                         Figure 1: Basic Topology

   The goal of IP/LDP Local Protection IP Fast-Reroute is to reduce that traffic convergence
   time to 10s of milliseconds by using a pre-computed alternate interface, next-
   hop, in the event that the currently selected primary
   interface next-hop fails,
   so that the alternate can be rapidly used when the failure is
   detected.

   To clarify the behavior of IP/LDP Local Protection, 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 interface link to router
   P E as its
   primary next-hop.  Without IP/LDP Local Protection, IP Fast-Reroute, that
   interface link is the only
   next-hop that router S computes to reach D.  With IP/LDP Local Protection, IP Fast-Reroute, S
   also looks for an alternate next-hop
   interface to use.  In this example, S
   would determine that it could send traffic destined to D by using the interface
   link to router N_1 and therefore S would install the interface link to N_1 as
   its alternate next-hop.  At some later time, the link between router
   S and router P E could fail.  When that link fails, S (and most likely P) and E will be the
   first to detect it.  On detecting the failure, S will stop sending
   traffic destined for D towards P E via the failed link, and instead
   send the traffic to S's pre-computed alternate next-hop, which is the
   interface
   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.  The alternate next-hop can protect against a single link or
   node failure.

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

2. Terminology

   SPT --- Shortest

   A neighbor N can provide a loop-free alternate if and only if

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

                      Equation 1: Loop-Free Criterion

   A sub-set of loop-free alternate are downstream paths which must meet
   the more restrictive condition of

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

                   Equation 2: Downstream Path Tree

   D --- The destination router under discussion.

   S --- Criterion

1.1 Failure Scenarios

   The source router under discussion. It alternate next-hop can protect against a single link failure, a
   single node failure, or both.

   If only link protection is provided and the viewpoint from
                which IP/LDP Local Protection is described.

   P --- The router which node fails, it is
   possible for traffic using the primary next-hop neighbor to get from S alternates to D. Where there loop. This issue is an ECMP set for
   illustrated in Figure 2.  If Link(S->E) fails, then the shortest path from link-
   protecting alternate via N will work correctly.  However, if router E
   fails, then both S
          to D, these and N will be referred detect a failure and switch to as P_1, P_2, etc.

   N_i --- The ith neighbor of their
   alternates.  In this example, that would cause S

   R_i_j --- The jth neighbor of N_i, the ith neighbor of S.

   Distance_!S(N_i, D) --- The distance of the shortest path from N_i to
          D which does not go through router S.

   Distance_opt(A, B) --- The distance of redirect the shortest path from A
   traffic to B.

   Reverse Distance of a node X --- This is N and N to redirect the Distance_opt(X, S).

   Loop-Free Alternate --- This is traffic to S and thus causing a next-hop that is not
   forwarding loop.  Such a primary
          next-hop whose shortest path to scenario can arise because the destination from key
   assumption, that all other routers in the
          alternate neighbor does not go back through network are forwarding
   based upon the router S.
          This is also known as a downstream path or a feasible
          alternate.

          Downstream Path --- This shortest path, is violated because of a loop-free alternate.

   Link(A->B) --- A second
   simultaneous correlated failure - another link connecting router A connected to router B.

   ____\   This is an arrow indicating the same
   primary next-hop towards D.
       /

   @@@@\   This neighbor.

   Such a scenario may be a concern if node failure is an arrow indicating the alternate next-hop towards D
       /

   Primary Neighbor --- One or more not otherwise
   protected against.  Selection of the primary next-hops for S to
        reach the destination D goes directly to only downstream paths as alternates
   will ensure this neighbor.

   Loop-Free Neighbor --- A Neighbor N_i which is does not occur, but such a restriction can severely
   limit the primary
        neighbor and whose shortest path to D does not go through S.

   Loop-Free Node-Protecting Alternate --- This is a path via a Loop-
        Free Neighbor N_i which does not go through the particular
        primary neighbor coverage of alternates.

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

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

   It may be desirable to find an alternate which can protect against
   other correlated failures (of which node failure is being protected 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 reach the
        destination D.

   Loop-Free Link-Protecting Alternate --- This is
   SRLG.  General SRLGs may add unacceptably to the computational
   complexity of finding a path via loop-free alternate.

   However, a Loop-
        Free Neighbor N_i which does go through the particular primary
        neighbor sub-category of S which SRLGs is being protected to reach of interest and can be applied
   only during the destination
        D.

   Upstream Forwarding Loop --- selection of an acceptable alternate.  This sub-
   category is a forwarding loop which involves
        a set of routers, none to express correlated failures of links which are directly
   connected to the
        link which has caused the topology change that triggered a new
        SPF in any of the routers.

3. Finding an Alternate

   As with primary next-hops, an alternate next-hop is discussed in
   relation to a particular destination router D. same router.  For this discussion, example, if there are multiple
   logical sub-interfaces on the following terminology, same physical interface, such as described earlier and  illustrated in
   Figure 2, will be used.

   In IP routing, a router S can join VLANs
   on an Ethernet interface, if multiple interfaces use the shortest path tree (SPT) at
   exactly one point -- itself. 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 which
   does not use a link in the same local-SRLG as the primary next-hop.
   The local-SRLGs belonging to E can be protected against via node-
   protection; i.e. picking a loop-free node-protecting alternate.

2. Alternate Next-Hop Calculation

   To support IP Fast-Reroute, a router must be able to determine if a
   next-hop will provide a loop-free alternate before the router
   installs that next-hop allows
   traffic as an alternate.  That next-hop must go to a
   loop-free neighbor.

   To do this computation, a router could run an SPF from S the
   perspective of each of its neighbors as well as from its own
   perspective.  This provides the router with all the information
   necessary to D test the equations given is this specification.

2.1 Basic Loop-free Condition

   Alternate next hops used by implementations following this
   specification MUST conform to deviate from at least the SPT loop-freeness condition
   stated above in Equation 1.  Further conditions may be applied when
   determining link-protecting and/or node-protecting alternate next-
   hops as described in Sections 2.2 and then rejoin it. 2.3.

2.2 Node-Protecting Alternate Next-Hops

   For
   instance, if S were to send traffic destined for D an alternate next-hop to N_1 instead of
   P, thereby deviating from protect against node failure, the SPT, then when N_1 received it, N_1
   would send that traffic along its shortest path
   alternate next-hop MUST be loop-free with respect to D.

                                           +-----+
                          \          /    _| R_2 |
               +-----+__    \|     |/    / +-----+
               | N_3 |  \   -+     +- __/       \
               +-----+   \____       /           \
                \             \     /             \
                 \             +-----+             \
                  \           _| N_2 |              \
                   |       __/ +-----+               \
                    \     /         \                 |
                     \   /     /     \_               | the primary
   neighbor E and the destination.

   An alternate will be node-protecting if it doesn't go through the
   same primary neighbor as the primary next-hop.  This is the case if
   Equation 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)

      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
   possible that the neighbor may have equal-cost paths and one of those
   could provide a loop-free node-protecting alternate.  However, the
   decision as to which of equal-cost paths a router will use is a
   router-local decision.  Therefore, a router MUST assume that an
   alternate next-hop does not offer node protection if Equation 3 is
   not met.

2.3 Broadcast and NBMA Links

   The computation for link-protection is a bit more complicated for
   broadcast links.  In an SPF computation, a broadcast links is
   represented as a pseudo-node with links of 0 cost exiting the
   pseudo-node.  For an alternate to be considered link-protecting, it
   must be loop-free with regard to the pseudo-node.  Consider the
   example in Figure 3.

                         +-----+   |/        \              |    15
                         |  S  |   +-         \  |-------
                         +-----+      |
                   +-----+               \_| R_1
                            | 5       |
               /    /   \
                          /----\ 5 +-----+
                          |
             |/    /     \                  /         |
             +-   /       \                / PN |----|  N  |
                 /
                          \----/   +-----+          /   /       |
         +-----+/
                             | N_1          |         /  |/
                             | 5        |  P 2
                             |         +-----+        /   +-          |
                          +-----+            \          /             /
            \             \  \__      /             /
         \   \             \|   \    /             /
          \|  \            -+ 5  +-----+          /
          -+   \_________________|
                          |  E  |----|  D  |---------/  |
                          +-----+    +-----+
         Figure 2:  Topology for Terminology

3.1. 3: Loop-Free Alternates

   With Alternate that isn't Link-Protecting

   In Figure 3, N offers a loop-free alternates, the goal is to expand the set of points at alternate which S can cause its traffic to join the SPT.  To illustrate this
   let's first consider S's neighbors.  Router S has is link-protecting.
   If the ability primary next-hop uses a broadcast link, then an alternate must
   be loop-free with respect to send
   traffic that link's pseudo-node to any one of its neighbors N_i; this provide link
   protection.  This requirement is described in Equation 4 below.

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

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

   Because the easiest possible
   deviation shortest path from the SPT that 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 cause to happen.  Thus, all of
   router S's neighbors are candidate alternates at which only
   reach the neighbor N via the same pseudo-node.  This can occur
   because S could cause will direct traffic to rejoin away from the SPT.  However, shortest path to use an
   alternate.

2.4 Interactions with ISIS Overload, RFC 3137 and Costed Out Links

   As described in RFC 3137, there are cases where it is desirable not useful for router S
   to
   use a next-hop which results in traffic rejoining the SPT upstream of
   S, such that the traffic will transit S again.  This would cause have a
   loop.  Avoiding router used as a loop transit node.  For those cases, it is thus also
   desirable not to have the first constraint imposed router used on the
   alternate next-hop.  In Figure 2, S's neighbors N_2 and N_3 are not
   loop-free an alternate neighbors.

   A next-hop which goes to path.

   For computing an alternate, a neighbor that does router MUST not have a loop back to
   S and consider diverting from
   the SPF tree along a link whose reverse cost is not LSInfinity (for OSPF)
   or whose router has the primary next-hop may be selected as an alternate
   next-hop. overload bit set (for ISIS).

   In Figure 2, that is the case for S's neighbor N_1.  N_1
   is referred to as a loop-free alternate with respect to traffic
   flowing of OSPF, if all links from S to D  because there is no loop caused by forwarding
   traffic for D to N_1.

   An algorithm run on router S must be able to determine which
   neighbors provide loop-free alternates.  By running an SPF
   computation from S's perspective, router S can determine the distance
   from a neighbor N_i to
   have a reverse cost of LSInfinity, then router S MUST NOT consider
   using N_i as an alternate.

   Similarly in the destination D for case of ISIS, if N_i has the optimal path that
   does not go through S.  This is referred to overload bit set, then
   S MUST NOT consider using N_i as Distance_!S(N_i, D).
   If an alternate.

   This preserves the desired behavior of diverting traffic away from a neighbor N_i
   router which is a loop-free alternate, then following RFC 3137 and it must be cheaper
   (a lower metric) to get to the destination D without returning to S.
   This gives also preserves the following requirement, where Distance_opt(A, B) gives desired
   behavior when an operator sets the distance cost of the optimal path from A a link to B.

      Distance_!S(N_i, D) < Distance_opt(N_i, S) + Distance_opt(S, D)

              Equation 1: Criteria LSInfinity for a Loop-Free Alternate

   To check this equation, we can consider the other conditions where
   this
   maintenance which is not true.  Recall permitting traffic across that link unless
   there is no other path.

   If a link or router will take which is costed out was the shortest path only possible
   alternate to a destination that it can see.  Thus, if Distance_!S(N_i, D) >
   Distance_opt(N_i, S) + Distance_opt(S, D), then router N_i will,
   based on its own shortest path computations, determine to send protect traffic destined for D to S.  Similarly, if Distance_!S(N_i, D) =
   Distance_opt(N_i, S) + Distance_opt(S, D), then router N_i has equal
   cost paths to the destination D where one or more of those paths go
   through S.  In such a case where from a particular router N_i has an ECMP set S to
   reach the destination and one or more paths go through S, a
   particular destination, then the there will be no alternate provided for
   protection.

2.5 Selection Procedure

   A router N_i cannot provide supporting this specification SHOULD select a loop-free
   alternate because some traffic
   destined to D may be sent back next-hop for each primary next-hop used for a given prefix.
   A router MAY decide to S by N_i.

3.2. Selection of not use an Alternate

   The selection of available loop-free alternate
   next-hop.  A reason for such a decision might be that the loop-free
   alternate to use depends upon next-hop does not provide protection for the failure
   scenario for which the protection is intended.  As with other
   protection mechanisms, of interest.

   The selection should maximize the alternate selected will protect against
   only failure cases which can be
   protected against.

   The selection procedure depends on whether S has a single failure.  It primary
   neighbor or multiple primary neighbors.  A node S is possible defined to protect against have
   a single primary neighbor only if there are no equal cost paths that
   go through any other neighbor; i.e., a node
   failure, which appears as correlated link failures, by explicitly
   selecting S cannot be considered to
   have a loop-free alternate which single primary neighbor simply because S does not use that node.

3.2.1 Failure Scenarios

   The simplest case is to locate an support
   ECMP.

   If S has a single primary neighbor, then S SHOULD select a loop-free
   node-protecting alternate which protects against next-hop, if one is available.  If S has a
   choice between a
   link failure.

   A loop-free link-protecting node-protecting alternate may cause traffic looping in
   the event of
   and a node failure.  This issue loop-free node-protecting alternate which is illustrated not link-
   protecting, S SHOULD select a loop-free node-protecting alternate
   which is also link-protecting.  This can occur as explained in Figure 3.
   Section 2.3.  If Link(S->P) fails, then the link-protecting no loop-free node-protecting alternate via N will
   work correctly.  However, if router P fails, is available,
   then both S and N will
   detect MAY select a failure and switch to their alternates.  In this example,
   that would cause loop-free link-protecting alternate.

   If S to redirect has multiple primary neighbors, then S SHOULD select as a loop-
   free alternate either one of the traffic to N and N other primary next-hops or a loop-
   free node-protecting alternate.  S MAY select a loop-free link-
   protecting alternate.

   Each next-hop can be categorized as to redirect the
   traffic type of alternate it can
   provide to a particular destination D from router S and thus causing for a forwarding loop.  Such particular
   primary next-hop which goes to a scenario can
   arise because the key assumption, that all other routers in the
   network are forwarding based upon neighbor E.  A next-hop may provide
   one of the shortest path, is violated
   because following types of a second simultaneous correlated failure paths:

        Primary Path - another link
   connected to This is the same primary neighbor.

                                /
                            \   @@@
                          @@@   \
                   +-----+  /    +-----+
                   | next-hop.

        Loop-Free Node-Protecting Alternate - This next-hop satisfies
        Equations 1 and 3.  The path avoids S, S's primary neighbor E,
        and the link from S  |-------|  N  |
                   +-+---+   5   +-----+
                     |              |
                     | 5          5 |  |
                  |  |              | \|/
                 \|/ |              |
                     |    +-----+   |
                     +----|  P  |---+
                          +--+--+
                             |
                             |
                             | 10
                             |
                          +--+--+
                          |  D  |
                          +-----+
               Figure 3: to E.

        Loop-Free Link-Protecting Alternates Causing Loop on Node Failure

   Such Alternate - This next-hop satisfies
        Equation 1 but not Equation 3.  If the primary next-hop uses a scenario
        broadcast link, then this next-hop satisfies Equation 4.

        Unavailable - This may be a concern if node failure is not otherwise
   protected against.

   One way to solve such an issue is because the path goes through S to add a constraint that
        reach D, because the loop-
   free link is costed out, etc.

3. Using an Alternate

   If an alternate next-hop is loop-free with respect available, the router SHOULD redirect
   traffic to P and the destination.
   This gives a loop-free node-protecting alternate.  An alternate will
   be node-protecting if it doesn't go through the same primary neighbor
   as next-hop when the primary next-hop.  This is the case if Equation 2 is true,
   where N is the neighbor providing next-hop has
   failed.

   When a loop-free alternate.

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

   However unlike Equation 1, where if the equation did not hold, local interface failure is detected, traffic that was destined
   to go out the neighbor
   wasn't loop-free, if Equation 2 does not hold, failed interface must be redirected to the neighbor may still
   provide a loop-free appropriate
   alternate that is not node-protecting.  In next-hops.  Other failure detection mechanisms which detect
   the
   case loss of ECMP, the neighbor may even provide a node-protecting loop-
   free alternate, but S cannot determine this.

   It link or a node may also be desirable used to find an trigger redirection
   of traffic to the appropriate alternate which can protect
   against other correlated failures.  In the general case, these next-hops.  The mechanisms
   available for failure detection are
   handled by shared risk link groups (SRLGs) where any links discussed in [FRAMEWORK] and are
   outside the
   network can belong to the SRLG.  General SRLGs may add unacceptably scope of this specification.

   The alternate next-hop MUST be used only for traffic types which are
   routed according to the computational complexity of finding a loop-free alternate.

   However, a sub-category of SRLGs shortest path.  Multicast traffic is
   specifically out of interest and can be applied
   only during scope for this specification.

3.1 Terminating Use of Alternate

   A router MUST limit the selection amount of time an acceptable alternate.  This sub-
   category alternate next-hop is to express correlated failures of links which are
   connected to used
   after the same router.  For example, if there are multiple
   logical sub-interfaces on primary next-hop has become unavailable.  This ensures that
   the same physical interface, such as VLANs
   on an Ethernet interface, if multiple interfaces use router will start using the same
   physical port because of channelization, or if multiple interfaces
   share a correlated failure because they new primary next-hops.  It ensures
   that all possible transient conditions are on remvoed and the same line-card.
   This sub-category of SRLGs will be referred network
   converges according to as local-SRLGs.  A
   local-SRLG has all of its member links with one end connected the deployed routing protocol.

   It is desirable to avoid micro-forwarding loops involving S.  An
   example illustrating the
   same router.  Thus, router S could select a loop-free alternate which
   does not use a link problem is given in Figure 4.  If the same local-SRLG link
   from S to E fails, S will use N1 as an alternate and S will compute
   N2 as the new primary next-hop.
   The local-SRLGs belonging next-hop to P reach D.  If S starts using N2 as
   soon as S can be protected against via node-
   protection; i.e. picking a loop-free node-protecting alternate.

3.2.2 Broadcast and NBMA Interfaces

   The computation for node-protection compute and link-protection is a bit more
   complicated for broadcast interfaces.  In an SPF computation, a
   broadcast interface install its new primary, it is represented as a pseudo-node with links of 0
   cost exiting the pseudo-node.  For an alternate probable
   that N2 will not have yet installed its new primary next-hop.  This
   would cause traffic to loop and be considered
   link-protecting, it must avoid the pseudo-node.  Thus, a potential
   alternate which doesn't avoid dropped until N2 has installed the next node
   new topology.  This can be avoided by S delaying its installation and
   leaving traffic on the primary path
   cannot be used as alternate next-hop.

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

        Figure 4: 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 if before the next node on failure and therefore may have been forwarding
   traffic through S.  This will occur when the path is via a
   pseudo-node because previously
   upstream node is shorter than the potential alternate would use the link that
   may fail.  Additionally, an path via a loop-free alternate which would normally be termed
   node-protecting because
   neighbor.  In these cases, it avoided is useful to give sufficient time to
   ensure that the next node new primary neighbor and other nodes on the new
   primary path
   may be only link-protecting.  If have switched to the alternate avoids new route.

   If the pseudo-node
   but goes through the next node on the path (i.e. newly selected primary was loop-free before the real neighbor of
   S), failure, then the alternate
   it is link-protecting; if the alternate avoids
   not only the pseudo-node but the following node on safe to switch to that new primary immediately;  the new
   primary path,
   then wasn't dependent on the alternate is node-protecting.

3.2.3 Interactions with ISIS Overload, RFC 3137 failure and Costed Out Links

   As described in RFC 3137, there are cases where it is desirable therefore its path will
   not
   to have changed.

   Given that there is an alternate providing appropriate protection and
   while the assumption of a router used as a transit node.  For those cases, single failure holds, it is also
   desirable not safe to have delay
   the router used on an alternate path.

   For computing an alternate, a router MUST installation of the new primaries; this will not consider diverting from create
   forwarding loops because the SPF tree along a link whose reverse cost alternate's path to the destination is LSInfinity (for OSPF)
   known to not go via S or whose router has the overload bit set (for ISIS).

   In failed element and will therefore not be
   affected by the case 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 OSPF, the alternate next-
   hops for packet forwarding SHOULD terminate

      a) if all links from router S the new primary next-hop was loop-free prior to the topology
      change, or

      b) if a neighbor N_i
   have configured hold-down, which represents a reverse cost of LSInfinity, then router S cannot consider
   using N_i as an alternate.

   Similarly in worst-case bound
      on the case length of ISIS, if N_i the network convergence transition, has expired,
      or

      c) if notification of an unrelated topological change in the overload bit set, then
   S cannot consider using N_i as an alternate.

   This preserves the desired behavior of diverting traffic away from a
   router which
      network is following RFC 3137 and received.

4. Requirements on LDP Mode

   Since LDP traffic will follow the path specified by the IGP, it is
   also preserves possible for the desired
   behavior when an operator sets LDP traffic to follow the cost of a link loop-free alternates
   indicated by the IGP.  To do so, it is necessary for LDP to LSInfinity have the
   appropriate labels available for
   maintenance, of not permitting traffic across that link unless there
   is no other path.

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

3.2.4 Characterization of Neighbors

   Each neighbor N_i so that the
   appropriate out-segments can be categorized as to installed in the type of path forwarding plane
   before the failure occurs.

   This means that a Label Switched Router (LSR) running LDP must
   distribute its labels for the FECs it can provide to a particular destination D.  Once 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 which correspond to neighbors that aren't currently
   the primary paths paths
   have been determined and removed from consideration, each neighbor
   can are stored.  Similarly, LDP should be characterized as providing a path in one of
   downstream unsolicited mode, so that the following
   categories for a particular destination D.  It is possible labels for a
   neighbor to provide both the primary path and a loop-free link-
   protecting alternate.  The path through the neighbor N_i is either a:

        Loop-Free Node-Protecting Alternate - not a primary path and FEC are
   distributed other than along the
        path avoids both S, one of S's primary neighbors on SPT.

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

5. Routing Aspects
   An SPF-like computation is run for each topology, which corresponds
   to
        D and a particular OSPF area or ISIS level.  The IGP needs to determine
   the interface connecting S inheritance of loop-free alternates, as determined for singly
   advertised routes, to that primary neighbor.

        Loop-Free Link-Protecting Alternate - not a primary path multiply advertised routes, for protocols such
   as BGP and the
        path avoids S LDP and an interface connecting S for inter-area or inter-level routes.  These
   alternates are provided to one LDP and BGP for forwarding purposes only;
   the alternates are not redistributed in any fashion into other
   protocols.

   The alternate next-hop inheritance is described in the context of S's
        primary neighbors,
   inter-area routes, but goes through that primary neighbor on the
        path applies equally well to D.  Note that some neighbors of this type may have ECMP
        paths BGP routes and to reach the destination, where some of those paths
   routes which are
        independent of advertised by multiple routers in the IGP area.

5.1 Multiple-Region Routing

   Routes in different regions inherit their primary neighbor.

        Unavailable - because next-hops from the path goes through S to reach D,
        because
   border routers (area border routers (ABRs) or level boundary routers)
   which offer the interface shortest path to reach the neighbor is costed out, etc.

3.2.5 Selection Procedure

   Once destination(s) announcing the neighbors have been categorized, a selection can be made.
   The selection should maximize
   route.  Similarly, routes must inherit their alternate next-hop and
   will do so from the failure cases which can be
   protected against. same border routers.  The selection procedure depends on whether S has a single primary
   neighbor or multiple primary neighbors.  A node S is defined shortest path to have
   a single primary neighbor only if there are no equal cost paths that
   go through any other neighbor; i.e., a node S cannot an
   inter-region route may be considered to
   have a single primary neighbor just because S does not support ECMP.

   If S has learned from a single primary neighbor, then S SHOULD select a loop-free
   node-protecting alternate, if one is available.  If none is
   available, then S MAY select a loop-free link-protecting alternate.

   If S has multiple primary neighbors, then S should select an
   alternate to protect against the failure of each of border router.  In
   that case, both the primary
   next-hops.  The loop-free alternate selected should be either one of and the other primary next-hops or should provide node-protection.

4. Using an Alternate

   If an alternate next-hops can be
   inherited from that border router.  Figure 5 illustrates this case
   where D is available, it is used to redirect traffic when reached via ABR1; the primary next-hop has failed.

   When a local interface failure for ABR1 is detected, traffic that was destined
   to go out the failed interface must be redirected to E and
   the appropriate
   alternate next-hops.  The loop-free node-protecting alternate next-hop is pre-computed to be
   the most appropriate as mentioned in the selection criteria in the
   event of the failure scenario being protected against (i.e. link or
   node failure).

   IP/LDP Local Protection does not require any mechanisms for the
   detection of the failure. A1.

                            .............
                      ......             ......
                   ...                         ...
                 ..                               ..
               ..   10  +-----+    5    +-----+  5  ..
              .  +------| A1  +---------| R1  |-----+ .
            ..   |      +-----+         +-----+     | .
            .    |                                +-----+  10
           .     |                 +--------------| ABR1|---------+
           .     |                 |      5       +-----+         |
          .  +-----+     5     +---+-+                .           |
          .  |  S  |-----------|  E  |------------+   .         +-----+
           . +-----+           +-----+   10       |   .         |  D  |
           .     |                                |   .         +-----+
            .    |                                |  .             |
            ..   |     +-----+                  +-----+  20        |
              .  +-----| A2  |------------------| ABR2|------------+
               .   10  +-----+    5             +-----+
                ...                               ...
                   ...                         ...
                      .........................

            Figure 5: Inter-Region Destination via One Border Router

   The same mechanisms that enable RSVP-TE
   Fast-Reroute can work here.  Because the alternate next-hop is pre-
   computed, it should be extremely fast to switch traffic shortest path to use it,
   exactly an inter-region route may be learned from
   multiple border routers with at least 2 different primary neighbors,
   as is the case with RSVP-TE Fast-Reroute.

5. Requirements on LDP Mode

   Since LDP traffic will follow the path specified by the IGP, it illustrated in Figure 6.  D is
   also possible for the LDP traffic reached via ABR1 and ABR2 with
   equal cost from S.  The primary neighbor to follow the loop-free alternates
   indicated by reach ABR1 is E1 and the IGP.  To do so, it
   alternate is necessary for LDP A1.  The primary neighbor to have the
   appropriate labels available for reach ABR2 is E2 and the
   alternate so that the
   appropriate out-segments is A2.  In this case, there are equal-cost primary next-
   hops to reach D and they can protect each other.  In this example,
   the primary next-hops would be installed in to E1 and E2; if the forwarding plane
   before the failure occurs.

   This means that a Label Switched Router (LSR) running LDP must
   distribute its labels for link to E2
   failed, then E1 could be used as an alternate and vice-versa.  Thus
   the FECs it alternates can provide be obtained from the primary next-hops.

                            ..........
                      ......          ......
                   ...                      ...
                 ..                            ..
               ..   10  +-----+    5    +-----+  ..
              .  +------| A1  +---------| R1  |-----+
            ..   |      +-----+         +-----+     |.
            .    |             +-----+            +-----+  10
           .     | +-----------| E1  |------------| ABR1|---------+
           .     | |       5   +-----+    5       +-----+         |
          .  +-----+                                   .          |
          .  |  S  |---+  5    +-----+   10            .        +-----+
           . +-----+   +-------| E2  |------------+   .         |  D  |
           .     |             +-----+            |   .         +-----+
            .    |                                |  .             |
            ..   |     +-----+                  +-----+  20        |
              .  +-----| A2  |------------------| ABR2|------------+
               .   10  +-----+    5             +-----+
                ...                            ...
                   ...                      ...
                      ......          ......
                            ..........

                    Figure 6: Inter-Region Destination via
             Multiple Border Routers and Multiple Primary Neighbors

        In the third case, the shortest path to all its
   neighbors, regardless of whether or not they are upstream.
   Additionally, LDP must an inter-region route
        may be acting learned from multiple border routers but with a single
        primary neighbor.  This is shown in liberal label retention mode so
   that Figure 7, where D can be
        equally reached from S via ABR1 and ABR2.  The alternate next-
        hop to reach ABR1 is A1 while the labels which correspond alternate to interfaces that aren't currently reach ABR2 is A2.
        It is necessary to select one of the primary next-hop are stored.  Similarly, LDP should alternates to 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 inherited.

                            .............
                      ......             ......
                   ...                         ...
                 ..                               ..
               ..    5  +-----+   15    +-----+ 20  ..
              .  +------| A1  +---------| R1  |-----+ .
            ..   |      +-----+         +-----+     | .
            .    |                                +-----+  10
           .     |                 +--------------| ABR1|---------+
           .     |                 |      15      +-----+         |
          .  +-----+     5     +---+-+                .           |
          .  |  S  |-----------|  E  |------------+   .         +-----+
           . +-----+           +-----+    5       |   .         |  D  |
           .     |                                |   .         +-----+
            .    |                                |  .             |
            ..   |     +-----+                  +-----+  20        |
              .  +-----| A2  |------------------| ABR2|------------+
               .   10  +-----+   15             +-----+
                ...                               ...
                   ...                         ...
                      ......             ......
                            .............

                    Figure 7: Inter-Region Destination via
               Multiple Border Routers but One Primary Neighbor

5.1.1 Inheriting Alternate Next-Hops with One Primary Neighbor

   The main question when deciding whether an alternate can use the loop-free
   alternates without requiring any targeted sessions or signaling
   extensions for this purpose.

6. Routing Aspects

   An SPF-like computation be inherited
   is run for each topology, which corresponds
   to a particular OSPF area whether or ISIS level.  The IGP needs not that alternate will continue to determine provide the inheritance of loop-free alternates, as determined for singly
   advertised routes,
   necessary protection.  I.e., will the alternate continue to multiply advertised routes, for protocols such be usable
   as BGP and LDP an alternate and for inter-area provide the same link or inter-level routes.  These
   alternates are node protection with
   respect to the destination that was provided with respect to LDP and BGP for forwarding purposes only; the alternates are not redistributed in any fashion
   border router.  It can be proved that the alternate will be usable as
   an alternate and provide at least the same link or node protection
   that was provided with respect to the border router.  The alternate
   next-hop inheritance procedure SHOULD select a loop-free node-
   protecting alternate, if one is available.

5.1.2 OSPF Inter-Area Routes

   In OSPF, each area's links are summarized into a summary LSA, which
   is announced into an area by an Area Border Router.  ABRs announce
   summary LSAs into the backbone area and inject summary LSAs of the
   backbone area into other
   protocols. non-backbone areas.  A route can be learned
   via summary LSA from one or more ABRs; such a route will be referred
   to as a summary route.

   The alternate next-hop inheritance for summary routes is as described
   in the context Section 5.1.1

5.1.3 OSPF External Routing

   Rules of inheritance of alternate next-hops for external routes is
   the same as for inter-area routes, but applies equally well destinations.  The additional complication
   comes from forwarding addresses, where an ASBR uses a forwarding
   address to BGP routes and indicate to
   routes which are advertised by multiple all routers in the IGP area.

6.1 Multiple-Region Routing

   Routes in different regions inherit their primary next-hops from Autonomous System to use
   the
   border routers (area border specified address instead of going through the ASBR.  When a
   forwarding address has been indicated, all routers (ABRs) or level boundary routers)
   which offer in the topology
   calculate the shortest path to the destination(s) announcing link specified in the external
   LSA.  In this case, the
   route.  Similarly, routes must inherit their alternate next-hop and
   will do so from of the same border routers.  The shortest path to an
   inter-region route may be learned from a single border router.  In
   that case, both the primary and the alternate next-hops can forwarding link
   should be
   inherited from that border router.  Figure 4 illustrates this case
   where D is reached via ABR1; used, in conjunction with the primary next-hop of the
   forwarding link, instead of those associated with the ASBR.

5.1.4 ISIS Multi-Level Routing

   ISIS maintains separate databases for ABR1 each level with which it is P
   dealing.  Nodes in one level do not have any information about state
   of nodes and edges of the loop-free node-protecting alternate is A1.

   The shortest path other level. ISIS level boundary points ,
   also known as ISIS level boundary routers, are attached to an inter-region route may be learned from
   multiple border both
   levels.  ISIS level boundary routers with at least 2 different primary neighbors,
   as is illustrated summarize the destinations in Figure 5.  D
   each, level. ISIS inter-level route computation is reached via ABR1 and ABR2 with
   equal cost from S.  The primary neighbor very similar to reach ABR1 is P1 and the
   OSPF inter area routing.  Rules for alternate next-hop inheritance is A1.  The primary neighbor to reach ABR2 is P2 and
   the
   alternate is A2.  In this case, there same as described in Section 5.1.1

5.2 OSPF Virtual Links

   OSPF virtual links are equal-cost primary next-
   hops to reach D and they can protect each other.  In this example,
   the primary next-hops would be used to P1 and P2; if the connect two disjoint backbone areas
   using a transit area.  A virtual link to P2
   failed, then P1 could be used as an alternate and vice-versa.  Thus is configured at the alternates can be obtained from border
   routers of the primary next-hops.

                            .............
                      ......             ......
                   ...                         ...
                 ..                               ..
               ..   10  +-----+    5    +-----+  5  ..
              .  +------| A1  +---------| R1  |-----+ .
            ..   |      +-----+         +-----+     | .
            .    |                                +-----+  10
           .     |                 +--------------| ABR1|---------+
           .     |                 |      5       +-----+         |
          .  +-----+     5     +---+-+                .           |
          .  |  S  |-----------|  P  |------------+   .         +-----+
           . +-----+           +-----+   10       |   .         |  D  |
           .     |                                |   .         +-----+
            .    |                                |  .             |
            ..   |     +-----+                  +-----+  20        |
              .  +-----| A2  |------------------| ABR2|------------+
               .   10  +-----+    5             +-----+
                ...                               ...
                   ...                         ...
                      ......             ......
                            .............

            Figure 4: Inter-Region Destination via One Border Router

                            ..........
                      ......          ......
                   ...                      ...
                 ..                            ..
               ..   10  +-----+    5    +-----+  ..
              .  +------| A1  +---------| R1  |-----+
            ..   |      +-----+         +-----+     |.
            .    |             +-----+            +-----+  10
           .     | +-----------| P1  |------------| ABR1|---------+
           .     | |       5   +-----+    5       +-----+         |
          .  +-----+                                   .          |
          .  |  S  |---+  5    +-----+   10            .        +-----+
           . +-----+   +-------| P2  |------------+   .         |  D  |
           .     |             +-----+            |   .         +-----+
            .    |                                |  .             |
            ..   |     +-----+                  +-----+  20        |
              .  +-----| A2  |------------------| ABR2|------------+
               .   10  +-----+    5             +-----+
                ...                            ...
                   ...                      ...
                      ......          ......
                            ..........

                    Figure 5: Inter-Region Destination via
             Multiple Border Routers and Multiple Primary Neighbors

        In the third case, the shortest path to an inter-region route
        may be learned from multiple border routers but with a single
        primary neighbor.  This is shown in Figure 6, where D can be
        equally reached from S via ABR1 and ABR2.  The alternate next-
        hop to reach ABR1 is A1 while the alternate to reach ABR2 is A2.
        It is necessary to select one of the alternates to be inherited.

                            .............
                      ......             ......
                   ...                         ...
                 ..                               ..
               ..    5  +-----+   15    +-----+ 20  ..
              .  +------| A1  +---------| R1  |-----+ .
            ..   |      +-----+         +-----+     | .
            .    |                                +-----+  10
           .     |                 +--------------| ABR1|---------+
           .     |                 |      15      +-----+         |
          .  +-----+     5     +---+-+                .           |
          .  |  S  |-----------|  P  |------------+   .         +-----+
           . +-----+           +-----+    5       |   .         |  D  |
           .     |                                |   .         +-----+
            .    |                                |  .             |
            ..   |     +-----+                  +-----+  20        |
              .  +-----| A2  |------------------| ABR2|------------+
               .   10  +-----+   15             +-----+
                ...                               ...
                   ...                         ...
                      ......             ......
                            .............

                    Figure 6: Inter-Region Destination via
               Multiple Border Routers but One Primary Neighbor

6.1.1 Inheriting Alternate Next-Hops with One Primary Neighbor

   The main question when deciding whether an alternate can be inherited
   is whether or not that alternate will continue to provide the
   necessary protection.  I.e., will the alternate continue to be usable
   as an alternate and provide the same link or node protection with
   respect to the destination that was provided with respect to the
   border router.  The relationships shown in Figure 6 will be used for
   illustrative purposes, although the topology connecting them may be
   more general than that shown.  The proofs and explanations are
   provided in Appendix A, but the answer is that the alternate will be
   usable as an alternate and provide at least the same link or node
   protection that was provided with respect to the border router.  The
   alternate next-hop inheritance procedure SHOULD select a loop-free
   node-protecting alternate, if one is available.

6.1.2 OSPF Inter-Area Routes

   In OSPF, each area's links are summarized into a summary LSA, which
   is announced into an area by an Area Border Router.  ABRs announce
   summary LSAs into the backbone area and inject summary LSAs of the
   backbone area into other non-backbone areas.  A route can be learned
   via summary LSA from one or more ABRs; such a route will be referred
   to as a summary route.

   The alternate next-hop inheritance for summary routes is as described
   in Section 6.1.1

6.1.3 OSPF External Routing

   Rules of inheritance of alternate next-hops for external routes is
   the same as for inter-area destinations.  The additional complication
   comes from forwarding addresses, where an ASBR uses a forwarding
   address to indicate to all routers in the Autonomous System to use
   the specified address instead of going through the ASBR.  When a
   forwarding address has been indicated, all routers in the topology
   calculate the shortest path to the link specified in the external
   LSA.  In this case, the alternate next-hop of the forwarding link
   should be used, in conjunction with the primary next-hop of the
   forwarding link, instead of those associated with the ASBR.

6.1.4 ISIS Multi-Level Routing

   ISIS maintains separate databases for each level with which it is
   dealing.  Nodes in one level do not have any information about state
   of nodes and edges of the other level. ISIS level boundary points ,
   also known as ISIS level boundary routers, are attached to both
   levels.  ISIS level boundary routers summarize the destinations in
   each, level. ISIS inter-level route computation is very similar to
   OSPF inter area routing.  Rules for alternate next-hop inheritance is
   the same as described in Section 6.1.1

6.2 OSPF Virtual Links

   OSPF virtual links are used to connect two disjoint backbone areas
   using a transit area.  A virtual link is configured at the border
   routers of the disjoint area.  There are two scenarios, depending
   upon the position of the root, router S.

   If router S is itself an ABR or one of the endpoints of the disjoint
   area, then router S must resolve its paths to the destination on the
   other side of the disjoint area by using the summary links in the
   transit area and using the closest ABR summarizing them into the
   transit area.  This means that the data path may diverge from the
   virtual neighbor's control path.  An ABR's primary and alternate
   next-hops are calculated by RAPID on the transit area.

   The primary next-hops to use are determined based upon the closest
   set of equidistant ABRs; the same rules described in Section 6.1.1
   for inter-area destinations must be followed for OSPF virtual links
   to determine the alternate next-hop.  The same ECMP cases apply.

   If router S is not an ABR, then all the destinations on the other
   side of the disjoint area will inherit the virtual link's endpoint,
   the transit ABR.  The same OSPF inter-area rules described in Section
   6.1.1 must be followed here as well.

   A virtual link cannot be used as an alternate next-hop.

6.3 BGP Next-Hop Synchronization

   Typically BGP prefixes are advertised with AS exit routers router-id,
   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/LDP Local Protection
   computes the alternate next-hops to the all the IGP destinations,
   which includes 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 continue to use the IGP optimal
   distance to find the nearest exit router.  MBGP routes do not need to
   copy the alternate next hops.

6.4 Multicast Considerations

   IP/LDP Local Protection does not apply to multicast traffic.  The
   alternate next-hops SHOULD not used for multi-cast RPF checks.

7. Security Considerations

   This document does not introduce any new security issues. The
   mechanisms described in this document depend upon the network
   topology distributed via an IGP, such as OSPF or ISIS.  It is
   dependent upon the security associated with those protocols.

8.  Full Copyright Statement

   Copyright (C) The Internet Society (2004). All Rights Reserved.

   This document and translations of it may be copied and furnished to
   others, and derivative works that comment on or otherwise explain it
   or assist in its implementation may be prepared, copied, published
   and distributed, in whole or in part, without restriction of any
   kind, provided that the above copyright notice and this paragraph are
   included on all such copies and derivative works.  However, this
   document itself may not be modified in any way, such as by removing
   the copyright notice or references to the Internet Society or other
   Internet organizations, except as needed for the  purpose of
   developing Internet standards in which case the procedures for
   copyrights defined in the Internet Standards process must be
   followed, or as required to translate it into languages other than
   English.

   The limited permissions granted above are perpetual and will not be
   revoked by the Internet Society or its successors or assigns.

   This document and the information contained herein is provided on an
   "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
   TASK FORCE DISCLAIMS 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.

9. References

   [FRAMEWORK] M. Shand, "IP Fast Reroute Framework", draft-ietf-rtgwg-
   ipfrr-framework-01.txt, June 2004

   [LDP] L. Anderson, P. Doolan, N. Feldman, A. Fredette, B. Thomas,
   "LDP Specification", RFC 3036, January 2001

   [RSVP-TE] D. Awduche, L. Berger, D. Gan, T. Li, V Srinivasan, G.
   Swallow, "RSVP-TE: Extensions to RSVP for LSP Tunnels", RFC 3209,
   December 2001

   [RSVP-TE FRR] P. Pan, D. Gan, G. Swallow, JP Vasseur, D. Cooper, A.
   Atlas, and M. Jork, "Fast Reroute Extensions to RSVP-TE for LSP
   Tunnels", work-in-progress draft-ietf-mpls-rsvp-lsp-fastreroute-
   06.txt, June 2004

   [RFC3137]  Retana, A., Nguyen, L., White, R., Zinin, A., and
   McPherson, D., "OSPF Stub Router Advertisement", RFC 3137, June 2001
   [RFC3277] D. McPherson, "Intermediate System to Intermediate System
   (IS-IS) Transient Blackhole Avoidance", RFC 3277, April 2002

   [ISIS] R. Callon, "Use of OSI IS-IS for Routing in TCP/IP and Dual
   Environments", RFC 1195, December 1990

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

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

   [RFC2370] R. Coltun, "The OSPF Opaque LSA Option", RFC 2370, July
   1998

10. Authors Information

   Raveendra Torvi
   Avici Systems
   101 Billerica Avenue
   N. Billerica, MA 01862
   USA
   email: rtorvi@avici.com
   phone: +1 978 964 2026

   Gagan Choudhury
   AT&T
   Room D5-3C21
   200 Laurel Avenue
   Middletown, NJ 07748
   USA
   email: gchoudhury@att.com
   phone: +1 732 420-3721

   Christian Martin
   Verizon
   1880 Campus Commons Drive
   Reston, VA 20191
   email: cmartin@verizon.com

   Brent Imhoff
   WilTel Communications
   3180 Rider Trail South
   Bridgeton, MO 63045
   USA
   email: brent.imhoff@wcg.com
   phone: +1 314 595 6853

   Don Fedyk
   Nortel Networks
   600 Technology Park
   Billerica, MA 01821
   email: dwfedyk@nortelnetworks.com
   phone: +1 978 288 3041

11. Editor's Information

   Alia Atlas
   Avici Systems
   101 Billerica Avenue
   N. Billerica, MA 01862
   USA
   email: aatlas@avici.com
   phone: +1 978 964 2070

Appendix A: Loop-Free Alternate Proofs

   Consider where A2 is a loop-free alternate with respect to S and ABR2.  Will A2
   be a loop-free alternate with respect to S and D?  Let there be three ABRs which
   must be considered.  Each ABR can represent a group of ABRs with the same
   characteristics.

                            .............
                      ......             ......
                   ...                         ...
                 ..                               ..
               ..    5  +-----+   15    +-----+ 20  ..
              .  +------| A1  +---------| R1  |-----+ .
            ..   |      +-----+         +-----+     | .
            .    |                                +-----+  10
           .     |                 +--------------| ABR1|---------+
           .     |                 |      15      +-----+         |
          .  +-----+     5     +---+-+                .           |
          .  |  S  |-----------|  P  |------------+   .         +-----+
           . +-----+           +-----+    5       |   .         |  D  |
           .     |                                |   .         +-----+
            .    |                                |  .             | |
            ..   |     +-----+                  +-----+  20        | |
              .  +-----| A2  |------------------| ABR2|------------+ |
               .   10  +-----+    15            +-----+              |
                ...       |                       ...                |
                   ...    +---------------+    ...                   |
                      ......    10     +--+--+.          20          |
                            ...........| ABRt|-----------------------+
                                       +-----+
                    Figure 7: Inter-Region Destination via
               Multiple Border Routers but One Primary Neighbor

        ABR1 is from the set of ABRs where D_opt(A2, ABR1) = D_opt(A2,
        S) + D_opt(S, ABR1). In other words, A2 is not loop-free with
        regards to S and ABR1.  Additionally, D_opt(S, D) = D_opt(S,
        ABR1) + D_opt(ABR1, D) so ABR1 is on a shortest path from S to
        D.

        ABR2 is from disjoint area.  There are two scenarios, depending
   upon the set of ABRs where D_opt(A2, ABR2) < D_opt(A2,
        S) + D_opt(S, ABR2). In other words, A2 is loop-free with
        regards to S and ABR2.  Additionally, D_opt(S, D) = D_opt(S,
        ABR2) + D_opt(ABR2, D) so ABR2 is on a shortest path from S to
        D.

        ABRt is from a set position of ABRs where D_opt(S, D) < D_opt(S, ABRt) +
        D_opt(ABRt, D).  In other words, ABRt is not on a shortest path
        from S to D.

        First, we will prove that D_opt(A2, D) < D_opt(A2, ABR1) +
        D_opt(ABR1, D).  In other words, the shortest path from A2 to D
        does not go through ABR1.

        The shortest path from A2 to D via ABR1 also goes via S. A
        shortest path from S to D goes via ABR1.
                  Step i: D_opt(A2, ABR1) + D_opt(ABR1, D) =
                 D_opt(A2, S) + D_opt(S, ABR1) + D_opt(ABR1, D)

        The shortest path from A2 to D via ABR2 does not go through root, router S.
        ABR2 is on a shortest path from S to D.
                  Step ii: D_opt(A2, ABR2) + D_opt(ABR2, D) <
                D_opt(A2, S) + D_opt(S, ABR2) + D_opt(ABR2, D)

        From previous and given that ABR1 and ABR2 provide equal-cost
        paths from S to D:
                 Step iii: D_opt(A2, ABR2) + D_opt(ABR2, D) <
                D_opt(A2, S) + D_opt(S, ABR1) + D_opt(ABR1, D)

        From previous and Step i:
                  Step iv: D_opt(A2, ABR2) + D_opt(ABR2, D) <
                        D_opt(A2, ABR1) + D_opt(ABR1, D)

          Step v: D_opt(A2, D) <= D_opt(A2, ABR2) + D_opt(ABR2, D) <
                       D_opt(A2, ABR1) + D_opt(ABR1, D)
        Thus, the optimal path from A2 to D cannot go through ABR1.

   Next, we will prove that if D_opt(A2, D) = D_opt(A2, ABRt) +
   D_opt(ABRt, D), then A2 is still loop-free with respect to

   If router S and D.
   In other words, even if A2's shortest path to D goes through is itself an ABRt
   which isn't on a shortest path from ABR or one of the endpoints of the disjoint
   area, then router S must resolve its paths to D, the path from A2 to D is
   still loop-free with respect to S destination on the
   other side of the disjoint area by using the summary links in the
   transit area and D. using the closest ABR summarizing them into the
   transit area.  This is proved via
   contradiction.

        Assume means that D_opt(A2, D) goes through ABRt.

                  Step i: D_opt(A2, ABRt) + D_opt(ABRt, D) <=
                        D_opt(A2, ABR2) + D_opt(ABR2, D)

        Because A2 is loop-free with respect to S and ABR2
                  Step ii: D_opt(A2, ABR2) + D_opt(ABR2, D) <
                 D_opt(A2, S) + D_opt(S, ABR2) + D_opt(ABR2, D)

        Because ABR2 is on a shortest the data path may diverge from S to D the
   virtual neighbor's control path.  An ABR's primary and ABRt is not
                  Step iii: D_opt(S, ABR2) + D_opt(ABR2,D) <
                        D_opt(S, ABRt) + D_opt(ABRt, D)

        From previous alternate
   next-hops are calculated by adding Dopt(A2, S) to both sides
           Step iv: D_opt(A2, S) + D_opt(S, ABR2) + D_opt(ABR2,D) <
                 D_opt(A2, S) + D_opt(S, ABRt) + D_opt(ABRt, D)

        From Steps i and ii:
                  Step v: D_opt(A2, ABRt) + D_opt(ABRt, D) <
                 D_opt(A2, S) + D_opt(S, ABR2) + D_opt(ABR2, D)

        From Steps iv and v:
                  Step vi: D_opt(A2, ABRt) + D_opt(ABRt, D) <
                 D_opt(A2, S) + D_opt(S, ABRt) + D_opt(ABRt, D)

        Therefore, if D_opt(A2, D) is via ABRt, it does not go through
        S.

   These two proofs show that if A2 is loop-free with respect to S and
   ABR2, then A2 is loop-free with respect on the transit area.

   The primary next-hops to S and D.

Appendix A.1 Loop-Free Node-Protecting Alternate Proofs

   It use are determined based upon the closest
   set of equidistant ABRs; the same rules described in Section 5.1.1
   for inter-area destinations must also be shown that if A2 is loop-free and node-protecting
   with respect to S and ABR2, then A2 will still be node-protecting
   with respect followed for OSPF virtual links
   to determine the alternate next-hop.  The same ECMP cases apply.

   If router S and D.  In is not an ABR, then all the destinations on the other words, that A2
   side of the disjoint area will inherit the virtual link's endpoint,
   the transit ABR.  The same OSPF inter-area rules described in Section
   5.1.1 must be loop-free
   with respect to P and D.

   This is shown where D_opt(S, D) = D_opt(S, P) + D_opt(P, D), so that
   D_opt(P, ABR1) + D_opt(ABR1, D) = D_opt(P, ABR2) + D_opt(ABR2, D).

   First, it has already been proven that followed here as well.

   A virtual link cannot be used as an ABR offering equal-cost
   from S to D which is also loop-free alternate next-hop.

5.3 BGP Next-Hop Synchronization

   Typically BGP prefixes are advertised with respect to S AS exit routers router-id,
   and D will be
   selected AS exit routers are reached by A2 over an ABR offering equal-cost from S means of IGP routes. BGP resolves
   its advertised next-hop to D the immediate next-hop by potential
   recursive lookups in the routing database.  IP Fast-Reroute computes
   the alternate next-hops to the all the IGP destinations, which
   includes 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 continue to use the IGP optimal distance to
   find the nearest exit router.  MBGP routes do not loop-free with respect need to S and D.  Since copy the
   alternate
   inheritance next hops.

5.4 Multicast Considerations

   Multicast traffic is out of scope for this specification of IP Fast-
   Reroute.  The alternate next-hops SHOULD not used for multi-cast RPF
   checks.

6. Security Considerations

   This document does not introduce any new security issues. The
   mechanisms described in this document depend upon the network
   topology distributed via an IGP, such as OSPF or ISIS.  It is of interest only where all
   dependent upon the ABRs offering equal-
   cost paths security associated with those protocols.

7.  Full Copyright Statement

   Copyright (C) The Internet Society (2004).  This document is subject
   to D have the same primary next-hop P, if A2 is loop-free rights, licenses and node-protecting for one ABR offering equal-cost paths to D, then
   A2 is node-protecting for restrictions contained in BCP 78, and
   except as set forth therein, the authors retain all those ABRs.

   Next, given that A2's optimal path to ABR2 does not go through P, is
   to prove that if A2's optimal path to D goes via some ABRt, that that
   path does not go through P. their rights."

   This can be shown using variable
   replacement of document and the second proof given as follows:

        Assume that D_opt(A2, D) goes through ABRt.
                  Step i: D_opt(A2, ABRt) + D_opt(ABRt, D) <=
                        D_opt(A2, ABR2) + D_opt(ABR2, D)

                  Step ii: D_opt(A2, ABR2) + D_opt(ABR2, D) <
                 D_opt(A2, P) + D_opt(P, ABR2) + D_opt(ABR2, D)

                  Step iii: D_opt(P, ABR2) + D_opt(ABR2,D) <
                        D_opt(P, ABRt) + D_opt(ABRt, D)

        From previous by adding Dopt(A2, P) to both sides
           Step iv: D_opt(A2, P) + D_opt(P, ABR2) + D_opt(ABR2,D) <
                 D_opt(A2, P) + D_opt(P, ABRt) + D_opt(ABRt, D)

        From Steps i and ii:
                  Step v: D_opt(A2, ABRt) + D_opt(ABRt, D) <
                 D_opt(A2, P) + D_opt(P, ABR2) + D_opt(ABR2, D)

        From Steps iv and v:
                  Step vi: D_opt(A2, ABRt) + D_opt(ABRt, D) <
                 D_opt(A2, P) + D_opt(P, ABRt) + D_opt(ABRt, D)

        Therefore, if Dopt(A2, D) is via ABRt, it does not go through 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 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.

8. References

   [FRAMEWORK] M. Shand, "IP Fast Reroute Framework", draft-ietf-rtgwg-
   ipfrr-framework-01.txt, June 2004

   [LDP] L. Anderson, P.

   This proves that if A2 provides a loop-free node-protecting alternate
   for S Doolan, N. Feldman, A. Fredette, B. Thomas,
   "LDP Specification", RFC 3036, January 2001

   [RSVP-TE] D. Awduche, L. Berger, D. Gan, T. Li, V Srinivasan, G.
   Swallow, "RSVP-TE: Extensions to reach ABR2, then A2 will also provide a loop-free node-
   protecting alternate RSVP for S LSP Tunnels", RFC 3209,
   December 2001

   [RSVP-TE FRR] P. Pan, D. Gan, G. Swallow, JP Vasseur, D. Cooper, A.
   Atlas, and M. Jork, "Fast Reroute Extensions to reach RSVP-TE for LSP
   Tunnels", work-in-progress draft-ietf-mpls-rsvp-lsp-fastreroute-
   07.txt, June 2004

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

   [RFC3277] D. McPherson, "Intermediate System to Intermediate System
   (IS-IS) Transient Blackhole Avoidance", RFC 3277, April 2002

   [ISIS] R. Callon, "Use of OSI IS-IS for Routing in TCP/IP and Dual
   Environments", RFC 1195, December 1990

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

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

   [RFC2370] R. Coltun, "The OSPF Opaque LSA Option", RFC 2370, July
   1998

9. Authors Information

   Raveendra Torvi
   Avici Systems
   101 Billerica Avenue
   N. Billerica, MA 01862
   USA
   email: rtorvi@avici.com
   phone: +1 978 964 2026

   Gagan Choudhury
   AT&T
   Room D5-3C21
   200 Laurel Avenue
   Middletown, NJ 07748
   USA
   email: gchoudhury@att.com
   phone: +1 732 420-3721

   Christian Martin
   Verizon
   1880 Campus Commons Drive
   Reston, VA 20191
   email: cmartin@verizon.com

   Brent Imhoff
   WilTel Communications
   3180 Rider Trail South
   Bridgeton, MO 63045
   USA
   email: brent.imhoff@wcg.com
   phone: +1 314 595 6853

   Don Fedyk
   Nortel Networks
   600 Technology Park
   Billerica, MA 01821
   email: dwfedyk@nortelnetworks.com
   phone: +1 978 288 3041

10. Editor's Information

   Alia Atlas
   Avici Systems
   101 Billerica Avenue
   N. Billerica, MA 01862
   USA
   email: aatlas@avici.com
   phone: +1 978 964 2070