[Docs] [txt|pdf] [Tracker] [Email] [Nits]

Versions: 00 01

   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
   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
      The list of Internet-Draft Shadow Directories can be
      accessed at
      This Internet-Draft will expire on September 03, 2009.

                     Expires September 2009            [Page 1]

Internet-Draft      draft-ali-pce-brpc-p2mp-ext-00.txt
      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",
      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
         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
      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
      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
      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
   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
      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-
      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
      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

                     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-
   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.
      This documents and the information contained therein are provided

                     Expires September 2009            [Page 10]

Html markup produced by rfcmarkup 1.123, available from https://tools.ietf.org/tools/rfcmarkup/