Subject: RE: [Pce] Requirement for less-constrained pathindraft-ietf-pce-c omm-protocol-gen-reqs-00.txt

From: "Gray, Eric" <[email-masked]>
Date: Mon, 25 Jul 2005 07:28:36 -0400

I think the point here is that there was absolutely no consensus to include
this in the
PCE protocol requirements.
 
One of the WG chairs - JP - asked if this should be included.  A highly
polar discussion
followed in which several people weighed in against doing so.
 
The fact that it may seem like a good idea to the author(s) is insufficient
reason to put
it in the draft, once the draft has become a working group document.
 
Therefore, lacking overwhelming indications that a consensus does exist to
put it in the
working group's draft, the author(s) should remove it.
 
--
Eric

-----Original Message-----
From: LE ROUX Jean-Louis RD-CORE-LAN
[mailto:[email-masked]]
Sent: Monday, July 25, 2005 4:45 AM
To: Igor Bryskin; JP Vasseur; Gray, Eric
Cc: [email-masked]
Subject: RE: [Pce] Requirement for less-constrained
pathindraft-ietf-pce-comm-protocol-gen-reqs-00.txt

Hi Igor, all
 
Please see inline for some comments,

  _____  

De : [email-masked] [mailto:[email-masked]] De la
part de Igor Bryskin
Envoyé : mardi 19 juillet 2005 17:41
À : JP Vasseur; Gray, Eric
Cc : [email-masked]
Objet : Re: [Pce] Requirement for less-constrained
pathindraft-ietf-pce-comm-protocol-gen-reqs-00.txt

JP.
 
As I have indicated earlier I don't believe that the complexity associated
with signaling of constraint relaxation strategy justifies the results. 
[JLLR] Please don't make things more complex than they are in practical
operational cases...

A practical case, that is deployed btw, is SRLG exclusion in FRR bypass
tunnel path computation:
The operator wants a path that excludes a set of SRLGs, and if this path
cannot be found he wants a path that excludes the maximum number of SRLGs in
this set. Unfortunately the PCC cannot guess this best relaxed set and for
instance if #SRLG = 4 this may lead  to 16 requests :-(
Conversely the PCE can run an algorithm that will return a path maximizing
the number of excluded SRLGs.
This is a simple case where less constrained paths are highly valuable.
 
Another simple case is "bounded delay bandwidth constrained" path
computation:
If the path cannot be found, I want the PCE to provide me a bandwidth
constrained path with a relaxed delay bound
or a delay bounded path with a relaxed bandwidth constraint. Unfortunately I
cannot guess these relaxed values, and it sound really
valuable, and not so complex (there are highly efficient heuristics) for the
PCE to perform such relaxation....
 
 Most of the constraints are non-boolean, and it is difficult IMO to provide
a simple yet flexible way for a PCC to articulate the desired way of
relaxation wrt each of the constraints.
[JLLR] In practical operational cases you won't have a lot of constraints,
so this sounds quite simple to articulate such relaxation (one could use a
set of bits vectors).
 
  And what if the constraints are not independent? For instance, what if a
PCC wants to get best tradeoff of several constraints ? 
[JLLR] We could also find a simple way to express these cases (again with a
vector encoding dependent constraints to be relaxed...)
My suggestion is to start with allowing for PCC to specify in a single
request a set of mandatory constraints and an ordered list of sets of
relaxable constraints: first, use the first set in the list (+ mandatory, of
course), if path computation fails - use the second one and so forth. 
[JLLR] Do you include constraint values or just identify constraints to be
relaxed? 
If the latter, then we fully agree.
 
 This is a much simpler way of doing the constraint relaxation and could be
just good enough, although it makes the size of requests and response
larger.
[JLLR] Simpler than which way?? 
 
By the way, do you remember that sometime ago I suggested to design the
PCC-PCE protocol in a such a way where each request/response is a BASIC
style program
  that could be interpreted  by both PCC and PCE? The intention was to
