Subject: [Pce] AD review of draft-ietf-pce-pcep-inter-domain-p2mp-procedures

From: "Adrian Farrel" <[email-masked]>
Date: Thu, 10 Oct 2013 22:45:57 +0100

Hello authors of draft-ietf-pce-pcep-inter-domain-p2mp-procedures,

I have received the publication request from your document shepherd and
performed my usual AD review prior to initiating IETF last call and IESG
evaluation. The purpose of my review is to iron out any issues that we
can within the WG before moving ahead for the wider review.

Thank you for pushing this work as experimental and recognising the 
need for more development before moving to the standards track.

This document is nearly ready, but has a small collection of issues that
I would like you to look at. Many of these can be handled as editorial 
and resolved with small changes to the text. A few are slightly larger
and might need a little discussion.

Please treat all of these points as open for discussion and negotiation.

Thanks for your work,
Adrian

---

Please do a scrub for acronyms and make sure they are expanded on first
use in the main body of text.

LSR
P2P

---

Section 2

   Sub-tree: used to minimize packet duplication when P2P
   TE sub-LSPs traverse common links.

Tells me what it is used for but not what it is. Can you add an
explanation of what it is?

And what is a sub-LSP?

---

Section 3

I'm surprised that you say...

   However, [RFC6006] does not provide the necessary mechanisms and
   procedures to request the computation of inter-domain P2MP TE LSPs.

I should have thought the request was very simple and exactly as
defined in RFC 6006. That is, a PCC requests the computation of a P2MP
LSP and supplies the source, the destinations, and any other relevant
constraints. There is, in fact, nothing in a PCReq that limits or opens
a computation request to apply to one or more domains.

---

Section 3

   As described in [RFC5671] the computation of a P2MP tree
   requires three major pieces of information.  The first is the path
   from the ingress LSR of a P2MP TE LSP to each of the egress LSRs, the
   second is the traffic engineering related parameters, and the third
   is the branch capability information.

This didn't feel right, so I went back to 5671 and on re-reading, I
can't find this reference. Maybe I missed it and you can point me to it.

