 1/draftietfpcepcepinterdomainp2mpprocedures06.txt 20140603 08:14:24.783845541 0700
+++ 2/draftietfpcepcepinterdomainp2mpprocedures07.txt 20140603 08:14:24.827846618 0700
@@ 1,25 +1,24 @@

PCE Working Group Q. Zhao
InternetDraft D. Dhody
Intended status: Experimental Huawei Technology
Expires: November 11, 2014 D. King
+Expires: December 3, 2014 D. King
Old Dog Consulting
Z. Ali
Cisco Systems
R. Casellas
CTTC
 May 11, 2014
+ June 3, 2014
PCEbased Computation Procedure To Compute Shortest Constrained P2MP
Interdomain Traffic Engineering Label Switched Paths
 draftietfpcepcepinterdomainp2mpprocedures06
+ draftietfpcepcepinterdomainp2mpprocedures07
Abstract
The ability to compute paths for constrained pointtomultipoint
(P2MP) Traffic Engineering Label Switched Paths (TE LSPs) across
multiple domains has been identified as a key requirement for the
deployment of P2MP services in MPLS and GMPLScontrolled networks.
The Path Computation Element (PCE) has been recognized as an
appropriate technology for the determination of interdomain paths of
P2MP TE LSPs.
@@ 36,21 +35,21 @@
InternetDrafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as InternetDrafts. The list of current Internet
Drafts is at http://datatracker.ietf.org/drafts/current/.
InternetDrafts 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 InternetDrafts as reference
material or to cite them other than as "work in progress."
 This InternetDraft will expire on November 11, 2014.
+ This InternetDraft will expire on November 29, 2014.
Copyright Notice
Copyright (c) 2014 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
(http://trustee.ietf.org/licenseinfo) in effect on the date of
publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect
@@ 58,21 +57,21 @@
include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . .3
1.1. Scope . . . . . . . . . . . . . . . . . . . . . . . . . .3
1.2. Requirements Language . . . . . . . . . . . . . . . . . .3
2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . .4
 3. Problem Statement . . . . . . . . . . . . . . . . . . . . . .5
+ 3. Examination of Existing Mechanisms . . . . . . . . . . . . .5
4. Assumptions . . . . . . . . . . . . . . . . . . . . . . . . .6
5. Requirements . . . . . . . . . . . . . . . . . . . . . . . . .7
6. Objective Functions and Constraints. . . . . . . . . . . . . .8
7. P2MP Path Computation Procedures . . . . . . . . . . . . . . .8
7.1. CoreTrees . . . . . . . . . . . . . . . . . . . . . . . .9
7.2. Optimal CoreTree Computation Procedure. . . . . . . . . .12
7.3. Subtree Computation Procedures . . . . . . . . . . . . .13
7.4. PCEP Protocol Extensions . . . . . . . . . . . . . . . . .13
7.4.1. The Extension of RP Object . . . . . . . . . . . . . .13
7.4.2. Domain and PCE Sequence . . . . . . . . . . . . . . .14
@@ 140,52 +139,37 @@
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].
2. Terminology
Terminology used in this document is consistent with the related
MPLS/GMPLS and PCE documents [RFC4461], [RFC4655], [RFC4875],
[RFC5376], [RFC5440], [RFC5441], [RFC5671] and [RFC5862].
 ABR: Area Border Router. Router used to connect two IGP domains
 (areas in OSPF or levels in ISIS).

 ASBR: Autonomous System Border Router. Router used to connect
 together ASes of the same or different Service Providers via one or
 more InterAS links.

 Boundary Node (BN): is either an ABR in the context
 of interarea Traffic Engineering or an ASBR in the context of
 interAS Traffic Engineering.
+ The additional terms CoreTree, Leaf Domain, Path Tree, Path Domain
+ Sequence, Path Domain Tree, Root Domain, SubTree and Transit/branch
+ Domain are further defined below.
CoreTree: a P2MP tree where the root is the ingress Label Switching
Router (LSR), and the leaf nodes are the entry BNs of the leaf
domains.
 Domain: a collection of network elements within a common sphere of
 address management or path computational responsibility such as an
 Interior Gateway Protocol (IGP) area or an Autonomous System (AS).

 Entry BN of domain(n): a BN connecting domain(n1) to domain(n) along
 a determined sequence of domains.
