Network Working Group                             Albert J. Tian
Internet Draft                                    Naiming Shen
Expiration Date: Jan 2005                         Redback Networks
                                                  July 2004


             Fast Reroute using Alternative Shortest Paths


                draft-tian-frr-alt-shortest-path-01.txt



1. Status of this Memo


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


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


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




2. Abstract


   Repair path mechanism is an important element in IP/LDP fast reroute.
   In this document we propose a way to calculate local repair paths
   using alternative shortest paths. The solution can provide complete
   coverage for all destinations within an IGP area that can possibly be
   protected.


   In this document we also suggested an "Explicit Path with Loose
   Segment" model that can be used to characterize, classify, and
   analyse repair paths. We proved some of the common properties of
   loose segments, and showed that the model can be used to characterize
   all existing fast reroute solutions.




Tian                                                            [Page 1]


Internet Draft   draft-tian-frr-alt-shortest-path-01.txt       July 2004



   Based on the properties of loose segments, we also provided a way to
   maximize the use of loose segments in a repair path based on
   alternative shortest path, in order to simplify the repair path
   implementation.



3. Introduction


   To construct a repair path, the termination point of the repair path
   must be determined first. Then we can calculate the repair path from
   the router at point of local repair (PLR) to the termination point
   without going through the nexthop router being protected. The
   resulting explicit path from the calculation is usually a strict path
   that lists all nodes on the path. The path can then be simplified by
   maximizing the use of loose hops. The resulting path can then be
   implemented using mechanisms such as LSP source route or RSVP-TE.



4. Select the Termination Point of Repair Path


   Since node protection can also cover link failure and its in general
   difficult to distinguish between link and node failure, node failure
   is always assumed, unless the nexthop is a single point of failure.


   On a PLR router P, to protect a destination D from the failure of
   nexthop N, the termination point T of a repair path can be one of the
   following:


    If the nexthop N is not the primary egress point E for D, then
    either
    a) terminate at the primary egress point E for D, or
    b) terminate at the next-nexthop node from P to E [NHFRR].


    If the nexthop N is the primary egress point E for D, then
    c) if there exists an alternative egress point E' for D, terminate
       at E';
    d) if there are no alternative egress points, terminate at E and
       attempt link protection.


   Terminating repair path at next-nexthop has several advantages over
   terminating at egress point:


    1) since there are usually much less next-nexthops than egress
       points, next-nexthop based solution requires much less repair
       paths to be calculated and maintained.


    2) next-nexthop based repair path can protect multicast traffic
       [NHFRR-MCAST], while egress based repair path can not.




Tian                                                            [Page 2]


Internet Draft   draft-tian-frr-alt-shortest-path-01.txt       July 2004



   In some cases, next-nexthop based repair paths may be less optimal
   for some destinations, but this usually is not a concern.


   If the nexthop is the only egress, then it is a single point of
   failure. In this case, link protection is attempted. Repair paths can
   be calculated easily by disqualifying the link between P and N.  The
   rest of the discussions in this document will focus on the node
   protection cases (i.e. cases a, b and c above).



5. Use Alternative Shortest Paths as Repair Paths


   Once the termination point T is decided, we can move on to the
   calculation of repair paths from P to T.


   Repair paths are used by the PLR router P to quickly recover from the
   failure of a nexthop N, therefore the repair path can not go through
   the nexthop N that is being protected.


   For a destination D, one way to find the repair path on PLR router P
   to protect nexthop N's failure is to calculate shortest alternative
   paths from P to termination point T that do not go through N.


   For networks that are running link state IGP such as OSPF or ISIS, a
   simple way to calculate alternative shortest paths is to remove N
   from the link state database and re-run SPF from PLR P's point of
   view. This SPF will find all the alternative shortest paths from P to
   all possible T not going through N, therefore it will find out all
   the repair paths needed to cover N's failure, except for cases where
   N is a single point of failure. To protect all P's nexthops, the same
   calculation needs to be done for each nexthop.


   We use the notion ASP-N<A,B> to represent the set of alternative
   shortest paths between A and B that do not go through N.



6. Construct Repair Paths using Explicit Paths


   Since repair paths can not follow normal IP routing, therefore they
   have to be explicitly paths. Even in ECMP cases, when one of the ECMP
   nexthop fails, traffic has to be explicitly directed to the other
   ECMP nexthops. Therefore the ECMP based repair paths are still
   explicit paths.


   An explicit path can be expressed as a list of nexthops that the path
   must traverse. Each hop can be either strict or loose.


   In general there are two ways to implement an explicit path:




