INTERNET DRAFT      IP Fast-reroute Using Tunnels              Apr 2005
 Network Working Group                                     S. Bryant
 Internet Draft                                          C. Filsfils
 Expiration Date: Oct 2005                                S. Previdi
                                                            M. Shand
                                                       Cisco Systems
                                                            Apr 2005
                      IP Fast Reroute using tunnels
 Status of this Memo
    By submitting this Internet-Draft, each author represents that any
    applicable patent or other IPR claims of which he or she is aware
    have been or will be disclosed, and any of which he or she becomes
    aware will be disclosed, in accordance with Section 6 of BCP 79.
    Internet-Drafts are working documents of the Internet Engineering
    Task Force (IETF), its areas, and its working groups.  Note that
    other groups may also distribute working documents as Internet-
    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
    The list of current Internet-Drafts can be accessed at
    The list of Internet-Draft Shadow Directories can be accessed at
    This draft describes an IP fast re-route mechanism that provides
    backup connectivity in the event of a link or router failure. In
    the absence of single points of failure and asymmetric costs, the
    mechanism provides complete protection against any single failure.
    If perfect repair is not possible, the identity of all the
    unprotected links and routers is known in advance.
 Bryant et al.              Expires Oct 2005                    [Page 1]

 INTERNET DRAFT      IP Fast-reroute Using Tunnels              Apr 2005
 Table of Contents
 1. Introduction......................................................4
 2. Goals, non-goals, limitations and constraints.....................4
   2.1. Goals.........................................................4
   2.2. Non-Goals.....................................................5
   2.3. Limitations...................................................5
   2.4. Constraints...................................................5
 3. Repair Paths......................................................6
   3.1. Tunnels as Repair Paths.......................................6
   3.2. Tunnel Requirements...........................................9
     3.2.1. Setup.....................................................9
     3.2.2. Multipoint................................................9
     3.2.3. Directed forwarding.......................................9
     3.2.4. Security..................................................9
 4. Construction of Repair Paths.....................................10
   4.1. Identifying Repair Path Targets..............................10
   4.2. Determining Tunneled Repair Paths............................10
     4.2.1. Computing Repair Paths...................................11
     4.2.2. Extended F-space.........................................12
     4.2.3. Loop-free Alternates.....................................12
     4.2.4. Selecting Repair Paths...................................12
   4.3. Assigning Traffic to Repair Paths............................13
   4.4. When no Repair Path is Possible..............................13
     4.4.1. Unreachable Target.......................................14
     4.4.2. Asymmetric Link Costs....................................14
     4.4.3. Interference Between Potential Node Repair Paths.........14
   4.5. Multi-homed Prefixes.........................................17
   4.6. LANs and pseudo-nodes........................................18
     4.6.1. The Link between Routers S and E is a LAN................19 Case 1...............................................19 Case 2...............................................19 Simplified LAN repair................................20
     4.6.2. A LAN exists at the release point........................20
     4.6.3. A LAN between E and its neighbors........................20
     4.6.4. The LAN is a Transit Subnet..............................21
 5. Failure Detection and Repair Path Activation.....................21
   5.1. Failure Detection............................................21
   5.2. Repair Path Activation.......................................21
   5.3. Node Failure Detection Mechanism.............................21
 6. Loop Free Transition.............................................22
 7. IPFRR Capability.................................................22
 8. Enhancements to routing protocols................................23
 9. IANA considerations..............................................23
 10. Security Considerations...............Error! Bookmark not defined.
    This draft uses the terms defined in [FRMWK]. This section defines
    additional words, acronyms, and actions used in this draft.
 Bryant et al.              Expires Oct 2005                    [Page 2]

 INTERNET DRAFT      IP Fast-reroute Using Tunnels              Apr 2005
    Directed        The ability of the repairing router (S) to
    forwarding      specify the next hop (G) on exit from a
                    tunnel end-point (F)
    Extended F-     The union of the F-space of the neighbors of
    space           a specific router with respect to a common
                    Extended F-space does not include the
                    additional space reachable though directed
    F               The router in F-space to which a packet is
                    tunneled for repair.
    FG              A router that is in both F and G space and
                    hence does not need directed forwarding.
    F-space         F-space is the set of routers reachable from
                    a specific router without any path
                    (including equal cost path splits)
                    transiting a specified component.
                    For example, the F-space of S, is the set of
                    routers that S can reach without using E
                    (router failure case) or the S-E link
                    failure case).
    G               The router in G space, to which the packet
                    is directed by router F on exit from the
                    repair tunnel. G will always be adjacent to
                    F, or F itself.
    G-space         G-space is the set of routers from which a
                    specific router can be reached without any
                    path (including equal cost path splits)
                    transiting a specified component.
    Interference    The condition where the network costs are
                    such that a repairing router cannot tunnel a
                    packet sufficiently far from a failed node
                    such that it is not attracted back to the
                    failed node via another of that node's
 Bryant et al.              Expires Oct 2005                    [Page 3]

 INTERNET DRAFT      IP Fast-reroute Using Tunnels              Apr 2005
 1.    Introduction
    When a link or node failure occurs in a routed network, there is
    inevitably a period of disruption to the delivery of traffic until
    the network re-converges on the new topology. Packets for
    destinations which were previously reached by traversing the failed
    component may be dropped or may suffer looping. Traditionally such
    disruptions have lasted for periods of at least several seconds,
    and most applications have been constructed to tolerate such a
    quality of service.
    Recent advances in routers have reduced this interval to under a
    second for carefully configured networks using link state IGPs.
    However, new Internet services are emerging which may be sensitive
    to periods of traffic loss which are orders of magnitude shorter
    than this.
    Addressing these issues is difficult because the distributed nature
    of the network imposes an intrinsic limit on the minimum
    convergence time which can be achieved.
    However, there is an alternative approach, which is to compute
    backup routes that allow the failure to be repaired locally by the
    router(s) detecting the failure without the immediate need to
    inform other routers of the failure. In this case, the disruption
    time can be limited to the small time taken to detect the adjacent
    failure and invoke the backup routes. This is analogous to the
    technique employed by MPLS Fast Reroute [MPLSFRR], but the
    mechanisms employed for the backup routes in pure IP networks are
    necessarily very different.
    A framework for IP Fast Reroute [IPFRR] provides a summary of the
    proposed IPFRR solutions, and a partial solution using equal cost
    multi-path and loop-free alternate case is described in [BASIC].
    This draft describes extensions to the basic repair mechanism in
    which we propose the use of tunnels to provide additional logical
    downstream paths. These mechanisms provide almost 100% repair
    connectivity in practical networks.
 2.    Goals, non-goals, limitations and constraints
 2.1.      Goals
    The following are the goals of IPFRR:
         o  Protect against any link or router failure in the network.
         o  No constraints on the network topology or link costs.
 Bryant et al.              Expires Oct 2005                    [Page 4]

 INTERNET DRAFT      IP Fast-reroute Using Tunnels              Apr 2005
         o  Never worse than the existing routing convergence
         o  Co-existence with non-IP fast-reroute capable routers in
            the network.
 2.2.      Non-Goals
    The following are non-goals of IPFRR:
         o  Protection of a single point of failure.
         o  To provide protection in the presence of multiple
            concurrent failures other than those that occur due to the
            failure of a single router.
         o  Shared risk group protection.
         o  Complete fault coverage in networks that make use of
            asymmetric costs.
 2.3.      Limitations
    The following limitations apply to IPFRR:
         o  Because the mechanisms described here rely on complete
            topological information from the link state routing
            protocol, they will only work within a single link state
            flooding domain.
         o  Reverse Path Forwarding (RPF) checks cannot be used in
            conjunction with IPFRR. This is because the use of tunnels
            may result in packets arriving over different interfaces
            than expected.
 2.4.      Constraints
    The following constraints are assumed:
         o  Following a failure, only the routers adjacent to the
            failure have any knowledge of the failure.
         o  There is insufficient time following a failure to compute a
            repair strategy based on knowledge of the specific failure
            that has occurred.
         o  Multiple concurrent failures may not be protected.
 Bryant et al.              Expires Oct 2005                    [Page 5]

 INTERNET DRAFT      IP Fast-reroute Using Tunnels              Apr 2005
 3.    Repair Paths
    When a router detects an adjacent failure, it uses a set of repair
    paths in place of the failed component, and continues to use this
    until the completion of the routing transition. Only routers
    adjacent to the failed component are aware of the nature of the
    failure. Once the routing transition has been completed, the router
    will have no further use for the repair paths since all routers in
    the network will have revised their forwarding data and the failed
    link will have been eliminated from this computation.
    Repair paths are pre-computed in anticipation of later failures so
    they can be promptly activated when a failure is detected.
    Three types of repair path are used to achieve the repair:
      1. Equal cost path-split.
      2. Loop-free Alternate.
      3. Tunnel.
    The operation of equal cost path-split and loop-free alternate is
    described in [BASIC]. A tunneled repair path tunnels traffic to
    some staging point from which it will travel to its destination
    using normal forwarding without looping back. The repair path can
    be thought of as providing a virtual link, originating at a router
    adjacent to a failure, and diverting traffic around the failure.
    This is equivalent to providing a virtual loop-free alternate to
    supplement the physical loop-free alternates.
 3.1.      Tunnels as Repair Paths
    The repair strategies described in this draft operate on the basis
    that if a packet can somehow be sent to the other side of the
    failure, it will subsequently proceed towards its destination
    exactly as if it had traversed the failed component. See Figure 1.
        Repair Path from S to E
          |           |
          |           v
    Figure 1 Simple Link Repair
    Creating a repair path from S to E may require a packet to traverse
    an unnatural route. If a suitable natural path starts at a neighbor
    (i.e. it is a loop-free alternate), then S can force the packet
    directly there. If this is not the case, then S may create one by
    using a tunnel to carry the packet to a point in the network where
    there is a real loop-free alternate. Note that the tunnel does not
 Bryant et al.              Expires Oct 2005                    [Page 6]

 INTERNET DRAFT      IP Fast-reroute Using Tunnels              Apr 2005
    have to go from S to E. The tunnel can terminate at any router in
    the network, provided that S can be sure that the packet will
    proceed correctly to its destination from that router.
    A repair path computed for a link failure may not however work
    satisfactorily when the neighboring router has, itself, failed.
    This is illustrated in Figure 2.
         Repair path from S to E
         |                         |
         |            <------------+
         +---------->              |
         |                         |
          Repair Path from S1 to E
    Figure 2 Looping Link Repair when Router Fails
    Consider the case of a router E with just two neighbors S and S1.
    When router E fails, both S and S1 will observe the failure of
    their local link to E, but will have no immediate knowledge that E
    itself has failed. If they were both to attempt to repair traffic
    around their local link, they would invoke mutual repairs which
    would loop.
    Since it is not easy for a router to immediately distinguish
    between a link failure and the failure of its neighbor, repair
    paths are calculated in anticipation of adjacent router failure.
    Thus, for each of its protected links, router S (Figure 3)
    pre-computes a set of tunneled repair paths, one for each of the
    neighbors (S1, S2 and S3) of its neighbor E on the S-E link. The
    set of destinations that are normally assigned to link S-E will be
    assigned to a repair path based on the neighbor of E through which
    router E would have forwarded traffic to them.
 Bryant et al.              Expires Oct 2005                    [Page 7]

 INTERNET DRAFT      IP Fast-reroute Using Tunnels              Apr 2005
             Repair S-S1
           |             |
           |             |
           |             |
           ||            |           ^
           ||            |           |
           ||Repair S-S3 |           |
           |+---------->[S3]         |
           |                         |
              Repair S-S2
    Figure 3: Repair paths in anticipation of a router failure
    The set of repair paths in Figure 3 will function correctly in the
    case of link and router failure. However, in some network
    topologies they may not provide a means for traffic to reach router
    E itself. This is important in cases where E is a single point of
    failure and E is still functional (i.e. the failure was actually a
    failure of the S-E link). Hence, in addition to computing repair
    paths for the neighbors of its neighbor on a protected link, a
    router also calculates a repair path for the neighbor itself. This
    is illustrated in Figure 4.
              Repair S-E
           |                |
           | Repair S-S1    |
           ||            |  /
           ||            | /
           ||            |/
           ||            |           ^
           ||            |           |
           ||Repair S-S3 |           |
           |+---------->[S3]         |
           |                         |
              Repair S-S2
    Figure 4 The full set of S-E repair paths.
    In the event of a failure, the only traffic that is assigned to the
    link repair path (the S-E repair) is that traffic which has no
    other path to its destination except via E. As we have already
    seen, there is a danger that traffic assigned to this link repair
    path may loop if E has failed, therefore, when the repair paths are
 Bryant et al.              Expires Oct 2005                    [Page 8]

 INTERNET DRAFT      IP Fast-reroute Using Tunnels              Apr 2005
    invoked, a loop detection mechanism is used which promptly detects
    the loop and, upon detection, withdraws the link (S-E) repair path
    from service.
 3.2.      Tunnel Requirements
    There are a number of IP in IP tunnel mechanisms that may be used
    to fulfill the requirements of this design. Suitable candidates
    include IP-in-IP [RFC1853], GRE [RFC1701] and L2TPv3 [L2TPv3]. The
    selection of the specific tunneling mechanism (and any necessary
    enhancements) used to provide a repair path is outside the scope of
    this document. However the following sections describe the
    requirements for the tunneling mechanism.
 3.2.1.        Setup.
    When a failure is detected, it is necessary to immediately redirect
    traffic to the repair paths. Consequently, the tunnels used must be
    provisioned beforehand in anticipation of the failure. IP fast
    re-route will determine which tunnels it requires. It must
    therefore be possible to establish tunnels automatically, without
    management action, and without the need to manually establish
    context at the tunnel endpoint.
 3.2.2.        Multipoint
    To reduce the number of tunnel endpoints in the network the tunnels
    should be multi-point tunnels capable of receiving repair traffic
    from any IPFRR router in the network.
 3.2.3.        Directed forwarding.
    Directed forwarding must be supported such that the router at the
    tunnel endpoint (F) can be directed by the router at the tunnel
    source (S) to forward the packet directly to a specific neighbor.
    Specification of the directed forwarding mechanism is outside the
    scope of this document. Directed forwarding might be provided using
    an enhancement to the IP tunneling encapsulation, or it might be
    provided through the use of a single MPLS label stack entry
    [RFC3032] interposed between the IP tunnel header and the packet
    being repaired.
 3.2.4.        Security
    A lightweight security mechanism should be supported to prevent the
    abuse of the repair tunnels by an attacker. This is discussed in
    more detail in Section 10.
 Bryant et al.              Expires Oct 2005                    [Page 9]

 INTERNET DRAFT      IP Fast-reroute Using Tunnels              Apr 2005
 4.    Construction of Repair Paths
 4.1.      Identifying Repair Path Targets
    To establish protection for a link or node it is necessary to
    determine which neighbors of the neighboring node should be targets
    of repair paths. Normally all neighbors will be used as repair path
    targets. However, in some topologies, not all neighbors will be
    needed as targets because, prior to the failure, no traffic was
    being forwarded through them by the repairing router.  This can be
    determined by examining the normal shortest path tree (SPT)
    computed by the repairing router.
    In addition, the neighboring router E will also be the target of a
    repair path for any destinations for which E is a single point of
 4.2.      Determining Tunneled Repair Paths
    The objective of each tunneled repair path is to deliver traffic to
    a target router when a link is observed to have failed. However, it
    is seldom possible to use the target router itself as the tunnel
    endpoint because other routers on the repair path, that have not
    learned of the failure, will forward traffic addressed to it using
    their least cost path which may be via the failed link. This is
    illustrated in Figure 5 in which all link costs are one in both
    directions. Router S's intended repair path for traffic to D when
    link S-E fails is the path W-X-Y-Z-S1. However, if router S makes
    S1 be the tunnel endpoint and forwards the packet to router W,
    router W will immediately return it to S because its least cost
    path to S1 is S-E-S1 (cost 3 versus cost 4) and has no knowledge of
    the failure of link S-E.
                |                 |
                |                 |
    Figure 5. Repair path to target router S1.
    Thus the tunnel endpoint needs to be somewhere on the repair path
    such that packets addressed to the tunnel end point will not loop
    back towards router S. In addition, the release point needs to be
    somewhere such that when packets are released from the tunnel they
    will flow towards the target router (or their actual destination)
    without being attracted back to the failed link. By inspection, in
    Figure 5, suitable tunnel endpoints are routers X, Y, and Z.
    Note that it is not essential that traffic assigned to a repair
    path actually traverse the target router for which the repair path
 Bryant et al.              Expires Oct 2005                   [Page 10]

 INTERNET DRAFT      IP Fast-reroute Using Tunnels              Apr 2005
    was created. If, for example, in Figure 5, if a packet's
    destination were normally reached via the path S-E-S1-Z-?-?-?, once
    it was released at any of the possible tunnel endpoints, it would
    arrive at its destination by the best available route without
    traversing S1.
    In general, the properties that are required of tunnel endpoints
         o  the end point must be reachable from the tunnel source
            without traversing the failed link; and
         o  when released, tunneled packets will proceed towards their
            destination without being attracted back over the failed
            link or node.
    Provided both of these conditions are met, packets forwarded on the
    repair path will not loop.
    In some topologies it will not be possible to find a tunnel
    endpoint that exhibits both the required properties. For example,
    in Figure 5, if the cost of link X-Y were increased from one to
    four in both directions, there is no longer a viable endpoint
    within the fragment of the topology shown.
    To solve this problem we introduce the concept of directed
    forwarding from the tunnel endpoint. Directed forwarding allows the
    originator of a tunneled packet to instruct that, when it is
    decapsulated at the end of the tunnel, it be forwarded via a
    specific adjacency, and not be subjected to the normal forwarding
    decision process. This effectively allows the tunnel to be extended
    by one hop. So, for example, in Figure 5 with the cost of link X-Y
    set to four, it would be possible to select X as the tunnel
    endpoint with the directive that X always forward the packets it
    decapsulates via the adjacency to Y. Thus, router X is reached
    from S using normal forwarding, and directed forwarding is then
    used to force packets to router Y, from where S1 can be reached
    using normal forwarding.
    Provided link costs are symmetrical, it can be proved that it is
    always possible to compute a tunneled repair path (possibly using
    directed forwarding) around a link failure, and that the tunnel
    endpoint (F) and the release point (G) will be coincident, or may
    be separated by at most one hop.
 4.2.1.        Computing Repair Paths
    For a router S, determining tunneled repair paths around a
    neighboring router E, the set of potential tunnel end points
    includes all the routers that can be reached from S using normal
    forwarding without traversing the failed link S-E. This is termed
    the "F-space" of S with respect to the failure of E. Any router
 Bryant et al.              Expires Oct 2005                   [Page 11]

 INTERNET DRAFT      IP Fast-reroute Using Tunnels              Apr 2005
    that is on an equal cost path split via the failed link is excluded
    from this set.
    The resulting set defines all the possible tunnel end points that
    could be used in repair paths originating at router S for the
    failure of link S-E. This set can be obtained by computing an SPT
    rooted at S and excising the sub-tree reached via the S-E link.
    The set of possible release points can be determined by computing
    the set of routers that can reach the repair path target without
    traversing the failed link. This is termed the "G-space" of the
    target with respect to the failure. The G-space can be obtained by
    computing a reverse shortest path tree (rSPT) rooted at the repair
    path target, with the sub-tree which traverses the failed link (or
    node) excised. The rSPT uses the cost towards the root rather than
    from it and yields the best paths towards the root from other nodes
    in the network.
    The intersection of the target's G-space with S's F-space includes
    all the possible release points for any repair path not employing
    directed forwarding. Where there is no intersection, but there
    exist a pair of routers, F in S's F-space and G in the target's
    G-space, router F can be used as the tunnel endpoint with directed
    forwarding to the release point G.
 4.2.2.        Extended F-space
    The description in section 4.2.1 calculated router S's F-space
    rooted at S itself. However, since router S will only use a repair
    path when it has detected the failure of the link S-E, the initial
    hop of the repair path need not be subject to S's normal forwarding
    decision process. Thus we introduce the concept of extended F-
    space. Router S's extended F-space is the union of the F-spaces of
    each of S's neighbors. The use of extended F-space may allow router
    S to repair to targets that were otherwise unreachable.
 4.2.3.        Loop-free Alternates
    When a loop-free alternate exists, no tunneling is required.
 4.2.4.        Selecting Repair Paths
    The mechanisms described above will identify all the possible
    release points that can be used to reach each particular target.
    (The circumstances when no release points exist are described in
    section 4.4.) In a well-connected network there are likely to be
    multiple possible release points for each target, and all will work
    correctly. For simplicity, one release point per target is chosen.
    All will deliver the packets correctly so, arguably, it does not
    matter which is chosen. However, one release point may be preferred
    over the others on the basis of path cost or some other criteria.
 Bryant et al.              Expires Oct 2005                   [Page 12]

 INTERNET DRAFT      IP Fast-reroute Using Tunnels              Apr 2005
    It is an implementation matter as to how the release point is
 4.3.      Assigning Traffic to Repair Paths
    Once the repair path for each target has been selected, it is
    necessary to determine which of the destinations normally reached
    via the protected link should be assigned to which of the repair
    paths when the link fails.
    This is achieved by recording which neighbor of E would be used to
    reach each destination reachable over S-E when running the original
    SPF. Traffic assignment is then simply a matter of assigning the
    traffic which E would have forwarded via each neighbor to the
    repair path which has that neighbor as its target.
    Although the repair paths are calculated based on traffic addressed
    to specific targets, it can be proved that the traffic assignment
    algorithm guarantees that the repair path can be used for any
    traffic assigned to it.
    Where E would normally split the traffic to a particular
    destination via two or more of its neighbors, it is an
    implementation decision whether the repaired traffic should be
    split across the corresponding set of repair paths.
    The repair path to E itself is normally used just for traffic
    destined for E and any prefixes advertised by E. However, under
    some circumstances, it may be impossible to compute a repair path
    to one or more of E's neighbors, for example, because E is a single
    point of failure. In this case traffic for the destinations served
    by the otherwise irreparable targets is assigned to the repair path
    with E as its target, in the optimistic assumption that router E is
    still functioning. If router E is indeed still functioning, this
    will ensure delivery of the traffic. If, however, router E has
    failed, the traffic on this repair path will loop as previously
    shown in section 3.1. The way this is detected, and the course of
    action when it is detected, is described in section 5.3.
 4.4.      When no Repair Path is Possible
    Under some circumstances, it will not be possible to identify a
    repair path to one or more of the targets. This can occur for the
    following reasons:
         o  The neighboring router that is presumed to have failed
            constitutes a single point of failure in the network.
         o  Severely asymmetric link costs may cause an otherwise
            viable physical repair path to be unusable.
 Bryant et al.              Expires Oct 2005                   [Page 13]

 INTERNET DRAFT      IP Fast-reroute Using Tunnels              Apr 2005
         o  Interference may occur between the repair paths of
            individual targets.
    In practice, these cases are unlikely to be encountered frequently.
    Networks that will benefit from the mechanisms described here will
    usually exhibit considerable redundancy and are normally operated
    with largely symmetric link costs. Note that a router's inability
    to compute a full set of repair paths for one of its links does not
    necessarily affect its ability to do so for its other links.
    Example topologies illustrating each of the three cases above are
    described in the following subsections.
 4.4.1.        Unreachable Target
    If the failure of a neighboring router makes one or more of its
    neighbors genuinely unreachable, clearly it will not be possible to
    establish a repair path to such targets. Such single points of
    failure are not expected to be encountered frequently in properly
    designed networks, and will probably occur only when the network
    has previously suffered other failures that have reduced its
 4.4.2.        Asymmetric Link Costs
    When link costs have been set asymmetrically, it is possible that a
    repair path cannot be constructed even using directed forwarding.
    Although it is trivial to construct a network fragment with this
    property, this should not be regarded as a major problem. Firstly,
    asymmetric link costs are seldom used deliberately. And, secondly,
    even when an asymmetric link cost prevents one potential repair
    path being used, there will normally be other ones available.
 4.4.3.        Interference Between Potential Node Repair Paths
    Under some circumstances the existence of one neighbor may
    interfere with a potential repair path to another. Consider the
    topology shown in Figure 6, in which all links have a symmetrical
    cost of one, with the exception of that between H and I, which has
    a cost of 3. In this example, the fact that router J is a neighbor
    of E prevents the discovery of a repair path from router S to
    router S1 despite the existence of an apparently suitable path.
 Bryant et al.              Expires Oct 2005                   [Page 14]

 INTERNET DRAFT      IP Fast-reroute Using Tunnels              Apr 2005
                     |          |         |
                     |          |         |
    Figure 6. Interference between repair paths
    A repair path from router S to J can use J itself as the release
    point by employing directed forwarding from I. However, it is not
    possible to identify a suitable release point for a repair path to
    router S1 within the topology shown since there is nowhere that
    router S can reach that will subsequently forward traffic to
    router S1 except via the forbidden link E-S1 (J's least cost path
    to S1 is J-E-S1). This is because the extended F-space of router S
    is separated by more than one hop from the G-space of router S1.
    Since the topology shown in Figure 6 will typically form part of a
    much larger topology, a different, and possibly more circuitous
    repair path from S to S1, that does not go via J, may be
    discovered. This is illustrated in Figure 7. In this enhanced
    topology, a repair path to S1 using Y as the release point can be
       |          |         |
       |          |         |
             |         |
             |         |
    Figure 7. Resolving interference in a larger network
    Note that, in Figure 6, if the traffic for S1 were assigned to the
    repair path for J, it would correctly reach S1 because J would
    assign it to its repair path to S1. That is, packets from S to S1
    would travel via two successive tunnels. Consequently, this is
    referred to as a "secondary repair path". However, it is not always
    the case that interference can be handled in this fashion and it is
    possible to create looping repair paths.
    One possibility of looping repair paths is illustrated in Figure 8.
    All links have a symmetrical cost of one with the exception of H-I,
    which is cost 3 in both directions, and K-L and L-S1 which are cost
    5 in the indicated direction and cost 1 in the other.
 Bryant et al.              Expires Oct 2005                   [Page 15]

 INTERNET DRAFT      IP Fast-reroute Using Tunnels              Apr 2005
         |          |          |^
         |          |          |5
    Figure 8 Looping secondary repair paths
    In this topology, S can establish a repair path to J, but cannot
    establish a repair path to S1 because of interference. Router S
    might assign traffic intended for S1 onto its repair path to J
    expecting it to undergo a secondary repair towards S1. However,
    because of the asymmetrical link costs, J is unable to establish a
    repair path to S1. It is only able to establish a repair path to S.
    If J, like S, elected to forward repaired traffic to S1 using its
    (only) repair path to S, similarly expecting a secondary repair to
    get it to its destination, traffic for S1 would loop between S
    and J. Thus when interference occurs, the possibility of a
    secondary repair path cannot be relied upon to ensure that traffic
    reaches its destination.
    In order to determine the viability of secondary repair paths, it
    is necessary for each router to take into account the repair paths
    which the other neighbors of router E can achieve. These can be
    computed locally by running the repair path computation algorithms
    rooted at each of those neighbors. It is only necessary to compute
    the repair paths from the routers to which router S can establish
    repair paths, with targets of those routers to which repair paths
    have not yet been established.
    It is then possible to determine whether all routers can now be
    reached by invoking secondary (or if necessary tertiary, etc.)
    repair paths, and if so, to which primary repair path traffic for
    each target should be assigned.
    There is another, more subtle, possibility of loops arising when
    secondary repair paths are used. This is illustrated in Figure 9,
    where all links are cost 1 with the exception of L-K which has a
    cost 5 in that direction and cost 1 in the direction K-L.
                 |          |          |
                 |          |          |
                [L]         |         [D]
                5|          |          |
                v|          |          |
    Figure 9 Example of an apparently non-looping secondary repair path
    which results in a loop.
 Bryant et al.              Expires Oct 2005                   [Page 16]

 INTERNET DRAFT      IP Fast-reroute Using Tunnels              Apr 2005
    Router S has a primary repair path to I (with a release point
    of K), and I has a primary repair path to S1 (with a release point
    of E). It would appear that these form a non-looping secondary
    repair path from S to S1. As usual, the primary repair path from S
    to I has been computed on the basis of destinations normally
    reachable through E-I. However, when making use of the secondary
    repair path, the traffic inserted in the repair path from S to I
    will be destined not for one of the routers normally reachable via
    E-I, but for S1. Hence this repair path is not necessary valid for
    such traffic and in this example it will have a 50% probability of
    being forwarded back along the path K-L-S-E-S1, and hence looping.
    This problem can in general be avoided by choosing a release point
    for the initial primary repair with the property that traffic for
    the secondary target (S1) is guaranteed to traverse the primary
    target (I). This can be achieved by computing the rSTF rooted at
    the secondary target (S1) and examining the sub-tree which
    traverses the primary target. It can be proved that in the absence
    of asymmetric link costs, such a release point will always exist.
    Where asymmetric link costs prevent this, the traffic can be
    encapsulated to the intermediate router (I), which may require the
    use of double encapsulation. On reaching router I, the traffic for
    S1 is decapsulated and then forwarded in I's primary repair path to
    S1 (via router E, in the example).
 4.5.      Multi-homed Prefixes
    Up to this point, it has been assumed that any particular prefix is
    "attached" to exactly one router in the network, and consequently
    only the routers in the network need be considered when
    constructing repair paths, etc. However, in many cases the same
    prefix will be attached to two or more routers. Common cases are:
         o  The subnet present on a link is advertised from both ends
            of the link.
         o  Prefixes are propagated from one routing domain to another
            by multiple routers.
         o  Prefixes are advertised from multiple routers to provide
            resilience in the event of the failure of one of the
    In general, this causes no particular problems, and the shortest
    route to each prefix (and hence which of the routers to which it is
    attached should be used to reach it) is resolved by the normal SPF
    process. However, in the particular case where one of the instances
    of a prefix is attached to router E, or to a router for which
    router E is a single point of failure, the situation is more
 Bryant et al.              Expires Oct 2005                   [Page 17]

 INTERNET DRAFT      IP Fast-reroute Using Tunnels              Apr 2005
     |                     |                       p
     |                     |                       |
    Figure 10 A multi-homed prefix p
    Consider a prefix p, which is attached to router E and some other
    router N as illustrated in Figure 10. Before the failure of the
    link S-E, p is reachable from S via S-E. After the failure it
    cannot be assumed that E is still reachable. If traffic to p is
    assigned to a link repair path to E (as it would be if p were
    attached only to E), and router E has failed, then it would loop
    and subsequently be dropped. Traffic for p cannot simply be
    assigned to whatever repair path would be used for traffic to N,
    because other routers, which are not yet aware of any failure, may
    direct the traffic back towards E, since the instance of p attached
    to E is closer.
    A solution is to treat p itself as a neighbor of E, and compute a
    repair path with p as a target. However, although correct, this
    solution may be infeasible where there are a very large number of
    such prefixes, which would result in an unacceptably large
    computational overhead.
    Some simplification is possible where there exist a large number of
    multi-homed prefixes which all share the same connectivity and
    metrics. These may be treated as a single router and a single
    repair path computed for the entire set of prefixes.
    An alternative solution is to tunnel the traffic for a multi-homed
    prefix to the router N where it is also attached (see Figure 10).
    If this involves a repair path that was already tunneled, then this
    requires double encapsulation.
 4.6.      LANs and pseudo-nodes
    In link state protocols a LAN is represented by a construct known
    as a pseudo-node in IS-IS and a network LSA in OSPF.
    In order to deal correctly with this representation of LANs, the
    algorithms described in this draft require certain modifications.
    There are four cases which require consideration. These are
    described in the following subsections.
 Bryant et al.              Expires Oct 2005                   [Page 18]

 INTERNET DRAFT      IP Fast-reroute Using Tunnels              Apr 2005
 4.6.1.        The Link between Routers S and E is a LAN
    In this case, the link which is being protected is a LAN, and the
    router E which has potentially failed is reachable over the LAN.
    This is illustrated in Figure 11.
      |    |       |      |
     [E]  [X]     [Y]    [Z]
    Figure 11 The link between routers S and E is a LAN
    There are two possible failure modes in this case.          Case 1
    Router E or its interface to the LAN may have failed independently
    of the rest of the LAN. In this case the remaining routers on the
    LAN (routers X, Y and Z) will remain reachable from router S. These
    routers do not appear as direct neighbors of router E in the link
    state database and are not treated as neighbors of router E for the
    purposes of this specification because no traffic from router S
    would be directed through router E to any of these routers.
    However, each of these neighboring routers will have router E as a
    neighbor and they will initiate their own repair paths in the event
    of the failure of router E or its LAN interface.
    Repair paths are computed with the non-LAN neighbors of E as
    targets, and also E itself (the "link-failure" repair path). Note
    that since the remaining neighbors of S on the LAN are assumed to
    be still reachable when the link to E has failed, these repair
    paths may traverse the LAN.
    A separate set of repair paths is required in anticipation of the
    potential failure of each router on the LAN.          Case 2
    Router S's interface to the LAN may have failed (or the entire LAN
    may have failed). In either event, simultaneous failures will be
    observed from router S to all the remaining routers on the LAN
    (routers E, X, Y and Z). In this case, the pseudo-node itself can
    be treated as the "adjacent" router (i.e. the router normally
    referred to as "router E"), and repairs constructed using the
    normal mechanisms with all the neighbors of the pseudo-node
    (routers E, X, Y and Z) as repair path targets. If one or more of
    the routers had failed in addition to the LAN connectivity,
    treating it as a repair path target would not be viable, but this
 Bryant et al.              Expires Oct 2005                   [Page 19]

 INTERNET DRAFT      IP Fast-reroute Using Tunnels              Apr 2005
    would be a case of multiple simultaneous failures which is out of
    scope of this specification.
    The entire sub-tree over S's LAN interface is the failed component
    and is excised from the SPT when computing S's extended F-space.
    For the G-spaces of the targets, the sub-tree over the LAN
    interface of the target is excised.          Simplified LAN repair
    A simpler alternative strategy is to always consider the LAN and
    all routers attached to it as failing as a single unit. In this
    case, a single set of repair paths is computed with targets being
    the entire set of non-LAN neighbors of all the routers on the LAN,
    together with "link-repair" paths with all the routers on the LAN
    as targets. Any failure of one or more LAN adjacencies results in
    these repair paths being invoked for all neighbors on the LAN.
    These repair paths must not traverse the LAN, and so must be
    computed by excising the entire sub-tree reachable over S's LAN
    interface from S's SPT (i.e. the entire LAN is the failed
    component). The G-spaces are computed as normal, with the LAN
    neighbors or their interface to the LAN being excised as
    appropriate. This is simpler than the approach proposed above, but
    will fail to make use of possible repair paths (or even path
    splits) over the LAN. In particular, if the only viable repair
    paths involve the LAN, it will prevent any repair being possible.
 4.6.2.        A LAN exists at the release point
    When computing the viable release points, it may be that one or
    more of the leaf nodes are actually pseudo-nodes. In this case, the
    release point is deemed to be any of the parent nodes on the LAN by
    which the pseudo-node had been reached, and when computing the
    extended set of release points (reachable by directed forwarding),
    all the remaining routers on the LAN may be included.
 4.6.3.        A LAN between E and its neighbors
    If there is a LAN between router E and one or more of E's neighbors
    (other than router S), then rather than treating each of those
    neighbors as a separate target to which a repair path must be
    computed, the pseudo-node itself can be treated as a single target
    for which a repair path can be computed. If there are other
    neighbors of E which are directly attached to E, including those
    which may also be attached to the LAN, they must still be treated
    as an individual repair path target.
    Normally a repair path with the pseudo-node as its target will have
    a release point before the pseudo-node. However it is possible that
    the release point would be computed as the pseudo-node itself. This
    will occur if the rSPT rooted at the pseudo-node includes no
 Bryant et al.              Expires Oct 2005                   [Page 20]

 INTERNET DRAFT      IP Fast-reroute Using Tunnels              Apr 2005
    routers other than itself. In this case a single repair with the
    pseudo-node as target is not possible, and it is necessary to
    compute individual repair paths whose target are each of the
    neighbors of E on the LAN.
 4.6.4.        The LAN is a Transit Subnet.
    This is the most common case, where a LAN is traversed by a repair
    path, but is not in any of the special positions described above.
    In this case no special treatment is required, and the normal SPF
    mechanisms are applicable.
 5.    Failure Detection and Repair Path Activation
    The details of repair path activation are inherently
    implementation-dependent and must be addressed by individual design
    specifications. This section describes the implementation
    independent aspects of the failover to the repair path.
 5.1.      Failure Detection
    The failure detection mechanism must provide timely detection of
    the failure and activation of the repair paths. The failure
    detection mechanisms may be media specific (for example loss of
    light), or may be generic (for example BFD). Multiple detection
    mechanisms may be used in order to improve detection latency. Note
    that in the case of a LAN it may be necessary to monitor
    connectivity to all of the adjacent routers on the LAN.
 5.2.      Repair Path Activation
    The mechanism used by the router to activate the repair path
    following failure will be implementation specific.
    An implementation that is capable of withdrawing the repair may
    delay the start of network convergence in order to minimize network
    disruption in the event that the failure was a transient.
 5.3.      Node Failure Detection Mechanism
    When router S detects a failure of the S-E link, it will invoke the
    link repair path from itself to router S. This S-E link repair is
    always invoked because even if all other traffic can be re-routed,
    E is always a single point of failure to itself. If router E has
    failed, the S-E link repair can result in a forwarding loop. A node
    failure detection mechanism is therefore needed. A suitable
    mechanism might be to run BFD [BFD] between S and E, over the S-E
    link repair path.
 Bryant et al.              Expires Oct 2005                   [Page 21]

 INTERNET DRAFT      IP Fast-reroute Using Tunnels              Apr 2005
    When the node failure detection mechanism has determined that
    router E has failed it withdraws the S-E link repair path. The node
    failure detection and revocation of the S-E link repair needs to be
    expedited, in order to minimize the duration of collateral damage
    to the network cause by packets looping around the S-E link repair
    If E is a single point of failure to some destinations, then
    withdrawing the S-E link repair has no impact on network
    connectivity, because those destinations will have been rendered
    unreachable by the failure of router E.
    If E is not a single point of failure, but traffic to some
    destinations is being repaired via the S-E link because of the
    inability to provide suitable repair paths, then there are
    destinations that are rendered temporarily unreachable by IPFRR.
    The IPFRR loop free convergence mechanism delays normal convergence
    of the network. Consideration therefore has to be given to the
    relative importance of the traffic being protected and the traffic
    being black-holed. Depending on the outcome of that consideration,
    the IPFRR loop-free strategy may need to be abandoned.
 6.    Loop Free Transition
    Once the repair paths have been activated, data will again be
    forwarded correctly. At this stage only the routers directly
    adjacent to the failure will be aware of the failure because no
    routing information concerning the failure has yet been propagated
    to other routers. The network now has to be transitioned to normal
    operation using the available components.
    During network transition inconsistent state may lead to the
    formation of micro-loops. During this period, packets may be
    prevented from reaching the repair path, may expire due to
    transiting an excessive number of hops, may be subject to excessive
    delay, and the resultant congestion may disrupt the passage of
    other packets through the network. A loop free transition technique
    which allows the network to re-converge without packet loss or
    disruption is therefore required.
    A number of suitable loop-free convergence techniques are described
    in [LVCONV].
 7.    IPFRR Capability
    In the previous sections it has been assumed that all routers in
    the network are capable of acting as IPFRR routers, performing such
    tasks as tunnel termination and directed forwarding. In practice
    this is unlikely to be the case, partially because of the
    heterogeneous nature of a practical network, and partially because
    of the need to progressively deploy such capability. IPFRR
    therefore needs to support some form of capability announcement,
 Bryant et al.              Expires Oct 2005                   [Page 22]

 INTERNET DRAFT      IP Fast-reroute Using Tunnels              Apr 2005
    and the algorithms need to take these capabilities into account
    when calculating their path repair strategies. For example, the
    ability of routers to function as tunnel end points and perform
    directed forwarding will influence the choice of repair path.
    However, routers which are simply traversed by repair paths
    (tunneled or not) do not need to be IPFRR capable in order to
    guarantee correct operation of the repair paths.
 8.    Enhancements to routing protocols
    It will be seen from the above that a number of enhancements to the
    appropriate routing protocols are needed to support IPFRR. The
    following possible enhancements have been identified:
         o  The ability to advertise IPFRR capability
         o  The ability to advertise tunnel endpoint capability
         o  The ability to advertise directed forwarding identifiers
         o  The ability to announce the start of a loop-free
            transition, and to abort a loop-free transition.
         o  The ability to signal transition completion status to
         o  The ability to advertise that a link is protected.
    Capability advertisement should make use of existing capability
    mechanisms in the routing protocols. The exact set of enhancements
    will depend on specific IPFRR design choices.
 9.    IANA Considerations
    There are no IANA considerations that arise from this architectural
    description of IPFRR. However there will be changes to the IGPs to
    support IPFRR in which there will be IANA considerations.
 10.     Security Considerations
    Changes to the IGPs to support IPFRR do not introduce any
    additional security risks.
    The security implications of the increased convergence time due to
    the loop avoidance strategy depend on the approach to multiple
    failures. If the presence of multiple failures results in the
    network aborting the loop free strategy, then the convergence time
    will be similar to that of a conventional network. On the other
    hand, an attacker in a position to disrupt part of a network might
    use this to disrupt the repair of a critical path.
 Bryant et al.              Expires Oct 2005                   [Page 23]

 INTERNET DRAFT      IP Fast-reroute Using Tunnels              Apr 2005
    The tunnel endpoints need to be secured to prevent their use as a
    facility by an attacker. Performance considerations indicate that
    tunnels cannot be secured by IPsec [IPSEC]. A system of packet
    address policing, both at the tunnel endpoints and at the edges of
    the network would prevent an attacker's packet arriving at a tunnel
    endpoint and would seem to be the best strategy.
    When a fast re-route is in progress, there may be an unacceptable
    increase in traffic load over the repair path. Network operators
    need to examine the computed repair paths and ensure that they have
    sufficient capacity.
    The authors acknowledge the significant technical contributions
    made to this work by their colleagues: John Harper and Kevin Miles.
 Intellectual Property Statement
    The IETF takes no position regarding the validity or scope of any
    Intellectual Property Rights or other rights that might be claimed
    to pertain to the implementation or use of the technology described
    in this document or the extent to which any license under such
    rights might or might not be available; nor does it represent that
    it has made any independent effort to identify any such rights.
    Information on the procedures with respect to rights in RFC
    documents can be found in BCP 78 and BCP 79.
    Copies of IPR disclosures made to the IETF Secretariat and any
    assurances of licenses to be made available, or the result of an
    attempt made to obtain a general license or permission for the use
    of such proprietary rights by implementers or users of this
    specification can be obtained from the IETF on-line IPR repository
    The IETF invites any interested party to bring to its attention any
    copyrights, patents or patent applications, or other proprietary
    rights that may cover technology that may be required to implement
    this standard.  Please address the information to the IETF at
 Full copyright statement
    Copyright (C) The Internet Society (2004). This document is subject
    to the rights, licenses and restrictions contained in BCP 78, and
    except as set forth therein, the authors retain all their rights.
    This document and the information contained herein are provided on
 Bryant et al.              Expires Oct 2005                   [Page 24]

 INTERNET DRAFT      IP Fast-reroute Using Tunnels              Apr 2005
 Normative References
    There are no normative references.
 Informative References
    Internet-drafts are works in progress available from
 [BASIC]      Alia Atlas, Ed., et al., "Basic Specification
              for IP Fast-Reroute: Loop-free Alternates",
              October 2004, (work in progress).
 [BFD]        Katz, D., and Ward, D., "Bidirectional
              Forwarding Detection", <draft-katz-ward-bfd-
              01.txt>, August 2003 (work in progress).
 [IPFRR]      Shand, M., "IP Fast-reroute Framework",
              October 2004, (work in progress).
 [IPSEC]      Kent, S., Atkinson, R., "Security Architecture
              for the Internet Protocol", RFC 2401
 [L2TPv3]     J. et al., "Layer Two Tunneling Protocol
              (Version 3)", <draft-ietf-l2tpext-l2tp-base-
              14.txt>, June 2004, (work in progress).
 [LFCONV]     Bryant, S., Shand, M., "A Framework for Loop-
              free Convergence", <draft-bryant-shand-lf-conv-
              frmwk-00.txt>, October 2004,(work in progress).
 [MPLSFRR]    Pan, P. et al, "Fast Reroute Extensions to
              RSVP-TE for LSP Tunnels", <draft-ietf-mpls-
              rsvp-lsp-fastreroute-05.txt> (work in
 [RFC1701]    S. Hanks. et al.,RFC-1701,"Generic Routing
              Encapsulation (GRE)". October 1994.
 [RFC1853]    Simpson, W., RFC-1853, "IP in IP Tunneling".
              October 1995.
 [RFC3032]    Rosen E., et al., RFC-3032, "MPLS Label Stack
              Encoding", January 2001.
 Bryant et al.              Expires Oct 2005                   [Page 25]

 INTERNET DRAFT      IP Fast-reroute Using Tunnels              Apr 2005
 Authors' Addresses
    Stewart Bryant
    Cisco Systems,
    250, Longwater Avenue,
    Green Park,
    Reading, RG2 6GB,
    United Kingdom.             Email:
    Clarence Filsfils
    Cisco Systems,
    De Kleetlaan 6a,
    1831 Diegem,
    Belgium                     Email:
    Stefano Previdi
    Cisco Systems,
    Via Del Serafico 200
    00142 Roma,
    Italy                       Email:
    Mike Shand
    Cisco Systems,
    250, Longwater Avenue,
    Green Park,
    Reading, RG2 6GB,
    United Kingdom.             Email:
 Bryant et al.              Expires Oct 2005                   [Page 26]