provide a very flexible way for a PCE to describe its capabilities and
introduce new ones, and for PCC to take the most of the PCE and specify what
exactly it wants from the requested path computation (what constraints and
optimization criterias to be used and how)
 
[JLLR] 
Note that this has already been proposed by Kireeti two years ago to pass
constraints in RSVP
(see
<http://www.watersprings.org/pub/id/draft-kompella-mpls-rsvp-constraints-01.
txt>
http://www.watersprings.org/pub/id/draft-kompella-mpls-rsvp-constraints-01.t
xt)
I have major concerns regarding the complexity of this approach. Please note
that the PCE may run quite complex algorithms (e.g. multi-constraint
heuristic algorithms, or, yet to be added in the charter, steiner tree
heuristics, requiring CPU intensive computation...). Do you also assume
passing the code for such complex algorithms??? This would drastically
complexify PCC operations....
 
It would be very easy to support the constraint relaxation strategies no
matter how complex they are :=)
[JLLR] Ah yes of course if you put a lot of complexity on the PCC :-(
 
I agree with you that this would provide a huge flexibility in the way to
express constraints,
but think about the standardization effort that this would imply (unless you
want to rely on Java applets :-))
 
Best Regards,
 
JL
 
Cheers,
Igor

----- Original Message ----- 
From: JP Vasseur <mailto:[email-masked]>  
To: Gray, Eric <mailto:[email-masked]>  
Cc: [email-masked] <mailto:[email-masked]>  
Sent: Tuesday, July 19, 2005 9:47 AM
Subject: Re: [Pce] Requirement for less-constrained path
indraft-ietf-pce-comm-protocol-gen-reqs-00.txt

Hi Eric, 

On Jul 18, 2005, at 3:57 PM, Gray, Eric wrote:

JP,

    From your earlier response, I see that you're aiming 
at the "greater of two evil" solutions.  Tch, tch, tch!!

    Please see below...

--> -----Original Message-----
--> From: JP Vasseur [ mailto:[email-masked] <mailto:[email-masked]>
]
--> Sent: Thursday, July 14, 2005 9:19 PM
--> To: Adrian Farrel
--> Cc: Gray, Eric; [email-masked] <mailto:[email-masked]> 
--> Subject: Re: [Pce] Requirement for less-constrained path
--> indraft-ietf-pce-comm-protocol-gen-reqs-00.txt
--> 
--> 
--> 
--> On Jul 14, 2005, at 12:26 PM, Adrian Farrel wrote:
--> 
--> > I want to pitch in on this thread because I think (I) see 
--> > where both JP and Eric are coming from. JP's proposals have
--> > the potential to significantly reduce the PCE processing 
--> > and cut down number of PCC-PCE transactions, but they also
--> > have the ability to massively increase the processing and  
--> > the size of the PCC-PCE transactions.
--> >
--> 
--> that said, it it pretty straightforward to see that the benefits  
--> undoubtedly outweigh the drawbacks. The request processing is  
--> definitely negligible compared to the communication overhead.

This is the point of obvious disagreement.

Good so at least we agree on the disagreement ;-)

--> Actually, it could be shown that the non support of such capability  
--> would have a drastic scalability impact on the solution especially  
--> upon resource contention.

Only if you assume that communication is the bottleneck.

Just try to decompose the various steps occurring during a path computation
(request/reply) especially when the constraints cannot be fully satisfied:
1) Path computation request sent to the PCE
2) PCE processing which includes:
    - queueing delay (PCE scheduler)
    - service time (PCE scheduler)
3) Path computation reply sent to the PCE.

Then repeat such cycle until a path is successfully computed.

Now consider the two cases where:
A- The PCC has to send multiple requests trying to guess the set of
constraints that could lead to a successful path computation.
B- The PCC specifies a set of rules and the PCE tries to find a path by
means of a single request

A few important facts:

