PCE Working Group Z. Ali T. Saad Internet Draft Cisco Systems, Inc. Intended status: Standard Track March 04, 2009 Expires: September 03, 2009 BRPC Extensions for Point-to-Multipoint Path Computation draft-ali-pce-brpc-p2mp-ext-00.txt Status of this Memo This Internet-Draft is submitted to IETF in full conformance with the provisions of BCP 78 and BCP 79. This document may contain material from IETF Documents or IETF Contributions published or made publicly available before November 10, 2008. The person(s) controlling the copyright in some of this material may not have granted the IETF Trust the right to allow modifications of such material outside the IETF Standards Process. Without obtaining an adequate license from the person(s) controlling the copyright in such materials, this document may not be modified outside the IETF Standards Process, and derivative works of it may not be created outside the IETF Standards Process, except to format it for publication as an RFC or to translate it into languages other than English. 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 September 03, 2009. Expires September 2009 [Page 1] Internet-Draft draft-ali-pce-brpc-p2mp-ext-00.txt Abstract The ability to compute constrained Traffic Engineering Label Switched Paths (TE LSPs) for point-to-multipoint (P2MP) LSPs in Multiprotocol Label Switching (MPLS) and Generalized MPLS (GMPLS) networks across multiple domains (where a domain is a collection of network elements within a common sphere of address management or path computational responsibility such as an IGP area or an Autonomous Systems) has been identified as a key requirement [PCEP-P2MP-REQ]. This document addresses this requirement by extending backward recursive path computation (BRPC) technique proposed for Point-to-Point (P2P) LSPs in [P2P-BRPC] for P2MP LSP path computation in a multiple domains network. Conventions used in this document In examples, "C:" and "S:" indicate lines sent by the client and server respectively. 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 0. Table of Contents 1. Introduction...............................................3 2. Terminology................................................4 3. General Assumptions........................................5 4. Extension to BRPC Procedure for Path Computation for P2MP LSP...........................................................5 4.1. Definition of X-VSPT(i)...............................5 4.2. Definition of X-VSPT(i, d)............................6 4.3. P2MP-BRPC procedure...................................6 4.4. P2MP-BRPC Procedure Completion Failure................8 4.5. Example...............................................8 5. VSPT Encoding..............................................9 Expires September 2009 [Page 2] Internet-Draft draft-ali-pce-brpc-p2mp-ext-00.txt 6. IANA Considerations........................................9 7. Security Considerations....................................9 8. References.................................................9 8.1. Normative References..................................9 8.2. Informative References................................9 Author's Addresses...........................................10 1. Introduction The ability to compute constrained Traffic Engineering Label Switched Paths (TE LSPs) for point-to-multipoint (P2MP) LSPs in Multiprotocol Label Switching (MPLS) and Generalized MPLS (GMPLS) networks across multiple domains (where a domain is a collection of network elements within a common sphere of address management or path computational responsibility such as an IGP area or an Autonomous Systems) has been identified as a key requirement [PCEP-P2MP-REQ]. [P2P-BRPC] specifies a procedure for inter-domain shortest constrained paths computation for point-to-point (P2P) LSPs, using backward recursive path computation (BRPC) technique. This draft extends the technique specified in [P2P-BRPC] for P2MP LSP path computation. Just like [P2P-BRPC], its P2MP-TE extension preserves confidentiality across domains, which is sometimes required when domains are managed by different Service Providers. A P2MP tree is a graphical representation of all TE links that are committed for a particular P2MP LSP. In other words, a P2MP tree is a representation of the corresponding tunnel on the TE network topology. A sub-tree is a part of the P2MP tree describing how the root or an intermediate P2MP LSPs minimizes packet duplication when P2P TE sub-LSPs traverse common links. The computation of a P2MP tree requires three major pieces of information. The first is the path from the ingress LSR of a P2MP LSP to each of the egress LSRs, the second is the traffic engineering related parameters, and the third is the branch capability information. Generally, inter-domain P2MP tree (i.e. whose source and destinations of the P2MP LSP reside in a multiple different domains) is particularly difficult to compute even for a distributed PCE architecture. For instance, while the BRPC recursive path computation may be well-suited for P2P paths, P2MP path computation involves multiple branching path segments from the source to the multiple destinations. As such, inter-domain P2MP path computation may result in a plurality of per-domain path options that may be difficult to coordinate efficiently and effectively between domains. That is, when one or more domains have a multiple ingress and/or egress border nodes, there is currently no known technique for one domain to determine which border routers another domain will utilize for the inter-domain P2MP tree, Expires September 2009 [Page 3] Internet-Draft draft-ali-pce-brpc-p2mp-ext-00.txt and to limit the computation of the P2MP tree to those utilized border nodes. A trivial solution to computation of inter-domain P2MP tree would be to compute shortest inter-domain P2P paths from source to each destination and then combine them to generate an inter-domain Steiner P2MP tree. This, however, may require replication of incoming packets to all the P2P LSPs at the ingress PE to accommodate multipoint communication. Obviously, this solution is very inefficient for a couple of reasons. First, it places more replication burden on the ingress PE and hence has poor scaling characteristics, and second it does not make use of bandwidth sharing when one or more S2L LSPs share links along their paths, hence wasting bandwidth resources, memory and MPLS label space in the network. Apart from path computation difficulties faced due to the inter-domain topology visibility issues, the computation of the minimum P2MP Steiner tree, i.e. one which guarantees the least cost resulting tree, is an NP-complete problem. Moreover, adding and/or removing a single destination to/from the tree may result in an entirely different tree. In this case, the frequent Steiner tree computation process may prove computationally intensive, and the resulting frequent tunnel reconfiguration may even cause network destabilization. There are several heuristic algorithms presented in the literature that approximate the result within polynomial time that are applicable within the context of a single-domain. This draft extends the technique specified in [P2P-BRPC] for P2MP LSP path computation in an inter-domain environment using PCE [RFC4655]. 2. Terminology This document borrows terminology from [P2P-BRPC], which is repeated here for quick reference. ABR: Area Border Routers. Routers used to connect two IGP areas (areas in OSPF or levels in IS-IS). ASBR: Autonomous System Border Routers. Routers used to connect together ASes of the same or different Service Providers via one or more Inter-AS links. Boundary Node (BN): a boundary node is either an ABR in the context of inter-area Traffic Engineering or an ASBR in the context of inter-AS Traffic Engineering. Entry BN of domain(n): a BN connecting domain(n-1) to domain(n) along a determined sequence of domains. Expires September 2009 [Page 4] Internet-Draft draft-ali-pce-brpc-p2mp-ext-00.txt Exit BN of domain(n): a BN connecting domain(n) to domain(n+1) along a determined sequence of domains. Inter-AS TE LSP: A TE LSP that crosses an AS boundary. Inter-area TE LSP: A TE LSP that crosses an IGP area boundary. LSR: Label Switching Router. LSP: Label Switched Path. PCC: Path Computation Client. Any client application requesting a path computation to be performed by the Path Computation Element. 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. PCE(i) is a PCE with the scope of domain(i). TED: Traffic Engineering Database. VSPT: Virtual Shortest Path Tree. X-VSPT: Extended Virtual Shortest Path Tree. 3. General Assumptions This document makes the same assumptions as outlined in [P2P-BRPC] and will not be repeated here. 4. Extension to BRPC Procedure for Path Computation for P2MP LSP This section describes the extension to BRPC procedure defined in [P2P-BRPC]. It also details procedure on how extended BRPC can be used for path computation of a P2MP LSP. 4.1. Definition of X-VSPT(i) Definition of X-VSPT(i) is similar to definition of VSPT(i) in [P2P-BRPC], with a few exceptions outlined in the following. In the case of computation of VSPT(i), PCE(i) only considers the entry BNs of domain(i). That is only the BNs that provide connectivity from domain(i-1). This works well in P2P case as there is only one destination and there is no added value in knowing connectivity from BNs that do not Expires September 2009 [Page 5] Internet-Draft draft-ali-pce-brpc-p2mp-ext-00.txt provide connectivity from domain(i-1). However, for the case of P2MP tree path computation, and since there is usually more than one destination per P2MP LSP (some residing in different destination domains) knowing the connectivity from BNs that are not connected with domain(i-1) is useful. Specifically, it improves the ability of the ingress PCE to compute lower cost P2MP trees by favoring paths for new destination that branch off existing sub-tree as opposed to shortest end-to-end P2P path from source to destination. The set of BN-ex of domain remains the same as defined in [P2P- BRPC]. X-VSPT(i) is defined as follows- In each domain (i), o There is a set of X-en(i) all entry BNs, such that BN- en(k,i) is the kth entry BN of domain(i). o There is a set of Y-ex(i) exit BNs, such that BN- ex(k,i) is the kth exit BN of domain(i). VSPT(i), as defined in [P2P-BRPC], for P2P LSP is a tree that provides a list of shortest paths from BN-en(1,i), BN- en(2,i), ... BN-en(j,i) to destination such that j <= [X- en(i)], where [X-en(i)] is the number of entry BNs in domain(i). The X-VSPT(i), in addition to VSPT(i), includes shortest paths from the BN-en(k,i) to all BN-ex(i), such that k is the BN that is along the shortest path to destination, and BN-ex(i) is an exit BN in domain (i). Nonetheless, the X- VSPT(i) may exclude some BN-ex(i) according to policy constraints (either due to local policy or policies signaled in the path computation request). Also, when more than one BN-ex(i) connect to the same neighboring domain (domain (i+1)), the X-VSPT(i) only includes the BN-ex along the least cost path to domain (i+1). In the presence of inter-AS link, the X-VSPT includes the path of the inter-AS TE links connecting domain(i) to domain(i+1). For destination domain, the X-VSPT(i) includes shortest paths from the destination node to the set of BN-ex nodes. 4.2. Definition of X-VSPT(i, d) X-VSPT(i, d) is defined as X-VSPT at domain(i) to reach destination d of a P2MP tree. 4.3. P2MP-BRPC procedure In the following we outline steps of the P2MP-BRPC procedure. Expires September 2009 [Page 6] Internet-Draft draft-ali-pce-brpc-p2mp-ext-00.txt Given a set of destinations D = 1, 2, ... d, where |D| is the total number of destinations in the P2MP LSP. This draft assumes that the ingress PCE, PCE(1), has a mechanism to determine the set of PCEs (i.e. PCE-chain) to be traversed for the computation of the inter-domain path on per destination basis. The said mechanism is outside the scope of this document. Note, it is possible for the ingress PCE, PCE(1), to request path computation for destinations sequentially (one-by-one), or simultaneously (in-parallel). In the former case, the computation burden in P2MP-BRPC can be further reduced. PCE(1) can include the P2MP sub-tree(d-1), which includes X- VSPT(1, 1), X-VSPT(1, 2), ..., X-VSPT(1, d-1), i.e. that for destinations up to (d-1), in the PCE request for destination (d). By doing so, it is possible for PCE(n^d, d) to immediately compute a best path for (d) by computing a path from (d) to the closest branching node within the P2MP sub-tree(d-1). However, in this version of the draft only parallel requests for computation of XVSPT(n^d, d) for d = 1, 2, . . . D are considered. Denote by PCE(n^d, d) the PCE in the destination domain(n) of destination (d). A PCC discovers a PCE, PCE(1), that is capable of serving its path computation request and forwards to it the P2MP path computation request. PCE(1) will then iteratively send P2MP path requests to all destinations d = 1, 2, ... D, in the P2MP tree, as follows: Start of iteration(d): Step (1, d): PCE(1) sends a computation request for P2MP- BRPC to PCE(n^d, d). Step (2, d): PCE(n^d, d) computes X-VSPT(n^d, d) by including, in addition to VSPT(i), constraints shortest paths from the destination node (d) to all exit BNs BN- ex(i), as described earlier. When multiple BN-ex(n^d) connect to the same neighboring domain (domain (n^d +1)), the X-VSPT(n^d) only includes the BN-ex along the least cost path to domain (n^d +1). In the presence of inter-AS link, the X-VSPT includes the path of the inter-AS TE links connecting domain(n^d) to domain(n^d+1). Step (3, d): X-VSPT(n^d) is forwarded to PCE((n-1)^d,d). According to [P2P-BRPC], PCE((n-1)^d) computes VSPT((n- 1)^d) by finding constrained shortest paths from all BN- en((n-1)^d) to the destination (d) using VSPT((n)^d). When this step is completed, only a sub-set of BN- en((n)^d) are selected. At this point, PCE((n-1)^d,d) can prune those BN-en that were not considered in computation Expires September 2009 [Page 7] Internet-Draft draft-ali-pce-brpc-p2mp-ext-00.txt of VSPT((n-1)^d), and the respective X-VSPT((n)^d) branches attached to them. PCE((n-1)^d,d) appends to VSPT((n-1)^d) the X-VSPT((n- 1)^d) by by finding constrained shortest paths from all BN-en((n-1)^d) to all other BN-ex((n-1)^d). When multiple BN-ex((n-1)^d) connect to the same neighboring domain, the X-VSPT((n-1)^d) only includes the BN-ex along the least cost path to that domain. Step(i,d): the previous procedure is repeated PCE(i^d,d) where i= n-1 ... 2. End of iteration When PCE(1) receives replies with X-VSPTs(2,d) for all destinations, it forms a virtual graph composed of the source node, BNs included in the X-VSPTs, and the destinations. PCE(1) can then use a suitable heuristic to compute a feasible P2MP tree. Note, an X-VSPT(i, d) tree 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 BN is specified) so as to preserve confidentiality along with the respective cost. In the later case, various techniques can be used in order to retrieve the computed explicit paths on a per domain basis during the signaling process thanks to the use of path keys as described in [I- D.ietf-pce-path-key]. 4.4. P2MP-BRPC Procedure Completion Failure TBA in a later version of the document. 4.5. Example TBA in a later version of the document. 5. PCEP Protocol Extensions The X-BRPC procedure proposed in this document requires the specification of a new flag of the RP object carried within the PCReq message (defined in [PCEP]), as follows X-VSPT Flag Bit Number Name Flag TBD X-VSPT When set, the VSPT Flag indicates that the PCC requests the computation of an inter-domain P2MP-TE TE LSP using the X-BRPC procedure Expires September 2009 [Page 8] Internet-Draft draft-ali-pce-brpc-p2mp-ext-00.txt defined in this document. 5. VSPT Encoding Similar to the VSPT, the X-VSPT can be returned within a PCRep message. The encoding may consist of non-ordered lists of EROs where each ERO represents a path segment from a entry BN to the exit BNs, or from destination to an exit BN as described earlier in Section 4.3. Encoding using SERO is to be considered in the later version of this document. 6. IANA Considerations A new flag of the RP object (specified in [PCEP]) is defined in this document. X-VSPT Flag Bit Number Name Flag Reference TBD X-VSPT This document. 7. Security Considerations TBA in a later version of the document. 8. References 8.1. Normative References [P2P-BRPC] JP. Vasseur, et al, A Backward Recursive PCE-based Computation (BRPC) Procedure To Compute Shortest Constrained Inter-domain Traffic Engineering Label Switched Paths, draft-ietf-pce-brpc-09.txt, work in progress. [PCEP] Vasseur, JP., Ed. and JL. Le Roux, Ed., "Path Computation Element (PCE) communication Protocol (PCEP)", draft-ietf-pce-pcep, work in progress. 8.2. Informative References [PCEP-P2MP-REQ] S. Yasukawa, A. Farrel," PCC-PCE Communication Requirements for Point to Multipoint Multiprotocol Label Switching Traffic Engineering (MPLS TE)". [RFC4655] Farrel, A., Vasseur, J., and J. Ash, "A Path Computation Element (PCE)-Based Architecture", RFC 4655, August 2006. Expires September 2009 [Page 9] Internet-Draft draft-ali-pce-brpc-p2mp-ext-00.txt Author's Addresses Zafar Ali Cisco Systems, Inc. Email: zali@cisco.com Tarek Saad Cisco Systems, Inc. Email: tsaad@cisco.com Copyright Notice Copyright (c) 2009 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents in effect on the date of publication of this document (http://trustee.ietf.org/license-info). Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Legal This documents and the information contained therein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST 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 THEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Expires September 2009 [Page 10]