Tian                                                            [Page 3]


Internet Draft   draft-tian-frr-alt-shortest-path-01.txt       July 2004



   a) Stateful Explicit Path: this method installs special forwarding
      state on each router that is specified in the explicit path. An
      example of this method is RSVP-TE. There is little or no per
      packet overhead, but states need to be maintained in the network.
      This method can handle arbitrary explicit paths. Also RSVP-TE can
      support QoS along the path.


   b) Source Routed Explicit Path: this method use some form of source
      routing to encode the path in the packet itself. An example of
      this method is LSP source route [LSP-SRC-RT]. The benefit of
      this method is that no state need to be maintained in the
      network, therefore this method can scale to a large number of
      explicit paths. The limitation is that due to the per packet
      overhead, this method is only suitable for simple paths with
      small number of routers specified. Please note that a simple path
      is not necessarily short. One loose hop specified in the path can
      traverse a large number of routers.


   There are other solutions for fast reroute. They can all be viewed as
   some form of limited source routing. We will discuss this later in
   appendix A.



7. Loose Hops in Explicit Repair Paths


   There are several benefits of using loose segments in repair paths.



7.1. Reduce Number of Hops Specified


   In any case, there is incentive to reduce the number of hops that
   need to be specified in an explicit path. The simplest way to reduce
   the number of routers that need to be specified in an explicit path
   is through the use of loose hops.


   For stateful explicit paths, if loose segment optimization using
   tunnels is enabled [LOOSE-OPT], then the use of loose segments can
   reduce the amount of state installed in the network.


   For source routed explicit paths, the use of loose segments can
   reduce the per packet overhead.











Tian                                                            [Page 4]


Internet Draft   draft-tian-frr-alt-shortest-path-01.txt       July 2004



7.2. Trailing Loose Hop Optimization


   If the last segment of an explicit repair path is a loose segment,
   then as an optimization the explicit path can terminate early at the
   beginning of the trailing loose segment. From there on, the packets
   can be forwarded towards destination based on normal routing, and the
   actual path traversed by the packets will not be affected by the
   failure of the router being protected.


   It can be proven that this optimization is also valid for repair
   paths terminating on next-nexthop router.


   Consider the following topology where P is the PLR, N is the nexthop
   being protected, H is the next-nexthop, E is the egress. Path P-A-B-H
   is the next-nexthop based repair path. All links shown below except
   link <P,N> are loose segments that may traverse multiple routers.




                 A-----B--------+
                / \   / \       |
               /   \ /   \      |
              P-----N-----H-----E


            Figure 2


   It can be proven that if segment <B,H> can be a loose hop for repair
   path P-A-B-H, then repair path P-A-B is sufficient to protect all
   traffic from P that passes through next-nexthop H.



7.3. Characters of Loose Hops


   One requirement for a repair path is that it can not pass through the
   router being protected regardless of its status.  Therefore any loose
   hop in an explicit repair path must not pass through the router being
   protected.



7.3.1. Theorem 1


   The following theorem can help identifying the loose segments in an
   explicit path.


   Theorem 1:


   Let SP<A,B> be the set of shortest paths between A and B. If paths in
   SP<A,B> do not pass through N when N is available, then the set




Tian                                                            [Page 5]


Internet Draft   draft-tian-frr-alt-shortest-path-01.txt       July 2004



   SP<A,B> will not change when N and only N becomes unavailable.


   Proof:


   When node N becomes unavailable, the cost of the links between N and
   its neighbors increase from some finite value to infinity. If the
   cost of any path between A and B is changed after N's failure, it can
   only become higher. Therefore N's failure will not add any new paths
   to SP<A,B>.


   If N is the only node that becomes unavailable, then the costs of
   links not connected to N will not be changed. Therefore the cost of
   the paths not passing through N will not be changed. That means the
   costs of the paths in SP<A,B> will not be changed. Therefore N's
   failure will not remove any paths from SP<A,B>.


   So N's failure will not change SP<A,B>.


   END.


   Basically theorem 1 means that if the shortest paths between A and B
   do not pass through the router N being protected, then segment <A,B>
   can be safely used as a loose segment in a repair path protecting N,
   because the actual path for the loose segment will not be affected by
   N's failure.



