Subject: [Roll] [roll] #38: Decoupling routing metrics/constraints from Objective function

From: "roll issue tracker" <[email-masked]>
Date: Wed, 26 May 2010 09:52:04 -0000

#38: Decoupling routing metrics/constraints from Objective function
--------------------------------+-------------------------------------------
 Reporter:  jpv@…               |       Owner:  jpv@…        
     Type:  defect              |      Status:  new          
 Priority:  major               |   Milestone:               
Component:  rpl                 |     Version:               
 Severity:  Active WG Document  |    Keywords:               
--------------------------------+-------------------------------------------
 Email for JP Vasseur April 14:

 Dear all,

 Just an (important) clarification: as you know, we have defined routing
 "attributes" in the metric ID to be used
 as metrics or a constraints. And considering the number of applications
 for RPL, we will more than likely see a
 number of combinations of metrics and/or constraints. Should we want to
 specify an OF each time we want to
 use of combination of metric/constraint, we would certainly overlflow the
 RFC editor queue ;-) It would be nice
 to have a discussion on how we could come up with the limited number of
 OF, taking out the metric/constraint
 from the OF semantics. That would greatly simplify the work and still
 gives us the required flexibility.

 Thanks.

 JP.

 Email from Dominique Barthel on May 21

 Dear all,
 The current situation is that the metrics to be recorded/accumulated are
 defined in a DIO, while the combination/comparison algorithm to select the
 best route(s) based on these metrics is described in OF  documents. I find
 this situation suboptimal, for several reasons:

 · given the variety of LLNs applications out there and there need for
 complex combined metrics fitted to their application, it seems every
 system vendor will want to define its own Objective Function, thereby
 multiplying RFCs and reducing interoperability between devices of
 different vendors to one OF, namely OF0.

 · once a network is deployed, the nodes only know a few OFs, those that
 have been programmed in. A firmware updgrade is required to change the
 routing behavior beyond that. Given that nodes are going to be deployed
 for years in the field, I would want RPL to be more flexible at run time.

 Therefore, I suggest we remove  from the OF documents the description of
 the way the metrics are combined and the best route(s) selected, and
 provide a flexible model to encode this directly in the DIO, much like we
 already describe in a DAG Metric container how metrics are accumulated or
 recorded along a path. Some ideas will be proposed in a later post.

 Thoughts from the WG ?
 Best regards
 Dominique

-- 
Ticket URL: <http://trac.tools.ietf.org/wg/roll/trac/ticket/38>
roll <http://tools.ietf.org/wg/roll/>

---

From: Philip Levis <[email-masked]>
Date: Wed, 26 May 2010 09:00:11 -0700

On May 26, 2010, at 2:52 AM, roll issue tracker wrote:

> -------------------------------- 
> +-------------------------------------------
> -------------------------------- 
> +-------------------------------------------

I reiterate that I'm not convinced this is a good idea. In this  
domain, flexibility has a cost, in terms of code size and therefore  
unit price.

Phil

---

From: JP Vasseur <[email-masked]>
Date: Wed, 26 May 2010 18:22:27 +0200

Hi Phil,

Point well taken. Let me try to quickly reiterate the argument and get  
feed-back from others (this is why I
opened a ticket to hear the opinion of others).

In the metric-ID, we have defined a set of routing attributes that can  
be used as constraints and/or metrics,
which will be carried in the DAG container object. We currently have  
the concept of OF that determines a
set of rule for DODAG parent selection, ...

There are two options:
1) We decide to hard-code the metric/constraint (remember that  
constrained-based routing is a MUST in the
requirement documents) in the OF
2) We keep the decoupling option as defined today in the metric ID.

1) simply means that each time you define a new combination of metric  
and/or constraint, you must redefine
a new OF ! As I was pointed out when we had a discussion, looking at  
the spectrum of applications we will
likely have to define a *number* of OF, with little flexibility in the  
deployments. Just for the sake of illustration,
take one application Smart Grid: if you look at RPL deployment for  
Smart Metering, Distribution Automation,
Home Energy management, you already have at least 3 or 4 OFs since  
these applications will not use the
same metrics and/or constraints (ETX, Delays, battery-operated  
constraint, ...). Now considering all of the
other applications (Industrial, building, home), one can easily see  
that this won't scale.

