[Docs] [txt|pdf] [Tracker] [Email] [Nits] [IPR]

Versions: 00

Internet Draft                               Alia Atlas (Avici Systems)
Expires: August 2004                    Raveendra Torvi (Avici Systems)
                                                 Gagan Choudhury (AT&T)
                                             Christian Martin (Verizon)
                                                  Brent Imhoff (Wiltel)
                                                     Don Fedyk (Nortel)


                        IP/LDP Local Protection

                  draft-atlas-ip-local-protect-00.txt

Status of this Memo

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

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

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

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

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


Abstract

   This document defines an architecture and selection process for
   providing local protection for IP unicast and/or LDP traffic in the
   event of a single link or node failure until the router has
   converged.  When computing the primary next-hop for a prefix, a
   router S also determines an alternate next-hop which can be used if
   the primary next-hop fails.  The alternate can be either a loop-free
   alternate, which goes to a neighbor whose shortest path to the prefix
   does not go back through the router S, or a U-turn alternate, which
   goes to a neighbor whose primary next-hop to the prefix is the router
   S, and which has itself a loop-free node-protecting alternate, which
   thus does not go through router S to reach the destination prefix.




Atlas et al.                                                    [Page 1]


Internet Draft                                               August 2004


   A router may indicate the capability to break U-turns on its links;
   only such links can be used as U-turn alternate next-hops.  To signal
   this capability, a router must be capable of detecting when it
   receives traffic for a given destination from a primary neighbor for
   that destination and the router must forward that traffic to the
   selected alternate next-hop.

   To support U-Turn alternates and node-protection, a router must know
   what links its neighbor can consider for alternates, how a neighbor
   will select an alternate, and upon which interfaces a neighbor can
   break U-turns.  This document defines a common selection criteria
   which MUST be followed.  In addition, it is necessary to signal two
   capabilities per link.  First is whether U-turns can be broken on the
   link and second is whether the link can be used as an alternate, as
   determined administratively.




Contents

  1  Introduction  .................................................  3
  2  Terminology  ..................................................  4
  3  Finding an Alternate  .........................................  6
    3.1 Types of Alternates  .......................................  6
      3.1.1 Loop-Free Alternates ...................................  7
      3.1.2 U-Turn Alternates  .....................................  8
        3.1.2.1 ECMP U-Turn Neighbors  ............................. 11
        3.1.2.2 U-Turn Neighbor's Alternate  ....................... 13
          3.1.2.2.1 Computing Alternate So Primary Next-Hop Can
                    Use Computing Router for U-Turn Alternate....... 15
    3.2 Selection of an Alternate  ................................. 15
      3.2.1 IP Local Protection Alternate Capability  .............. 16
      3.2.2 U-Turn Breaking Capability  ............................ 16
      3.2.3 Characterization of Neighbors  ......................... 16
      3.2.4 Selection Procedure  ................................... 17
        3.2.4.1 Alternate Selection With One Primary Neighbor ...... 17
        3.2.4.2 Alternate Selection With Multiple Potential
                Primary Neighbors .................................. 19
  4  Using an Alternate  ........................................... 19
    4.1 Breaking U-Turns  .......................................... 19
    4.1.1 Broadcast and NBMA Interfaces  ........................... 21
    4.2 Responding to a Local Failure  ............................. 22
  5  Requirements on LDP Mechanics  ................................ 23
  6  Routing Interactions .......................................... 23
    6.1 OSPF Inter-Area Routing  ................................... 23
    6.2 OSPF External Routing  ..................................... 25
    6.3 ISIS Multi-Level Routing  .................................. 25



Atlas et al.                                                    [Page 2]


Internet Draft                                               August 2004


    6.4 OSPF Virtual Links  ........................................ 26
    6.5 BGP Next-Hop Synchronization  .............................. 26
    6.6 Interactions with ISIS Overload, RFC 3137
        and Costed Out Links  ...................................... 26
    6.7 Multicast Considerations  .................................. 27
  7  Security Considerations  ...................................... 27
  8  Intellectual Property Considerations  ......................... 27
  9  Full Copyright Statement  ..................................... 27
  10 References  ................................................... 28
  11 Authors Information  .......................................... 29


1. Introduction

   Applications 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.  This document describes a mechanism to
   allow 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.

   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  |                | N_1 |
                       +-----+                +-----+
                          \                     /
                       \   \  4              3 /  /
                        \|  \                 / |/
                        -+   \    +-----+    /  +-
                              \---|  D  |---/
                                   +-----+

                         Figure 1: Basic Topology




Atlas et al.                                                    [Page 3]


Internet Draft                                               August 2004


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

   To clarify the behavior of IP/LDP Local Protection, consider the
   simple topology in Figure 1.  When router S computes its shortest
   path to router D, router S determines to use the interface to router
   P as its primary next-hop.  Without IP/LDP Local Protection, that is
   the only next-hop that router S computes to reach D.  With IP/LDP
   Local Protection, 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 interface to router N_1 and therefore S would
   install the interface to N_1 as its alternate next-hop.  At some
   point later, the link between router S and router P could fail.  If
   that link fails, S (and most likely P) will be the first to detect
   it.  On detecting the failure, S will stop sending traffic destined
   to D towards P via the failed link, and instead send the traffic to
   S's pre-computed alternate next-hop, which is the interface to N_1,
   until a new SPF is run and its results are installed.  As with the
   primary next-hop, the 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.  In the modified example, N_1 has a loop-free
   node-protecting alternate to reach D; N_1 can reach D directly.  If S
   could use N_1 in such a scenario, then the topologies where there are
   acceptable alternates could increase.  Such an alternate is termed a
   U-turn alternate; S sends to a neighbor N_1 whose primary neighbor
   for that traffic is S.  N_1 detects this situation and rather than
   forwarding the traffic back to S, in a U-turn loop, N_1 breaks the
   U-Turn and forwards the traffic to N_1's alternate.

   The existence of a suitable alternate next-hop is topology dependent;
   in real networks, the addition of U-Turn alternates has substantially
   improved the coverage of alternates for the source/destination pairs
   in those networks over that available with only loop-free alternates.

2. Terminology

   SPT --- Shortest Path Tree




Atlas et al.                                                    [Page 4]


