Subject: RE: [Pce] Requirement for less-constrained path indraft-ietf-pce- comm-protocol-gen-reqs-00.txt

From: "Gray, Eric" <[email-masked]>
Date: Mon, 18 Jul 2005 15:57:10 -0400

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]]
--> Sent: Thursday, July 14, 2005 9:19 PM
--> To: Adrian Farrel
--> Cc: Gray, Eric; [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.
  
--> 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.
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?

--> 
--> > 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.

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.

--> 
--> > 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.

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, 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?

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

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

---

From: JP Vasseur <[email-masked]>
Date: Tue, 19 Jul 2005 09:47:25 -0400

Hi Eric,

> This is the point of obvious disagreement.

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

> 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

> issue is not with messaging, then what is it?

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

> 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, ...

> 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.

> 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.

> 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

/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.

---

From: "Igor Bryskin" <[email-masked]>
Date: Tue, 19 Jul 2005 11:41:20 -0400

JP.

As I have indicated earlier I don't believe that the complexity associated with signaling of constraint relaxation strategy justifies the results. 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. And what if the constraints are not independent? For instance, what if a PCC wants to get best tradeoff of several constraints ? 

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. 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.

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) 

It would be very easy to support the constraint relaxation strategies no matter how complex they are :=)

Cheers,
Igor
  ----- Original Message ----- 
  From: JP Vasseur 
  To: Gray, Eric 
  Cc: [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,

    JP,

        Please see below...

  Just try to decompose the various steps occurring during a path computation (request/reply) especially when the constraints cannot be fully satisfied:

  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

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

    --> 

  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, ... 

  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.

  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.

    --> 

  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.

  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.

    especially if you 

    --> 
    --> >

    You miss the point.

    scheme (a)

    scheme (b)

    scheme (c)

    ... and so on ...

    --> 
    --> >

  /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. 

  /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] ---

------------------------------------------------------------------------------

---

From: JP Vasseur <[email-masked]>
Date: Tue, 19 Jul 2005 12:00:38 -0400

Hi Igor,

Removing text since the message exceeds the max message size on the  
SMTP server ... see all about constraints relaxation ;-))

Comment: The co-authors of the PCEP ID propose to remove it from the  
PCEP ID (in the next revision) since the topic deserves its own ID.  
The PCEP ID will deal with basic protocol operations and set of  
messages/objects.

On Jul 19, 2005, at 11:41 AM, Igor Bryskin wrote:

> JP.
>
> As I have indicated earlier I don't believe that the complexity  
> associated with signaling of constraint relaxation strategy  
> justifies the results. 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. And what if the constraints are not independent? For  
> instance, what if a PCC wants to get best tradeoff of several  
> constraints ?
>

Wouldn't you have to configure it somewhere if you wanted to reach  
that objective ?

> 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. 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.

We can discuss the details of this in Paris, but this a perfectly  
valid way of allowing a PCC for the specification of constraint  
relaxation (although it does not address the "guessing" issue for non  
boolean constraint but we could find an easy way to deal with this).  
Good ! What I'm trying to avoid is a succession of serialized path  
computation requests without providing the ability for the PCE to  
come up with a closest match but no need to restart the whole thread  
here ...

>
> 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)
>

Well at this point, we may want to get more feed-back from Service  
Providers.

Cheers,

JP.

> It would be very easy to support the constraint relaxation  
> strategies no matter how complex they are :=)
>
> Cheers,
> Igor

---

From: Eiji Oki <[email-masked]>
Date: Wed, 20 Jul 2005 09:54:24 +0900

Hi

From SP point of view, the less-constraint approach is highly useful.
It is beneficial for an operator to get a suggested path by PCE
according to simple constraint relaxation rules with an efficient manner.

Thank you.
Eiji

On Tue, 19 Jul 2005 09:47:25 -0400

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

[snip]