Internet Draft
Internet Draft                                          Sriganesh Kini
Expires : April, 2001                                  Murali Kodialam
<draft-kini-restoration-shared-backup-00.txt>            T.V.Lakshman 
                                                           - Bell Labs

                                                     Curtis Villamizar
                                                       - Avici Systems
                                                                        
             Shared backup Label Switched Path restoration

             draft-kini-restoration-shared-backup-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

   Traffic engineering using MPLS involves the setting up of label
   switched paths (LSP) possibly with explicit routing and with
   bandwidth guarantees (for label switched paths). The reliability of
   these LSPs can be increased by providing a backup LSP onto which
   traffic can be switched upon failure of an element in the path of the
   active LSP. Backup LSPs can be routed in a way that bandwidth can be
   shared between backup links of more than one active path while still
   guaranteeing recoverability for a set of failures. This sharing greatly
   increases the network efficiency, thereby increasing the number of LSPs
   that can be carried while maintaining guarantees. Algorithms which can
   route such recoverable LSPs while using only aggregate network usage 
   information are being developed.

   This informational draft illustrates the concept of sharing links along
   backup paths and examines the requirements from link state
   information and the signaling functions.





S. Kini, et al                Expires April, 2001                   [Page 1] 
                                                                            
Internet Draft draft-kini-shared-backup-lsp-restoration-00.txt November 2000  

1. Introduction                                                               
                                                                              
   The Multi Protocol Label Switching (MPLS) working group has developed a    
   framework and standards which enable traffic engineering of networks.      
   The framework is described in [8] and the architecture is described in
   [7]. The MPLS framework is becoming increasing popular to traffic
   engineer IP networks.                                                 
                                                                              
   MPLS uses the label swapping paradigm to switch data over an LSP. The      
   functional capabilities required for operations in an MPLS domain are      
   described in [9]. The network layer routing determines the route of an     
   LSP from the topology of the network and the current demands of the        
   applications utilizing the network. Link state routing protocols like
   OSPF (as described in [1]) and IS-IS (as described in [2]) can provide
   the topology information to network layer routing that engineers
   traffic. Signaling protocols like RSVP (as described in [9] and [10])
   and LDP (as described in [11] and [12]) are then used to setup the LSP.
                                                                              
   Since a LSP traverses a fixed path in the network, its reliability
   depends on the links and nodes along the path. Traditionally IP
   networks have carried only best-effort traffic. However new applications
   are using the IP network infrastructure in ways that make it highly
   desirable to incorporate faster repair.

   MPLS based recovery provides a faster restoration mechanism
   than layer 3 routing. Several methods have been proposed for MPLS
   based recovery. A framework and terminology for MPLS based recovery
   is described in [3].

   Setting up a backup LSP for an active LSP (e.g. [6]) is one way to
   achieve reliability. A straightforward solution to this problem is to
   find two disjoint paths. However this requires at least twice the amount
   of network resources. For a restoration objective like single link
   failure recovery, links on the backup path can be shared between
   different active paths in a way that single link failure restoration
   is guaranteed. This must be done without requiring per-LSP routing
   information for all LSPs currently carried by the network, since keeping
   track of per-LSP routing information for the whole network is not
   feasible. It is more desirable to efficiently route recoverable LSPs
   with shared backups using only aggregate network usage information.
   Aggregate information useful for setting up shared backup paths is
   obtainable by adding a few new information elements to the link state
   advertisement of a link state routing protocol like OSPF or ISIS.
   Algorithms which can operate using aggregate information are being 
   developed. An example of one such algorithm is described later.
   Other examples of such algorithms are in [4],[5]. These algorithms
   achieve a very high degree of sharing by using aggregate information 
   that can be conveyed by a link state routing protocol.

   The key concept of sharing backup paths is described in section 2.
   The requirements from link state protocols and signaling protocols
   is briefly examined in section 3.


S. Kini, et al                Expires April, 2001                   [Page 2] 
                                                                            
Internet Draft draft-kini-shared-backup-lsp-restoration-00.txt November 2000  


2. Concept of sharing backup paths
                                                                              
   A brief description of the concept of sharing is described in this
   section.

   The model under which these principle of sharing is expected to be
   deployed is very general. Requests for LSPs should be routed as they
   arrive (online). A new type of LSP can be computed where given
   a source and destination, an active path and a backup path (possibly
   shared) is calculated. Links on the backup path are possibly shared
   between backup paths of other active paths in a way that single
   link/node failure restoration is guaranteed. As requests for setup and
   teardown of such LSPs arrive and link failures occur the total link
   bandwidth allocated for active paths and backup paths vary accordingly.

   Section 2.1 through 2.3 illustrate the sharing concept through some
   examples and section 2.4 outlines one simple algorithm that achieves
   sharing and guarantees single link failure recovery. This algorithm 
   needs only aggregate information. [4] and [5] are other instances of
   similar algorithms. They achieve a very high degree of sharing using
   only aggregate information.