So the proposal is easy ... just remove the hard coding constraint  
from the OF definition, and this provides
you a much more flexible solution at no cost. Then you will  
drastically reduce the number of OF to specify.

I do not agree with your "Cost" argument. This is in fact most likely  
the opposite since some devices will have
to support multiple instances, thus most likely, multiple OF if you  
hard code the metric/constraint, thus leading
to more cost complexity.

Last but not least, you can also have scenarios where you may want to  
relax constraint. With 1), no need to
support multiple OFs, you just remove the constraint.

Thoughts from others ?

JP.

---

From: Yoav Ben-Yehezkel <[email-masked]>
Date: Thu, 27 May 2010 12:04:56 +0300

Hi,

I agree that whatever we select in the end must not require us to define a
new OF per "metric/constraint combination".

I agree that if we come up with a small limited set of OFs - that might be
simpler to code, but not very flexible or extendible. My current
impression is that the decoupling that the metric supports now is highly
flexible in this perspective and not that complex.

We've had cases where we started off with one metric installed a few
thousands of units, only to realize that we didn't think about a few
constraints as well. It would have made backwards compatibility issues
much easier to handle if our stack was ready to have the constraints
further down the road.

Best regards,
Yoav

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of JP
Vasseur
Sent: Wednesday, May 26, 2010 7:22 PM
To: Philip Levis
Cc: [email-masked]
Subject: Re: [Roll] [roll] #38: Decoupling routing metrics/constraints
from Objective function

Hi Phil,

There are two options:

Thoughts from others ?

JP.

On May 26, 2010, at 6:00 PM, Philip Levis wrote:

>> Reporter:  jpv@.               |       Owner:  jpv@.

_______________________________________________
Roll mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/roll

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Thu, 27 May 2010 11:28:32 +0200

Hi Yoav and Dominique:

I agree with you all that we need to decouple. In my mind image, the OF
ties the result of the metric computation with some other policies that
implement the objective.
If we need some logic to play with the metrics themselves in order to
figure out something scalar off them, that should come with the metrics,
like having a metrics function in parallel to the objective function.
So, would you need a code for that metric function? Would that be in the
metric draft then?

Pascal

> From: [email-masked] [mailto:[email-masked]] On Behalf
Of
> Yoav Ben-Yehezkel
> Sent: Thursday, May 27, 2010 11:05 AM
> To: JP Vasseur; Philip Levis
> Cc: [email-masked]
> fromObjective function
impression is
> that the decoupling that the metric supports now is highly flexible in
this
> perspective and not that complex.
> 
much
> easier to handle if our stack was ready to have the constraints
further down
> the road.
from
> Objective function
feed-
> back from others (this is why I opened a ticket to hear the opinion of
others).
> In the metric-ID, we have defined a set of routing attributes that can
be used
> as constraints and/or metrics, which will be carried in the DAG
container
> object. We currently have the concept of OF that determines a set of
rule for
> DODAG parent selection, ...
> 
> There are two options:
> constrained-based routing is a MUST in the requirement documents) in
the
> OF
> and/or constraint, you must redefine a new OF ! As I was pointed out
when
> we had a discussion, looking at the spectrum of applications we will
likely
> have to define a *number* of OF, with little flexibility in the
deployments.
> Just for the sake of illustration, take one application Smart Grid: if
you look at
> RPL deployment for Smart Metering, Distribution Automation, Home
Energy
> management, you already have at least 3 or 4 OFs since these
applications
> will not use the same metrics and/or constraints (ETX, Delays,
battery-
> operated constraint, ...). Now considering all of the other
applications
> (Industrial, building, home), one can easily see that this won't
scale.
> So the proposal is easy ... just remove the hard coding constraint
from the OF
> definition, and this provides you a much more flexible solution at no
cost.
> Then you will drastically reduce the number of OF to specify.
> 
> 
the
> opposite since some devices will have to support multiple instances,
thus
> most likely, multiple OF if you hard code the metric/constraint, thus
leading
> Last but not least, you can also have scenarios where you may want to
relax
> constraint. With 1), no need to support multiple OFs, you just remove
the
> constraint.
> >> Just an (important) clarification: as you know, we have defined
> >> routing "attributes" in the metric ID to be used as metrics or a
> >> constraints. And considering the number of applications for RPL, we
> >> will more than likely see a number of combinations of metrics
and/or
> >> constraints. Should we want to specify an OF each time we want to
use
> >> of combination of metric/constraint, we would certainly overlflow
the
> >> RFC editor queue ;-) It would be nice to have a discussion on how
we
> >> could come up with the limited number of OF, taking out the
> >> metric/constraint from the OF semantics. That would greatly
simplify
> >> the work and still gives us the required flexibility.
> >

