Subject: [Roll] I-D Action:draft-ietf-roll-minrank-hysteresis-of-03.txt

From: [email-masked]
Date: Tue, 03 May 2011 16:00:01 -0700

A New Internet-Draft is available from the on-line Internet-Drafts directories.
This draft is a work item of the Routing Over Low power and Lossy networks Working Group of the IETF.

	Title           : The Minimum Rank Objective Function with Hysteresis
	Author(s)       : O. Gnawali, P. Levis
	Filename        : draft-ietf-roll-minrank-hysteresis-of-03.txt
	Pages           : 10
	Date            : 2011-05-03

The Routing Protocol for Low Power and Lossy Networks (RPL) uses
objective functions to construct routes that optimize or constrain
the routes it selects and uses.  This specification describes the
Minimum Rank Objective Function with Hysteresis (MRHOF), an objective
function that selects routes that minimize a metric, while using
hysteresis to reduce churn in response to small metric changes.
MRHOF works with metrics that are additive along a route, and the
metric it uses is determined by the metrics RPL Destination
Information Object (DIO) messages advertise.

A URL for this Internet-Draft is:
http://www.ietf.org/internet-drafts/draft-ietf-roll-minrank-hysteresis-of-03.txt

Internet-Drafts are also available by anonymous FTP at:
ftp://ftp.ietf.org/internet-drafts/

Below is the data which will enable a MIME compliant mail reader
implementation to automatically retrieve the ASCII version of the
Internet-Draft.

---

From: Phoebus Chen <[email-masked]>
Date: Thu, 12 May 2011 14:36:53 +0200

Omprakash,

I like the changes you made to the document.

(Background: discussion leading to "4. Using MRHOF for Metric Maximization")
http://www.ietf.org/mail-archive/web/roll/current/msg06066.html

May I suggest alternate wording to the following text in Section 4:

       There is a fixed and well-known maximum metric value corresponding
       to the best path.  This is the path cost for the DAG root.
       Example, the best link reliability has a value of 1.

       Metrics are all positive.  Example, link reliability is always
       positive.

Change to:

       There is a fixed and well-known maximum metric value corresponding
       to the best path.  This is the path cost for the DAG root.
       For example, the logarithm of the best link reliability has a
       value of 0.

       The metrics in the maximization problem are all negative.
       For example, the logarithm of the link reliability is always
       negative.

In the original text, the metrics are positive in the original 
maximization problem where we multiply the reliabilities, but the reader 
may not be thinking in that context since everything in the MRHOF 
document refers to additive metrics.

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

P.S. while you're at it, I suggest this change to the last line of the 
abstract:

s/determined by the metrics RPL Destination Information Object (DIO) 
messages advertise./determined by the metrics advertised by the RPL 
Destination Information Object (DIO) messages./

On 5/4/11 1:00 AM, [email-masked] wrote:
> _______________________________________________
> Roll mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/roll

---

From: Omprakash Gnawali <[email-masked]>
Date: Thu, 12 May 2011 09:13:13 -0700

On Thu, May 12, 2011 at 5:36 AM, Phoebus Chen <[email-masked]> wrote:
> In the original text, the metrics are positive in the original maximization
> problem where we multiply the reliabilities, but the reader may not be
> thinking in that context since everything in the MRHOF document refers to
> additive metrics.

I think you are pointing out a different generality of this MRHOF. I
can change the title of this sub section to address both maximization
and multiplicative metrics. The text for maximization can remain as it
is. I can add a sentence at the end of that subsection saying we can
use MRHOF with some multiplicative metrics by converting them to the
additive version of that metric by taking their log. Does that satisfy
your concern?

- om_p

---

From: Phoebus Chen <[email-masked]>
Date: Thu, 12 May 2011 19:25:55 +0200

Response inline below.

On 5/12/11 6:13 PM, Omprakash Gnawali wrote:
> On Thu, May 12, 2011 at 5:36 AM, Phoebus Chen<[email-masked]>  wrote:
>> Omprakash,
>>

I'm still hesitant about the sentence "Metrics are all positive" in the 
context of the surrounding text.  Even when I first read it, my first 
reaction was "Maximization with positive metrics?  Just make your path 
as long as possible to add all the links.  Why would there be a 
maximum?"  Of course, this is because most of the document up to this 
point only refers to additive metrics and there isn't a clarification 
that the original optimization problem in the example was that of 
maximizing the product (where all link metrics are between 0 and 1), not 
the sum.  It's important here that the link metrics are less than 1 so 
that log(reliability) is negative.  You can say that this is implicit 
from the condition that there is a maximum path metric, but I think we 
should save the reader a littler thinking here and just state it.

My suggestion is to only address maximization problems using additive 
metrics, and use the example of log(reliability) to indicate how one 
type of maximization problem with multiplicative metrics can be 
converted to one with additive metrics.  The MRHOF document has been 
talking only about additive metrics thus far anyways, so I don't think 
we're restricting ourselves too much here.

I know, I was arguing for more generality (include maximization!) and 
now I'm asking you to restrict it.  I would have made a more clear 
recommendation in the beginning if I had thought it through a bit more. ;)

---

From: Philip Levis <[email-masked]>
Date: Thu, 12 May 2011 10:59:01 -0700

On May 12, 2011, at 10:25 AM, Phoebus Chen wrote:

> I'm still hesitant about the sentence "Metrics are all positive" in the context of the surrounding text.  Even when I first read it, my first reaction was "Maximization with positive metrics?  Just make your path as long as possible to add all the links.  Why would there be a maximum?"  Of course, this is because most of the document up to this point only refers to additive metrics and there isn't a clarification that the original optimization problem in the example was that of maximizing the product (where all link metrics are between 0 and 1), not the sum.  It's important here that the link metrics are less than 1 so that log(reliability) is negative.  You can say that this is implicit from the condition that there is a maximum path metric, but I think we should save the reader a littler thinking here and just state it.
> 
> My suggestion is to only address maximization problems using additive metrics, and use the example of log(reliability) to indicate how one type of maximization problem with multiplicative metrics can be converted to one with additive metrics.  The MRHOF document has been talking only about additive metrics thus far anyways, so I don't think we're restricting ourselves too much here.
> 
> I know, I was arguing for more generality (include maximization!) and now I'm asking you to restrict it.  I would have made a more clear recommendation in the beginning if I had thought it through a bit more. ;)

Phoebus, we're well past last call now. If your recommendations/suggestions are oscillating I'm not sure it's a good idea to incorporate them at such a late point. We want to be converging not spinning.

Phil