+ Entry BN of domain(n): a Boundary Node (BN) connecting domain(n1) to
+ domain(n) along a determined sequence of domains.
Exit BN of domain(n): a BN connecting domain(n) to domain(n+1) along
a determined sequence of domains.
 Leaf Domain: a domain with one or more leaf nodes.
+ HPCE: Hierarchical PCE (as per [RFC6805]).
 OF: Objective Function. a set of one or more optimization criterion
 (criteria) used for the computation of paths either for single or for
 synchronized requests (e.g. path cost minimization), or the
 synchronized computation of a set of paths (e.g. aggregate bandwidth
 consumption minimization, etc.). See [RFC4655] and [RFC5541].
+ Leaf Domain: a domain with one or more leaf nodes.
Path Tree: a set of LSRs and TE links that comprise the path
of a P2MP TE LSP from the ingress LSR to all egress LSRs (the leaf
nodes).
Path Domain Sequence: the known sequence of domains for a path
between the root domain and a leaf domain.
Path Domain Tree: the tree formed by the domains that the P2MP path
crosses, where the source (ingress) domain is the root domain.
@@ 194,23 +178,21 @@
Root Domain: the domain that includes the ingress (root) LSR.
Subtree: a P2MP tree where the root is the selected entry BN of the
leaf domain and the leaf nodes are the destinations (leaves) in
that domain. The subtrees are grafted to the coretree.
Transit/branch Domain: a domain that has an upstream and one or more
downstream neighbor domain.
 VSPT: Virtual Shortest Path Tree [RFC5441].

3. Problem Statement
+3. Examination of Existing Mechanisms
The Path Computation Element (PCE) defined in [RFC4655] is an entity
that is capable of computing a network path or route based on a
network graph, and applying computational constraints. A Path
Computation Client (PCC) may make requests to a PCE for paths to be
computed.
[RFC4875] describes how to set up P2MP TE LSPs for use in MPLS and
GMPLScontrolled networks. The PCE is identified as a suitable
application for the computation of paths for P2MP TE LSPs [RFC5671].
@@ 260,41 +242,41 @@
(i.e., it cannot produce a Minimum Cost Tree (MCT)) and in the
context of interdomain P2MP TE LSPs it cannot be used to reduce the
number of domain boundary nodes that are transited. Computing P2P TE
LSPs individually does not guarantee the generation of an optimal
P2MP tree for every definition of "optimal" in every topology.
Per Domain path computation [RFC5152] may be used to compute P2MP
multidomain paths, but may encounter the issues previously
described. Furthermore, this approach may also be considered to have
scaling issues during LSP setup. That is, the LSP to each leaf is
 signaled separately, and each boundary node must perform path
+ signaled separately, and each boundary node needs to perform path
computation for each leaf.
P2MP Minimum Cost Tree (MCT), i.e. a computation which guarantees the
least cost resulting tree, typically is an NPcomplete problem.
Moreover, adding and/or removing a single destination to/from the
tree may result in an entirely different tree. In this case,
frequent MCT path computation requests may prove computationally
intensive, and the resulting frequent tunnel reconfiguration may
even cause network destabilization.
This document presents a solution, procedures and extensions to
PCEP to support P2MP interdomain path computation.
4. Assumptions
Within this document we make the following assumptions:
o Due to deployment and commercial limitations (e.g., interAS
 peering agreements), the path domain tree will be known in
 advance;
+ (Autonomous System) peering agreements), the path domain tree will
+ be known in advance;
o Each PCE knows about any leaf LSRs in the domain it serves;
Additional assumptions are documented in [RFC5441] and are not
repeated here.
5. Requirements
This section summarizes the requirements specific to computing inter
domain P2MP paths. In these requirements we note that the actual
@@ 331,27 +313,27 @@
5. Reoptimization of existing subtrees SHOULD be supported.
6. It SHOULD be possible to compute diverse P2MP paths from existing
P2MP paths.
6. Objective Functions and Constraints
For the computation of a single or a set of P2MP TE LSPs, a request
to meet specific optimization criteria, called an Objective Function
 (OF), may be used. Using an OF to select the "best" candidate path,
+ (OF), MAY be used. Using an OF to select the "best" candidate path,
include:
o The subtree within each domain SHOULD be optimized using minimum
cost tree [RFC5862], or shortest path tree [RFC5862].
 In addition to the OFs, the following constraints may also be