7.3.2. Theorem 2


   The following theorem can further improve theorem 1.


   Theorem 2:


   Let ASP_N<A,B> be the set of alternative shortest paths between A and
   B that do not go through N.  Let l(ASP_N<A,B>) be the path length for
   ASP_N<A,B>. It is the shortest distance between A and B for paths
   that do not go through N.  Let d(A,N) be the shortest distance
   between A and N.  Let d(N,B) be the shortest distance between N and
   B.


   If the following condition holds, then SP<A,B> do not go through N.


      l(ASP_N<A,B>) < d(A,N) + d(N,B)      ....... Condition 1


   Proof


   All the paths between A and B can be divided into two sets, those
   that pass through N, and those that do not pass through N.  For paths




Tian                                                            [Page 6]


Internet Draft   draft-tian-frr-alt-shortest-path-01.txt       July 2004



   that pass through N, the shortest distance between A and B is d(A,N)
   + d(N,B). For paths that do not pass through N, by definition the
   shortest path is ASP_N<A,B>, and its length is l(ASP_N<A,B>). Because
   condition 1 is true, ASP_N<A,B> is shorter than any path that goes
   through N. Therefore ASP_N<A,B> is the shortest among all paths
   between A and B. Therefore ASP_N<A,B> is SP<A,B>. Since ASP_N<A,B> do
   not go through N, SP<A,B> do not go through N.


   END.


   Essentially Theorem 2 means that if the length of the alternative
   shortest path between A and B that do not go through N is shorter
   than the distance between A and N plus the distance between N and B,
   then the segment <A,B> can be used as a loose segment in a repair
   path protecting N.



7.4. Finding Loose Segments in Alternative Shortest Path


   Based on theorem 1 and theorem 2, an algorithm can be devised to find
   loose hops in alternative shortest paths.


   Given an alternative shortest path ASP_N<P,T> = <R1, R2, ..., Rm>
   from PLR P to termination point T not going through nexthop N, it can
   be used to protect N.


   Run SPF from N's point of view to find out d(N,X), for all X.


   If all link metrics are symmetrical, then d(X,N) = d(N,X), for all X.
   If some link metrics are asymmetrical, then run an additional reverse
   metric SPF from N's point of view to find out d(X,N), for all X.


   Let c(Ri, Rj) be the link metric from Ri to Rj.


   The following algorithm maximizes the length of loose hops in the
   alternative shortest path. It evaluates a segment on the path against
   theorem 2, if it can be a loose hop, then extend the segment by one
   hop and re-evaluate again, till a point that the segment is no longer
   a loose segment. In this way the algorithm finds the longest loose
   segment on the path for a given starting point.


   Algorithm Find_Loose_Hops
   {
       len = 0;
       start = 1;
       end = start;
       while (end < m) {
           if (len + c(R[end],R[end+1]) >= d(R[start],N) + d(N,R[end])) {




Tian                                                            [Page 7]


Internet Draft   draft-tian-frr-alt-shortest-path-01.txt       July 2004



               if (len == 0) {
                   output segment <R[end], R[end+1]> as a strict hop;
                   end = end+1;
                   start = end;
                   if (start > m) break;
               } else {
                   output segment <R[start],R[end]> as a loose hop;
                   start = end;
               }
           } else {
               len = len + c(R[end],R[end+1]);
               end = end+1;
               if (end == m) {
                   output segment <R[start],R[end]> as a loose hop;
               }
           }
       }
   }



7.5. Implementing Repair Paths


   IP TE Route Switched Path [IP-TE-RSP] can be used to implement
   arbitrary repair paths in a pure IP network.


   If MPLS is enabled, then LSP source route [LSP-SRC-RT] and RSVP-TE
   (possibly with loose segment optimization [LOOSE-OPT]), can be used
   to construct arbiturary repair paths using MPLS.


   All of the above mechanisms can benefit from the use of loose
   segments in repair paths. In most cases, a repair path is expected to
   conatin some loose segments, in perticular a long loose segment at
   the end. For RSVP based solutions, if optimization of loose segments
   is enabled, then the actual amount of state information maintained in
   a network can be greatly reduced. For LSP source route, the use of
   loose segments can reduce the label stack size.


   Please note that under some topologies the repair paths may require
   multiple strict hops to route around the router being protected.  For
   example, in the following topology as shown in Figure 1, P-N-H-E was
   the primary path. In order for PLR P to implement repair path P-A-B-
   H-E to protect failure in N, the first three segments must all be
   strict. The repair path is of type SSSL. Link metrics are show next
   to the links.


                    2
                 A-----B
              2 / \   / \ 2




