Subject: [Roll] MRHOF draft-06 comments

From: Dario Tedeschi <[email-masked]>
Date: Wed, 07 Mar 2012 13:38:30 +0200

Below are some comments and questions on a few areas in the latest MRHOF 
draft that seem a little confusing.

In section 3.3. "
     MRHOF uses this Rank value to compute the Rank it associates with the
     path through each member of the parent set. The Rank associated with
     a path through a member of the parent set is the maximum of the
     corresponding calculated Rank value from above and that node's
     advertised Rank plus MinHopRankIncrease.
"

Which of the following formulae match the above description?
     PathRank = RankValue + AdvRank + MinHopRankIncrease
     PathRank = MAX(RankValue, AdvRank) + MinHopRankIncrease
     PathRank = MAX(RankValue, (AdvRank + MinHopRankIncrease))
Where:
     PathRank is the Rank associated with a path through a member of the 
parent set
     AdvRank is a node's advertised Rank
     RankValue is the Rank value taken from Table 1 in the draft.

Perhaps adding something like one of the above formulae would help in 
describing exactly how a node arrives at its own Rank?

In section 3.3. "
     A node sets its Rank to the maximum of three values:
     ...
"
Could the above be simplified/removed by just saying that members in the 
parent set meet the following condition:
     ( DAGRank(PathRank) < DAGRank(thisNode.AdvRank) )
Where:
     thisNode.AdvRank is a joining node's current Rank (starting at 
infinity before having joined a DODAG).
The above condition allows a parent's path Rank to vary up to an upper 
bound implicitly set by MinHopRankIncrease, before a node might exclude 
that parent from the set and possibly choose another preferred parent.

In section 3.4. "
                             This value is the path cost of the member of
    the parent set with the highest path cost.  Thus, while
    cur_min_path_cost is the cost through the preferred parent, a node
    advertises the highest cost path from the node to the root through a
    member of the parent set.  The value of the highest cost path is
    carried in the metric container corresponding to the selected metric
    when DIO messages are sent.
"
It's quite strange that the advertised path cost could be one associated 
with a member in the parent set that isn't currently in the path to the 
root. In my view, this could quite easily distort a DODAG away from its 
optimum, because nodes may advertised costs that are more pessimistic 
than need be. Surely once a node has selected a preferred parent, it 
should advertise the cost of that path through that parent, since that 
is the real and optimal cost to the root.

Reading the section further, MRHOF with ETX is exclude from the above 
requirement. Was that intentional?

Regards
Dario

---

From: Philip Levis <[email-masked]>
Date: Wed, 7 Mar 2012 07:38:18 -0800

On Mar 7, 2012, at 3:38 AM, Dario Tedeschi wrote:

> Below are some comments and questions on a few areas in the latest MRHOF draft that seem a little confusing.
> 
> In section 3.3. "

The last one. I'll clarify in the next revision. I appreciate your pointing out the lack of clarity in the current text.

> Where:
>    PathRank is the Rank associated with a path through a member of the parent set
> Perhaps adding something like one of the above formulae would help in describing exactly how a node arrives at its own Rank?
> 
> In section 3.3. "
> Could the above be simplified/removed by just saying that members in the parent set meet the following condition:

I don't think so. Among other things, the node decides on its advertised rank based on the parent set. Or are you saying that the parent set at execution i should be affected by the node's advertised rank at execution i-1? Or that a node picks a desired DAGRank and then sets its parent set accordingly?

The reason this part of the specification becomes complicated is because it's possible for Rank and metric values to diverge due to MinHopRankIncrease. I.e., let's say that MinHopRankIncrease is 512. This corresponds to an ETX of 4 (metric value 512). If you have a 3 hop path whose links have an ETX of 1, then the metric value will be 512 but the Rank will be 2048. Reconciling ETX and MinHopRankIncrease isn't difficult, but it starts to be weird on metrics like Node Energy. Hence the recommendation at the end about the relationship of MinHopRankIncrease and metrics.

> Where:
>    thisNode.AdvRank is a joining node's current Rank (starting at infinity before having joined a DODAG).
> The above condition allows a parent's path Rank to vary up to an upper bound implicitly set by MinHopRankIncrease, before a node might exclude that parent from the set and possibly choose another preferred parent.
> 
> In section 3.4. "
> It's quite strange that the advertised path cost could be one associated with a member in the parent set that isn't currently in the path to the root. In my view, this could quite easily distort a DODAG away from its optimum, because nodes may advertised costs that are more pessimistic than need be. Surely once a node has selected a preferred parent, it should advertise the cost of that path through that parent, since that is the real and optimal cost to the root.