+ In addition to the OFs, the following constraints MAY also be
beneficial for interdomain P2MP path computation:
1. The computed P2MP "coretree" SHOULD be optimal when only
considering the paths to the leaf domain entry BNs.
2. Grafting and pruning of multicast destinations (subtree) within
a leaf domain SHOULD ensure minimal impact on other domains
and on the coretree.
3. It SHOULD be possible to choose to optimize the coretree.
@@ 380,43 +362,43 @@
7. P2MP Path Computation Procedures
A P2MP Path computation can be broken down into two steps of core
tree computation and grafting of subtrees. Breaking the procedure
into two steps has following impact 
o The coretree and subtree are smaller in comparison to
the full P2MP Tree and are thus easier to compute.
 o An implementation may choose to keep the coretree fairly static
+ o An implementation MAY choose to keep the coretree fairly static
or computed offline (tradeoff with optimality).
 o Adding/Pruning of leaves required changes to subtree in leaf
+ o Adding/Pruning of leaves which require changes to subtree in leaf
domain only.
o The PCEP message size is smaller in comparison.
The following sections describe the coretree based procedures to
satisfy the requirements specified in the previous section. A core
tree based solution provides an optimal interdomain P2MP TE LSP.
7.1. CoreTrees
A coretree is defined as a tree that satisfies the following
conditions:
o The root of the coretree is the ingress LSR in the root domain;
o The leaves of the coretree are the entry boundary nodes in the
leaf domains.
 To support confidentiality these nodes and links may be hidden using
+ To support confidentiality these nodes and links MAY be hidden using
the pathkey mechanism [RFC5520], but they MUST be computed and be a
part of coretree.
For example, consider the Domain Tree in Figure 1 below,
representing a domain tree of 6 domains, and part of the resulting
coretree which satisfies the aforementioned conditions.
++
 Domain D1
 R 
@@ 499,35 +481,35 @@
Figure 3: CoreTree with PathKey
7.2. Optimal CoreTree Computation Procedure
Applying the coretree procedure to large groups of domains, such as
the Internet, is not considered feasible or desirable, and is out of
scope for this document.
The following extended BRPCbased procedure can be used to compute
 the coretree. Note that a root PCE may further use its own enhanced
+ the coretree. Note that a root PCE MAY further use its own enhanced
optimization techniques in future to compute the coretree.
A BRPCbased coretree path computation procedure is described below:
 1. Using the BRPC procedures to compute the VSPT(i) for each leaf
 BN(i), i=1 to n, where n is the total number of entry nodes for
 all the leaf domains. In each VSPT(i), there are a number of
 P(i) paths.
+ 1. Using the BRPC procedures to compute the VSPT(i) (Virtual
+ Shortest Path Tree) for each leaf BN(i), i=1 to n, where n is the
+ total number of entry nodes for all the leaf domains. In each
+ VSPT(i), there are a number of P(i) paths.
2. When the root PCE has computed all the VSPT(i), i=1 to n, take
one path from each VSPT and form all possible sets of paths, we
call them PathSet(j), j=1 to M, where M=P(1)xP(2)...xP(n);
 3. For each PathSet(j), there are n S2L (Source to Leaf BN) paths
+ 3. For each PathSet(j), there are n S2L (SourcetoLeaf) BN paths
and form these n paths into a coretree(j);
4. There will be M number coretrees computed from step3. An
optimal coretree is selected based on the OF and constraints.
Note that, since point to point BRPC procedure is used to compute
VSPT, the path request and response messages format as per [RFC5440]
are used.
Also note that the application of BRPC in the aforementioned
@@ 550,23 +532,23 @@
paths for an optimal coretree.
The proposed method may present a scalability problem for the
dynamic computation of the coretree (by iterative checking of all
combinations of the solution space), specially with dense/meshed
domains. Considering a domain sequence D1, D2, D3, D4, where the
Leaf Boundary Node is at domain D4, PCE(4) will return 1 path.
PCE(3) will return N paths, where N is E(3) x X(3), where E(k) x
X(k) denotes the number of entry nodes times the number of exit
nodes for that domain. PCE(2) will return M paths, where M = E(2)
 x X(2) x N = E(2) x X(2) x E(3) x X(3) x 1, Etc. Generally
 speaking the number of potential paths at the ingress CE Q =
 \prod E(k) x X(k).