Internet Draft                                               August 2004


   D --- The destination router under discussion.

   S --- The source router under discussion. It is the viewpoint from
                which IP/LDP Local Protection is described.

   P --- The router which is the primary next-hop neighbor to get from S
          to D. Where there is an ECMP set for the shortest path from S
          to D, these will be referred to as P_1, P_2, etc.

   N_i --- The ith neighbor of 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 the shortest path from A to B.

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

   Loop-Free Alternate --- This is a next-hop that is not a primary
          next-hop whose shortest path to the destination from the
          alternate neighbor does not go back through the router S.

   U-Turn Alternate --- This is an alternate next-hop of S that goes to
          a neighbor N_i, whose primary next-hop is S, and whose
          alternate is loop-free with respect to S and N_i.  In other
          words, this is an alternate that would normally loop traffic
          back to the source (S), but which itself has an alternate that
          does not loop back to the source (S).

   Link(A->B) --- A link connecting router A to router B.

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

   @@@@\   This is an arrow indicating the alternate next-hop towards D
       /

   Primary Neighbor --- One or more of the primary next-hops for S to
        reach the destination D goes directly to this neighbor.

   Loop-Free Neighbor --- A Neighbor N_i which is not the primary
        neighbor and whose shortest path to D does not go through S.

   U-Turn Neighbor --- A neighbor N_i is a U-Turn neighbor of router S
        with respect to a given destination D if and only if S is a
        primary neighbor of  N_i to reach the destination D for all



Atlas et al.                                                    [Page 5]


Internet Draft                                               August 2004


        primary paths which go through S to reach D.

   ECMP U-Turn Neighbor --- A neighbor N_i which is a U-Turn neighbor
        and which has at least one equal cost path to reach D that does
        not go through S as well as the path(s) which do go through S to
        reach D.

   Looping Neighbor --- A neighbor N_i is a looping neighbor of router S
        with respect to a given destination D if any of N_i's optimal
        paths to D goes through S, but S is not the primary next-hop of
        N_i for all those paths 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 of S which is being protected to reach the
        destination D.

   Loop-Free Link-Protecting Alternate --- This is a path via a Loop-
        Free Neighbor N_i which does go through the particular primary
        neighbor of S which is being protected to reach the destination
        D.

   U-Turn Node-Protecting Alternate --- This is a path via a U-Turn
        Neighbor N_i which does not go through S or any of S's primary
        neighbors to reach the destination D.

   U-Turn Link-Protecting Alternate --- This is a path via a U-Turn
        Neighbor N_i which does not go through S but does go through one
        or more of S's primary neighbors to reach the destination D.

   Upstream Forwarding Loop --- This is a forwarding loop which involves
        a set of routers, none of 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

3.1. Types of Alternates

   As with primary next-hops, an alternate next-hop is discussed in
   relation to a particular destination router D.   For this discussion,
   the following terminology, illustrated in Figure 2, will be used.
   The router on which the search for an alternate is proceeding is S.
   The primary next-hop neighbor to get from S to D is P.  Additionally,
   S has various neighbors which will be labeled N_1, N_2, etc.   Where
   an arbitrary neighbor of S is intended, N_i will be used.  Routers
   which are neighbors of neighbors will be labeled R_1, R_2, etc.



Atlas et al.                                                    [Page 6]


Internet Draft                                               August 2004


   Where an arbitrary neighbor of a neighbor N_i is intended, it will be
   refered to as R_i_j.

   In IP routing, a router S can join the shortest path tree (SPT) at
   exactly one point -- itself.  An alternate next-hop allows traffic
   from S to D to deviate from the SPT and then rejoin it.  For
   instance, if S were to send traffic destined for D to N_1 instead of
   P, thereby deviating from the SPT, then when N_1 received it, N_1
   would send that traffic along its shortest path to D.

                                           +-----+
                          \          /    _| R_2 |
               +-----+__    \|     |/    / +-----+
               | N_3 |  \   -+     +- __/       \
               +-----+   \____       /           \
                \             \     /             \
                 \             +-----+             \
                  \           _| N_2 |              \
                   |       __/ +-----+               \
                    \     /         \                 |
                     \   /     /     \_               |
                   +-----+   |/        \              |
                   |  S  |   +-         \  +-----+    |
                   +-----+               \_| R_1 |    |
               /    /   \                  +-----+    |
             |/    /     \                  /         |
             +-   /       \                /          |
                 /       +-----+          /   /       |
         +-----+/        | N_1 |         /  |/        |
         |  P  |         +-----+        /   +-        |
         +-----+            \          /             /
            \             \  \__      /             /
         \   \             \|   \    /             /
          \|  \            -+    +-----+          /
          -+   \_________________|  D  |---------/
                                 +-----+

                    Figure 2:  Topology for Terminology

3.1.1. Loop-Free Alternates

   To expand the set of points at which S can cause its traffic to join
   the SPT, first consider S's neighbors.  Router S has the ability to
   send traffic to any one of its neighbors N_i; this is the easiest
   possible deviation from the SPT that S can cause to happen.  Thus,
   all of router S's neighbors are possible points at which S could
   cause traffic to rejoin the SPT.  However, it is not useful for
   router S to use a next-hop which results in rejoining the SPT



Atlas et al.                                                    [Page 7]


Internet Draft                                               August 2004


   upstream of S, such that the traffic will transit S again.  This
   would cause a loop.  Avoiding a loop is thus the first constraint
   imposed on the alternate next-hop.   In Figure 2, this is the case
   for S's neighbors N_2 and N_3.

   A next-hop which goes to a neighbor that does not have a loop back to
   S and is not the primary next-hop may be selected as an alternate
   next-hop.  In Figure 2, that is the case for S's neighbor N_1.  Such
   alternates are referred to as loop-free alternates because there is
   no loop caused by using them.

   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 the destination D for the optimal path that
   does not go through S.  This is referred to as Distance_!S(N_i, D).
   If a neighbor N_i can provide a loop-free alternate, then it is
   cheaper to get to the destination without going through S than by
   going through S.  This gives the following requirement, where
   Distance_opt(A, B) gives the distance of the optimal path from A to
   B.

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

              Equation 1: Criteria for a Loop-Free Alternate

   Recall that a router will take the shortest path 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 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 a router N_i has an ECMP set to reach the destination
   and one or more paths go through S, then the router N_i cannot
   provide a loop-free alternate because some traffic destined to D may
   be sent back to S by N_i.  Thus, if N_i is to decide not to send
   traffic for D back to S, N_i must observe that the shortest path to D
   does not go through S; Equation 1 gives this requirement in terms
   which can be determined by router S.