---

From: JP Vasseur <[email-masked]>
Date: Thu, 27 May 2010 11:37:41 +0200

> ties the result of the metric computation with some other policies  

yes

> So, would you need a code for that metric function? Would that be in  

if for example, you need to come with a polynomial function of  
multiple metrics
(this was a suggestion from Dominique some time ago), this would  
indeed be
an object in the metric-ID. For the time being, we already have the  
flexibility to
add metrics/constraints (and indicate their nature) in the ID

jP.

> Of JP

---

From: "Mathilde Durvy (mdurvy)" <[email-masked]>
Date: Thu, 27 May 2010 14:27:42 +0200

Hi JP, Pascal,

I like the idea of decoupling things, however I'm not quite sure to
understand how it would work. Does it mean that there is no OCP object
carried by the DIO, only metric/constraint objects which include how to use
them?
If this is the case how do you assess that you support the OCP? How do you
know which objective function to call when you receive a DIO? In short how
does this decoupling affect the DIO processing.
(right now, in our implementation when a node receives a DIO, it simply
looks at the ocp and based on this value it calls the corresponding
objective function (an actual C function) to order the potential parent with
respect to the existing ones) 

Best,
Mathilde

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of JP
Vasseur
Sent: jeudi, 27. mai 2010 11:38
To: Pascal Thubert (pthubert)
Cc: [email-masked] WG
Subject: Re: [Roll] [roll] #38: Decoupling routing
metrics/constraintsfromObjective function

On May 27, 2010, at 11:28 AM, Pascal Thubert (pthubert) wrote:

> Hi Yoav and Dominique:
>
> I agree with you all that we need to decouple. In my mind image, the 
> OF ties the result of the metric computation with some other policies 
> that implement the objective.

yes

> figure out something scalar off them, that should come with the 
> metrics, like having a metrics function in parallel to the objective 
> function.
> So, would you need a code for that metric function? Would that be in 
> the metric draft then?

if for example, you need to come with a polynomial function of multiple
metrics (this was a suggestion from Dominique some time ago), this would
indeed be an object in the metric-ID. For the time being, we already have
the flexibility to add metrics/constraints (and indicate their nature) in
the ID

jP.

>> Subject: Re: [Roll] [roll] #38: Decoupling routing metrics/ 
>> constraints fromObjective function
>>
>> Hi,
>>

---

From: JP Vasseur <[email-masked]>
Date: Thu, 27 May 2010 15:01:44 +0200

Hi,

> carried by the DIO, only metric/constraint objects which include how  

There would be an OF specified along the lines on Section 10:
	10. Guidelines for Objective Functions . . . . . . . . . . . . . . 59

And by the way, as you can see we do not specify the metrics in use.
And the metrics/constraints would be specified independently using the  
DAG metric Container.
A node could (if needed) add policy functions.

Does that make sense ?

Thanks.

JP.

> multiple
>>> constraints

---

From: Richard Kelsey <[email-masked]>
Date: Thu, 27 May 2010 11:01:40 -0400

> From: JP Vasseur <[email-masked]>
> Date: Wed, 26 May 2010 18:22:27 +0200
> 
> There are two options:

Here is a third option :-).

I think there are really three categories of information,
not two:

  - Path-specific metric/constraint values, such as the
    actual ETX or latency of a path.

  - Evaluation and combining functions for comparing sets of
    metric/constraint values and calculating rank deltas.
    Is an ETX=2, Latency=5 path better or worse than ETX=3,
    Latency=4 path, and by how much?

  - The OF, which uses an evaluation function in determining
    which parents to use, and so forth.

Only the path-specific metric/constraint values need to be
in every DIO.  Some of the information currently sent in the
Metric Container is really part of the evaluation function,
in that it relates to how the values are used and not what
they are.

