Subject: [Roll] Decoupling Metrics and OF

From: JP Vasseur <[email-masked]>
Date: Wed, 14 Apr 2010 14:08:22 +0200

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.

---

From: Omprakash Gnawali <[email-masked]>
Date: Wed, 14 Apr 2010 15:00:48 -0700

On Wed, Apr 14, 2010 at 5:08 AM, JP Vasseur <[email-masked]> wrote:
> 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.

This makes sense if we take the position that the intricate logic that
makes a metric actually work in path selection is implementation
detail.

To say that -- all that is necessary for ETX metric-based routing is a
little bit of hysteresis and adding the metric along the links --
would be too simplistic and an implementation that does just that
probably will perform poorly in practice. A lot of thought and
experiences have guided the use of these metrics in the wireless
networks so it makes sense to write them down somewhere. The metric
draft does not seem the place to write them path selection logic
specific to that metric.

It would be instructive to look at all the additive metrics - hopcount
(OF0) and ETX (ETXOF), latency, etc. to see if they can be practically
treated as just numbers without regard to what they are during path
selection. Are there wireless networks that everyone is happy with
where the network can route on any additive metric without any metric
specific logic in path selection? If there are, it would make a case
for metric-agnostic OFs but I haven't personally seen such examples.

I can see a few common metrics to have their own objective functions
to incorporate the experiences on how to properly use those metrics in
path selection. At least - Hopcount, ETX, and latency. If we make sure
that the design of new OFs is guided by deep experience, I doubt we
will have a large number of OFs in the near future. Then as there is
more experience using other metrics, there can be more objective
functions.

Lets discuss and find ways to make the best use of these metrics. That
discussion should decide the number of RFCs we need.

Thanks.

- om_p

---

From: JP Vasseur <[email-masked]>
Date: Thu, 15 Apr 2010 11:10:04 +0200

> discussion should decide the number of RFCs we need.

Yes, we may have OF where specific handling of the metrics are  
required and must then be
part of the OF itself. For many other ones, we could certainly use a  
generic OF and leave
the metric out of it, relying on the semantic defined in the metric  
ID. We're in sync.

Cheers.

JP.

---

From: Richard Kelsey <[email-masked]>
Date: Thu, 15 Apr 2010 08:48:52 -0400

> From: JP Vasseur <[email-masked]>
> Date: Thu, 15 Apr 2010 11:10:04 +0200
>
> Yes, we may have OF where specific handling of the metrics
> are required and must then be part of the OF itself. For
> many other ones, we could certainly use a generic OF and
> leave the metric out of it, relying on the semantic
> defined in the metric ID. We're in sync.

Well, I'm not entirely in sync :-).

I completely agree that we should define at least one
generic OF that does not depend on the details of the
metrics in use.

Where I disagree is with metric containers needing to
describe the properties of the metrics (additive, etc.).
For a node to make use of an OF and associated metrics, it
has to implement both the OF and the metrics.  While the OF
might be able to get away with only knowing that a metric is
additive, implementing the metric requires knowing what it
is.  To participate in a DODAG that uses ETX, for example, a
node has to know how to calculate ETX.  It doesn't seem like
a stretch for the node to also know that ETX is additive.

                              -Richard Kelsey

---

From: JP Vasseur <[email-masked]>
Date: Thu, 15 Apr 2010 14:59:48 +0200

> generic OF that does not depend on the details of the

OK.

> is.

There are several reson that I think are strongly advocating for  
decoupling
the metrics from the OF:
1) The number of OFs that we would have to define considering the number
of potential combinations of {metrics,constraints}
2) That provides much more flexibility ... for example, you may want  
to define
a simple OF and let the root choose (or even dynamically adapt the  
metrics
and constraints to take into account). For the sale of illustration,  
the root may
receive for feed-back suggesting to relax a constraint "on the fly",  
which could
be done without having to support multiple OF on the node.

> To participate in a DODAG that uses ETX, for example, a

---