- In case of A, when the constraint is not a boolean (e.g. bandwidth), it is
really a guess and even an approach based on dichotomy would unavoidably
lead to a non negligible number of cycles. 
- Some path computation algorithms have the capability to relax constraints
"on the fly" thus saving CPU cycles compared to serialized path
computations. 
- Without entering into some gory details about network analysis, queueing
systems and implementation-specific algorithms, try to decompose the steps
1), 2) and 3), and you'll easily identify where the bottlenecks are when
comparing the two approaches (especially 2).
- The set of rules does not have to be complex (see an example below) and
more importantly does not have to be used when inappropriate

Reality is that messaging only becomes a bottleneck if
message processing is excessively complex and/or it is 
done in a poorly thought out way. If the communication
issue is not with messaging, then what is it?

I'm of course not suggesting to design poorly thought out and excessively
complex messaging ;-)

--> 
--> > Thus we need to be quite careful in the specification of the
--> > protocol requirements and the protocol itself. It is not OK
--> > for us to say that if an individual PCC is irresponsible or 
--> > stupid that is its problem, because such an implementation
--> > would break the accessibility to the PCE for other 'normal' 
--> > PCCs.
--> >
--> 
--> On this aspect, I do agree !
--> 
--> > Unless there are "standard" constraint back-off functions 
--> > it is hard to conceive of a PCE guessing the correct back-
--> > off for the PCC that issued the request. Note that the more 
--> > "speculative paths" the PCE computes the more CPU it uses.
--> 
--> Speculative paths is definitely not an option considering the 
--> number of permutations ... we would unavoidably quickly fall
--> into some NP-Complete issues ;-) ... This is why the suggestion 
--> is made to start some discussion on the hierarchical relaxation 
--> policy. Note that it does not have to be awfully complex ...

Here we have many things said in few words. I know, because I can
identify numerous points for both agreement and disagreement.  :-)

The issue with permutations (and NP-complete issues) is one part
on which I think we agree.

The notion that a hierarchical relaxation approach avoids this is
one part on which I think we disagree.

Finally, the "wish" that it does not have to be complex is quite
interesting.  The only way that it will not be complex, is if the
actual decision making process is very simple in every case. The
point of contention is the fact that - while it probably can be 
very simple in most cases - it will almost certainly not be 1) the
same in every case and 2) good enough in every case.

Ah here I fully agree with you (last paragraph ;-)). The goal may not be to
design a solution that will address *all* cases and that will be good in
*all* cases. 
As a system designer, I'd be very happy if the proposed solution solves the
vast majority of the issues in an simple way. When not appropriate, just do
not use it. Vendor implementations should be able to be flexible enough so
that the operator could choose when to use such approach. See other similar
examples with hierarchical BGP policy rules, ACLs, ... 

If a different hierarchical relaxation policy might apply under
different circumstances, then the complexity of the protocol is
going to be greater than the combination of all "simple cases".

If the approach is not "good enough", then a PCC is forced to
fall back on the multiple messages approach.  Net gain: ~zero.

Indeed, we agree on the fact that we could make it awfully complex and
consequently not practically usable. I could also come up with many such
examples ... Conversely, one could easily come up with
*real*life*use*of*TE*scenario where such approach would be quite useful.
*Again*, think of how Service Providers use TE today ... Let me give you a
simple example here (which by the way would cover a good % of current
needs):

Packet LSPs,
Two constraints: affinity=RED and bandwidth=10
The set of constraints cannot be fully satisfied because of resource
contention.

Case A: The PCC sends multiple requests until a path can be found.
Case B: The PCC sends one request (affinity=RED, bandwidth=10) and specifies
to first relax the affinity, then find the closest bandwidth match. Note
that a different policy may be adopted different LSP types.

With such a simple example, you can easily see the benefit of B-
-> Reduced PCE processing (delay and service time)
-> Cut-down the number of transactions
-> Simple constraint relaxation rule

=> consequently reduced path computation delay

