Subject: [Roll] Fwd: New Version Notification for draft-gnawali-roll-minrank-hysteresis-of-00

From: Omprakash Gnawali <[email-masked]>
Date: Mon, 14 Jun 2010 12:52:17 -0700

Here is a draft that describes a metric-agnostic objective function.

- om_p

---------- Forwarded message ----------
From: IETF I-D Submission Tool <[email-masked]>
Date: Mon, Jun 14, 2010 at 12:50 PM
Subject: New Version Notification for
draft-gnawali-roll-minrank-hysteresis-of-00
To: [email-masked]
Cc: [email-masked]

A new version of I-D, draft-gnawali-roll-minrank-hysteresis-of-00.txt
has been successfully submitted by Omprakash Gnawali and posted to the
IETF repository.

Filename:        draft-gnawali-roll-minrank-hysteresis-of
Revision:        00
Title:           The Minimum Rank Objective Function with Hysteresis
Creation_date:   2010-06-14
WG ID:           Independent Submission
Number_of_pages: 8

Abstract:
Hysteresis delays the effect of changes in link metric on parent
selection.  Such delay makes the topology stable despite jitters in
link metrics.  The Routing Protocol for Low Power and Lossy Networks
(RPL) allows the use of objective functions to construct routes that
optimize or constrain a routing metric on the paths.  This
specification describes MRHOF, an objective function that minimizes
the node rank in terms of a given metric, while using hysteresis to
prevent excessive rank churn.  The use of MRHOF with RPL results in
nodes selecting stable paths that minimize the given routing metric
to the DAG roots.

The IETF Secretariat.

---

From: Yoav Ben-Yehezkel <[email-masked]>
Date: Tue, 15 Jun 2010 00:06:03 +0300

Hi,

I went over the new draft. Still I have a few comments to make sure the
following are covered:

1- There are cases where only one parent can be used, even if it is a bad
selection that does not pass the necessary criteria - it is either this or
nothing. The hysteresis should accommodate for that I think.

2- The hysteresis may need to be stable over time (not just one time the
threshold passes) in order to improve the parent. It could be a few times
(may be configurable) of passing the threshold, it could be percentage of
passing the threshold, etc. Otherwise, the network may easily become
unstable with constant changes, which as far as I know utility companies
don't like to see. Some say this is even more important than improving the
link (so hysteresis with large threshold is important for these in
particular). At least from my experience with PLC networks, each time one
turns on/off a device there's a good chance of improvement or
disconnection.

3- Sometimes a mixture of objectives are required to be used for
improvement. You may need to be able to improve to a parent node with both
constraint(s) and OF improvement (for example, it has at least RSSI X and
also better hop count).

Are all these issues covered?

Best regards and good work,
Yoav

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of
Omprakash Gnawali
Sent: Monday, June 14, 2010 10:52 PM
To: ROLL WG
Subject: [Roll] Fwd: New Version Notification for
draft-gnawali-roll-minrank-hysteresis-of-00

- om_p

---------- Forwarded message ----------
From: IETF I-D Submission Tool <[email-masked]>
Date: Mon, Jun 14, 2010 at 12:50 PM
Subject: New Version Notification for

Abstract:

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

---

From: Yoav Ben-Yehezkel <[email-masked]>
Date: Tue, 15 Jun 2010 00:43:36 +0300

One more thing, I think hysteresis should also be applied before a node
decides that its current preferred parent is no longer its preferred
parent (maybe this will require implicitly taking into account that some
messages from that parent were lost based on timeouts).

Yoav

-----Original Message-----
From: Yoav Ben-Yehezkel [mailto:[email-masked]]
Sent: Tuesday, June 15, 2010 12:06 AM
To: 'Omprakash Gnawali'; 'ROLL WG'
Subject: RE: [Roll] Fwd: New Version Notification for

Hi,

-----Original Message-----

- om_p

