Subject: Re: [Roll] RPL preferred vs. alternate parents

From: "Roger K. Alexander" <[email-masked]>
Date: Thu, 27 Aug 2009 18:27:06 -0400

Hi Pascal,

Thanks again for the feedback. 

Roger
> -----Original Message-----
> From: Pascal Thubert (pthubert) [mailto:[email-masked]]
> Sent: Wednesday, August 26, 2009 5:53 AM
> To: Roger K. Alexander
> Cc: [email-masked]; [email-masked]; Tim Winter
> Subject: RE: [Roll] RPL preferred vs. alternate parents
> 
> >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).
> 
> 
> 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.
> 

If nodes are 'greedy' but observe rank in their associations then greed, in
terms of permitting multiple alternatives, is not a bad thing.

> 
> >
> >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.
> 
> 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.
> 

The establishment of routing state outward along the DAG is the basis on
which nodes discover/maintain the routing members of its sub-DAG.

> 
> >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.
> 
> 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.
> 
> 

I may not have been very clear. My references to a node's sub-DAG  is to the
set of nodes of lower rank that have a path to the DAG root through the
given node. Nodes that maintain state have as part of their routing table
(for outward routes) all nodes that are in their sub-DAG. Together with
parents (that provide the default routes towards the DAG root), these are
the only route entries required to be maintained by a node for the
particular DAG. Therefore for re-attaching to DAG these nodes should be part
of the restricted set.

> >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
> 
> 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.
> 
> >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
> 
> 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.
> 
> >(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.
> 
> 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.

For nodes that keep state it will be necessary that sub-DAG information be
maintained for outward routing. Some further discussion may be in order.

> 
> >Thanks for your feedback.
> 
> Pleasure;
> 
> Pascal
> 
> >
> >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:
> >>
> >> >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 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
> >> >that are not exactly 1, and/or fractional depths, aren't we?]
> >>
> >> 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)."
> >> >- 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,
> >> >
> >> >
> >> >
> >> >
> >> >
> >> >	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.
> >> >
> >> >
> >> >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.
> >> >
> >> >
> >> >
> >> >
> >> >
> >> >
> >> >	Can anybody offer a substantiated explanation?
> >> >	Thanks
> >> >
> >> >	Dominique
> >> >	_______________________________________________
> >> >	Roll mailing list
> >> >	[email-masked]
> >> >	https://www.ietf.org/mailman/listinfo/roll
> >> >
> >> >
> >> >
> >> >_______________________________________________
> >> >Roll mailing list
> >> >[email-masked]
> >> >https://www.ietf.org/mailman/listinfo/roll
> >> _______________________________________________
> >> Roll mailing list
> >> [email-masked]
> >> https://www.ietf.org/mailman/listinfo/roll