CCAMP Working Group Geng-Sheng Kuo (Editor) Internet Draft Qing Huang (Editor) Expiration Date: February 2004 Generalized MPLS Recovery Resource Sharing draft-kuo-gmpls-recovery-resource-sharing-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 [RFC-2026]. 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. For potential updates to the above required-text see: http://www.ietf.org/ietf/1id-guidelines.txt Abstract Many protection and restoration (P&R) techniques are proposed to protect LSP in GMPLS networks. Provisioning better P&R capability requires that more recovery resources be allocated on protection LSP, which may lead to resource waste in GMPLS networks. This draft presents a scheme of recovery resource sharing with traffic balancing for GMPLS LSP P&R. Its focus is on the discussions of working and protection LSPs selection and shared resource allocation and release. G.S Kuo et al. - Internet Draft - Expires [page 1] draft-ietf-kuo-gmpls-recovery-resource-sharing-00.txt February 2004 Table of Contents 1. Introduction...................................................2 2. Notions........................................................3 3. Recovery resource sharing with traffic balancing...............4 4. Signaling implementation.......................................5 5. Resource allocation and release................................7 5.1 Resource allocation............................................7 5.2 Resource release...............................................8 6. Performance evaluation........................................10 7. Application to LSP segment protection and restoration.........10 8. Conclusions...................................................10 9. Acknowledgments ............................................. 10 10. Intellectual Property Considerations..........................10 11. References....................................................11 12. Authors' Addresses............................................12 13. Full Copyright Statement......................................12 Conventions used in this document: The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [RFC2119]. In addition, the reader is assumed to be familiar with the terminology used in [GMPLS-ARCH], [RFC-3471], [RFC-3473] and referenced as well as [TERM] and [FUNCT]. 1. Introduction As the real-time and multimedia-oriented services are rapidly increasing on Internet, a small link or node failure is not acceptable to customers. Service continuity is becoming much more important than before. Protection and Restoration (P&R) (see [TERM]) is an efficient way to improve service continuity by establishing protection path for working path. Obviously, recovery resources reserved on protection path are idle at most time, which is unreasonable from the viewpoint of resource utilization. An efficient way to improve recovery resource utilization is to have protection LSPs, whose working LSPs are physically disjoint, share bandwidth resources. This mechanism was coined as shared mesh restoration and described in [GMPLS-ANAL]. Clearly, not all GMPLS recovery mechanisms can provide recovery resource sharing. For example, in the 1+1 protection mechanism, the traffic is transmitted simultaneously on both the working and protection LSPs. The selector at the egress will decide which path to use according to the quality of signal. Obviously, no recovery resources can be shared in 1+1 protection, while other recovery mechanisms such as M:N recovery do provision resource sharing. G.S Kuo et al. - Internet Draft - Expires [page 2] draft-ietf-kuo-gmpls-recovery-resource-sharing-00.txt February 2004 To share the recovery resources can save bandwidth in networks, thus, rejected session setup requests can be decreased in a certain degree. Moreover, maximum recovery resource sharing with traffic balancing can further decrease rejected session setup requests in GMPLS networks. We will discuss the scheme to optimize recovery resource sharing with traffic balancing and the implementation of the scheme. Section 2 introduces the notions used in the draft. Section 3 describes the scheme to optimize recovery resource sharing with traffic balancing. Section 4 provides the signaling implementation of the scheme. Section 5 discusses resource allocation and release. Section 6 evaluates the performance of proposed scheme. Section 7 presents the application of the scheme in LSP segment protection and restoration. And, Section 8 concludes this draft. 2. Notions We model the network as G=(V, E), where V is the set of nodes and E is the set of all links in networks. A LSP is defined as LSP={s, r1, ..., rn, d}, where s and d denote source and destination nodes respectively, and rk denotes the k-th intermediate LSR along the LSP. In addition, to identify a LSP in GMPLS networks, either a global identifier (ID) or a triple must be used. To simplify the presentation, the global identifier (ID) is used in this draft. Furthermore, the following notations are defined: l(i, j): The link from nodes i to j. Cij: The cost of l(i, j). b: The bandwidth demand of a LSP setup request. Bij: Total amount of bandwidth reserved for protection LSPs on l(i, j). Rij: Total amount of residual bandwidth on l(i, j). RLij: Set of protection LSPs that traverse l(i, j). RLij={RLij[1], RLij[2], ..., RLij[K]}, where RLij[k] is the ID of the k-th protection LSP and K is the total number of protection LSPs on l(i, j). PLij: Set of LSPs which are protected by l(i, j). PLij={PLij[1], PLij[2], ..., PLij[K]}, where PLij[k] is the ID of the k-th LSP protected by RLij[k]. fij[k]: The recovery bandwidth required to be allocated to RLij[k]. fij[k] is always equal to the bandwidth demand of PLij[k]. G.S Kuo et al. - Internet Draft - Expires [page 3] draft-ietf-kuo-gmpls-recovery-resource-sharing-00.txt February 2004 tij[k][m]: The bandwidth that RLij[k] shares with RLij[m], where k<>m. So, the actual recovery bandwidth allocated to RLij[k] is fij[k] - sum {m=1}^K [tij[k][m]]. WLij: Set of working LSPs that traverse l(i, j). Inf(Wlsp): Information about WLij of all links along Wlsp, where Wlsp={s, w1, ..., wn, d} is the selected working LSP. That is Inf(Wlsp)=WLsw1 OR WLw1w2 OR ... OR WLwnd. Weight[i,j]: Weight of l(i, j) used in computing a route. In this draft, we assume node i is the dominating node of l(i, j), that is, the information about WLij, RLij, PLij, fij[k] and tij[k][m] are held in node i locally. Thus, WLij, RLij, PLij, fij[k] and tij[k][m] can be refreshed on node i when any working or protection LSP traversing l(i, j) is set up. 3. Recovery resource sharing with traffic balancing In the proposed scheme, only information of Bij and Rij is required for computing a route, that is, only Bij and Rij are flooded in networks. The flooding of Bij and Rij can be easily implemented by route protocol extensions OSPF [GMPLS-OSPF] / IS-IS [OSPF-ISIS] in GMPLS. The current solutions for recovery resource sharing are the two approaches mentioned in [GMPLS-ANAL]: Full Information and Partial Information approaches. We coin the scheme as Proper Information approach. When computing the route of working LSP, the Proper Information approach computes the weight of l(i, j) as follows, _ _ Cij / Rij (Rij >= b) | Weight[i,j]=|_ _ infinity (otherwise) After the working LSP is selected, when protection LSP is being selected, Weight[i,j] should be computed as follows, ---- Cij (Bij >= b) | Weight[i,j]=|---- Cij+Cij*(1-Bij/b) (Bij=b-Bij) | ---- infinity (otherwise) G.S Kuo et al. - Internet Draft - Expires [page 4] draft-ietf-kuo-gmpls-recovery-resource-sharing-00.txt February 2004 The weight computation of l(i, j) above has two advantages: a) It can provision more probability of recovery resource sharing in GMPLS networks. b) It can balance the traffic in GMPLS networks. When computing working LSP, it is obvious that the Weight(i, j) will be less if l(i, j) has more residual bandwidth. When protection LSP is selected, Weight(i, j) will be less if l(i, j) has reserved more bandwidth. Thus, links with more reserved bandwidth will be more possible to be selected as the parts of protection LSP. Suppose Plsp is selected as protection LSP. Let Bw(i,j) represents the recovery resources that should be allocated for Plsp on l(i, j). The computation of Bw(i, j) is conducted on node i as follows. TmpSet = Inf(Wlsp) AND PLij; PLij[n] is an element in TmpSet; w = Bij - sum{n} [fij[n]]; ---- 0 (b <= w) | Bw(i,j)=|---- b - w (Rij >= b-w, b>w) | ---- infinity (otherwise) Note that Bw(i,j) may be set to infinity as above, which means recovery resource reserving action may fail on l(i, j). The reason of this is the bandwidth estimation in computing protection LSP is inaccurate. Two conditions in computing Weight[i,j] for protection LSP may cause the failure of Plsp setup: a)Even if Bij>=b is satisfied, only x bandwidth units can be shared due to the restriction that the protected LSPs must be physically disjoint, where x=b-Bij is satisfied, b-Bij bandwidth units need to be allocated at least as recovery resources. But, only x bandwidth units can be shared due to the restriction that the protected LSPs must be physically disjoint, where xk) h) a = b - Bw(i,j); i) For all RLij[m] in S, While a>0 do { if a=fij[m] then { tij[k][m] = fij[m]; tij[m][k] = fij[m]; a =a-fij[m]; } S = S - { RLij[m] };} G.S Kuo et al. - Internet Draft - Expires [page 7] draft-ietf-kuo-gmpls-recovery-resource-sharing-00.txt February 2004 Note that the resource allocation procedure of protection LSP is more complex than that of working LSP since more information would be refreshed. In addition, the refresh of WLij, RLij, PLij and fij[k] are easier to understand than computation of tij[k][m]. When computing tij[k][m], a set S, which contains the protection LSP IDs with which the new protection LSP Plsp may share bandwidth, is obtained first. Then, some LSPs in S are selected to share bandwidth with Plsp. Next, the amount of shared bandwidth of each selected LSP RLij[m] is computed. Finally, both tij[k][m] and tij[m][k] are updated. 5.2 Resource release The resource release also consists of two procedures: resource release for working LSP and resource release for protection LSP. The resource release procedures are as follows: Proc.1) A working LSP Wlsp is being released. LSP ID of Wlsp is X and bandwidth demand is b units. For any link l(i, j) along Wlsp, when node i receives PATHTEAR message: a) Rij = Rij + b; b) WLij = WLij-{X}; Proc.2) A new protection LSP Plsp is being released. LSP ID of Plsp is Y and bandwidth demand is b units. Let c denote the bandwidth that will be actually released. For any link l(i, j) along Plsp, when node i receives PATHTEAR message: a) RLij = RLij - { RLij[k] }; (Suppose RLij[k] = Y;) b) PLij = PLij - { PLij[k] }; c) tmp=0; d) For all m if tij[k][m] <> 0 then { tij[m][k]=0; tmp = tmp + tij[k][m]; tij[k][m]=0; } e) c = fij[k] - tmp; f) fij[k] = 0; g) Rij = Rij + c; h) Bij = Bij - c; The release of working LSP is quite easy to implement. Much attention should be paid to protection LSP release. When protection LSP Plsp is setup, it may share some reserved resources with others. Also, some resources allocated to Plsp may be shared by other prot- ection LSPs during the hold time of Plsp. These shared resources should not be released when Plsp is released. So, the key point for resource release is to know about the information of shared resources in all links. In the above procedures, the release of Plsp can be achieved efficiently because the required information of fij[k] and tij[k][m], which are updated in resource allocation procedures, can be obtained on node i easily. G.S Kuo et al. - Internet Draft - Expires [page 8] draft-ietf-kuo-gmpls-recovery-resource-sharing-00.txt February 2004 The resource allocation and release procedures can be illustrated using the following network topology: ======X(3)======= a-----------------b |======Y(5)=======| |* * * *| working LSP |* * * *| ========== |* ****Y'(5)**** *| |******X'(3)******| Protection LSP c-----------------d ************* |******Z'(7)******| |* *| |* *| |* *| e-----------------f ======Z(7)======= In the initial state, two working LSPs X and Y are established between nodes a and b. The bandwidth demands of X and Y are 3 and 5 units respectively. The protection LSPs for X and Y are X'={a,c,d,b} and Y'={a,c,d,b}. Note that X' and Y' can not share recovery resources since X and Y are not physically disjoint. Thus, we can obtain Bcd=8, RLcd={X',Y'}, PLcd={X,Y}, fcd[1]=3, fcd[2]=5, tcd[1][2]=0 and tcd[2][1]=0. Now, a new LSP Z is setup between nodes e and f with 7 units of bandwidth demand. The protection LSP for Z is Z'={e,c,d,f}. Clearly, no resource requires to be allocated on l(c,d) because Z' can share resources with X' and Y' due to the fact that LSP Z is disjoint with LSPs X and Y. In terms of above resource allocation procedures, we obtain Bcd=8, RLcd={X',Y',Z'}, PLcd={X,Y,Z}, fcd[1]=3, fcd[2]=5, fcd[3]=7, tcd[1][3]=3, tcd[2][3]=4, tcd[3][1]=3 and tcd[3][2]=4 after Z' is established. Next, we give the examples of shared resource release on l(c,d). Three situations will be considered, which are releasing Z' first, releasing X' first and releasing Y' first. i) Releasing Z' first: In this situation, LSP Z expires before X and Y. According to the resource release procedures, the bandwidth would be released for Z' on l(c, d) is computed as fcd[3]-tcd[3][1]-tcd[3][2]=0. So, no resource should be released when releasing Z'. Thus, the refreshed information is Bcd=8, RLcd={X',Y'}, PLcd={X,Y}, fcd[1]=3, fcd[2]=5, tcd[1][2]=0 and tcd[2][1]=0, which is the same as that in the initial state. ii) Releasing X' first: On l(c,d), the recovery resources for X' are all shared by Z', thus, the bandwidth would be released for X' is fcd[1]-tcd[1][3]=0. After X' is released, the refreshed info- rmation is Bcd=8, RLcd={Y',Z'}, PLcd={Y,Z}, fcd[1]=5, fcd[2]=7, tcd[1][2]=4 and tcd[2][1]=4. G.S Kuo et al. - Internet Draft - Expires [page 9] draft-ietf-kuo-gmpls-recovery-resource-sharing-00.txt February 2004 iii) Releasing Y' first: When releasing Y', only parts of recovery resources for it should be released because some recovery resources are being shared by Z'. Here, the bandwidth released is fcd[2]-tcd[2][3]=1. In terms of resource release procedures, we obtain the refreshed information on l(c,d), which is Bcd=7, RLcd={X',Z'}, PLcd={X,Z}, fcd[1]=3, fcd[2]=7, tcd[1][2]=3 and tcd[2][1]=3. 6. Performance evaluation We evaluated the performance of Proper Information approach in different tested networks by simulation. Two aspects are examined, 1) recovery overhead, which is the rate of the total bandwidth allocated for working LSP to the total bandwidth reserved for prote- ction LSP in networks. 2) rejected requests. The proposed scheme has been compared to a Full Information approach (see [GLI]), which has optimal performance in recovery overhead. The results show that the scheme gives a performance difference of less than 3% in recovery overhead compared to [GLI]. However, the number of rejected requests in [GLI] is always double of that for the proposed scheme. Clearly, the Proper Information approach decreases the rejected requests in networks significantly due to its capability of traffic balancing. 7. Application to LSP segments protection and restoration The Proper Information approach can be applied to LSP segments prot- ection and restoration without any modification. But the performance needs further study. 8. Conclusion This draft discussed the issue of recovery resource sharing with traffic balancing in GMPLS networks. We proposed the Proper Informa- tion approach to provision the capability of recovery resource sharing and traffic balancing. The Proper Information approach needs less additional information than other approaches. Moreover, no additional signaling procedure is required. We highlighted the implementation of it, including resource allocation and release procedures. And, the proposed scheme indeed improves resource utilization and decreases the rejected requests in networks. 9. Acknowledgments 10. Intellectual Property Considerations This section is taken from Section 10.4 of RFC2026 [RFC-2026]. G.S Kuo et al. - Internet Draft - Expires [page 10] draft-ietf-kuo-gmpls-recovery-resource-sharing-00.txt February 2004 The IETF takes no position regarding the validity or scope of any intellectual property 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; neither does it represent that it has made any effort to identify any such rights. Information on the IETF's procedures with respect to rights in standards-track and standards-related documentation can be found in BCP-11. Copies of claims of rights made available for publication 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 implementors or users of this specification can be obtained from the IETF Secretariat. The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights, which may cover technology that may be required to practice this standard. Please address the information to the IETF Executive Director. 11. References [GMPLS-ARCH] E.Mannie (Editor) et al., "Generalized MPLS Architecture," Work in progress, draft-ietf-ccamp- gmpls-architecture-07.txt, May 2003. [RFC-2026] S.Bradner, "The Internet Standards Process -- Revision 3," BCP 9, IETF RFC 2026, October 1996. [RFC-2119] S.Bradner, "Key words for use in RFCs to Indicate Requirement Levels," BCP 14, IETF RFC 2119, March 1997. [RFC-3471] L.Berger (Editor) et al., "Generalized MPLS - Signaling Functional Description," IETF RFC 3471, January 2003. [RFC-3472] P.Ashwood-Smith (Editor) et al., "Generalized Multi- Protocol Label Switching (GMPLS) Signaling Constraint -based Routed Label Distribution Protocol (CR-LDP) Extensions", IETF RFC 3472, January. 2003. [RFC-3473] L.Berger (Editor) et al., "Generalized MPLS Signaling - RSVP-TE Extensions," IETF RFC 3473, January 2003. [FUNCT] J.P.Lang (Editor) et al., "Generalized MPLS Recovery Functional Specification," Work in progress, draft-ietf -ccamp-gmpls-recovery-functional-01.txt, September 2003. [GMPLS-ANAL] D.Papadimitriou (Editor) et al., "Analysis of Generalized Multi-Protocol Label Switching (GMPLS) -based Recovery Mechanisms (including Protection and Restoration)", work in progress, draft-ietf-ccamp-gmpls -recovery-analysis-02.txt, September 2003. G.S Kuo et al. - Internet Draft - Expires [page 11] draft-ietf-kuo-gmpls-recovery-resource-sharing-00.txt February 2004 [TERM] E.Mannie and D.Papadimitriou (Editors), "Recovery (Protection and Restoration) Terminology for GMPLS," Work in progress, draft-ietf-ccamp-gmpls-recovery- terminology-02.txt, May 2003. [GLI] G.Li et al., "Efficient distributed restoration path selection for shared mesh restoration," IEEE/ACM Trans. Networking, vol. 11, pp. 761-771, October 2003. 12. Authors' Addresses Geng-Sheng Kuo Phone: E-mail: gskuo@ieee.org Qing Huang E-mail:huangqing_bupt@hotmail.com 13. Full Copyright Statement "Copyright (C) The Internet Society (date). 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." G.S Kuo et al. - Internet Draft - Expires [page 12]