Subject: [Roll] RPL preferred vs. alternate parents

From: <[email-masked]>
Date: Wed, 5 Aug 2009 13:08:22 +0200

Hello all,

I have a question regarding the preferred vs. alternate parents in the
RPL draft.

The RPL draft consistently states :
- 3.3.1.5 "It is recommended that a node maintain its DAG Parent set
such that its most preferred parent from the OCP goals also has the
greatest depth value in the DAG parent set."
- 3.4.1 "For a node N, and its most preferred parent M, .... all parents
in the DAG parent set must be of a depth less than or equal to
DAGDepth(M)."
- 5.2.1 "All nodes in the DAG Parent set should be of a depth less than
or equal to the most preferred DAG parent."

However, the rationale offered in 3.4.1 isn't quite clear to me. "This
mechanism serves to avoid loops in the case where an alternate parent is
used- if no alternate parent is deeper than the preferred parent then
loops are avoided."
It seems to me that once the packet has been forwarded by node N to an
alternate parent, it's _that_ parent's responsability to forward it
further up the DAG without loop, not node N's. What has the ordering of
node N's preferred parent vs node N's alternate parents to do with it?

Further, the whole text of 3.4.1 ("more optimum", "same optimality",
"less optimum") leads one to think that higher in the DAG is better.
Something sounds wrong to me if node N's preferred parent should
precisely be the "worse" of its parents.

Can anybody offer a substantiated explanation?
Thanks

Dominique

---

From: "M. B. Anand" <[email-masked]>
Date: Wed, 5 Aug 2009 21:16:13 -0400

Hi Dominique,

> precisely be the "worse" of its parents.

The alternates will themselves be at equal or less depth compared to the
preferred, but they may not offer the _node N_ a chance to become less deep
because that depends also on the node's optimization metric w.r.t the
alternates. If one of the candidate neighbors does offer this, by all means
the node can make that candidate the preferred. This is the `moving inwards
along the DAG' - section 3.3.1.6, 5th paragraph. Of course, the node N will
then need to update its set of parents. So the preferred parent will be the
"best" according to the node's optimization.

The idea is to forward traffic or move inwards - less deep - in DAGDepth -
then there will never be loops. Forwarding sideways - same DAGDepth - is
also allowed but that has some chance of loops. Going deeper will create the
chance of loops.

BTW, in the draft "higher" in the DAG means closer to the root, inwards in
the DAG. See for example, Section 3.3.1.6, Section 5.3, point #6, Section
5.3.3.1 etc. I think you mean "lower" when you say " leads one to think that
higher in the DAG is better".

Regards,
Anand.

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

---

From: <[email-masked]>
Date: Thu, 6 Aug 2009 11:40:30 +0200

Hello Anand, all,
 
Thanks for your answer. I do indeed share the notion that "higher" means "closer to the root".
Let me try to reformulate my question with an example.

Node N springs into existence and discovers a few neighbors A, B, C and D
- node A advertises depth 1.25
- node B depth 3.75
- node C depth 4.50
- node D depth 8.25
Given the advertised depth, the link costs and other characteristics, Node N determines through its objective function that its preferred parent is node B and that it should take 5.25 (= B's depth 3.75 + link cost 1.50) as its own depth.
Node N then fleshes up its DAG by adding alternate parents:
- node D is out of the question because it is lower in the DAG (event horizon).
- node A can be considered for inclusion as an alternate parent
>From the excerpts of the RPL draft quoted below, as well as from Pascal's email, I understand that C is not eligible to become an alternate parent to N.
My question is: "Why?"

The only tentative explanation I've read so far is in the RPL draft, Section 3.4.1 "This mechanism serves to avoid loops in the case where an alternate parent is used- if no alternate parent is deeper than the preferred parent then loops are avoided." which I don't view as an explanation. If each node only forwards packet to nodes with lesser depth (barring forwarding to siblings for this discussion) then loops will be avoided even is C is included as an alternate parent of N. 
Am I mistaken somewhere?

[Of course, if we enforce depth to be integers and node N's depth to be exactly its preferred parent's depth + 1, then this whole discussion goes away. But it is my understanding that we are now dealing with increments that are not exactly 1, and/or fractional depths, aren't we?]

Regards, 
Dominique

Quotes :
- 3.3.1.5 "It is recommended that a node maintain its DAG Parent set such that its most preferred parent from the OCP goals also has the greatest depth value in the DAG parent set."
- 3.4.1 "For a node N, and its most preferred parent M, .... all parents in the DAG parent set must be of a depth less than or equal to DAGDepth(M)."
- 5.2.1 "All nodes in the DAG Parent set should be of a depth less than or equal to the most preferred DAG parent."
- Pascal's email July 3rd 14:06 +0200 "The idea on the table would be to select a preferred parent (that might not be least depth because depth might not be the foremost argument in parent selection) and then constrain all other parents to be not_deeper." http://www.ietf.org/mail-archive/web/roll/current/msg01463.html
________________________________

De : M. B. Anand [mailto:[email-masked]] 
Envoyé : jeudi 6 août 2009 03:15
À : BARTHEL Dominique RD-TECH-GRE
Objet : Re: [Roll] RPL preferred vs. alternate parents

Hi Dominique,

The alternates will themselves be at equal or less depth compared to the preferred, but they may not offer the _node N_ a chance to become less deep because that depends also on the node's optimization metric w.r.t the alternates. If one of the candidate neighbors does offer this, by all means the node can make that candidate the preferred. This is the `moving inwards along the DAG' - section 3.3.1.6, 5th paragraph. Of course, the node N will then need to update its set of parents. So the preferred parent will be the "best" according to the node's optimization. 