There is a good reason for this, which is in line with the RPL specification: MaxRankIncrease. MaxRankIncrease creates a tension between advertising the Rank associated with the path through the preferred parent and requiring a new DODAG iteration. If a node advertises the Rank associated with the path through its preferred parent, but the next best member of the parent set is more than MaxRankIncrease greater in path length, then if the preferred parent fails the node can no longer route. So a node can advertise a conservative Rank which gives it flexibility in selection of a preferred parent in case of failure. 

There is also a tension between the size of the parent set and how conservative the advertised Rank is. For example, let's say MaxRankIncrease is very large, such that nodes can move down in the DODAG very freely, depending on the data path to detect possible routing loops. Then a node can maintain a parent set of size 1, its preferred parent, and advertise a very accurate Rank value.

> Reading the section further, MRHOF with ETX is exclude from the above requirement. Was that intentional?

No -- can you point me to the exact text which leads you to this conclusion, so I can fix it?

Thank you for your comments -- very helpful!

Phil

---

From: Dario Tedeschi <[email-masked]>
Date: Thu, 08 Mar 2012 14:20:32 +0200

Hi Philip

Thank you for the quick response. Please see my comments in-line.

On 12-03-07 05:38 PM, Philip Levis wrote:
>>     ( DAGRank(PathRank)<  DAGRank(thisNode.AdvRank) )
> I don't think so. Among other things, the node decides on its advertised rank based on the parent set.
That seems wrong to me: Shouldn't a node's advertised rank be based on 
the preferred parent it selects and the cost through that parent, while 
the preferred parent is selected based on the path costs of each member 
in the parent set. The parent set is a sub-set of those nodes closer to 
the root (lesser integer rank) than yourself.

>   Or are you saying that the parent set at execution i should be affected by the node's advertised rank at execution i-1?
Yes, except I'd change "should" to "could". Also, perhaps I should have 
used the word CurrentRank instead of thisNode.AdvRank to be more clear. 
I realise there is a bootstrap issue here, but the way I see it, a node 
starts off with an infinite rank (even though it would not advertise 
that). Starting at the bottom of the DODAG, the node ratchets up closer 
to the root as it hears and selects a new parent with sufficiently lower 
path cost.

> The reason this part of the specification becomes complicated is because it's possible for Rank and metric values to diverge due to MinHopRankIncrease. I.e., let's say that MinHopRankIncrease is 51…
OK, but the node still has to determine path Rank for each potential 
parent so why not use it to determine the parent set. Essentially if the 
path Rank of node A would not cause node B's advertised rank to increase 
more than one integer step (should node A be selected as a parent), then 
node A can be considered as a member of the parent set of node B. 
Otherwise, node A cannot be a member of node B's parent set. This would 
also ensure that node B never advertises a rank higher than it had 
previously advertised, because it could never have members in its parent 
set that would cause it to do so.

Another question I have for section 3.3: Item 2 says, "The Rank of the 
member of the parent set with the highest advertised Rank plus one". Is 
that really just "plus one" or should it be "plus MinHopRankIncrease" 
(i.e. plus one step in integer rank)?

>> In section 3.4 ...

In section 3.4 "
     If ETX is the selected metric, cur_min_path_cost is directly used as
     Rank and never advertised in a metric container.
"
If cur_min_path_cost is the path cost through the preferred parent how 
would the OF (using ETX) advertise the highest path cost of a member in 
the parent set. Or is it that the second and subsequent sentences in the 
first paragraph of section 3.4 do not apply to MRHOF when it's using ETX.

Regards
Dario

---

From: Philip Levis <[email-masked]>
Date: Thu, 8 Mar 2012 08:44:05 -0800

Responses inline.

On Mar 8, 2012, at 4:20 AM, Dario Tedeschi wrote:

> That seems wrong to me: Shouldn't a node's advertised rank be based on the preferred parent it selects and the cost through that parent, while the preferred parent is selected based on the path costs of each member in the parent set. The parent set is a sub-set of those nodes closer to the root (lesser integer rank) than yourself.

This isn't how DIO advertisements and parent sets work: take a look at the RPL spec. The parent set is the set of neighbors a node decides it might route through.  It might change its preferred parent to another element of the preferred parent set very quickly, more quickly than you want to advertise Rank changes through DIOs (think fast failover in case of a link seeing a burst of losses). Because of MaxRankIncrease, this means that a node must advertise a Rank conservative enough to use any member of its parent set. I.e. if you have a MaxRankIncrease of 10, a MinHopRankIncrease of 10, a preferred parent whose path has a Rank of 30 and a second parent whose past cost has a Rank of 51, you have to advertise a Rank >= 41, or you will not be able to fail over to the second parent when the first parent fails.

