PCE BOF Internet Draft Nagao Ogino Proposed Status: Informational KDDI R&D Labs. Expires: March 2005 September 2004 Path Computation Model for Recovery LSPs Using External PCE draft-ogino-pce-recovery-pc-model-00.txt Status of this Memo This document is an Internet-Draft and is subject to all provisions of section 3 of RFC 3667. 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 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. This Internet-Draft will expire on March 2005. Copyright Notice Copyright (C) The Internet Society (2004). Abstract This document proposes a PC model, where the recovery LSP route in a domain is computed using an external PCE. Recovery LSP computation that promotes bandwidth sharing between other recovery LSPs requires unreserved bandwidth information that corresponds to each failure position or SRLG. However, the present IGP-TE can only advertise unreserved bandwidth information corresponding to eight priority Ogino Expires - March 2005 [Page 1] Internet Draft September 2004 classes to each LSR involved in an IGP area. An external PCE in a domain can compute efficient recovery LSP routes by exclusively preserving such unreserved bandwidth information without any extension of the present IGP-TE. 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 RFC 2119 [RFC2119]. Table of Contents 1. Introduction...................................................2 2. Principle of Recovery Path Computation Model...................3 3. Recovery Path Computation Procedure............................4 4. Recovery Path Computation Example..............................5 5. Scalability Considerations.....................................8 6. Security Considerations........................................8 7. IANA Considerations............................................8 8. Acknowledgements...............................................8 9. References.....................................................8 9.1 Normative References.......................................8 9.2 Informational References...................................9 10. Authors' Addresses............................................9 11. Intellectual Property Statement...............................9 11.1 IPR Disclosure Acknowledgement...........................10 12. Full Copyright Statement.....................................10 1. Introduction Path Computation Element (PCE) [PCE-ARCHITECTURE, PCE-PROBLEM] is indispensable when path computation requires Traffic Engineering (TE) information that cannot be advertised by routing protocols. For an example, path computation in a domain may require TE information that cannot be advertised to other domains by the present inter-domain routing protocols [BGP-4]. In this case, only PCE involved in that domain can compute an optimal Label-Switched Path (LSP) route in the domain without any extension of the inter-domain routing protocols [INTER-DOMAIN-FRAMEWORK, INTER-DOMAIN-PATH-COMP]. Likewise, path computation in a domain may require TE information that cannot be advertised to each Label Switching Router (LSR) in the domain by the present intra-domain routing protocols. In this case, an external PCE in the domain can compute an efficient LSP route by exclusively preserving such required TE information without any extension of the intra-domain routing protocols. Ogino Expires - March 2005 [Page 2] Internet Draft September 2004 This document proposes a PC model, where recovery LSP route in a domain is computed using an external PCE. Recovery LSP computation that promotes bandwidth sharing between other recovery LSPs requires unreserved bandwidth information that corresponds to each failure position or SRLG. However, the present IGP-TE can only advertise unreserved bandwidth information corresponding to eight priority classes to each LSR involved in an IGP area [OSPF-TE, IS-IS-TE]. An external PCE in a domain can compute efficient recovery LSP routes by exclusively preserving such unreserved bandwidth information without any extension of the present IGP-TE. Here, a domain is considered to include a working LSP segment that can be protected by a recovery LSP. 2. Principle of Recovery Path Computation Model In this document, the bandwidth protection for packet-LSPs and shared-mesh restoration for all of the TE-LSPs are considered to be recovery schemes [RECOVERY-TERMINOLOGY]. In those recovery schemes, recovery LSPs can share the link bandwidth if the protected segments of working LSPs are never exposed to damage at the same time [RECOVERY-ANALYSIS]. A PCE can compute efficient backup LSP routes that ensure such link bandwidth sharing in the context of fast reroute bandwidth protection of packet-LSPs [PCE-BACKUP-COMP-FRWK]. An external PCE in a domain can compute efficient recovery LSP routes that promote such link bandwidth sharing without any extension of the present IGP-TE. A working LSP is composed of several segments and each segment is protected by a recovery LSP. Though a single segment is never involved in two domains, multiple segments may be included in a single domain. A working LSP always occupies the link bandwidth. However, a recovery LSP occupies the link bandwidth only when the corresponding working LSP segment incurs damage. Thus, the link bandwidth actually utilized changes according to whether the accommodated recovery LSPs are conveying the protected traffic or not. Designating the unoccupied link bandwidth by "unreserved bandwidth", its extent within a link depends on the occurrence of any failure and the position of that failure, even if the accommodated LSPs in that link remain unchanged. Link bandwidth available for a recovery LSP is a factor of link failures that the corresponding working LSP may incur in the case of link protection. These, in turn, are triggered by node failures that may occur within the corresponding working LSP in the case of node protection, and decided by Shared Risk Link Groups (SRLGs) that the corresponding working LSP belongs to in the case of the SRLG protection. Here, the SRLGs that an LSP belongs to are defined as an SRLG aggregation that the links accommodating the LSP belong to. Ogino Expires - March 2005 [Page 3] Internet Draft September 2004 Moreover, recovery LSPs can share the link bandwidth if the protected segments of working LSPs are never simultaneously exposed to damage. When link bandwidth available for a recovery LSP exceeds the minimum unreserved bandwidth in that link, the recovery LSP can share the link bandwidth with other recovery LSPs accommodated in the same link. If the volume of the minimum unreserved bandwidth and that available for a newly requested recovery LSP can be known, the bandwidth rate at which the newly requested recovery LSP can share the link bandwidth with other accommodated recovery LSPs can be calculated. Bandwidth sharing can be promoted by reducing the link weight as the bandwidth sharing rate becomes larger. As described above, recovery LSP computation that promotes bandwidth sharing between recovery LSPs requires unreserved bandwidth information corresponding to each link failure, each node failure, and each SRLG. However, the present IGP-TE can only advertise unreserved bandwidth information corresponding to eight priority classes to each LSR involved in an IGP area [OSPF-TE, IS-IS-TE]. An external domain-based PCE can achieve the aforementioned efficient recovery LSP computation through exclusive preservation of unreserved bandwidth information without any extension of the present IGP-TE. 3. Recovery Path Computation Procedure The head-end LSR of recoverable TE-LSP, ingress LSR into the domain, and PCEs in other domains may request path computation to an external PCE [INTER-DOMAIN-RSVP-TE]. The external PCE computes a route for a working LSP segment and the corresponding recovery LSP respectively. Firstly, the external PCE computes a route for the working LSP segment based on the originating and terminating LSRs of the LSP segment designated by the requester. Because the available bandwidth for a working LSP is the minimum unreserved bandwidth, links with minimum unreserved bandwidth amounting to less than the working LSP bandwidth are removed. Then, the shortest path is selected as the route for a working LSP segment. The external PCE decreases all of the unreserved bandwidth volumes in the links newly accommodating the working LSP segment. All of the unreserved bandwidths corresponding to all link and node failures and all the SRLGs are reduced by the working LSP bandwidth. Next, the external PCE computes a route for the corresponding recovery LSP. The external PCE excludes the links traversed by the working LSP segment in the case of link protection, the transit nodes for the working LSP segment in the case of node protection, and the SRLGs that the working LSP segment belongs to in the case of SRLG protection. Ogino Expires - March 2005 [Page 4] Internet Draft September 2004 Available bandwidth for the recovery LSP in each link can be known from the route selected for the corresponding working LSP segment. In other words, the route for the working LSP segment details the link and node failures that the working LSP segment may incur and the SRLGs to which the working LSP segment belongs. The available bandwidth for the recovery LSP in each link is identical to the least unreserved bandwidth among those corresponding to such link and node failures and SRLGs. The external PCE removes all links with available bandwidth less than the recovery LSP. The external PCE then calculates the bandwidth sharing rate in each remaining link, using figures for the available and minimum unreserved bandwidths respectively, and then adjusting the link weight according to the bandwidth sharing rate calculated for the link. In other words, the link weight is reduced as the bandwidth sharing rate increases, and the selection of such a link is promoted. Finally, the shortest path between the originating and terminating LSRs for the working LSP segment is selected as the route for the recovery LSP. The external PCE reduces the unreserved bandwidths in the links newly accommodating the recovery LSP. The unreserved bandwidths corresponding to the link and node failures that the working LSP segment may incur are reduced by the recovery LSP bandwidth. The unreserved bandwidths corresponding to the SRLGs to which the working LSP segment belongs are also reduced by the recovery LSP bandwidth. Since the external PCE is required to be stateful, the external PCE must be notified when the recoverable TE-LSP is released. Moreover, unreserved bandwidth information preserved exclusively by the external PCE requires updating. The external PCE increases all of the unreserved bandwidths within links that have accommodated the segment of the released working LSP. All unreserved bandwidths corresponding to all link and node failures and all SRLGs are increased by the bandwidth of the released working LSP. The external PCE increases the unreserved bandwidths in the links that have accommodated the recovery LSP. The unreserved bandwidths corresponding to the link and node failures that the segment of released working LSP may incur are increased by the bandwidth of the released recovery LSP. The unreserved bandwidths corresponding to the SRLGs to which the segment of released working LSP belongs are also increased by the bandwidth of the released recovery LSP. The external PCE must preserve the path route information calculated for a segment of recoverable TE-LSP if the notification message for release of this segment of recoverable TE-LSP includes no such path route information for this segment of recoverable TE-LSP. 4. Recovery Path Computation Example Ogino Expires - March 2005 [Page 5] Internet Draft September 2004 The recovery path computation model is explained using the following example of domain topology. Here, only link protection is considered. LSR1************************LSR4 + \ / * + \ / * + \ / * + \ / * + \ / * + LSR5 * + * * * + * * * + * * * + * * * + * * * LSR2++++++++++++++++++++++++LSR3 In the above example, the bandwidth of each link is assumed to be 5.0. A segment of recoverable TE-LSP with a bandwidth of 3.0 is established between LSR1 and LSR3. The working LSP segment between LSR1 and LSR3 is established through LSR4 while the recovery LSP between LSR1 and LSR3 is established through LSR2. A segment of recoverable TE-LSP with a bandwidth of 1.0 is also established between LSR2 and LSR3. The working LSP segment between LSR2 and LSR3 is established through LSR5 while the recovery LSP connects LSR1 and LSR3 directly. Two recovery LSPs can share the bandwidth of link LSR2-LSR3 because the corresponding segments of working LSPs never incur damage simultaneously. At this time, the unreserved bandwidth information for link LSR2-LSR3 is as follows. This information is preserved exclusively in an external PCE. +----------------------+----------------------+ | Link failure | Unreserved bandwidth | +----------------------+----------------------+ | LSR1-LSR4 + 2.0 | +----------------------+----------------------+ | LSR4-LSR3 + 2.0 | +----------------------+----------------------+ | LSR2-LSR5 + 4.0 | +----------------------+----------------------+ | LSR5-LSR3 + 4.0 | +----------------------+----------------------+ | Others + 5.0 | +----------------------+----------------------+ This information clearly indicates that the available bandwidth for a working LSP is 2.0 in link LSR2-LSR3. It also indicates the available Ogino Expires - March 2005 [Page 6] Internet Draft September 2004 bandwidth for a recovery LSP to be 2.0 when the corresponding working LSP segment traverses either of the links LSR1-LSR4 or LSR4-LSR3. Further, data shows the available bandwidth for a recovery LSP to be 4.0 and the ability of a recovery LSP to share link bandwidth of 2.0 with other recovery LSPs when the corresponding working LSP segment traverses neither of the links LSR1-LSR4 nor LSR4-LSR3 but either of links LSR2-LSR5 or LSR5-LSR3. Finally, we learn that the available bandwidth for a recovery LSP is 5.0 and a recovery LSP can share the link bandwidth of 3.0 with other recovery LSPs when the corresponding working LSP segment traverses none of the links LSR1-LSR4, LSR4-LSR3, LSR2-LSR5 and LSR5-LSR3. Here, an external PCE receives a request to establish a segment of recoverable TE-LSP with a bandwidth of 3.0 between LSR2 and LSR3. The external PCE selects the shortest path LSR2-LSR5-LSR3 for the working LSP segment because link LSR2-LSR3 cannot accommodate this working LSP segment. The external PCE excludes links LSR2-LSR5 and LSR5-LSR3 because the working LSP segment already traverses those links. The external PCE removes links LSR1-LSR4 and LSR4-LSR3 because those links cannot accommodate the recovery LSP. Then, the external PCE selects the shortest path LSR2-LSR3 for the recovery LSP. At this time, the recovery LSP can share bandwidth of 2.0 with other recovery LSPs in link LSR2-LSR3. The bandwidth sharing rate becomes 67% because bandwidth of the recovery LSP is 3.0. Therefore, the external PCE may reduce the weight of link LSR2-LSR3 from 1.0 to 0.33 to promote selection of link LSR2-LSR3. As a result, the external PCE updates the unreserved bandwidth information for link LSR2-LSR3 as follows. +----------------------+----------------------+ | Link failure | Unreserved bandwidth | +----------------------+----------------------+ | LSR1-LSR4 + 2.0 | +----------------------+----------------------+ | LSR4-LSR3 + 2.0 | +----------------------+----------------------+ | LSR2-LSR5 + 1.0 | +----------------------+----------------------+ | LSR5-LSR3 + 1.0 | +----------------------+----------------------+ | Others + 5.0 | +----------------------+----------------------+ If the release of this established segment of recoverable TE-LSP, with bandwidth of 3.0 between LSR2 and LSR3, is notified, the external PCE must update this unreserved bandwidth information for link LSR2-LSR3 to its previous state. Ogino Expires - March 2005 [Page 7] Internet Draft September 2004 5. Scalability Considerations When a centralized external PCE exclusively preserving the required TE information is prepared in a domain, both the processing and memory loads of the path computation concentrate on this PCE. The size of a domain needs to be decided on, based on the available processing and memory capacities of the centralized PCE. Although load sharing by distributed PCEs is possible within a domain, this scenario requires fast synchronization of TE information between the distributed PCEs. 6. Security Considerations This document does not raise any new security issues, beyond those of the PCE architecture [PCE-ARCHITECTURE]. 7. IANA Considerations This document makes no request for IANA action. 8. Acknowledgements The authors would like to thank to Jean Philippe Vasseur and Adrian Farrel for their encouragement in the submission of this document. 9. References 9.1 Normative References [PCE-ARCHITECTURE] Farrel, A., Vasseur, J. P., and Ash, J., "Path Computation Element (PCE) Architecture", draft-ash-pce-architecture- 00.txt, September 2004 (work in progress). [PCE-PROBLEM] Ash, J. and Farrel, A., "Path Computation Element Problem Statement", draft-ash-pce-problem-statement-00.txt, June 2004 (work in progress). [PCE-BACKUP-COMP-FRWK] Vasseur, J. P., Charny, A., Faucheur, F. L., Achirica, J. and Roux, J. L., "Framework for PCE-based MPLS-TE Fast Reroute Backup Path Computation", draft-leroux-pce-backup-comp-frwk- 00.txt, July 2004 (work in progress). Ogino Expires - March 2005 [Page 8] Internet Draft September 2004 9.2 Informational References [BGP-4] Rekhter, Y. and Li, T., "A Border Gateway Protocol 4 (BGP-4)", RFC 1771, March 1995. [OSPF-TE] Katz, D., Yeung, D. and Kompella, K., "Traffic Engineering Extensions to OSPF Version 2", RFC 3630, September 2003. [IS-IS-TE] Li, T. and Smit, H., "IS-IS extensions for Traffic Engineering", RFC 3784, June 2004. [INTER-DOMAIN-FRAMEWORK] Farrel, A., Vasseur, J. P., and Ayyangar, A., "A Framework for Inter-Domain MPLS Traffic Engineering", draft- farrel-ccamp-inter-domain- framework-01.txt, July 2004 (work in progress). [INTER-DOMAIN-RSVP-TE] Ayyangar, A. and Vasseur, J. P., "Inter-domain MPLS Traffic Engineering- RSVP-TE extensions", draft-ayyangar-ccamp- inter-domain-rsvp-te-00. txt, July 2004 (work in progress). [INTER-DOMAIN-PATH-COMP] Vasseur, J. P., Ayyangar, A., and Zhang, R., "Inter-domain Traffic Engineering LSP path computation methods", draft-vasseur-ccamp-inter- domain-path-comp-00.txt, July 2004 (work in progress). [RECOVERY-TERMINOLOGY] Mannie, E. and Papadimitriou, D., "Recovery (Protection and Restoration) Terminology for Generalized Multi- Protocol Label Switching (GMPLS)", draft-ietf-ccamp-gmpls-recovery- terminology-04.txt, April 2004 (work in progress). [RECOVERY-ANALYSIS] Papadimitriou, D. and Mannie, E., "Analysis of Generalized Multi-Protocol Label Switching (GMPLS)-based Recovery Mechanisms (including Protection and Restoration)", draft-ietf-ccamp- gmpls-recovery-analysis-03.txt, April 2004 (work in progress). 10. Authors' Addresses Nagao Ogino KDDI R&D Laboratories Inc. 2-1-15 Ohara, Kamifukuoka-shi Saitama 356-8502 JAPAN Email: ogino@kddilabs.jp 11. Intellectual Property Statement Ogino Expires - March 2005 [Page 9] Internet Draft September 2004 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 at http://www.ietf.org/ipr. 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 ietf- ipr@ietf.org. 11.1 IPR Disclosure Acknowledgement 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. 12. 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 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. Acknowledgment Funding for the RFC Editor function is currently provided by the Internet Society. Ogino Expires - March 2005 [Page 10]