+ x X(2) x N = E(2) x X(2) x E(3) x X(3) x 1, etc. Generally
+ speaking the number of potential paths at the ingress PCE Q =
+ prod E(k) x X(k).
Consequently, it is expected that the coretree will be typically
computed offline, without precluding the use of dynamic, online
mechanisms such as the one presented here, in which case it SHOULD be
possible to configure transit PCEs to control the number of paths
sent upstream during BRPC (trading trimming for optimality at the
point of trimming and downwards).
7.3. Subtree Computation Procedures
@@ 604,33 +586,36 @@
The extended format of the RP object body to include the C bit is as
follows:
The C bit is added in the flag bits field of the RP object to signal
the receiver of the message that the request/reply is for inter
domain P2MP coretree or not.
The following flag is added in this draft:
+ Bit Number Name Flag
+ TBA Coretree computation (Cbit)
+
C bit (CoreTree bit  1 bit):
0: This indicates that this is not for an interdomain P2MP
coretree.
1: This indicates that this is a PCEP request or a response
for the computation of a interdomain coretree or for the
grafting of a subtree to a interdomain coretree.
7.4.2. Domain and PCE Sequence
The procedure as described in this document requires the domaintree
 to be known in advance. This information may be either
+ to be known in advance. This information MAY be either
administratively predetermined or dynamically discovered by some
means such as Hierarchical PCE (HPCE) [RFC6805] framework, or
derived through the IGP/BGP routing information.
Examples of ways to encode the domain path tree include [RFC5886]
using PCEID Object and [DOMAINSEQ].
7.5. Using HPCE for Scalability
The ingress/root PCE is responsible for the coretree computation as
@@ 748,41 +733,44 @@
9.5. Requirements on Other Protocols and Functional Components
A PCE operates on a topology graph that may be built using
information distributed by TE extensions to the routing protocol
operating within the network. In order that the PCE can select a
suitable path for the signaling protocol to use to install the P2MP
TE LSP, the topology graph MUST include information about the P2MP
signaling and branching capabilities of each LSR in the network.
Mechanisms for the knowledge of other domains, the discovery of
 corresponding PCEs and their capabilities should be provided and that
+ corresponding PCEs and their capabilities SHOULD be provided and that
this information MAY be collected by other mechanisms.
Whatever means is used to collect the information to build the
topology graph, the graph MUST include the requisite information. If
the TE extensions to the routing protocol are used, these SHOULD be
as described in [RFC5073].
9.6. Impact on Network Operation
The use of a PCE to compute P2MP paths is not expected to have
significant impact on network operations. However, it should be
noted that the introduction of P2MP support to a PCE that already
provides P2P path computation might change the loading of the PCE
significantly, and that might have an impact on the network behavior,
especially during recovery periods immediately after a network
failure.
The dynamic computation of coretrees might also have an impact on
the load of the involved PCEs as well as path computation times.
+ It should be noted that precomputing and maintaining domaintrees
+ might be a considerable administration effort on the operator.
+
9.7. Policy Control
[RFC5394] provides additional details on policy within the PCE
architecture and also provides context for the support of PCE Policy.
They are also applicable to Interdomain P2MP Path computation via
the coretree mechanism.
10. Security Considerations
As described in [RFC5862], P2MP path computation requests are more
@@ 920,21 +908,21 @@
Authentication Option", RFC 5925, June 2010.
[RFC6805] King, D. and A. Farrel, "The Application of the Path
Computation Element Architecture to the
Determination of a Sequence of Domains in MPLS and
GMPLS", RFC 6805, November 2012.
[PCEPMIB] Koushik, K., Stephan, E., Zhao, Q., King, D., and J.
Hardwick, "PCE communication protocol (PCEP)
Management Information Base (Work in Progress)",
 February 2014.
+ April 2014.
[PCEPP2MPMIB] Zhao, Q., Dhody, D., Palle, U., and D. King,
"Management Information Base for the PCE
Communications Protocol (PCEP) When Requesting
PointtoMultipoint Services (Work in Progress)",
Aug 2012.
[DOMAINSEQ] Dhody, D., Palle, U., and R. Casellas, "Standard
Representation Of Domain Sequence (Work in
Progress)", July 2014.