Again, I'm not claiming that all problems could be solved this way and that
an operator should/could always use such hierarchical constraints approach
but there are many circumstances whereby such approach would be IMO highly
valuable.

Of course, I'll wait for service providers to confirm that statement.

--> 
--> > So we must keep good control on this. It is a
--> > computational myth that it is possible to relax different  
--> > constraints on a
--> > single computational pass.
--> 
--> Ah no ... there are several constraints for which 
--> constraint can be relaxed and closest match can be 
--> found in on-go.
--> 
--> That said, even if it were not the case, the solution 
--> would still be valuable to cut-down the communication 
--> overhead and amount of processing signaling be the 
--> PCE's scheduler.
--> 
--> > In fact, the question "where did my computation fail"
--> > is notoriously impossible to answer except with the   
--> > response "in the network".
--> >
--> > Thus we should give full control to the PCC, and let 
--> > the PCE choose to supply less information if it thinks   
--> > that the PCC is asking too much. This control includes:
--> >
--> > a. The ability to say "this or nothing"
--> > b. The ability to say "tell me what constraints I
--> >    might relax to get a path"
--> > c. The ability to say "give me n alternate paths with 
--> >    with your choice of relaxed constraints" (c. is 
--> >    like b but with the paths supplied, and it is 
--> >    important to control the number)
--> > d. A way to state which constraints may be relaxed 
--> >    absolutely (this is easy)
--> > e. A way to replace one constraint supplied by the  
--> >    PCC with another also supplied by the PCC
--> > f. A way to specify an ordering for relaxation in 
--> >    recomputation attempts.
--> >
--> > My feeling is that e might be satisfied in the protocol  
--> > simply by listing the same object multiple times. But f
--> > is very messy. As soon as I have a few constraints and 
--> > I am willing to relax each of them by degrees I have a
--> > very complex relaxation problem to express.
--> 
--> Well not so sure ... Let's wait for the meeting in Paris to 
--> have an open discussion. I'd be happy to provide some ideas.
--> Actually one could point out that such constraint relaxation 
--> are used TODAY in operational networks (with CSPF).

One could point that out, if one wants to show that having 
a PCC make separate requests is the right way to go. I was
under the impression you were arguing the opposition point
of view.

In the CSPF case you identify, the Traffic Engineer is both
a PCC and a PCE and - with respect to the relaxation mode,
it is much more likely to act like a PCC than a PCE. In other
words, given a requirement for TE tunnel routing, it will 
most likely complete a computation based on a single set of
constraints and - if that fails - it may elect to relax the
path requirements and try again with different constraints.

But this is the whole point. When the PCE is co-located this can be done
without introducing substantial delays ... Conversely, think of a PCE
receiving a burst of requests from tens of PCCs after a network failure ...
this is precisely one of the aspects that I want to optimize.

This is essentially PCC behavior. Pushing this behavior into
the PCE saves on external messaging overhead, but at a huge
cost in complexity.  Now, instead of having a self-contained
entity (the PCC) deciding how next to proceed in getting a 
Path (should any attempt fail), it must communicate a decision 
making process to a delegate (the PCE) for every Path request
- irrespective of whether or not that Path Request would fail.

Unless the decision making options are very limited, this must
impose a higher level of processing on the PCE just to decode,
store and - eventually - act on the decision making process.

I doubt that the communication overhead is the bottle-neck for
PCE-PCC transactions, or the network over which they transpire.
I also strongly suspect that deployments will tend toward more
PCCs than PCEs, so - assuming that (for example) there are ten
times as many PCCs as PCEs - what is the advantage gained by
pushing the work of 1,000 PCCs onto 100 PCEs, 

no no ... we do not push the work of 1,000 PCCs onto 100 PCEs ... by
supporting such constraint relaxation approach you drastically reduce the
processing load on PCEs.

Jumping to the end of this email (considering the text provided above).

especially if you 
assume that most path requests will be satisfied prior to a PCC 
traversal of the decision tree.