3.1.2. U-Turn Alternates

   In examining realistic networks, it was seen that loop-free
   alternates did not provide adequate coverage for the traffic between
   all the source-destination pairs.  This means that it is not
   sufficient to expand the set of points where S can cause its traffic
   to join the SPT to be only S's neighbors.



Atlas et al.                                                    [Page 8]


Internet Draft                                               August 2004


   The next possibility is to see whether S could expand its SPT join
   points to include router S's neighbors' neighbors.  This is only of
   interest if S had no loop-free node-protecting alternate available
   for the given destination D.  If there are no loop-free alternates,
   that implies that all of S's non-primary neighbors will send traffic
   for D back to S.

   The topology shown in Figure 3 gives an example where router S has no
   loop-free alternate to reach D.  Router S uses P as its primary
   next-hop (distance of 30).  S has three other neighbors, but all of
   them will send traffic for D back through S.

                                    +-----+  \
                                    | N_4 |\  \|      /  +-----+
                                    +-----+ \ -+    |/  /| R_3 |
                                      /      \      +- / +-----+
                                     /     15 |      _/      |
                                    |         |   5 /        |
                                    | 50       \   /         |
                +-----+             |         +-----+        |
                | N_2 |            /   ______/| N_3 |        |
                +-----+ \         /   /       +-----+     70 |
                 |    \  \|      /   / 30   /                |
               10|     \ -+     /   /     |/                 |
                 |   15 \      +-----+    +-                 |
              @  |       \-----|  S  |                       |
              @  |     /       +-----+                       |
             \@/ |     @@@@        |                         |
                 |     \      |    |10                      /
                 |            |    |                       /
              +-----+        \_/   |                      /
              | R_2 |           +-----+                  /
              +-----+           |  P  |                 /
                 \              +-----+                /
              \   \ 40            /                   /
               \|  \          10 /  /                /
               -+   \           / |/                /
                    +-----+    /  +-               /
                    | R_1 |---/                   /
                    +-----+                      /
                        \     10            +-----+
                     \   \------------------|  D  |
                      \|                    +-----+
                      -+

                        P is primary next-hop of S
                   N_2 and N_3 are U-Turn Neighbors of S
                      N_4 is a Looping Neighbor of S



Atlas et al.                                                    [Page 9]


Internet Draft                                               August 2004


   Figure 3: Terminology of Looping Neighbors and Example U-Turn Alternate

   In order for S to be able to use a neighbor's neighbor as a point
   where S's traffic can rejoin the SPT, S must be able to direct
   traffic to a neighbor N_i and that neighbor N_i must be able to
   direct traffic to one of its appropriate neighbors R_i_j instead of
   along the SPT.  In deciding to use its alternate, S has the ability
   to force traffic destined to D to go through the selected alternate
   neighbor N_i.  However, for S to reach the appropriate neighbor's
   neighbor R_i_j, the selected neighbor N_i  must be able to detect
   that the traffic should not be sent along its shortest path to D,
   which would lead back to S, and should instead be sent to its
   appropriate neighbor R_i_j.

   This detection and forwarding contrary to the SPT by N_i must occur
   without any communication from S upon the failure which would cause S
   to redirect the traffic to N_i.  There is already communication from
   S to N_i indicating when a link has failed, but such communication
   would cause the fail-over of traffic to take longer than the desired
   10s of milliseconds if N_i depended upon it to decide that it should
   forward contrary to the SPT.  In essence, the assumption being made
   is that the time budget to recover traffic in the event of a failure
   is being consumed by router S's detection of the failure and switch-
   over to its pre-computed alternate.

   With that assumption, it is clear that N_i's behavior to forward
   traffic contrary to the SPT on receiving traffic from S must be a
   default behavior.  This default behavior must not change how traffic
   is forwarded unless a forwarding loop is detected; basic IP
   forwarding must be preserved in the absence of a failure.  Router N_i
   can detect if it is receiving traffic from a neighbor to whom it
   would forward that traffic; this detection is done via a reverse
   forwarding check.  Such a reverse forwarding check should consider
   not only if traffic is received on the same interface as it would be
   forwarded out, but whether it was received from the same neighbor to
   whom it would be forwarded.  Normally, if traffic fails a reverse
   forwarding check (i.e. would be forwarded out to the same neighbor as
   received from), then that traffic is either discarded or forwarded
   into a loop.  In IP/LDP Local Protection, however, traffic that fails
   a reverse forwarding check is forwarded to the appropriate R_i_j, if
   available, rather than being discarded.

   First, this detection can be used by N_i to determine not to forward
   the traffic according to the SPT (or discard it), but to instead send
   the traffic to N_i's appropriate neighbor R_i_j.  N_i can only detect
   the traffic to be redirected if S sends it directly to N_i, which is
   under S's control, and if N_i would send that traffic back to S,
   according to the SPT.  This motivates the definition of a Looping



Atlas et al.                                                   [Page 10]


Internet Draft                                               August 2004


   Neighbor and a U-turn Neighbor.

        Looping Neighbor --- A neighbor N_i is a looping neighbor of
                             router S with respect to a given
                             destination D if any of N_i's shortest
                             paths to D goes through S but S is not the
                             primary next-hop of  N_i for all those
                             paths through S.

        U-Turn Neighbor --- A neighbor N_i is a U-Turn Neighbor of
                            router S with respect to a given destination
                            D if and only if S is a primary next-hop of
                            N_i to reach the destination D for all
                            primary paths which go through S to reach D.


   A Looping Neighbor cannot provide any type of alternate.  A U-Turn
   neighbor may be able to provide an alternate.  In Figure 3, S has two
   U-Turn Neighbors N_2 and N_3 and one looping neighbor N_4.  For
   neighbor N_4, the path to D is N_3 to S to N_1 to R_1 to D; because
   there is a node between N4 and S on the path, N_4 is a looping
   neighbor.

   Mathematically, for a neighbor N_i to be a U-Turn neighbor, it is
   necessary that Equation 2, which is the exact opposite of Equation 1,
   be true.  If the equality is true, that means that there are multiple
   optimal paths, at least one of which goes through S and one does not.
   Such a neighbor may be an ECMP U-Turn neighbor or may be a looping
   neighbor.

     Distance_!S(N_i, D) >= Distance_opt(N_i, S) + Distance_opt(S, D)

                  Equation 2: U-Turn or Looping Neighbor

   Additionally, all optimal paths to reach D that go via S must be via
   a direct link between N_i and S.  If a neighbor N_i satisfies
   Equation 2 and all optimal paths to reach D that go via S are via a
   direct link between N_i and S, then it is a U-turn neighbor.

   The above clarifies what a U-Turn neighbor is and how such a neighbor
   can detect traffic from router S and redirect it.  It is still
   necessary to describe where the U-Turn neigbhor N_i redirects the
   traffic.