The idea is to forward traffic or move inwards - less deep - in DAGDepth - then there will never be loops. Forwarding sideways - same DAGDepth - is also allowed but that has some chance of loops. Going deeper will create the chance of loops.

BTW, in the draft "higher" in the DAG means closer to the root, inwards in the DAG. See for example, Section 3.3.1.6, Section 5.3, point #6, Section 5.3.3.1 etc. I think you mean "lower" when you say " leads one to think that higher in the DAG is better". 

Regards,
Anand.

	Dominique

---

From: "M. B. Anand" <[email-masked]>
Date: Thu, 6 Aug 2009 13:43:19 -0400

Dominique,

On Thu, Aug 6, 2009 at 5:40 AM, <[email-masked]>wrote:

> Given the advertised depth, the link costs and other characteristics, Node
> N determines through its objective function that its preferred parent is
> node B and that it should take 5.25 (= B's depth 3.75 + link cost 1.50) as
> its own depth.
> From the excerpts of the RPL draft quoted below, as well as from Pascal's
> email, I understand that C is not eligible to become an alternate parent to
> N.
> My question is: "Why?"
>
> The only tentative explanation I've read so far is in the RPL draft,
> Section 3.4.1 "This mechanism serves to avoid loops in the case where an
> alternate parent is used- if no alternate parent is deeper than the
> preferred parent then loops are avoided." which I don't view as an
> explanation. If each node only forwards packet to nodes with lesser depth
> (barring forwarding to siblings for this discussion) then loops will be
> avoided even is C is included as an alternate parent of N.
> Am I mistaken somewhere?
>
> [Of course, if we enforce depth to be integers and node N's depth to be
> exactly its preferred parent's depth + 1, then this whole discussion goes
> away. But it is my understanding that we are now dealing with increments
> that are not exactly 1, and/or fractional depths, aren't we?]

Ah, I see what you meant. BTW, DAGDepth is an 8-bit unsigned integer, but
the discussion doesn't go away since increments larger than 1 are possible,
as you pointed out. You can have depth(B) = 4, depth(C) = 5, depth (N thru
B) = 6, with the same point.

In that case, you are saying why can't the node pick as its alternate the
set of neighbors that are all less deep than _itself_ .

In that example, node N could _forward_ to C but could not move to C without
co-ordinating everyone else behind it since that would increase its depth
(assuming that is so - if not, N could, if allowed by its optimization
function, switch to C as the preferred).

The idea I think is to construct a graph to allow each node to have a set of
parents that could offer the node a better depth than its "preferred"
because then it could switch to one of them without delay if needed without
affecting anything else. A particular neighbor may be preferred for other
reasons than depth depending on what is being optimized. All others may be
less preferred but a node can go to any of them without increasing its
depth. The parent set has also to do with the DAG structure and its
maintenance and not just the temporary forwarding - it would be the subset
of neighbors you could forward to that you can also move to.

Best regards,
Anand.

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Wed, 19 Aug 2009 18:01:51 +0200

Hi Dominique ad Anand:

>Given the advertised depth, the link costs and other characteristics, Node N determines through its objective
>function that its preferred parent is node B and that it should take 5.25 (= B's depth 3.75 + link cost 1.50)
>as its own depth.
>From the excerpts of the RPL draft quoted below, as well as from Pascal's email, I understand that C is not
>eligible to become an alternate parent to N.
>My question is: "Why?"

The text has been reshuffled and that might explain why the rationale is unclear. Placing a limit that the depth of the best parent is the worst depth for any acceptable parent is not for loop avoidance, you could pick any parent set and be deeper than the worst of them and that'd be cool. 

The reason is to "honestly" place an event horizon on what can make you move, in order to avoid the so called greedy behavior. In your example, the event horizon includes only A and B so whatever happens to C is ignored. This avoids a greedy behavior of leaving the tree to reattach behind C, which C could emulate later to attach behind self, and we're in a greedy loop.

>
>The only tentative explanation I've read so far is in the RPL draft, Section 3.4.1 "This mechanism serves to
>avoid loops in the case where an alternate parent is used- if no alternate parent is deeper than the preferred
>parent then loops are avoided." which I don't view as an explanation. If each node only forwards packet to
>nodes with lesser depth (barring forwarding to siblings for this discussion) then loops will be avoided even
>is C is included as an alternate parent of N.
>Am I mistaken somewhere?
>
>[Of course, if we enforce depth to be integers and node N's depth to be exactly its preferred parent's depth +
>1, then this whole discussion goes away. But it is my understanding that we are now dealing with increments

You're perfectly right. If we migrate to finer sub-increments, we can accept C as a parent as opposed to sibling. 
The rule should now say that we derive our own depth from the preferred parent + link cost, and then an acceptable parent is anyone that's inwards from us, in your case A, B and C.

Great point :)

Pascal
 
>
>Regards,
>Dominique
>
>Quotes :
>- 3.3.1.5 "It is recommended that a node maintain its DAG Parent set such that its most preferred parent from
>the OCP goals also has the greatest depth value in the DAG parent set."
>- 3.4.1 "For a node N, and its most preferred parent M, .... all parents in the DAG parent set must be of a
>depth less than or equal to DAGDepth(M)."
>- Pascal's email July 3rd 14:06 +0200 "The idea on the table would be to select a preferred parent (that might
>not be least depth because depth might not be the foremost argument in parent selection) and then constrain
>all other parents to be not_deeper." http://www.ietf.org/mail-archive/web/roll/current/msg01463.html
>The alternates will themselves be at equal or less depth compared to the preferred, but they may not offer the
>_node N_ a chance to become less deep because that depends also on the node's optimization metric w.r.t the
>alternates. If one of the candidate neighbors does offer this, by all means the node can make that candidate
>the preferred. This is the `moving inwards along the DAG' - section 3.3.1.6, 5th paragraph. Of course, the
>node N will then need to update its set of parents. So the preferred parent will be the "best" according to
>the node's optimization.
>
>The idea is to forward traffic or move inwards - less deep - in DAGDepth - then there will never be loops.
>Forwarding sideways - same DAGDepth - is also allowed but that has some chance of loops. Going deeper will
>create the chance of loops.
>
>BTW, in the draft "higher" in the DAG means closer to the root, inwards in the DAG. See for example, Section
>3.3.1.6, Section 5.3, point #6, Section 5.3.3.1 etc. I think you mean "lower" when you say " leads one to
>think that higher in the DAG is better".
>
>Regards,
>Anand.
>
>
>
>
>
>

---

From: "Roger K. Alexander" <[email-masked]>
Date: Wed, 19 Aug 2009 18:24:10 -0400

Hi Pascal, WG,

I am not clear on the example given in Section 3.4.2.1 and referenced to
some degree in your response below regarding greedy parent selection. The
cycle set up by nodes alternating with each other regarding who is the
parent should be avoided if nodes in a DAG are always clear about the OCP
metrics establishing the parent-child relationship. Two nodes exchanging
(receiving) routing information will determine their respective depths/ranks
relative to the root of the DAG. The node with a higher depth/rank (closer
to the root) should always be the parent. Even as links change, once
relative depth/rank determines the parent-child relationship, nodes can be
greedy in parent selection provided that between any two nodes the
parent-child relationship is understood (which follows directly from the
routing information and confirmed via subsequent Destination
Advertisements).

In the example in Figure 2 with the root at node A, until link costs change
the depth of nodes B or C relative to the node A, one or the other (B or C)
will be the parent node. Depth/rank relative to the root establishes which
node is the parent. A node cannot maintain another node in its parent set
where that node, through Destination Advertisements, confirms itself as a
child of the node.  This would be consistent with the statement in Section
3.3.1.5 "A general property of the depth value presented by the node is that
it should be greater than that 'presented' by any of its DAG parents." With
this explicit specification 'greed' would be permitted without leading to
the cycle described in Section 3.4.2.

That also gets to a second issue that I would like to raise regarding a node
re-joining a DAG at a depth/rank lower (further from the root) than a
current preferred parent. As stated at the end of section 3.4.1, "In the
case where a node looses connectivity to the DAG, it must first leave the
DAG before it may then rejoin at a deeper point." It should not always be
necessary for the node to leave the DAG and invoke the process of freezing
the sub-DAG, etc. when the parent set becomes depleted. If the node can
establish a parent at a lower depth and that parent candidate is not on its
sub-DAG, the node should be free to make that attachment when the parent set
is depleted. 

For loop avoidance the node re-joining at lower depth should be restricted
to parents that are NOT on the node's sub-DAG (as determined by exchanged
and maintained DAs). With such a specification, if the parent set becomes
deleted the node can immediately re-join the DAG through a parent candidate
that is at a lower depth outside its sub-DAG. While this leads to a
temporary period in which the connectivity of the sub-DAG is suboptimal
(relative to prior advertised node depth), because it allows connectivity to
be maintained it may still be potentially preferable to the overhead of
freezing the sub-DAG and the subsequently triggered re-associations. The
temporary sub-optimality will be incrementally removed through the
subsequent routing update exchanges without creating the additional network
overhead.

Thanks for your feedback.

Roger K Alexander 

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On Behalf Of
> Pascal Thubert (pthubert)
> Sent: Wednesday, August 19, 2009 12:02 PM
> To: [email-masked]; Tim Winter
> Cc: [email-masked]
> Subject: Re: [Roll] RPL preferred vs. alternate parents
> 
> Hi Dominique ad Anand:
> 
> >From the excerpts of the RPL draft quoted below, as well as from
> Pascal's email, I understand that C is not
> The text has been reshuffled and that might explain why the rationale
> is unclear. Placing a limit that the depth of the best parent is the
> worst depth for any acceptable parent is not for loop avoidance, you
> could pick any parent set and be deeper than the worst of them and
> that'd be cool.
> 
> The reason is to "honestly" place an event horizon on what can make you
> move, in order to avoid the so called greedy behavior. In your example,
> the event horizon includes only A and B so whatever happens to C is
> ignored. This avoids a greedy behavior of leaving the tree to reattach
> behind C, which C could emulate later to attach behind self, and we're
> in a greedy loop.
> 
> >
> Section 3.4.1 "This mechanism serves to
> >avoid loops in the case where an alternate parent is used- if no
> alternate parent is deeper than the preferred
> >nodes with lesser depth (barring forwarding to siblings for this
> discussion) then loops will be avoided even
> >[Of course, if we enforce depth to be integers and node N's depth to
> be exactly its preferred parent's depth +
> You're perfectly right. If we migrate to finer sub-increments, we can
> accept C as a parent as opposed to sibling.
> The rule should now say that we derive our own depth from the preferred
> parent + link cost, and then an acceptable parent is anyone that's
> inwards from us, in your case A, B and C.
> 
> Great point :)
> 
> Pascal
> 
> >
> >Regards,
> >Dominique
> >
> >Quotes :
> such that its most preferred parent from
> >- 3.4.1 "For a node N, and its most preferred parent M, .... all
> parents in the DAG parent set must be of a
> >- 5.2.1 "All nodes in the DAG Parent set should be of a depth less
> than or equal to the most preferred DAG
> >parent."
> >The alternates will themselves be at equal or less depth compared to
> the preferred, but they may not offer the
> >The idea is to forward traffic or move inwards - less deep - in
> DAGDepth - then there will never be loops.
> >BTW, in the draft "higher" in the DAG means closer to the root,
> inwards in the DAG. See for example, Section

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Wed, 26 Aug 2009 11:53:25 +0200

>routing information and confirmed via subsequent Destination

The insertion of a new router curves the routing space and new values of metrics get propagated. Other routers that are influenced by that change have to reposition themselves in that new context. Doing so, they also modify the curve of the routing space. If that curve can influence the first router then we can be in a feedback loop and count to infinity. 

An example of that is an OF that cares for bandwidth. 2 nodes A and B that belong to different subDAGs might wish to attach to one another to augment their available bandwidth by using the other one's DAG. Say A has a smaller rank than B. B can attach to A immediately. Say now that B wished (greedily) to use A. It could detach and reattach deeper than A. And the loop starts.

The easy way to break that loop is to create an event horizon, like routers look towards the sink and whatever has a causality behind their back, they do not see so there cannot be in a feedback loop. By ignoring RAs from deeper, we limit the risk of a feedback loop in the OF.

This is tricky, because if for instance traffic or bandwidth utilization was used as a metric for an Objective Function, then the routing is actually influenced by stuff happening behind the horizon, and we know since early Arpanet that this is a feedback loop that leads to instabilities.

So I think we are saying the same thing. You can attach the many parents as long as you respect some rules like parenting. 

What I called greedy is not trying to have many parents, but being unfair or dishonest about it. Same rank routing (sibling) aims at fairness. It is expected that an OF honestly selects the parent that provides the best attachment for its objective and does not attach deeper than that in order to greedily get more while depriving the rest.

>the cycle described in Section 3.4.2.

The event horizon rule could be finer grained like ignore anything from one's subDAG as opposed to deeper in rank. 
It's just harder to figure out. Obviously, if all routers in the subDAG sent DAO and we had info in there to correlate with the RA-DIOs they also send, then we could ignore selectively those RA_DIOs. But we do not necessarily have NA_DAOs for all and space for states.

>sub-DAG, the node should be free to make that attachment when the parent set

Sure. But how do you know that. The whole process of detaching is about marking those nodes that we cannot attach back to. As you say, they are all in the subDAG, yet it's not the whole subDAG.

>and maintained DAs). With such a specification, if the parent set becomes

Sadly that's not always there not always complete nor in sync. I'm not sure that the group is ready to enforce DAOs at all times for that sole purpose.

>temporary period in which the connectivity of the sub-DAG is suboptimal

Note that on top, the draft says to detach from a parent that is going down to avoid count to infinity if the parent of there was wrong and the attachment router was in fact in its subDAG.

>subsequent routing update exchanges without creating the additional network

Well, the idea is on the table. 
Like I said, I do not think we force all the nodes to keep states for all nodes in their subDAGs.

>Thanks for your feedback.

Pleasure;

Pascal