---------- Forwarded message ----------
From: IETF I-D Submission Tool <[email-masked]>
Date: Mon, Jun 14, 2010 at 12:50 PM
Subject: New Version Notification for

Abstract:

The IETF Secretariat.

---

From: Omprakash Gnawali <[email-masked]>
Date: Mon, 14 Jun 2010 20:36:12 -0700

> nothing. The hysteresis should accommodate for that I think.

It is not clear if you always want to do that. My experience is a lot
of times this is a bad idea because repeated transmission attempts
from such poorly connected node can keep other nodes from duty-cycling
for example. In some cases, eg., power line, it is perhaps ok to try
as many times as you want on the best path you know of.

The difficulty for an OF is - how can it distinguish the two cases.
The case where you don't want to route because all the candidates have
large metric values. And the case where you want to route despite all
the candidates have large metric values. One approach is to have a
special configuration parameter that tells an OF to ignore the max
link/path cost parameter. Another is to just set the max link/path
cost parameter to something much larger than what the computed metric
values will ever be.

> turns on/off a device there's a good chance of improvement or

Wouldn't setting the parent threshold to be a large number make it
more stable in your scenario?

> constraint(s) and OF improvement (for example, it has at least RSSI X and

This part is not well specified yet - how would mrhof interact with
other OFs if you want to use multiple OFs. Ideas welcome.

- om_p

---

From: Omprakash Gnawali <[email-masked]>
Date: Mon, 14 Jun 2010 20:40:07 -0700

> messages from that parent were lost based on timeouts).

Do you think this is better done when the metrics are computed? For
example, EWMA the metric, rather than compute a fresh metric based on
last few samples.

- om_p

---

From: Yoav Ben-Yehezkel <[email-masked]>
Date: Tue, 15 Jun 2010 07:50:34 +0300

Unless I misunderstood your question - I think that there may not be a few
samples because the node is disconnected from its parent.

Thanks,
Yoav

-----Original Message-----
From: Omprakash Gnawali [mailto:[email-masked]]
Sent: Tuesday, June 15, 2010 6:40 AM
To: Yoav Ben-Yehezkel
Cc: ROLL WG
Subject: Re: [Roll] Fwd: New Version Notification for

- om_p

---

From: Yoav Ben-Yehezkel <[email-masked]>
Date: Tue, 15 Jun 2010 08:00:56 +0300

Quick response to first two items:

"It is not clear if you always want to do that. My experience is a lot
of times this is a bad idea because repeated transmission attempts
from such poorly connected node can keep other nodes from duty-cycling
for example. In some cases, eg., power line, it is perhaps ok to try
as many times as you want on the best path you know of."
Yoav: It is definitely not always. Just when there's no other choice.

" The difficulty for an OF is - how can it distinguish the two cases."
Yoav: When a node doesn't have a preferred parent and as long as no other
potential parent passes the threshold, it collects the messages from these
nodes even though they didn't pass the threshold and eventually picks the
best of these bad possible selections.

" Wouldn't setting the parent threshold to be a large number make it
more stable in your scenario?"
Yoav: let's take hop count metric for example. If one time you get better
hop count from a node that is not the preferred parent (say by 5 which is
also the threshold), it should not mean that you immediately switch this
node to be your preferred parent. You should only switch if you see that
this change is stable for a reasonable amount of time/messages. Setting
the threshold to a higher number would not solve this case. Maybe for ETX
this works though.

Thanks,
Yoav

-----Original Message-----
From: Omprakash Gnawali [mailto:[email-masked]]
Sent: Tuesday, June 15, 2010 6:36 AM
To: Yoav Ben-Yehezkel
Cc: ROLL WG
Subject: Re: [Roll] Fwd: New Version Notification for

- om_p

---

From: Omprakash Gnawali <[email-masked]>
Date: Mon, 14 Jun 2010 22:07:30 -0700

> the threshold to a higher number would not solve this case. Maybe for ETX