It seems to me that you may be mixing the process with the information.
I think it would be reasonable to say you need to know the network
topology that can connect the ingress with each of the egresses, but
the whole point of the exercise is to determine the paths from source to
destination. (Knowing the paths in advance is faintly reminiscent of a
computation technique for building a type of P2MP tree (shortest-path-
to-destination) that is only optimal in some dimensions.

---

Section 3

   Generally, an inter-domain P2MP tree (i.e., a P2MP tree with source
   and at least one destination residing in different domains) is
   particularly difficult to compute even for a distributed PCE
   architecture.  For instance, while the BRPC 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 multiple ingress and/or egress
   boundary nodes, there is currently no known technique for one domain
   to determine which boundary node of another domain will be utilized
   for the inter-domain P2MP tree, and no way to limit the computation
   of the P2MP tree to those utilized boundary nodes.

There seems to be a contradiction between these two paragraphs. In the
first you say that you could use BRPC but that it would be difficult. In
the second you say there is no known technique.

As it happens (and as a thought exercise), BRPC can be used relatively
simply to solve this problem. The issue, as you have correctly noted, is
that the amount of data gets very large, and coordination with many
destination domains is complex. But recall that BRPC assumes that the
domain sequence is predetermined, so the problem is not insurmountable.

That does not mean that I think using BRPC for this problem is
necessarily a good idea. Only that you should not state that it is
impossible to use it.

---

Section 3

   Computing P2P TE
   LSPs individually is not an acceptable solution for computing a P2MP
   tree.

While I am inclined to agree with you, your statement is too bold.
It is actually a perfectly viable solution that produces "good enough"
results in many situation. It may also be modified by placing some
restrictions on the later computations to improve the optimality of the
resultant tree.

So I think you need something along the lines of...

   Computing P2P TE
   LSPs individually does not guarantee the generation of an optimal
   P2MP tree for every definition of "optimal" in every topology.

---

Section 3

   P2MP Minimum Cost Tree (MCT), i.e. a computation which guarantees the
   least cost resulting tree, is an NP-complete problem.

Is MCT NP-complete? Do you have a reference? I can find reference for
Steiner being NP-complete, and Steiner is certainly a related problem.

---

Section 5

   1.  The computed P2MP TE LSP SHOULD be optimal when only considering
       the paths among the BNs.

I wonder why this is a requirement. Consider the figure below with
source (root) s and destinations (leaves) d1 through d3. let W, X, Y,
and Z be BNs.

             :         :          d1
             :         :         /
   a-b-c-d-e-W----g----Y-j-k-l-m-d2
  /          :         :       / \
 s------f----X--h---i--Z------o   d3
             :         :
             :         :

As stated this requirement prefers to use WY than XZ, yet using XZ will
result in the optimal tree by most normal measures.

Probably I am not interpreting your requirement correctly. But maybe it
could be clarified so that I would be more likely to get it right?

Perhaps you were trying to limit yourself to the "core tree". If so,
please consider the following figure.

             :         :          d1
             :         :         /
   a-----b---W----g----Y-j-k-l-m-d2
  /          :         :       / \
 s---c---d---X--h---i--Z------o   d3
             :         :
             :         :

In this case, the optimal core tree is sabWgY
But the optimal tree is scdXhiZom{d1,d2,d3}

---

Section 5

   2.  Grafting and pruning of multicast destinations in a domain SHOULD
       have no impact on other domains and on the paths among BNs.

It is fine to say that you have this as an objective, but I don't think
it is a requirement "specific to P2MP". It looks more like a constraint
that you wish to apply to your solution.

Even then, there are three issues you fail to note:
a. If you graft a destination in a domain that is not already part of
   the domain tree, then there will be an impact in another
   domain.
b. If you prune the last destination from within a domain there will be
   an impact in another domain.
c. You are only making this statement at the time of graft/prune, and
   not at the time of tree (or sub-tree) reoptimization.

It would almost certainly be better to rephrase this statement more
clearly in terms of what you are trying to achieve rather than the
result of that. It would appear that you do not want grafting a new
destination to cause the creation of an additional entry point to a
domain that already has an entry point. That is, you want the graft
to be contained to the subtree that is within a domain, and you accept
that the potential reduction in optimality of doing this (although I
note that you rejected the idea of setting up the P2MP tree in this
way).

---

Section 5

   5.  It SHOULD be possible to specify the domain entry and exit nodes.

   6.  Specifying which nodes are be used as branch nodes SHOULD be
       supported.

Way too much passive voice. Who can specify to whom in what message?

---

Section 6

   In addition to the OFs, the following constraint optimization may
   also be beneficial for P2MP path computation:

What is a "constraint optimization" if not an Objective Function?

---

Section 6

   3.  It SHOULD be possible to force the branches for all leaves within
       a domain to be in that domain.

I think you probably mean that is must be possible to limit the number
of entry points for a domain to be 1. This looks identical to the
previous point.

---

Section 7

   The following sections describe the core tree-based procedures to
   satisfy the requirements specified in the previous section.  A core
   tree-based solution provides an optimal inter-domain P2MP TE LSP.

No it doesn't as shown in the trivial example above.

But that is OK if (and only if!) your objective here is not to derive
optimal inter-domain P2MP TE LSPs, but to make an optimal core-tree
and let the final sub-trees go hang. That may be pretty acceptable
(especially or the transit carriers) and if you were to reposition the
document in that way, it would be fine.

---

Section 7.2

   The algorithms to compute the optimal large core tree are outside
   scope of this document.

What is a "large core tree" and how does it differ from a "core tree"?

---

I am pretty confused by the point of section 7.2.

What I think see is a complexity trade-off that recognises that it may
be easier to build a core tree first and then splice in leaves that live
in each domain. but it should be pretty clear that this trade-off 
sacrifices optimality with the potential of doing so fairly badly.

Additionally, I think that some of your objectives (section 6) are
hidden in the description in 7.2 where you have simply said "Apply
the OF to each of these M core trees and find the optimal Core Tree."

And this leaves me with two key points:
- Why can't the PCE use its own algorithms to look at the set of VSPTs
  to build the optimal core tree? Why do you require it to walk every
  possible path set?
- Why can't exactly the mechanism that you have described be applied to
  the full set of leaves? Or maybe to some mixture to leaves and BNs?
  Surely it is up to the PCE to make this choice.

I don't want to say to you "I wouldn't have done it like this", but I
think that to resolve my concerns you need to be clear in the document
about what trade-offs you are making and why, and you need to explain
what choices are open to the PCE.

---

7.4.1

My reading of http://www.iana.org/assignments/pcep/pcep.xhtml#rp-object
is that no bits are assigned for experimentation. How will your C bit be
kept safe in the field without colliding with some new PCEP feature
release?

---

7.4.2

   The procedure as described in this document requires the domain-tree
   to be known in advance.  This information may be provided dynamically
   as documented in the Hierarchical PCE (H-PCE) [RFC6805] framework, or
   obtained through the IGP/BGP routing information.

I don't think this reads right. Maybe:

"The information from which this domain-tree may be derived..."

---

7.4.2

Surely [DOMAIN-SEQ] is being used as a normative reference.

---

7.4.2

   The use of PCE sequence rather than domain-sequence, is
   based on deployment and implementation preference.

I think most readers will find this statement cryptic. 
1. What is the difference between domain-sequence and PCE-sequence?
2. In the case of deployment making a difference you can probably
   give some guidance.
3. In the case of implementation preference, isn't there some major
   risk of non-interoperability?

---

Section 7.5 is fine except for the way it is expressed. It says that
the ingress/root PCE will be required to have sessions with every PCE
providing a subtree. It says, "and here is a way to operate so it
doesn't."

You just need to fix the text so it reads better.

---

Section 7.6

I don't think that is a good or necessary use of "SHOULD".

---

Section 7.6

   1.  The BRPC procedure for each leaf node can be launched in parallel
       by the ingress/root PCE if the dynamic computation of the Core
       Tree is enabled.

   2.  Intra-domain P2MP paths can also be computed in parallel by the
       PCEs once the entry and exit nodes within a domain are known

This seems to be a change in direction from the previous text.

Does 1 actually mean s/each leaf node/each leaf BN/ ?

Does 2 actually mean s/Intra-domain P2MP paths/Intra-domain sub-trees/ ?