Tian                                                            [Page 8]


Internet Draft   draft-tian-frr-alt-shortest-path-01.txt       July 2004



               /  1\ /1  \
              P-----N-----H-----E
                 1     1     10


      Figure 2 A sample topology that requires complex repair path


   This repair path can only be supported by IP TE RSP, LSP source
   route, and RSVP-TE today.



8. Security Considerations


   This document does not introduce any new security issues.



9. References


    [IPFRR] M. Shand, "IP Fast Reroute Framework",
       draft-ietf-rtgwg-ipfrr-framework-01.txt, Work in progress.


    [NHFRR] N. Shen, P. Pang, "Nexthop Fast ReRoute for IP and MPLS",
       draft-shen-nhop-fastreroute-00.txt, Work in progress.


    [IP-TE-RSP] N. Shen, A. Tian, J, Zhuang, "IP Traffic Engineering
       With Route Switched Paths (RSPs)", Work in progress.


    [NHFRR-MCAST] N. Shen, L. Wei, D. Farinacci, "Discovering PIM-SM
       Next-Nexthop Downstream Nodes",
       draft-shen-pim-nnhop-nodes-00.txt, Work in progress.


    [LSP-SRC-RT] A. Tian, G. Apostolopoulos, "Source Routed MPLS LSP
       using Domain Wide Label",
       draft-tian-mpls-lsp-source-route-01.txt, July 2004, Work in
       progress.


    [LOOSE-OPT] A. Tian, N. Shen, "Loose Segment Optimization in
       Explicit Paths", draft-tian-rsvp-loose-seg-opt-00.txt,
       Work in progress.


    [LOOPFREE] Atlas, Torvi, Choudhury, Martin, Imhoff, Fedyk,
       "IP/LDP Local Protection",
       draft-atlas-ip-local-protect-loopfree-00.txt, Work in progress.


    [UTURN] Atlas, et al., "U-turn Alternates for IP/LDP Local
       Protection", draft-atlas-ip-local-protect-uturn-00.txt, Work in
       progress.


    [TUNNEL] Bryant, Filsfils, Previdi, Shand, "IP Fast Reroute using




Tian                                                            [Page 9]


Internet Draft   draft-tian-frr-alt-shortest-path-01.txt       July 2004



       tunnels", draft-bryant-ipfrr-tunnels-00.txt, May 2004, Work In
       Progress.


    [RSVPTE] Awduche, et al., "Extensions to RSVP for LSP Tunnels",
       RFC 3209, December 2001.


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



10. Author Information



   Albert Jining Tian
   Redback Networks, Inc.
   300 Holger Way
   San Jose, CA 95134
   Email: tian@redback.com


   Naiming Shen
   Redback Networks, Inc.
   300 Holger Way
   San Jose, CA 95134
   Email: naiming@redback.com



11. Appendix A: Classification of Repair Path Mechanisms



11.1. Two Hops: Strict - Loose (Type SL)


    Downstream Path (Loop-Free Alternative) [LOOPFREE]
    ECMP



11.2. Two Hops: Loose - Loose (Type LL)


    Tunnel Approach without directed forwarding [TUNNEL].



11.3. Three Hops: Loose - Strict - Loose (Type LSL)


    Tunnel Approach with directed forwarding [TUNNEL].









Tian                                                           [Page 10]


Internet Draft   draft-tian-frr-alt-shortest-path-01.txt       July 2004



11.4. Three Hops: Strict - Strict - Loose (Type SSL)


    U-Turn: only support a subset of the cases where the first hop node
    must be an upstream node. [UTURN]



11.5. Three Hops: Strict - Loose - Loose (Type SLL)


    Tunnel Approach with first strict hop optimization and without
    directed forwarding [TUNNEL].



11.6. Four Hops - Strict, Loose, then Strict, Loose (Type SLSL)


    Tunnel Approach with first strict hop optimization and directed
    forwarding [TUNNEL].



11.7. Arbitrary Mix of Loose and Strict Hops


    IP TE RSP [IP-TE-RSP]
    LSP Source Route [LSP-SRC-RT]
    RSVP-TE [RSVPTE]
    RSVP-TE with Loose Hop Optimization [LOOSE-OPT].



12. Full Copyright Statement


   Copyright (C) The Internet Society (year).  This document is subject
   to the rights, licenses and restrictions contained in BCP 78, and
   except as set forth therein, the authors retain all their rights.


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













Tian                                                           [Page 11]