--> 
--> >
--> > This is a problem that it is very easy for the PCC to  
--> > handle by issuing successive requests, but very hard for 
--> > the PCC to communicate to the PCE in a single request.
--> 
--> I do not think that it is hard for the PCC to communicate 
--> to the PCE in a single request.

You miss the point.

If "communication" was easy, you wouldn't have started this
discussion, and I wouldn't be continuing it.  :-)

Let's say that PCC X follows this scheme for one subset of its
requests:

scheme (a)
    Request a path with constraints A, B and C.
    On failure for A, request a path with constraint A1 that
        still satisfies B and C.
    On failure for A1, B or C, fail.

To cut down on communication overhead, we could communicate
this decision making policy to the PCE and make a single
request that either succeeds or fails according to this policy.

But this PCC (or another) also has a decision making schemes as
follows for other types of services:

scheme (b)
    Request a path with constraint A, C and D.
    On failure for C, request a path with constraints A and D
        only
    On failure for A or D, fail.

scheme (c)
    Request a path with constraints B, C and D.
    On failure (for B, C or D) request an unconstrained shortest
        path.

... and so on ...

Hence, given any arbitrary number of potential constraints, the
number of possible decision making policies we need to define
is clearly combinatorial (i.e. - NP) in the number of possible
constraints (and possible relaxations of each).

However, if we do not cover all of the possibilities, then we
constrain the services that our customers can sell, their ability
to differentiate themselves from their competitors and even the
service pricing structures that are available to their customers
in turn.

To eliminate this concern, all we need to do is define a language
for describing a decision making process.  Done much work in the
area of defining languages like this?  :-)

--> 
--> >
--> > So, I'd like to see some text from SPs on this subject 
--> > before we add anything to the requirements I-D.
--> >
--> 
--> I think that the DT is working on it.

So, this is confusing. Are you saying that it's out of the hands
of the WG because the authors are taking this work on anyway?

/Chair Hat/

I just meant that the DT was working on the new revision of
draft-ietf-pce-comm-protocol-gen-reqs with the intention to cover that
aspect for WG input (this new rev has now been published). As you know, by
definition, a Working Group document is owned by the Working Group. 

Your comments are of course more than welcome. 

/Chair hat removed/

We may just want to sit down in Paris and discuss more on this if you will.

JP.

--> 
--> Cheers,
--> 
--> JP.
--> 
--> > Cheers,
--> > Adrian
--> >
--> > --- [SNIP] ---

  _____  

_______________________________________________
Pce mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/pce

_______________________________________________
Pce mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/pce

---

From: JP Vasseur <[email-masked]>
Date: Mon, 25 Jul 2005 07:46:49 -0400

Hi Eric,

/ Chair Hat /

On Jul 25, 2005, at 7:28 AM, Gray, Eric wrote:

> I think the point here is that there was absolutely no consensus to  
> include this in the
> One of the WG chairs - JP - asked if this should be included.  A  
> highly polar discussion

Indeed, I asked to the WG whether there was a need for such capability.

> The fact that it may seem like a good idea to the author(s) is  
> insufficient reason to put

Correct, no WG consensus has been reached on this issue as of now.  
Several ones were opposed to it, several other ones were in favor.

> Therefore, lacking overwhelming indications that a consensus does  
> exist to put it in the

Here is the plan:
(1) Ask for a vote within the WG on this issue. I would suggest some  
discussion in Paris followed by discussion on the mailing list. The  
next revision of the protocol requirement will reflect the WG  
consensus on this particular aspect.
(2) For the next revision, the authors of the PCEP spec mentioned  
that they would remove the "less-constrained path computation" from  
the PCEP specification. "Less-constrained path computation" aspects  
will potentially be discussed in another ID, should there be a WG  
consensus.

Note that I would like us to make progress of the basic  
functionalities first (such as the PCE requirement ID, architecture,  
PCE communication protocol, ...) so as to meet our Milestones. More  
advanced features could be discussed in a second step.

Thanks.

JP.