3.1.2.1. ECMP U-Turn Neighbors

   The above definition for U-Turn Neighbor allows a neighbor, which has
   equal cost paths (an ECMP set) where one of those paths goes directly



Atlas et al.                                                   [Page 11]


Internet Draft                                               August 2004


   to S and others may not, to be a U-Turn Neighbor.   Consider the
   topology shown in Figure 4.  In this figure, N_1 has three equal-cost
   paths to reach D which are N_1 - S - P - D, N_1 - R_1 - D, and N_1 -
   R_2 - D.   Because the only path that goes through S goes directly
   through S, N_1 is a U-Turn neighbor of S.

                                +-----+------\
                             /--| N_1 |   5   \
                         /  /   +-----+\       \       +-----+
                       |/  / 10     \   \ 15    \------| R_3 |
                       +- /       10 \   \             +-----+
                         /            |   \  \             |
                      +-----+     |   |    \  \|           |
                      |  S  |    \|/  |     \ -+           |  |
                      +-----+         |      \             | \|/
                        /          +-----+    \            |
                   /   /  10       | R_1 |     \         15|
                 |/   /            +-----+      \          |
                 +-  /           /   /        +-----+      |
                    /          |/   / 20      | R_2 |      |
                 +-----+       +-  /          +-----+      |
                 |  P  |          |      /__  15 /         |
                 +-----+          |      \      /          |
                    \             |    /-------/        +-----+
                  \  \ 10         |   /                 |  X  |
                   \| \           |  /            /__   +-----+
                   -+  \       +-----+            \       / 15
                        \------|  D  |-------------------/
                               +-----+

                      Figure 4: ECMP U-Turn Neighbor

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

                         Equation 3: ECMP Neighbor

   A neighbor is an ECMP neighbor if Equation 3 is true.  The
   complication comes because S does not know whether a neighbor N_i
   supports ECMP or how that neighbor selects among the equal cost
   paths.  Recall that a node will only break U-Turns on the interfaces
   connected to that node's primary neighbors.

   Consider the topology in Figure 5, where N_2 has three equal cost
   primary neighbors which are S, N_1 and R_1.  If N_2 were to select
   only N_1 as its primary neighbor, then N_2 would break U-Turns only
   on traffic received from N_1 and not on traffic received from S.
   Therefore, S cannot consider N_2 as an ECMP U-Turn neighbor because S
   cannot rely upon N_2 to break U-turns for traffic destined to D which



Atlas et al.                                                   [Page 12]


Internet Draft                                               August 2004


   is received from S.

   If N_2 has multiple paths to reach D which go through S and not all
   such paths have a first hop which is a direct link between N_2 and S,
   then S cannot use N_2 as a U-Turn neighbor.

                                           10    +-----+
                              /   /--------------| N_2 |\  \
                            |/   /               +-----+ \  \|
                            +-  /             /----/ 5    \ -+
                               /             /      /      \
                              /      5  +-----+   |/        |
                             /     /----| N_1 |   +-        | 15
                          +-----+ /     +-----+             |
                          |  S  |/   /                   +-----+
                          +-----+  |/                    | R_1 |
                        /  /       +-                    +-----+
                      |/  / 5                                /
                      +- /                                  /  15
                  +-----+                         /--------/
                  |  P  |                        /
                  +-----+                       /    /
                      \                        /   |/
                   \   \ 5            +-----+ /    +-
                    \|  \-------------|  D  |/
                    -+                +-----+

       Figure 5: ECMP Neighbor Which is Not an ECMP U-Turn Neighbor

   If all paths from an ECMP neighbor N_i to destination D which go via
   S have S as the primary neighbor, then S can use N_2 as a ECMP U-Turn
   neighbor.

3.1.2.2. U-Turn Neighbor's Alternate

   The requirement for the neighbor's neighbor R_i_j to which a U-Turn
   Neighbor N_i will redirect traffic from S destined to D is that the
   traffic not come back to S.  Equation 4 gives this requirement that
   R_i_j must have a path to D that does not go through S which is
   shorter than the path to D going via S.  This can be expressed as
   follows.

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

                Equation 4: Loop-Free Neighbor's Neighbor

   Equation 4 means that a U-Turn neighbor's alternate cannot be an ECMP
   set which contains that U-Turn neighbor.



Atlas et al.                                                   [Page 13]


Internet Draft                                               August 2004


   If N_i is a U-Turn neighbor, then the optimal path to D from N_i is
   via S; the path is N_i - S - ... - D.  Therefore, if the optimal path
   from R_i_j goes through N_i, it must also go through S.  Thus, if
   Equation 4 holds for a R_i_j, that implies that the path from R_i_j
   does not go through N_i.   This may be made clearer by considering
   Figure 6 below.  If the shortest path from R_1 to D went through N_1,
   then it would go through S as well, because the shortest path from
   N_1 to D is through S.  Therefore, if the shortest path from R_1 does
   not go through S, it cannot have gone through N_1.

                                            5    +-----+      @
                              /   /--------------| N_2 |\     @
                            |/   /               +-----+ \    \@/
                            +-  / /@\                     \
                               /  @                        \
                              /  @                          |
                             /                              | 15
                          +-----+                           |
                          |  S  |                        +-----+
                          +-----+                        | R_1 |
                        /  /                             +-----+
                      |/  / 5                                /
                      +- /                                  /   5
                  +-----+                         /--------/
                  |  P  |                        /
                  +-----+                       /    /
                      \                        /   |/
                   \   \ 5            +-----+ /    +-
                    \|  \-------------|  D  |/
                    -+                +-----+

                    Figure 6: U-Turn Alternate Example

     If the optimal path from Ri,j to D goes through N_i, then
            Distance_!S(R_i_j, D) >= Distance_opt(R_i_j, N_i) +
                                         Distance_opt(N_i, D)
     Because N_i is a U-Turn neighbor, the shortest path to D is via S:
      Distance_opt(N_i, D) = Distance_opt(N_i, S) + Distance_opt(S, D)

     The previous two equations can be combined to form the following:
            Distance_!S(R_i_j , D) >= Distance_opt(R_i_j, N_i) +
                               Distance_opt(N_i, S) + Distance_opt(S, D)

     Because Distance_opt(R_i_j, S) is the minimum distance of a path to
     get from R_i_j to S, the path to do so via N_i cannot have a lower
     distance.
            Distance_opt(R_i_j, S) <= Distance_opt(R_i_j, N_i) +
                                         Distance_opt(N_i, S)