It works if the metric has some low pass filter built to it. For
example, ETX with EWMA has this property. Latency with EWMA probably
has the same property.

What assumptions can  MRHOF make about the metrics? If it can assume
that the metric is already averaged, smoothed, then using one
threshold is good enough. If the metric has jitter, then I agree that
MRHOF should smooth that metric first, using hysteresis, averaging,
etc.

Garbage in garbage out is bad but no assumptions about the smoothness
of the metric could result in duplication of the smoothing
functionality - a good metric implementation probably already has some
averaging.

- om_p

---

From: Yoav Ben-Yehezkel <[email-masked]>
Date: Tue, 15 Jun 2010 08:59:34 +0300

OK - I see your point. Should these assumptions be specified somewhere?
BTW - I think there are newer references than the ones noted in your
draft, consider updating those.

Best regards,
Yoav

-----Original Message-----
From: Omprakash Gnawali [mailto:[email-masked]]
Sent: Tuesday, June 15, 2010 8:08 AM
To: Yoav Ben-Yehezkel
Cc: ROLL WG
Subject: Re: [Roll] Fwd: New Version Notification for

- om_p

---

From: "Navneet Agarwal (navagar)" <[email-masked]>
Date: Wed, 16 Jun 2010 11:57:09 +0530

Hi:
Couple of observations:
1. I guess this spec would supersede the etxof spec as the IANA value
recommendation is suggested to be 1. Is that right?
2. What about rank computation, step of rank and MinHopRankIncr values?
I think they could be different based on metrics applied.
3. I agree that the semantics of the threshold value and the smoothing
algorithm will be specific to the metric used. For example, for latency
and etx it could be based on percentage (or a delta) while for hop count
it could be delta. It would be good to specify in the document.

Thx

Regards,
Navneet

> From: [email-masked] [mailto:[email-masked]] On 
> Behalf Of Yoav Ben-Yehezkel
> Sent: Tuesday, June 15, 2010 11:30 AM
> To: Omprakash Gnawali
> Cc: ROLL WG
> Subject: Re: [Roll] Fwd: New Version Notification 
> fordraft-gnawali-roll-minrank-hysteresis-of-00
> 
> BTW - I think there are newer references than the ones noted 
> in your draft, consider updating those.
> 
> Best regards,
> Yoav
> 
> 
> > nodes even though they didn't pass the threshold and 
> eventually picks
> the
> > hop count from a node that is not the preferred parent (say 
> by 5 which
> is
> > also the threshold), it should not mean that you immediately switch 
> > this node to be your preferred parent. You should only 
> switch if you 
> > see that this change is stable for a reasonable amount of 
> > time/messages. Setting the threshold to a higher number would not 
> > solve this case. Maybe for
> ETX
> > this works though.
> 
> It works if the metric has some low pass filter built to it. 
> For example, ETX with EWMA has this property. Latency with 
> EWMA probably has the same property.
> 
> What assumptions can  MRHOF make about the metrics? If it can 
> assume that the metric is already averaged, smoothed, then 
> using one threshold is good enough. If the metric has jitter, 
> then I agree that MRHOF should smooth that metric first, 
> using hysteresis, averaging, etc.
> 
> Garbage in garbage out is bad but no assumptions about the 
> smoothness of the metric could result in duplication of the 
> smoothing functionality - a good metric implementation 
> probably already has some averaging.
> 
> - om_p

---

From: JP Vasseur <[email-masked]>
Date: Fri, 18 Jun 2010 19:31:31 +0200

Hi,

As pointed out in my comments on your ID (note that I am not saying  
that there are
no interesting points in the ID), we need to be careful at not trying  
to standardize
everything especially when there is no risk of interoperability issue.  
Many of the
examples discussed here are very much implementation specific.
I could provide a number of examples, where the behavior of a router  
or a host
is implementation specific and does not require standardization.

Thanks.

JP.