The evaluation function and the OF should go in the DODAG
Configuration suboption.  If you change the evaluation
function or the OF, then you are making a different DODAG.
Both the evaluation function and the OF are likely to have
static parameters that could be included in the DODAG
Configuration suboption or be configured out-of-band.

The evaluation function might have dynamic parameters in
addition to the metric values themselves, to allow for
things like tuning the relative importance of latency and
reliability, say.  I guess these could go in the Metric
Container.

This could all all be broken down into something like
the following:
  - The RPL draft.
  - The metric draft.
  - A draft defining a set of evaluation functions, similar
    to the cryptographic suites used by TLS and IPsec.
    Examples are minimize RTX, maximize latency, and so
    forth.
  - A parameterized generic OF

                                 -Richard Kelsey

---

From: Nicolas DEJEAN <[email-masked]>
Date: Thu, 27 May 2010 18:01:28 +0200

Hello WG,

I tend to favor an approach where constraints and cost functions can
be altered at run-time.
a. during the installation phase, it is important to be able to
release some constraints if the connectivity is considered
insufficient after network initial build-up
b. as the network approaches the end of its life, it is highly
desirable to be able to fine tune its behavior based on its observed
status, to make the best use of its last gulps of energy.
c. because we intend to have our networks operate for 10 or 20 years,
but we are pressured for deploying them soon, we trust that
researchers will come with improved ways to combine metrics and
constraints over the network lifetime (compound metrics, weight
factors, etc). Not being able to retrofit (without reflashing)
research results into an existing network for 20 years seems like a
tremendous waste of brainpower.

Another point is that in the current situation and with my
understanding, the OF has to define at least the following "things":
- the parent selection and usage policy (choose one or several
parents, usage of load balancing, ...)
- the metrics and constraints in use and how to combine them,
- the rank computation function.
- ...

That means that each time we want to change one of these parameters,
we have to define a new OF.
Decoupling metrics and constraints from the other parts of the OF
would already drastically reduce the risk of seeing an unmanageable
number of different OFs on the market.

As a conclusion, I woul say that decoupling OF and metrics would not
only give us a powerful tool for dynamic network optimization but also
allow us making a big step in the right direction for insuring the
interoperability of equipments coming from different vendors.

Your thoughts?

Nicolas.

---

From: "Mathilde Durvy (mdurvy)" <[email-masked]>
Date: Fri, 28 May 2010 10:16:31 +0200

Hi JP,

 [JP]  There would be an OF specified along the lines on Section 10: 
10. Guidelines for Objective Functions . . . . . . . . . . . . . . 59

And by the way, as you can see we do not specify the metrics in use.
And the metrics/constraints would be specified independently using the DAG
metric Container.
A node could (if needed) add policy functions.

Does that make sense ?

Yes, so if I take the only example of OF given in Section 10  "minimize the
path cost using the ETX metric and avoid 'Blue' links".  Using the
decoupling approach we would say something like "minimize the path cost as
defined by the metric container and avoid links as specified by the
constraint object". Correct?
Best,
Mathilde

---

From: JP Vasseur <[email-masked]>
Date: Fri, 28 May 2010 11:43:55 +0200

Hi Mathilde,

On May 28, 2010, at 10:16 AM, Mathilde Durvy (mdurvy) wrote:

> And the metrics/constraints would be specified independently using  
> the DAG metric Container.
> Yes, so if I take the only example of OF given in Section 10   
> "minimize the path cost using the ETX metric and avoid 'Blue'  
> links".  Using the decoupling approach we would say something like  
> "minimize the path cost as defined by the metric container and avoid  
> links as specified by the constraint object". Correct?

Absolutely.

Do you agree with that plan ?

Thanks.

JP.

---

From: JP Vasseur <[email-masked]>
Date: Fri, 28 May 2010 11:45:13 +0200

Hi Mathilde,

Absolutely.

Thanks.

JP.

---

From: "Mathilde Durvy (mdurvy)" <[email-masked]>
Date: Fri, 28 May 2010 13:22:54 +0200

Hi JP,

Hi JP,

Does that make sense ?

Absolutely.

Yes, it makes a lot of sense to me.
Mathilde