From: Richard Kelsey <[email-masked]>
Date: Thu, 15 Apr 2010 09:22:53 -0400

> Date: Thu, 15 Apr 2010 14:59:48 +0200
> 

JP,

I agree with everything you say here.  But none of it
requires that metric containers be self-describing.  Yes,
there needs to be a separation between metrics and the OF.
That interface does not need to be reflected in the packets.
The OF and metric implementations live in the same layer on
the same node.  They do not need to use IP to communicate.

                           -Richard Kelsey

---

From: Omprakash Gnawali <[email-masked]>
Date: Fri, 16 Apr 2010 15:36:25 -0700

> the same node.  They do not need to use IP to communicate.

It will be great to have some examples of those likely combinations to
make this discussion more concrete and to understand how to write one
general purpose OF. Low latency + Low ETX?

- om_p

---

From: Philip Levis <[email-masked]>
Date: Fri, 16 Apr 2010 16:29:53 -0700

> general purpose OF. Low latency + Low ETX?

Agreed. 

http://research.microsoft.com/en-us/um/people/blampson/33-hints/webpage.html

"Do one thing at a time, and do it well. An interface should capture the minimum essentials of an abstraction. Don’t generalize; generalizations are generally wrong."

Phil

---

From: Phoebus Chen <[email-masked]>
Date: Sat, 17 Apr 2010 19:00:29 +0200

JP,

I agree with Matteo
http://www.ietf.org/mail-archive/web/roll/current/msg03386.html
and Richard, that how the metrics are combined should be defined in the 
Objective Function and not in the metrics container.

Some of my opinions were expressed in an earlier email
http://www.ietf.org/mail-archive/web/roll/current/msg03212.html
(trying to link up the emails for those that are having trouble 
following the threads) but I will elaborate on it here below.

After all, what is an Objective Function?  It should not only describe 
how a link or node metric is calculated, but also how it is combined 
along the path(s) to get a path metric.  At the end of the day, you 
might want to compare such a path metric at a potential parent A with 
the path metric at a potential parent B to decide whether to add A or B 
to the parent set (among other rules for selecting parents).

Also, you may want to use a combination of operators to compute a single 
path metric that combined multiple types of link and node metrics.  One 
simple example is to take a weighted linear combination of two metrics 
(ex. w1*ETX + w2*latency, where w1 and w2 are constants).  There may be 
much better ways to combine metrics than this.  Trying to specify that 
now (in 2-bits, or n-bits) in the RPL metrics document will tie our 
hands later when a better idea of how to combine metrics arises.  Unless 
you want to deprecate and replace the RPL metrics RFC (when it becomes 
an RFC) each time a new way of combining metrics is proposed.

On the other hand, I don't see a problem with specifying the ways that 
different metrics can be combined in the RFCs for objective functions 
(so addition, max, min, multiply, etc. can be specified by n-bits + 
fields in a particular OCP object).  That might help limit the number of 
RFCs... there could be an RFC that tries to specify the different ways 
that various different metrics might be combined, and which gets 
deprecated by a later RFC when experimental evidence / experience 
suggests that there are other better ways to combine the metrics.

I'm trying to strike a balance between deprecating and replacing RFCs 
and limiting our options of combining metrics for objective functions.

As I indirectly indicated in another thread:
http://www.ietf.org/mail-archive/web/roll/current/msg03193.html
I see the Objective Function as something that tries to tie up some of 
the "loose ends" of the RPL specification.  They serve as "modules" that 
plug into RPL to tailor it to a particular application requirement.  I 
may have been a bit overzealous in my proposal of items that should be 
in the objective function, but maybe each of those items should be 
discussed ;).

-- 
Phoebus Chen
Postdoctoral Researcher
Automatic Control Lab, KTH (Royal Institute of Technology)
http://www.ee.kth.se/~phoebus

On 4/15/10 2:59 PM, JP Vasseur wrote:
>>> From: JP Vasseur<[email-masked]>
> _______________________________________________
> Roll mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/roll