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 <draft-ietf- mpls-arch-06.txt>, 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 <draft- ietf-mpls-ldp-06.txt>, 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]