Atlas et al.                                                   [Page 14]


Internet Draft                                               August 2004


     This can be combined with the previous equation to yield
     Distance_!S(R_i_j, D) >= Distance_opt(R_i_j, S) + Distance_opt(S,D)

     This equation is the opposite of Equation 4.  Thus, if Equation 4
     is true, then the optimal path from R_i_j to D does not go through
     N_i.

       Proof 1: Proof that a Loop-Free R_i_j (Neighbor's Neighbor)
                     Implies R_i_j Doesn't Loop to Neighbor N_i

   The proof given in Proof 1 means that if a U-Turn Neighbor N_i has
   itself a neighbor R_i_j that satisfies Equation 4, then that router
   R_i_j is itself a loop-free alternate with respect to N_i.
   Regrettably, the converse does not apply; just because R_i_j is
   loop-free with respect to N_i and D does not mean that R_i_j is
   loop-free with respect to S and D.

3.1.2.2.1. Computing Alternate So Primary Next-Hop Can Use Computing
           Router for U-Turn Alternate

   Each router independently computes the alternate that it will select.
   It is necessary to consider what alternate S could select so that S's
   primary next-hop P could use S as a U-Turn alternate.  In other
   words, consider the computation when S is in the role of a neighbor
   to the router doing the computation.

   To describe this using router S as the computing router, S would need
   to verify that both Equation 1 is true and that S's selected
   alternate N_i does not have a path that goes through P.

   This can be described as if N_i were doing the computation as
   follows.  The criteria described in Equation 4 requires that if a U-
   Turn neighbor N_i is to be used as a U-Turn alternate then N_i must
   have a loop-free alternate which avoids N_i's primary neighbor S.
   Such an alternate will be referred to as a loop-free node-protecting
   alternate.  N_i can identify loop-free alternates by checking the
   validity of Equation 5.  Additionally, N_i will need to tell whether
   the path from a loop-free R_i_j to D goes through N_i's primary
   next-hop neighbor, S.

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

                Equation 5: Neighbor's Loop-Free Alternate

3.2. Selection of an Alternate

   All routers that supports breaking U-Turns for IP/LDP Local



Atlas et al.                                                   [Page 15]


Internet Draft                                               August 2004


   Protection must follow common alternate selection criteria.  For a
   node S to use a U-Turn neighbor N_u for a U-turn alternate, S must
   know not only that N_u has an acceptable loop-free node-protecting
   alternate but that N_u can and will use it.  For S to be able to
   provide node-protection via a U-Turn alternate, S must know how N_u
   will select among the loop-free node-protecting alternates which are
   available.

3.2.1. IP Local Protectection Alternate Capability

   There are a number of different reasons why an operator may not wish
   for a particular interface to be used as an alternate.  For instance,
   the interface may go to an edge router or the interface may not have
   sufficient bandwidth to contain the traffic which would be put on it
   in the event of failure.

   Because a router's neighbors may desire to use that router to provide
   a U-turn alternate, a router must flood to its neighbors which
   interfaces are not capable of providing alternates.  This information
   allows a router's neighbors to accurately determine whether or not
   the router has a loop-free node-protecting alternate.

   The extensions to signal this local-protection alternate capability
   are described in [OSPF-LOCAL-PROTECT] and [ISIS-LOCAL-PROTECT].

3.2.2. U-Turn Breaking Capability

   A router S may only use its neighbor N_u as a U-Turn alternate if N_u
   indicates that it is capable of breaking U-Turns on a link between S
   and N_u.  The capability to break U-Turns must be signaled for a link
   in order for S to determine that it can use N_u as a U-Turn
   alternate.  By default, S MUST assume that a neighbor cannot provide
   a U-Turn alternate unless that neighbor indicates the U-Turn breaking
   capability on a link between S and N_u.  This U-Turn breaking
   capability need only be flooded to a node's neighbors.

   The extensions to signal the U-turn breaking capability are also
   described in [OSPF-LOCAL-PROTECT] and [ISIS-LOCAL-PROTECT].

3.2.3 Characterization of Neighbors

   Conceptually, each neighbor N_i is categorized as to the type of path
   which it can provide to a particular destination D.  Each neighbor
   can be characterized as providing a path in one of the following
   categories for a particular destination D.   The path through the
   neighbor N_i is either a:

        (A) Primary Path --- one of the shortest paths that is selected



Atlas et al.                                                   [Page 16]


Internet Draft                                               August 2004


        as a primary next-hop,

        (B) Loop-Free Node-Protecting Alternate --- not a primary path
        and the path avoids both S, the interfaces connecting S to its
        primary neighbors, and its primary neighbors on the path to D.

        (C) Loop-Free Link-Protecting Alternate --- not a primary path
        and the path avoids S and the interfaces connecting S to its
        primary neighbors, but goes through a primary neighbor on the
        path to D.

        (D) U-Turn Node-Protecting Alternate --- the neighbor is a U-
        Turn neighbor or a ECMP U-Turn neighbor and the alternate that
        the neighbor has selected does not go through a primary neighbor
        of S to reach D.

        (E) U-Turn Link-Protecting Alternate --- the neighbor is a U-
        Turn neighbor or a ECMP U-Turn neighbor and the alternate that
        the neighbor has selected goes through a primary neighbor of S
        to reach D.

        (F) Unavailable --- because the neighbor is looping or a U-Turn
        neighbor which didn't itself have a loop-free node-protecting
        path, or a U-Turn neighbor which couldn't break U-Turns or the
        links to the neighbor are configured to not be used as
        alternates.  The neighbor may also be disqualified because it is
        connected to S solely via broadcast interfaces which also have
        primary next-hops.

3.2.4. Selection Procedure

   Once the neighbors have been categorized, a selection can be made.
   The selection should maximize the failures which can be protected
   against.  A node S can only be used to break U-turns by its primary
   neighbors if S has a loop-free node-protecting alternate.

   The selection procedure depends on whether S has a single potential
   primary neighbor or multiple potential primary neighbors.  A router S
   is defined to have a single potential primary neighbor only if there
   are no equal cost paths that go through any other neighbor; i.e., a
   router S cannot be considered to have a single potential primary
   neighbor just because S does not support ECMP or just because S
   selects as primary next-hops links to only one potential primary
   neighbor.

3.2.4.1. Alternate Selection With One Primary Neighbor

   Because a router S can only be used to break U-Turns by its primary



Atlas et al.                                                   [Page 17]


Internet Draft                                               August 2004


   neighbor if S selects a loop-free node-protecting alternate, the
   following rules MUST be followed when selecting an alternate.

        1.  If a router S has one or more loop-free node protecting
        alternates, then S MUST select one of those alternates. Let M be
        the set of neighbors which provide loop-free node-protecting
        alternates.  If S has multiple loop-free node protecting
        alternates, then S MUST select the alternate through a N_k such
        that:

               D_!S(N_k, D) - D_opt(N_k, P) = min_forall m in M
                               (D_!S(m, D) - D_opt(m, P))

                Equation 6: Selection Among Multiple Loop-Free
                             Node-Protecting Alternates

        where P is the primary neighbor of S.

        To rephrase the above to consider the S is the node looking for
        a U-Turn alternate, the above way of selecting among loop-free
        node-protecting alternates ensures that N_i's primary neighbor S
        can determine which alternate was picked by N_i.  For S to know
        that S's U-Turn neighbor N_i can provide a loop-free node-
        protecting alternate, S must know if

            min_forall j in J ( D_!S(R_i_j, D) - D_opt(R_i_j, S) )
                                 < D_opt(S, D)

                Equation 7: Determination if a U-Turn Neighbor
                            can provide a U-Turn Alternate

        If a router obeys Equation 6 when selecting among multiple
        loop-free node-protecting alternates, as it MUST for IP/LDP
        Local Protection, this allows S to determine exactly which
        alternate was selected by N_i without needing to know the each
        D_!S(R_i_j).  Equation 7 allows S to determine that N_i has a
        loop-free node-protecting alternate.  Equation 6 allows S to
        know exactly which alternate will be selected so that S can
        determine whether that alternate protects against S's primary
        neighbor as well.  If there are multiple neighbors which provide
        the minimum as expressed in Equation 6, then a router can select
        among them arbitrarily.

        2. If a router S has no loop-free node-protecting alternates,
        then S's alternate selection has no consequences for its
        neighbors because S cannot provide a U-Turn alternate.
        Therefore, S can select freely among the loop-free link-
        protecting alternates, u-turn node-protecting alternates and u-



Atlas et al.                                                   [Page 18]


Internet Draft                                               August 2004


        turn link protecting alternates which S has available.  Clearly
        selecting a u-turn node-protecting alternate, if one is
        available, will provide node-protection, while the other options
        will not.  Selection among these categories is a router-local
        decision.

        3.  If S has neither loop-free node-protecting alternates,
        loop-free link-protecting alternates, u-turn node-protecting
        alternates, nor u-turn link-protecting alternates, then S has no
        alternate available for traffic to the destination D from the
        source S.

3.2.4.2. Alternate Selection With Multiple Potential Primary Neighbors

   The selection among multiple equal cost paths is a router-local
   decision.  Therefore, a router N_i cannot know which of the potential
   primary neighbors that S will choose to use.

   As described in Section 3.1.2.1, N_i can only select S for its U-Turn
   alternate if any potential primary neighbor which S might select,
   except for N_i itself, will not go via N_i to reach the destination
   D.

   Since a router S has multiple potential primary neighbors, router S
   MUST select one or more alternates for breaking U-Turns from among
   next-hops to its potential primary neighbors.  If router S does not
   have a potential primary neighbor that is node-protecting for a
   particular primary next-hop, that indicates that the particular
   primary neighbor will not use S as a U-turn alternate.

   Router S need not use the same alternate(s) for breaking U-Turns on
   traffic received from a primary next-hop as for when the primary
   next-hop fails.  The alternate(s) used when a primary next-hop fails
   are a router-local decision.

4. Using an Alternate

   If an alternate is available, it is used in two circumstances.  In
   the first circumstance, it is used to redirect traffic received from
   a primary next-hop neighbor.  In the second circumstance, it is used
   to redirect traffic when the primary next-hop has failed.  As
   mentioned in Section 3.2.4.2, for destinations with multiple
   potential primary neighbors, the alternates used for each purpose
   need not be the same.

4.1. Breaking U-Turns

   If one ignores potential security redirection, IP forwarding is a



Atlas et al.                                                   [Page 19]


Internet Draft                                               August 2004


   purely destination based algorithm.  Traffic is forwarded based upon
   the destination IP address, regardless of the incoming interface.

                           +--------------------------+
                           |          N_1             |
                           |                          |
                           |   primary    alternate   |
                           | D:  S            R_1     |
                           | C:  R_1          R_2     |
                           |                          |
                           |--------+--------+--------|
                           | D: R_1 | D: S   | D: S   |
                           | C: R_1 | C: R_1 | C: R_2 |
                           +--------------------------+
                             /           |         \
                            / L_1        | L_2      \ L_3
                           /             |           \
                          /           +-----+         \
                       +-----+        | R_2 |          \
                       |  S  |        +-----+         +-----+
                       +-----+          /             | R_1 |
                        /              /              +-----+
                       /              /                   /
                      /              /                   /
               +-----+              /          /--------/
               |  P  |             /          /
               +-----+         __ /  __      /
                   \          /  \  /  \    /
                    \        /    \/    \  /
                     \------ |           |
                              \ CLOUD   /
                             _/         |
                            /           |
                            \_   ___   /
                             /\_/   \_/
                            /          \
                           /            \
                          /            +-----+
                       +-----+         |  D  |
                       |  C  |         +-----+
                       +-----+

                    Figure 7: Example Forwarding Table

   As previously described in Section 3.1.2, IP/LDP Local Protection
   requires that a U-Turn neighbor be capable of detecting traffic
   coming from the primary next-hop neighbor and redirecting it to the
   alternate, if an alternate which is node-protecting is available.



Atlas et al.                                                   [Page 20]


Internet Draft                                               August 2004


   This becomes the new default behavior.  This behavior is described
   below.  A router which indicates that it is capable of breaking U-
   Turns on an interface MUST obey the following behavior on that
   interface.

        For an IP destination
            If the packet was received on an interface connected
                  to a primary neighbor
               then if the interface is U-Turn Breaking Capable
                   then if that primary next-hop has a loop-free
                             node-protecting alternate
                           then forward the packet to that alternate
                        else if interface is point-to-point
                             then discard
                             else if interface is configured for ICMP redirection
                                  then forward to primary and
                                       send ICMP redirect according to RFC 792
                                  else discard
                    else forward to a primary next-hop
            else forward to a primary next-hop

                              New Forwarding Rule

   To clarify the above behavior, consider the example below in Figure
   7. In this case, router N_1 has a primary and an alternate for two
   destinations D and C. The primary next-hop for destination D is
   router S and the alternate next-hop is R_1.  Similarly, the primary
   next-hop for destination C is router R_1 and the alternate next-hop
   is R_2.   The three interfaces L_1, L_2, and L_3 shown on router N_1
   have different forwarding tables as shown in Figure 7; additional
   interfaces would have the same forwarding table as for interface L_2,
   which is not a primary next-hop for either destination.

4.1.1. Broadcast and NBMA Interfaces

   With broadcast interfaces (i.e. Gigabit Ethernet) and NBMA
   interfaces, there can be multiple neighbors connected to the same
   interface.  The NBMA and broadcast interfaces can be treated
   identically for IP/LDP Local Protection.

   It is extremely desirable to have at most one forwarding table per
   interface.  Therefore, it must be considered whether all traffic
   received on an interface can be treated identically, regardless of
   the neighbor sourcing the traffic on that interface.

   The cost for any node on the broadcast interface to reach S or P will
   be identical.  Because all link costs are positive, no neighbor on
   the broadcast interface will ever send traffic to S along that



Atlas et al.                                                   [Page 21]


Internet Draft                                               August 2004


   interface in order to reach P.  Therefore, S can assume that any
   traffic received on the broadcast interface which goes to a
   destination via a primary next-hop neighbor that is also on the
   broadcast interface is in fact sent by that primary next-hop neighbor
   and should be redirected to break the U-Turn.

                 +-----------+-----------+------------+----------+
                 |           |           |            |          |
                 |           | /P\       | /P\        | /P\      | /P\
                 | 2        3|  |       3|  |        4|  |      5|  |
                 |           |           |            |          |
              +-----+      +-----+     +-----+     +-----+    +-----+
              |  P  |      |  S  |     | N_1 |     | N_2 |    | N_3 |
              +-----+      +-----+     +-----+     +-----+    +-----+
                 \            \  10
             \    \ 10      @  \________
              \|   \         @|         \
              -+    \        -+       +-----+
                     \        ________| N_4 |
                      \      /   10   +-----+
                    +-----+ /
                    |  D  |/
                    +-----+

                Figure 8: Topology With Broadcast Interface

   Thus, if router S has a primary next-hop neighbor for a given prefix
   on the broadcast interface, S should redirect all traffic received
   destined to that prefix on the broadcast interface to S's alternate
   next-hop.

   This does assume that all neighbors on a broadcast interface are
   routers or are properly configured hosts.  If this assumption is
   acceptable for a particular broadcast or NBMA interface, then traffic
   received on the interface, which is configured to be U-turn capable,
   for which there is no loop-free node-protecting alternate will be
   discarded.  If this assumption is not acceptable, i.e. if there is a
   locally connected host, then traffic received on the interface, which
   is configured to be U-turn capable, for which there is no loop-free
   node-protecting alternate should be forwarded back out the interface
   (i.e. to the primary) and an ICMP Redirect should be sent to the
   originating host.

   An interface can be either a primary next-hop or the alternate next-
   hop, but not both because there would be no protection if the
   interface failed.

4.2. Responding to a Local Failure



Atlas et al.                                                   [Page 22]


Internet Draft                                               August 2004


   When a local interface failure is detected, traffic that was destined
   to go out the failed interface must be redirected to the appropriate
   alternate next-hops.  The alternate next-hop is pre-computed to be
   reliable in the event of the failure scenario being protected against
   (i.e. link or node failure).

   IP/LDP Local Protection does not attempt to add anything new to the
   detection of the failure.  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 to use it,
   exactly as is the case with RSVP-TE Fast-Reroute.

5. Requirements on LDP Mechanics

   In order for LDP to take advantage of the alternate next-hops
   determined, 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 Switched Router (LSR) running LDP must
   distribute its labels for the 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 which correspond to interfaces that aren't currently
   the primary next-hop are stored.  Similarly, LDP should be in
   downstream unsolicited mode, so that the labels for the FEC are
   distributed other than along the SPT.

6. Routing Interactions

   Just as a standard SPF is run on a particular area or level to find
   the primary next-hops, IP Local Protection determines the alternates
   to use for a particular area or level.  An IGP must determine how to
   use those alternates for routes which are not in the local area.
   Additionally, those alternates must be communicated properly to LDP
   and BGP for their use.  IP Local Protection provides alternate paths
   for IGP destinations.  The alternates are provided to LDP and BGP for
   forwarding purposes only; the alternates are not redistributed in any
   fashion into other protocols.

6.1. OSPF Inter-Area Routing

   Each area in OSPF has its own link state database and corresponding
   topology.  IP Local Protection provides the primary next-hops and
   alternate next-hop for each Area Border Router.  The alternates for
   summary routes which can be reached via a particular Area Border
   Router (ABR) will be inherited from the ABR, just as the primary
   next-hops are currently.



Atlas et al.                                                   [Page 23]


Internet Draft                                               August 2004


   The complexity occurs when there is a set of ABRs which are
   equidistant from the router S and those ABRs are summarizing a common
   set of inter-area destinations.  This is a case where the router S
   will select from the primary next-hops to reach each of the ABRs in
   the set in order to form an ECMP set to reach the inter-area
   destination(s).

   Additional alternate inheritance rules are necessary in this case;
   the rules to follow depend upon the nature of the candidates for the
   ECMP set.  There are two scenarios, which will be explained in
   reference to Figure 9.

                          .........
                     .....         .....
                  ...                   ...
               ...     +-----+             ...
              .       /| A_1 |-------------\  .
             .       / +-----+              \  .
            .       /                        \-+-----+   5
          ..       /                           |ABR 1|--------\
          .       /        5    +-----+--------+-----+         \
         .       /     /--------| N_1 |    5       .            \
         .    +-----+-/         +-----+            .          +-----+
         .    |  S  |                              .          |  D  |
        .     +-----+-\                             .         +-----+
        .         \    \                            .       5    /
         .         \    \       +-----+            .    /-------/
         .          \    \------| N_2 |  5         .   /
         .           \          +-----+-------+-----+ /
          .           \                       |ABR.2|/
          ..          +-----+               /-+-----+
            .         | A_2 |--------------/    .
             .        +-----+                  .
              .                               .
               ...                         ...
                  ...   area 0          ...
                     .....         .....
                          .........

     Figure 9: Inheriting Alternates for ECMP Inter-Area Destinations

        1. ECMP Inter-Area Destination with more than one potential
        primary neighbor.

        2. ECMP Inter-Area Destination with a single primary neighbor.

   In Scenario 1, the paths from S to ABR-1 and ABR-2 are node-
   protecting with respect to each other; each neighbor is reached via a



Atlas et al.                                                   [Page 24]


Internet Draft                                               August 2004


   different primary next-hop to reach the destination D.  In this case,
   the primary next-hop to reach N_1 can be used as the alternate next-
   hop for N_2 and vice versa.  Finding the alternate next-hops in this
   scenario is straightforward, because the paths to ABR-1 and ABR-2 are
   disjoint.

   In Scenario 2, the primary neighbor to reach ABR-1 and ABR-2 is the
   same, so the alternate must protect against both the link to N_1
   failing and N_1 itself failing.  Let the set of ABRs which can be
   used to reach the destination be indexed up to T.  A loop-free node-
   protecting alternate A_i is a candidate if the following is true.

                              forall_t in T,
         if (D_opt(A_i, D) == D_opt(A_i, ABR_t) + D_opt(ABR_t, D))
            D_!S(A_i, ABR_t) < D_opt(A_i, S) + D_opt(S, ABR_t)

   The selection criteria between candidate alternate next-hops
   associated with ABRs in an ABR set MUST be as follows, for the same
   reason as described in Section 3.2.4.4.


        1. If there is one or more loop-free node-protecting alternates
        associated with one ABR in the set of ABRs, then router MUST
        select one of those alternates.  Let M be the set of neighbors
        which provide loop-free node-protecting alternates to at least
        one ABR in the set of ABRs.  If S has multiple loop-free node-
        protecting alternates, then S MUST select the alternate through
        N_k such that Equation 6 is satisfied.

        2. If there are no loop-free node-protecting alternates
        associated with an ABR in a set of ABRs, then S can select
        freely among the appropriate ABR alternates which are available.

6.2. 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.3. ISIS Multi-Level Routing




Atlas et al.                                                   [Page 25]


Internet Draft                                               August 2004


   Rules for alternate inheritance between levels in ISIS are the same
   as for OSPF inter-area routing.

6.4 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 IP Local Protection 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 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 MUST be followed here as well.

6.5 BGP Next-Hop Synchronization
   BGP simply inherits the alternate next-hop based upon the IGP
   destination which was selected.  The BGP decision process is
   unaltered.

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

   As described in RFC 3137, 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 consider diverting from
   the SPF tree along a link whose reverse cost is LSInfinity (for OSPF)
   or whose router has the overload bit set (for ISIS).

   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 cannot consider
   using N_i as an alternate.  If all links from a neighbor N_i to a
   neighbor's neighbor R_i_j have a reverse cost of LSInfinity, then
   router S cannot consider that N_i could provide a U-turn alternate
   via R_i_j.



Atlas et al.                                                   [Page 26]


Internet Draft                                               August 2004


   Similarly in the case of ISIS, if N_i has the overload bit set, then
   S cannot consider using N_i as an alternate.  If a neighbor's
   neighbor R_i_j has the overload bit set, then router S cannot
   consider that N_i could provide a U-turn alterante via R_i_j.

   This preserves the desired behavior of diverting traffic away from a
   router which is following RFC 3137 and it also preserves the desired
   behavior when an operator sets the cost of a link to LSInfinity 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.

6.7 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. Intellectual Property Considerations

   Avici Systems has intellectual property rights claimed in regard to
   the specification contained in this document.

9.  Full Copyright Statement

   Copyright (C) The Internet Society (2002). 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



Atlas et al.                                                   [Page 27]


Internet Draft                                               August 2004


   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.

10. References

   [OSPF-LOCAL-PROTECT] A. Atlas, R. Torvi, G. Choudhury, B. Imhoff, C.
   Martin, D. Fedyk, "OSPFv2 Extensions for Link Capabilities and IP/LDP
   Local Protection", draft-atlas-ospf-local-protect-cap-00.txt,
   February 2004, work-in-progress

   [ISIS-LOCAL-PROTECT] A. Atlas, R. Torvi, C. Martin, "ISIS Extensions
   for Signaling Local Protection Capabilities", draft-martin-isis-
   local-protect-cap-00.txt, February 2004, work-in-progress

   [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-
   04.txt, February 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




Atlas et al.                                                   [Page 28]


Internet Draft                                               August 2004


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

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

11. Authors Information

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

   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



Atlas et al.                                                   [Page 29]


Internet Draft                                               August 2004


   600 Technology Park
   Billerica, MA 01450
   email: dwfedyk@nortelnetworks.com
   phone: +1 978 288 3041















































Atlas et al.                                                   [Page 30]


Html markup produced by rfcmarkup 1.129d, available from https://tools.ietf.org/tools/rfcmarkup/