2.1 Sharing backup : single link failure recovery

   Figure 1 illustrates a simple case of sharing of backup paths in a way
   that single link failure can be recovered. A and B are label switch
   routers. Say each link is of unit bandwidth and each LSP request
   is also of unit bandwidth. L1 and L2 are two active paths. L1b is the
   backup for L1 and L2b is the backup for L2. L1b and L2b can be
   accomodated on the same link by sharing the bandwidth. Clearly, if
   either one of L1 or L2 fail the system can recover.
   

                            L1
                     ____________________ 
                    /                    \                 
                   |                      |                  
                  ----    L1b  L2b      ----               
                 | A  |----------------| B  |              
                  ----                  ----               
                   |                      |           
                    \____________________/
                            L2


        Figure 1 : Sharing backup links with link failure recovery
                                                                              
2.2 Sharing backup : single node failure recovery

   Figure 2 illustrates a simple case of sharing of backup paths in a way
   that single node failure can be recovered.


S. Kini, et al                Expires April, 2001                   [Page 3] 
                                                                            
Internet Draft draft-kini-shared-backup-lsp-restoration-00.txt November 2000  

                  ----             L2             ----               
                 | A  |--------------------------| B  |              
                  ----                            ----               
                   |                               |
                   |L2b                            |L2b
                   |                               |
                   |                               |
                  ----          L1b L2b           ----               
                 | C  |--------------------------| D  |              
                  ----                            ----               
                   |                               |
                   |L1b                            |L1b
                   |                               |
                   |                               |
                  ----     L1    ----     L1      ----               
                 | E  |---------| F  |-----------| G  |              
                  ----           ----             ----               

       Figure 2 : Sharing backup links with node failure recovery


   A,B, ... G are label switch routers. L1 is an active path along E-F-G.
   The corresponding backup L1b is along the path E-C-D-G. Similarly
   L2 is an active path along A-B. L2b is the corresponding backup path
   along A-C-D-B. Clearly, if max-bandwidth(L1,L2) is allocated on link
   C-D for L1b and L2b together, the system can ensure single node failure
   recovery.

2.3 Local restoration : single link/node recovery

   Local restoration (SONET like recovery constraints), can be achieved
   by providing intermediate nodes with a backup path. The intermediate
   nodes can switchover to the backup path immediately on getting a failure
   indication.

   Figure 3 illustrates an example of local restoration for single link
   failure recovery.


                          ----                   ----               
                     ____| D  |____        _____| E  |____          
                 L1b/     ----     \L1b   /L1b   ----     \L1b        
                   /                \    /                 \
                  ----      L1        ----       L1        ----               
                 | A  |--------------| B  |---------------| C  |              
                  ----                ----                 ----               

                  Figure 3 : Local restoration of link failure

   Clearly from section 2.1 sharing of backup paths can be done in this
   case to achieve single link/node failure recovery. In fact a further
   degree of sharing can be achieved by sharing of links between segments
   of the backup paths A-D-B and B-E-C (intra demand sharing).

S. Kini, et al                Expires April, 2001                   [Page 4] 
                                                                            
Internet Draft draft-kini-shared-backup-lsp-restoration-00.txt November 2000  


   Similarly Figure 4 illustrates an example of local restoration for single
   node failure recovery.

                           ----                            ----               
          ________________| E  |_____________        _____| F  |____          
      L1b/                 ----              \L1b   /L1b   ----     \L1b       
        /                                      \   /                 \
       ----      L1        ----       L1        ----        L1      ----  
      | A  |--------------| B  |---------------| C  |--------------| D  |     
       ----                ----                 ----                ----  
                             \                                      /
                              \L1b              ----               /L1b
                               \_______________| G  |_____________/    
                                                ----                   



        Figure 4 : Local restoration of single node/link failure


   Clearly from section 2.1 and 2.2, Figure 3, and Figure 4 backup sharing
   (intra and inter demand sharing) can be done in this case as well.

2.4 A simple algorithm for calculated shared backup path

   Terminology : Say for link (i,j)
   i) the cumulative bandwidth allocated for active paths is F(i,j)
   ii) the cumulative bandwidth allocated for backup paths is G(i,j)
   iii) the residual bandwidth free for allocation is R(i,j)

   For a request of bandwidth b the active path is calculated as the
   shortest path on the topology of links that have R(i,j) > b.
   Let M be the max of the F values along the active path. The backup
   path is calculated as follows. The cost of a link (u,v) is now taken as
   i) 0 if { M+b < G(u,v) } else
   ii) b if { G(u,v) <= M and b <= R(u,v) } else
   iii) M+b - G(u,v) if { M <= G(u,v) and M+b <= G(u,v)+R(u,v) } else
   iv) infinity in all other cases
  
   The backup path is calculated as the shortest path on the topology with
   the cost of links calculated as above.

   The lack of an active path or a backup path with finite cost represent
   failure conditions.

