Re: [6tsch] Rank rounding error, churn and hysteresis [was Zero Objective Function discussion]

[Xavier Vilajosana Guillen <[e-mail]>]

Hi Pascal,

I agree with you. In OpenWSN we have a stability counter that prevents
changing the parent in case of little sudden variations, (avoiding
hysteresis) and a mechanism to smooth rank increases, in case a node
receives suddenly a very big rank from its parent.

I also agree that little variations won't have an important effect. If you
see here a problem we can try to simulate some scenarios and see what
happens.

cheers!
Xavi




On Thu, Sep 12, 2013 at 2:37 AM, Pascal Thubert (pthubert) <
[e-mail]> wrote:

>  Hello Qin:****
>
> ** **
>
> In this particular case, a computation of DAGRank(rank) of 7 will prevent
> this node from attaching to other nodes that are also at 7, and will
> encourage more other nodes to attach to this. The end to end Rank
> calculation for children is only slightly affected since the 2 byte rank is
> used for the total rank computation.****
>
> ** **
>
> I think that the rounding errors are part of the errors, just like the
> stats of transmissions may vary.****
>
> Depending on the representation of ETX in memory, you might also have
> system that round to 1 decimal and others to 2 decimals and the same
> calculation may still create a similar effect.****
>
> ** **
>
> Is that a big deal? Well, Considering the variations on the ETX
> computation I do not think that this makes a lot of difference in the run
> time.****
>
> ** **
>
> What is more critical is to use a good hysteresis so as to avoid jumping
> over the integral boundary of DAGRank(rank) all the time.****
>
> ** **
>
> Both RFC 6552 and 6719 recommend you to do that, with RFC 6552
> dereferencing RFC 6719 that recommends to use a value boundary on Rank
> before reparenting.****
>
> http://tools.ietf.org/html/rfc6719#section-3.2.2 :****
>
> ** **
>
>    3.  If the smallest path cost for paths through the candidate****
>
>        neighbors is smaller than cur_min_path_cost by less than****
>
>        PARENT_SWITCH_THRESHOLD, the node MAY continue to use the current**
> **
>
>        preferred parent.  This is the hysteresis component of MRHOF.****
>
> ** **
>
> RFC 6552 recommends by default to follow that guidance in
> http://tools.ietf.org/html/rfc6552#section-4.1 ****
>
> ** **
>
>                                                            it is thus****
>
>    RECOMMENDED to base the computation of the step_of_rank on dynamic****
>
>    link properties such as the expected transmission count (ETX) metric***
> *
>
>    as introduced in [DeCouto03<http://tools.ietf.org/html/rfc6552#ref-DeCouto03>]
> and discussed in [RFC6551 <http://tools.ietf.org/html/rfc6551>].  "Minimum
> ****
>
>    Rank Objective Function with Hysteresis" [HYSTERESIS<http://tools.ietf.org/html/rfc6552#ref-HYSTERESIS>]
> provides****
>
>    guidance on how link cost can be computed and on how hysteresis can****
>
>    improve Rank stability.****
>
> ** **
>
> Additional tuning or methods exist to increase stability. We can start
> some work on that if we find that MRHOF’s method is not sufficient in our
> case.****
>
> ** **
>
> One method (Cisco IPR there) consists in hiding limited variations of the
> Rank to the children (around the last advertised 2 bytes value) until: ***
> *
>
> 1) a delta threshold is reached in the step of rank with parent (one-hop
> hysteresis)****
>
> or ****
>
> 2) Rank has to be recomputed because of the parent (the parent changes or
> the Rank of the parent changes)****
>
> ** **
>
> This method creates a laser effect by which a number of new values of Rank
> a recomputed and advertised as a single wave, whereby every node affected
> by the change re-centers its rank value to its current moving average,
> reducing the chances to hit condition 2) in the near future.****
>
> ** **
>
> What do you think?****
>
> ** **
>
> Pascal****
>
> ** **
>
> *From:* Qin Wang [mailto:[e-mail]]
> *Sent:* mercredi 11 septembre 2013 23:58
> *To:* Pascal Thubert (pthubert)
> *Cc:* [e-mail]; Thomas Watteyne; 6TSCH
> *Subject:* Re: [6tsch] Zero Objective Function discussion****
>
> ** **
>
> Hi Pascal,****
>
> ** **
>
> I agree with your calculation. But, I have a small question.****
>
> ** **
>
> If you calculate with rank_increase=(2*xmit/ack)*256, instead
> of rank_increase=(512*xmit/ack), then, you will get the result as follows.
> ****
>
> ** **
>
> r(1)=r(0)+2.66*256 = 2.66*256               => DAGRank(rank) = 2****
>
> r(2)=r(1)+2.66*256= 5.32*256                 => DAGRank(rank) = 5****
>
> r(3)=r(2)+2.66*256=7.98*256                  => DAGRank(rank) = 7****
>
> r(4)=r(3)+2.66*256=10.64*256                => DAGRank(rank) = 10****
>
> r(5)=r(4)+2.66*256=13.30*256                 => DAGRank(rank) = 13****
>
> You can see r(3) is different from that in your calculation. Obviously,
> the difference comes from different implementation. In another word,
> following same OF, different implementation may lead to different Rank
> value. Then, my question is if it is Ok while the motes from different
> vendors work together in a DAG.****
>
> Please point out if I'm wrong.****
>
> Thanks****
>
> Qin****
>
> ** **
>
> ** **
>
> ** **
>
> ** **
>
>  ****
>
> ** **
>
> On Wed, Sep 11, 2013 at 3:08 AM, Pascal Thubert (pthubert) <
> [e-mail]> wrote:****
>
> Hello Xavi:****
>
>  ****
>
> Great!****
>
>  ****
>
> I’d add the following:****
>
>  ****
>
> RFC 6550    3.5.1 <http://tools.ietf.org/html/rfc6550#section-3.5.1>. Rank Comparison (DAGRank())has:****
>
> “****
>
> When an Objective Function computes Rank, the Objective Function****
>
>    operates on the entire (i.e., 16-bit) Rank quantity.  When Rank is****
>
>    compared, e.g., for determination of parent relationships or loop****
>
>    detection, the integer portion of the Rank is to be used.  The****
>
>    integer portion of the Rank is computed by the DAGRank() macro as****
>
>    follows, where floor(x) is the function that evaluates to the****
>
>    greatest integer less than or equal to x:****
>
>  ****
>
>               DAGRank(rank) = floor(rank/MinHopRankIncrease)****
>
>  ****
>
>    For example, if a 16-bit Rank quantity is decimal 27, and the****
>
>    MinHopRankIncrease is decimal 16, then DAGRank(27) = floor(1.6875) =****
>
>    1.  The integer part of the Rank is 1 and the fractional part is****
>
>    11/16.****
>
>  ****
>
> “****
>
> DAGRank(rank) is what we expect to place in the Flow label and the join
> priority.****
>
> In our case:****
>
>  ****
>
> r(1)=r(0)+rank_increase = 0+683               => DAGRank(rank) = 2****
>
> r(2)=r(1)+683=1366                                         =>
> DAGRank(rank) = 5****
>
> r(3)=r(2)+683=2049                                         =>
> DAGRank(rank) = 8****
>
> r(4)=r(3)+683=2732                                         =>
> DAGRank(rank) = 10****
>
> r(5)=r(4)+683=3415                                         =>
> DAGRank(rank) = 13****
>
>  ****
>
> We see that the DAGRank() always increases at least by one. This is the
> desired property so as to ensure that we can detect loop with just one
> octet in the flow label.****
>
> Note that the real 2 octets Rank does not lose the rounding info since the
> DIP always passes 2 octets.****
>
>  ****
>
> Cheers,****
>
>  ****
>
> Pascal****
>
>  ****
>
> *From:* Xavier Vilajosana Guillen [mailto:[e-mail]]
> *Sent:* mardi 10 septembre 2013 19:53
> *To:* Pascal Thubert (pthubert)
> *Cc:* Thomas Watteyne; 6TSCH
> *Subject:* Re: [6tsch] Zero Objective Function discussion****
>
>  ****
>
> Hi all,
>
> after some study I agree that we can use the RFC6552 in the minimal 6TiSCH
> configuration. I would like to call for approval or more input from others
> before I consolidate the text in the draft.
>
> I put here an example following Pascal suggestion:
>
> Given
>
> Rf = 1
> Sp = 2* ETX
> Sr = 0
> minHopRankIncrease = 256 (default in RPL)****
>
> ETX=(xmit/ack)****
>
>  ****
>
> r(n) = r(p) + rank_increase
> rank_increase= (Rf*Sp + Sr) * minHopRankIncrease ****
>
> rank_increase=(512*xmit/ack)
>
>
> if we take 5 hops (95 are supported) network and r(0)=0 and xmit=100 and
> ack=75 for all nodes
>
> r(1)=r(0)+rank_increase = 0+683 with f=0
> r(2)=r(1)+683=1366 with f=1
> r(3)=r(2)+683=2049 with f=2
> r(4)=r(3)+683=2732 with f=2
> r(5)=r(4)+683=3415 with f=3
> ...
> etc...
>
> so f is monotonically increasing and the rank function enables more than
> enough hops.****
>
> Please provide feedback.****
>
> cheers!
> Xavi****
>
>  ****
>
>
> _______________________________________________
> 6tsch mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/6tsch****
>
> ** **
>