The specification is written this way in order to clearly separate the role of an OF -- neighbor set, parent set, and preferred parent selection, Rank computation -- from how RPL operates and maintains its invariants with respect to Rank.

> Yes, except I'd change "should" to "could". Also, perhaps I should have used the word CurrentRank instead of thisNode.AdvRank to be more clear. I realise there is a bootstrap issue here, but the way I see it, a node starts off with an infinite rank (even though it would not advertise that). Starting at the bottom of the DODAG, the node ratchets up closer to the root as it hears and selects a new parent with sufficiently lower path cost.

I'd argue that this is an implementation detail/decision?

> OK, but the node still has to determine path Rank for each potential parent so why not use it to determine the parent set. Essentially if the path Rank of node A would not cause node B's advertised rank to increase more than one integer step (should node A be selected as a parent), then node A can be considered as a member of the parent set of node B. Otherwise, node A cannot be a member of node B's parent set. This would also ensure that node B never advertises a rank higher than it had previously advertised, because it could never have members in its parent set that would cause it to do so.
> 

Note that the specification does *not* say how the parent set is selected. That is an implementation-specific decision. I feel it would be a mistake to specify parent set selection; I've seen enough variations and tweaks to achieve different goals, with different tradeoffs, that I'm uncomfortable making a strong recommendation of how to do it. That's why it's stayed out of the specification. 

> Another question I have for section 3.3: Item 2 says, "The Rank of the member of the parent set with the highest advertised Rank plus one". Is that really just "plus one" or should it be "plus MinHopRankIncrease" (i.e. plus one step in integer rank)?

It should be plus one, to maintain the invariant that a node advertises a Rank higher than every element of its parent set.

I should review these values again to make sure they satisfy all of RPL's invariants.

Hm -- I should probably also add a note about MaxRankIncrease and how this affects parent selection.

> If cur_min_path_cost is the path cost through the preferred parent how would the OF (using ETX) advertise the highest path cost of a member in the parent set. Or is it that the second and subsequent sentences in the first paragraph of section 3.4 do not apply to MRHOF when it's using ETX.

Ah, great, thanks. Just wanted to be sure I nail the exact text you see an issue with.

Phil

---

From: Dario Tedeschi <[email-masked]>
Date: Thu, 08 Mar 2012 13:49:45 +0200

Hi Philip

That seems wrong to me: Shouldn't a node's advertised rank be based on 
the preferred parent it selects, while the preferred parent is selected 
based on the path costs of each member in the parent set. The parent set 
is a sub-set of those nodes closer to the root (lesser integer rank) 
than yourself.

Yes, except I'd change "should" to "could". Also, perhaps I should have 
used the word CurrentRank instead of thisNode.AdvRank. I realise there 
is a bootstrap issue here, but the way I see it, a node starts off with 
an infinite rank (even though it would not advertise that). Starting at 
the bottom of the DODAG, the node ratchets up closer to the root as it 
hears and selects a new parent with sufficiently lower path cost.

OK, but the node still has to determine path Rank for each potential 
parent so why not use it to determine the parent set. Essentially, if 
the path Rank of node A would not cause node B's advertised rank to 
increase more than one integer step (should node A be selected as a 
parent), then node A can be considered as a member of the parent set of 
node B. Otherwise, node A cannot be a member of node B's parent set. 
This would also ensure that node B never advertises a rank higher than 
it has previously advertised.

One additional question for section 3.3.

>> In section 3.4. "Reading the section further, MRHOF with ETX is exclude from the above requirement. Was that intentional?
In section 3.4 "
the parent set.

Regards
Dario

---

From: Dario Tedeschi <[email-masked]>
Date: Fri, 09 Mar 2012 08:22:53 +0200

Thanks Philip

I think you have answered all my questions. I look forward to reading 
the next draft.

Dario

On 12-03-08 06:44 PM, Philip Levis wrote:
> This isn't how DIO advertisements and parent sets work: take a look at the RPL spec. The parent set is the set of neighbors a node decides it might route through.  It might change its preferred parent to another element of the preferred parent set very quickly, more quickly than you want to advertise Rank changes through DIOs (think fast failover in case of a link seeing a burst of losses). Because of MaxRankIncrease, this means that a node must advertise a Rank conservative enough to use any member of its parent set. I.e. if you have a MaxRankIncrease of 10, a MinHopRankIncrease of 10, a preferred parent whose path has a Rank of 30 and a second parent whose past cost has a Rank of 51, you have to advertise a Rank>= 41, or you will not be able to fail over to the second parent when the first parent fails.
>