3. Requirements for shared backup lsp restoration

   Requirements from link state routing protocols and signaling protocols
   is briefly described in this section.

   Aggregate information about a link that has to be conveyed by a link
   state routing protocol should consist of

S. Kini, et al                Expires April, 2001                   [Page 5] 
                                                                            
Internet Draft draft-kini-shared-backup-lsp-restoration-00.txt November 2000  

   i) The total bandwidth used on the link for active LSPs
   ii) Total bandwidth used on the link for backup LSPs
   iii) Total available bandwidth on the link

   The signaling protocol information elements should consist of
   i) The setup information and procedures for a backup LSP
   ii) The association between the active and backup LSP

4. Security Considerations

   This document raises no new security issues.

5. Acknowledgements

   The authors would like to thank Vishal Sharma and Roch Guerin for their
   comments on this work.

6. References

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

   [2] "Intermediate System to Intermediate System Intra-Domain Routeing
       Exchange Protocol for use in Conjunction with the Protocol for
       Providing the Connectionless mode Network Service (ISO 8473)", ISO
       DP 10589, February 1990.

   [3] Makam, V., Sharma, V., Huang, C., Owens, K., Mack-Crane, B., et
       al, "A Framework for MPLS-based Recovery," Work in Progress,
       Internet Draft <draft-makam-mpls-recovery-frmwrk-00.txt>,
       February 2000.

   [4] Lakshman, T.V., Kodialam, M., "Dynamic Routing of Bandwidth
       Guaranteed Tunnels with Restoration", Proceedings of INFOCOM 2000,
       April 2000.

   [5] Lakshman, T.V., Kodialam, M., "Dynamic Routing of Bandwidth
       Guaranteed Tunnels Using Aggregated Link Usage Information", 
       To be published in Proceedings of INFOCOM 2001.

   [6] Haskin, D., Krishnan, R., "A Method for Setting an Alternative Label 
       Switched Paths to Handle Fast Reroute", Work in Progress, Internet Draft
       <draft-haskin-mpls-fast-reroute-04.txt>, May 2000.

   [7] Rosen, E., Viswanathan, A., and Callon, R., "Multiprotocol Label
       Switching Architecture", Work in Progress, Internet Draft , August 1999.

   [8] Callon, R., Doolan, P., Feldman, N., Fredette, A., Swallow, G.,
       Viswanathan, A., "A Framework for Multiprotocol Label Switching",
       Work in Progress, Internet Draft <draft-ietf-mpls-framework-05.txt>,
       September 1999.

   [9] Braden, R., Zhang, L., Berson, S., Herzog, S., "Resource

S. Kini, et al                Expires April, 2001                   [Page 6] 
                                                                            
Internet Draft draft-kini-shared-backup-lsp-restoration-00.txt November 2000  


       ReSerVation Protocol (RSVP) -- Version 1 Functional
       Specification", RFC 2205, September 1997.

   [10] Awduche, D. et al "RSVP-TE: Extensions to RSVP for LSP Tunnels", Work in
       Progress, Internet Draft <draft-ietf-mpls-rsvp-lsp-tunnel-07.txt,
       August 1999.

   [11] Andersson, L., Doolan, P., Feldman, N., Fredette, A., Thomas,
       B., "LDP Specification", Work in Progress, Internet Draft , September 1999.

   [12] Jamoussi, B. "Constraint-Based LSP Setup using LDP", Work in
       Progress, Internet Draft <draft-ietf-mpls-cr-ldp-03.txt>,
       September 1999.

7. Author's Addresses

   Sriganesh Kini
   Lucent Technologies, Bell Labs
   Room 4C-526, 101 Crawfords Corner Road
   Holmdel, NJ 07733-3030
   Phone : 732 949 6418
   Email : kini@dnrc.bell-labs.com

   Murali Kodialam
   Lucent Technologies, Bell Labs
   Room 4D-525, 101 Crawfords Corner Road
   Holmdel, NJ 07733-3030
   Phone : 732 949 6296
   Email : muralik@dnrc.bell-labs.com

   T.V.Lakshman
   Lucent Technologies, Bell Labs
   Room 4D-531, 101 Crawfords Corner Road
   Holmdel, NJ 07733-3030
   Phone : 732 949 4778
   Email : lakshman@dnrc.bell-labs.com

   Curtis Villamizar
   Avici Systems
   Email : curtis@avici.com












S. Kini, et al                Expires April, 2001                   [Page 7] 
                                                                            
Internet Draft draft-kini-shared-backup-lsp-restoration-00.txt November 2000  


Full Copyright Statement

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

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

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

   This document and the information contained herein is provided on an
   "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
   TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING
   BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION
   HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF
   MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE."


























S. Kini, et al                Expires April, 2001                   [Page 8]