Networking Working Group JP. Vasseur (Editor) Internet-Draft Cisco Systems, Inc Expires: August 11, 2006 R. Zhang BT Infonet N. Bitar Verizon February 7, 2006 A Backward Recursive PCE-based Computation (BRPC) procedure to compute shortest inter-domain Traffic Engineering Label Switched Path draft-vasseur-ccamp-brpc-00.txt Status of this Memo 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 becomes aware will be disclosed, in accordance with Section 6 of BCP 79. 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 August 11, 2006. Copyright Notice Copyright (C) The Internet Society (2006). Abstract This document specifies a Path Computation Element (PCE)-based procedure to compute inter-domain Traffic Engineering (TE) Multiprotocol Label Switched (MPLS) and Generalized MPLS (GMPLS) Label Switched (LSP) constrained shortest paths. In this document a Vasseur, et al. Expires August 11, 2006 [Page 1] Internet-Draft draft-vasseur-ccamp-brpc-00.txt February 2006 domain is referred to as a collection of network elements within a common sphere of address management or path computational responsibility such as IGP areas and Autonomous Systems. Requirements Language 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. History . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3 3. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 4. General assumptions . . . . . . . . . . . . . . . . . . . . . 4 5. BRPC Procedure . . . . . . . . . . . . . . . . . . . . . . . . 5 5.1. Next-hop PCE discovery . . . . . . . . . . . . . . . . . . 5 5.2. Elements of procedure . . . . . . . . . . . . . . . . . . 6 6. PCEP Protocol Extensions . . . . . . . . . . . . . . . . . . . 8 7. Meric normalization . . . . . . . . . . . . . . . . . . . . . 9 8. Diverse en-to-end path computation . . . . . . . . . . . . . . 10 9. Path optimality . . . . . . . . . . . . . . . . . . . . . . . 10 10. 10. Reoptimization of an inter-domain TE LSP . . . . . . . . . 10 11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 10 12. Security Considerations . . . . . . . . . . . . . . . . . . . 11 13. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 11 14. References . . . . . . . . . . . . . . . . . . . . . . . . . . 11 14.1. Normative References . . . . . . . . . . . . . . . . . . . 11 14.2. Informative References . . . . . . . . . . . . . . . . . . 11 14.3. Informative References . . . . . . . . . . . . . . . . . . 11 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 13 Intellectual Property and Copyright Statements . . . . . . . . . . 14 Vasseur, et al. Expires August 11, 2006 [Page 2] Internet-Draft draft-vasseur-ccamp-brpc-00.txt February 2006 1. History The aim of this document is to specify a Backward Recursive PCE-based Computation (BRPC) procedure to compute shortest constrained inter- domain (G)MPLS TE LSP. Such procedure had been initially documented in draft-vasseur-ccamp-inter-domain-path-comp (Scenario 2) and is now moved to a separated ID in the light of the progress made by the PCE Working Group. Note that the protocol extensions related to the PCEP protocol (see [I-D.ietf-pce-pcep]) may be moved in a separate document. 2. Terminology ABR Routers: routers used to connect two IGP areas (areas in OSPF or levels in IS-IS). ASBR Routers: routers used to connect together ASes of a different or the same Service Provider via one or more Inter-AS links. Boundary LSR: a boundary LSR is either an ABR in the context of inter- area TE or an ASBR in the context of inter-AS TE. Inter-AS TE LSP: A TE LSP that crosses an AS boundary. Inter-area TE LSP: A TE LSP that crosses an IGP area. LSR: Label Switch Router. LSP: Label Switched Path. PCE: Path Computation Element: an entity (component, application or network node) that is capable of computing a network path or route based on a network graph and applying computational constraints. TED: Traffic Engineering Database. The notion of contiguous, stitched and nested TE LSPs is defined in [I-D.ietf-ccamp-inter-domain-rsvp-te] and will not be repeated here. 3. Introduction The requirements for inter-area and inter-AS MPLS Traffic Engineering have been developed by the Traffic Engineering Working Group (TE WG) and have been stated in [RFC4105] and [RFC4216] respectively. The framework for inter-domain MPLS Traffic Engineering has been Vasseur, et al. Expires August 11, 2006 [Page 3] Internet-Draft draft-vasseur-ccamp-brpc-00.txt February 2006 provided in [I-D.ietf-ccamp-inter-domain-framework]. [I-D.ietf-ccamp-inter-domain-pd-path-comp] proposes a path computation technique for computing inter-domain (G)MPLS TE LSP whereby the path is computed on a per-domain basis by the entry border node of each domain (each node in charge of computing a section of an inter-domain TE LSP path is always along the path of such TE LSP). Such path computation technique fulfills some of the requirements stated in [RFC4105] and [RFC4216]but not all of them. In particular, it cannot guarantee to find an optimal (shortest) inter-domain constrained path. Furthermore, it cannot be efficiently used to compute a set of inter-domain diversely routed TE LSP. The aim of this document is to describe a PCE-based TE LSP computation procedure to compute optimal inter-domain constrained (G)MPLS TE LSPs. Although one model consists of making the boundary routers act as PCE, the Backward Recursive PCE-based Computation (BRPC) procedure is not limited to that model. Qualifying a path as optimal requires some clarification. Indeed, a globally optimal TE LSP placement usually refers to a set of TE LSPs whose placements optimize the network resources with regards to a specified objective function (i.e a placement that reduces the maximum or average network load for instance). In this document, an optimal inter-domain constrained TE LSP is defined as the shortest path, satisfying the set of required constraints, that would be obtained in the absence of multiple domains (in other words, in a totally flat network between the source and destination of the TE LSP). The mechanisms proposed in this document are also applicable to (G)MPLS TE domains other than areas and ASs. 4. General assumptions In the rest of this document, we make the following set of assumptions common to inter-area and inter-AS TE: - Each area or AS is assumed to be capable of doing Traffic Engineering (i.e. running OSPF-TE or ISIS-TE and RSVP-TE). - No topology or resource information is distributed between domains (as mandated per [RFC4105] and [RFC4216]), which is critical to preserve IGP/BGP scalability and confidentiality in the case of TE LSPs spanning multiple domains. - While certain constraints like bandwidth can be used across different domains, certain other TE constraints like resource affinity, color, metric, etc. as listed in [RFC2702] could be Vasseur, et al. Expires August 11, 2006 [Page 4] Internet-Draft draft-vasseur-ccamp-brpc-00.txt February 2006 translated at domain boundaries. If required, it is assumed that, at the domain boundary LSRs, there will exist some sort of local mapping based on offline policy agreement, in order to translate such constraints across domain boundaries during the inter-PCE communication process. - The various ASBRs are BGP peers, without any IGP running on the inter-ASBR links. - Each AS can be made of several IGP areas. The path computation procedure described in this document applies to the case of a single AS made of multiple IGP areas, multiples ASs made of a single IGP areas or any combination of the above. For the sake of simplicity, each AS will be considered to be comprised of a single area in this document. The case of an Inter-AS TE LSP spanning multiple ASs where some of those ASs are themselves made of multiple IGP areas can be easily derived from this case by applying the BRPC procedure described in this document, recursively. 5. BRPC Procedure The BRPC procedure is a Multi-PCE path computation technique as described in [I-D.ietf-pce-architecture]. A possible model consists of hosting the PCE function on boundary routers (e.g. ABR or ASBR) but this is not mandated by the BRPC path computation procedure. BRPC does not make any assumptions with regards to the nature of the inter-domain TE LSP that could be contiguous, nested or stitched. No assumption is made on the actual path computation algorithm in use by the PCE (it can be any variant of CSPF, algorithm based on linear- programming to solve multi-constraints optimization problems and so on). 5.1. Next-hop PCE discovery The BRPC path computation procedure applies to the computation of an optimal constrained inter-domain TE LSP once the sequence of domains to be traversed has been determined. In tree-based topologies, the set of possible domains to be traversed is reduced to a single element (generally the case of Inter-area MPLS TE). When such set comprises more than one element (there exists more than one possible set of domains to reach the destination), procedures can be defined on the PCC to enforce the set of traversed domains. Alternatively, such selection can be made on the hop-by-hop basis relying on PCE discovery mechanism (e.g. using domain scope IGP advertisements as specified in [I-D.ietf-pce-disco-proto-igp]). Vasseur, et al. Expires August 11, 2006 [Page 5] Internet-Draft draft-vasseur-ccamp-brpc-00.txt February 2006 5.2. Elements of procedure Terminology - PCE(i) is a PCE with the scope of domain(i). - Boundary Router (BR): ABR or ASBR. - Entry BR of domain(n): a BR connecting domain(n-1) to domain(n). - Exit BR of domain(n): a BR connecting domain(n) to domain(n+1). - In each domain i: * a set of X-en(i) entry BRs noted BR-en(k,i) where BR-en(k,i) is the kth entry BR of domain(i). * a set of X-ex(i) exit BR noted BR-ex(k,i) where BR-ex(k,i) is the kth exit BR of domain(i). Definition of VSPT(i) A virtual shortest path tree VSPT(i) returned by PCE(i) to PCE(i-1) has the following form: Root (TE LSP destination) / I \ BR-en(1,i) BR-en(2,i) ... BR-en((j), i). Where j<= [X-en(i)] Each link of VSPT(i) represents the shortest path between the destination and BR-en(j,i) that satisfies the set of required constraints for the TE LSP (bandwidth, affinities, ...). These are path segments to reach the destination from BR-en(j,i). Note that just BR having connectivity with some BR of domain(i-1) must be considered. Furthermore, some BRs may be excluded according to policy constraints (either due to local policy or policies signaled in the path computation request). Step 1: the PCC needs to first determine the PCE capable of serving its path computation request. The path computation request is then relayed until reaching a PCE(n) such that the TE LSP destination resides in the domain(n). At each step of the process, the next PCE can either be statically configured or dynamically discovered via IGP/BGP extensions. If multiple PCEs are discovered, the PCE may Vasseur, et al. Expires August 11, 2006 [Page 6] Internet-Draft draft-vasseur-ccamp-brpc-00.txt February 2006 select a subset of these PCEs based on some local policies/ heuristics. Note also that a sequence of PCEs might be enforced by policy on the PCC and this constraint can be either carried in the PCECP path computation request or applied to the computed VSPT. Step 2: PCE(n) computes VSPT(n) made of the list of shortest constrained path(s) between every BR-en(j,n) and the TE LSP destination using a suitable path computation algorithm (e.g. CSPF). Step 3: PCE(n) returns the VSPT(n) to PC(n-1). - For i=n-1 to 2: PCE(i) concatenates the ASi topology (using its TED) with the received VSPT(i+1) and computes VSPT(i). In the case of Inter-AS TE, this operation also includes the links connecting ASBRs of ASi and ASi+1. End Each branch of the VSPT tree (path) may be returned in the form of an explicit path (in which case all the hops along the path segment are listed) or a loose path (in which case only the BR is specified) so as to preserve confidentiality. Note: in term of computation of an inter-AS TE LSP path, an interesting optimization consists of allowing the ASBRs to flood the TE information related to the inter-ASBR link(s) although no IGP TE is enabled over those links (and so there is no IGP adjacency over the inter-ASBR links). This of course implies for the inter-ASBR links to be TE-enabled although no IGP is running on those links. This allows the PCE of a domain to get entire TE visibility up to the set of entry ASBRs in the downstream domain. A PCE MAY decide to support local caching of path computation in order to optimize the path computation process. The downside of path caching is the potential increase of call set up failure. When caching is in use, it must be flushed upon TE LSP set up failure provided that the PCE is along the inter-area/AS TE LSP path. BRPC guarantees to find the optimal (shortest) constrained inter-domain TE LSP according to a set of defined domains to be traversed. Note that other variants of the BRPC procedure relying on the same principles are also possible. Note also that in case of ECMP paths, more than one path could be returned to the requesting LSR. The BRPC procedure may be used to compute path segments and could be used in conjunction with other path computation techniques (such as the per-domain path computation technique defined in [I-D.ietf-ccamp-inter-domain-pd- Vasseur, et al. Expires August 11, 2006 [Page 7] Internet-Draft draft-vasseur-ccamp-brpc-00.txt February 2006 path-comp]) to compute the end-to-end path. In this case end-to-end path optimality can no longer be guaranteed. 6. PCEP Protocol Extensions The BRPC path computation procedure requires the specification of a new PCEP (see [I-D.ietf-pce-pcep]) object carried within a PCReq message sent by a PCC to a PCE or by a PCE to another PCE so as to request from a downstream PCE the set of shortest constrained path(s) from the destination to a set of entry boundary routers. Indeed, the END-POINTS object specified in PCEP makes the assumption that both the source and the destination are known by the requester. Due to potential lack of visibility of the entry boundary routers of the downstream domain (e.g. Inter-AS MPLS TE case) the set of entry boundary router in a downstream domain may not be known by the requesting PCC: this requires to specify a new PCEP object named VSPT for the purpose of the BRPC path computation procedure where the VSPT object is used in a PCReq message so as to request from a downstream PCE the VSPT from the destination to all entry BRs satisfy the constraints. Because path segment(s) computed by a downstream PCE in the context of the BRPC procedure must be provided along with their respective path cost(s), the C flag of the RP object carried within the PCReq message MUST be set. It is the choice of the requester to appropriately set the O bit of the RP object. VSPT Object-Class is to be assigned by IANA (recommended value=14) VSPT Object-Type is to be assigned by IANA (recommended value=1) Vasseur, et al. Expires August 11, 2006 [Page 8] Internet-Draft draft-vasseur-ccamp-brpc-00.txt February 2006 The format of the VSPT object body is as follows: 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Reserved | Flags | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Destination IPv4 Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 2 - VSPT object body format (IPv4 Address) 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Reserved | Flags | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | | Destination IPv6 address (16 bytes) | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 3 - VSPT object body format (IPv6 Address) The destination IP address of the VSPT object corresponds to the VSPT root (TE LSP's destination) and is provided by the PCC originating the path computation request. No Flags are currently defined. 7. Meric normalization In the case of inter-area TE, the same IGP/TE metric scheme is usually adopted for all the IGP areas (e.g. based on the link-speed, propagation delay or some other combination of link attributes). Hence, the proposed set of mechanism always computes the shortest path across multiple areas obeying the required set of constraints with respect to a well-specified objective function. Conversely, in the case of Inter-AS TE, in order for this path computation to be meaningful, a metric normalization between ASs may be required. One solution to avoid IGP metric modification would be for the SPs to agree on a TE metric normalization scheme and use the TE metric for TE LSP path computation (in that case, this must be requested in the Path computation request) thanks to the COST object. Vasseur, et al. Expires August 11, 2006 [Page 9] Internet-Draft draft-vasseur-ccamp-brpc-00.txt February 2006 8. Diverse en-to-end path computation The PCEP protocol allows an LSR to request the computation of a set of diversely routed TE LSPs. In the context of the BRPC procedure, a set of diversely routed TE LSP between two LSRs can be computed since the paths segment(s) of the VSPT are simultaneously computed by a given PCE. Such a PCE-based path computation method allows for the computation of diverse paths under various objective functions (such as minimizing the sum of the costs of the N diverse paths, etc) in a very efficient manner, thus avoiding the well-known "trapping" problem: Indeed, with a 2-step approach consisting of computing the first path followed by the computation of the second path after having removed the set of network elements traversed by the first path (if that does not violate confidentiality preservation), one cannot guarantee that a solution will be found even if such solution exists. Furthermore, even if a solution is found, it may not be the most optimal one with respect to objective function such as minimizing the sum of the paths costs, bounding the path delays of both paths and so on. Finally, it must be noted that such a 2-step path computation approach is usually less efficient in term of signalling delays since it requires two serialized TE LSP set up. 9. Path optimality BRPC guarantees that the optimal (shortest) constrained inter-domain path will always be found. It must be noted that although the BRPC procedure applies to any type of inter-domain TE LSP (e.g. contiguous, stitched or nested), the use of local reoptimization with a stitched TE LSP may no longer guarantee to preserve the path optimality of the end-to-end path should the BRPC procedure be used in the first place. 10. 10. Reoptimization of an inter-domain TE LSP The ability to reoptimize an existing inter-domain TE LSP path has been explicitly listed as a requirement in [RFC4105] and [RFC4216]. In the case of a TE LSP reoptimization request, regular procedures apply as defined in PCEP where the path in use (if available on the head-end) is provided within the path computation request in order for the PCEs involved in the reoptimization request to avoid double bandwidth accounting. 11. IANA Considerations A new PCEP object is defined in this document that has an Object- Vasseur, et al. Expires August 11, 2006 [Page 10] Internet-Draft draft-vasseur-ccamp-brpc-00.txt February 2006 Class and an Object-Type. The new Object-Class and Object-Type should be assigned by IANA. VSPT Object The Object-Class of the VSPT object is to be assigned by IANA (recommended value=14). One Object-Type is defined for this object and should be assigned by IANA with a recommended value of 1. 12. Security Considerations The BRPC procedure does not introduce any additional security issues beyond the ones related to inter-PCE communication. 13. Acknowledgements The authors would like to thank Arthi Ayyangar and Adrian Farrel for their useful comments. 14. References 14.1. Normative References [I-D.ietf-pce-architecture] Farrel, A., "A Path Computation Element (PCE) Based Architecture", draft-ietf-pce-architecture-04 (work in progress), January 2006. [I-D.ietf-pce-pcep] Vasseur, J., "Path Computation Element (PCE) communication Protocol (PCEP) - Version 1 -", draft-ietf-pce-pcep-00 (work in progress), November 2005. [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. 14.2. Informative References 14.3. Informative References [I-D.ietf-ccamp-inter-domain-framework] Farrel, A., "A Framework for Inter-Domain MPLS Traffic Engineering", draft-ietf-ccamp-inter-domain-framework-04 Vasseur, et al. Expires August 11, 2006 [Page 11] Internet-Draft draft-vasseur-ccamp-brpc-00.txt February 2006 (work in progress), July 2005. [I-D.ietf-ccamp-inter-domain-pd-path-comp] Vasseur, J., "A Per-domain path computation method for establishing Inter-domain Traffic Engineering (TE) Label Switched Paths (LSPs)", draft-ietf-ccamp-inter-domain-pd-path-comp-01 (work in progress), October 2005. [I-D.ietf-ccamp-inter-domain-rsvp-te] Ayyangar, A. and J. Vasseur, "Inter domain GMPLS Traffic Engineering - RSVP-TE extensions", draft-ietf-ccamp-inter-domain-rsvp-te-02 (work in progress), October 2005. [I-D.ietf-pce-disco-proto-igp] Roux, J., "IGP protocol extensions for Path Computation Element (PCE) Discovery", draft-ietf-pce-disco-proto-igp-00 (work in progress), November 2005. [RFC2702] Awduche, D., Malcolm, J., Agogbua, J., O'Dell, M., and J. McManus, "Requirements for Traffic Engineering Over MPLS", RFC 2702, September 1999. [RFC4105] Le Roux, J., Vasseur, J., and J. Boyle, "Requirements for Inter-Area MPLS Traffic Engineering", RFC 4105, June 2005. [RFC4216] Zhang, R. and J. Vasseur, "MPLS Inter-Autonomous System (AS) Traffic Engineering (TE) Requirements", RFC 4216, November 2005. Vasseur, et al. Expires August 11, 2006 [Page 12] Internet-Draft draft-vasseur-ccamp-brpc-00.txt February 2006 Authors' Addresses JP Vasseur Cisco Systems, Inc 1414 Massachusetts Avenue Boxborough, MA 01719 USA Email: jpv@cisco.com Raymond Zhang BT Infonet 2160 E. Grand Ave. El Segundo, CA 90025 USA Email: raymond_zhang@bt.infonet.com Nabil Bitar Verizon 40 Sylvan Road Waltham, MA 02145 USA Email: nabil.bitar@verizon.com Vasseur, et al. Expires August 11, 2006 [Page 13] Internet-Draft draft-vasseur-ccamp-brpc-00.txt February 2006 Intellectual Property Statement 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. Disclaimer of Validity 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. Copyright Statement Copyright (C) The Internet Society (2006). 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. Acknowledgment Funding for the RFC Editor function is currently provided by the Internet Society. Vasseur, et al. Expires August 11, 2006 [Page 14]