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

Xavier Vilajosana Guillen <xvilajosana@eecs.berkeley.edu> Thu, 12 September 2013 13:34 UTC

Return-Path: <xvilajosana@berkeley.edu>
X-Original-To: 6tsch@ietfa.amsl.com
Delivered-To: 6tsch@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id AF7AF11E80EA for <6tsch@ietfa.amsl.com>; Thu, 12 Sep 2013 06:34:17 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.576
X-Spam-Level:
X-Spam-Status: No, score=-1.576 tagged_above=-999 required=5 tests=[AWL=0.400, BAYES_00=-2.599, FM_FORGED_GMAIL=0.622, HTML_MESSAGE=0.001]
Received: from mail.ietf.org ([12.22.58.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id J4T9EXTvhV9r for <6tsch@ietfa.amsl.com>; Thu, 12 Sep 2013 06:34:13 -0700 (PDT)
Received: from mail-pd0-f174.google.com (mail-pd0-f174.google.com [209.85.192.174]) by ietfa.amsl.com (Postfix) with ESMTP id 118A011E8166 for <6tsch@ietf.org>; Thu, 12 Sep 2013 06:34:10 -0700 (PDT)
Received: by mail-pd0-f174.google.com with SMTP id y13so10661404pdi.5 for <6tsch@ietf.org>; Thu, 12 Sep 2013 06:34:09 -0700 (PDT)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:reply-to:in-reply-to:references :date:message-id:subject:from:to:cc:content-type; bh=OrLyN/VMApEAYeA41A/chQ4lV4gLe6RH6bXD7EZjCig=; b=g/qhT++WaXPAhqHnKFL7w8q2IF/TqMWAnJ1R0ATenGa7FBz+NuVuFyNxgY5TF1ffc1 xldj//hJsRA1wuhP0VfOAAV896/Llaj1RKMIHn+8l9itt1Tb9LavCUvWMT/D0l9BOYv7 p1mjKt3uQkIHgY0FpuC3mD5EFK+0PnIjt3dXSoi54nrZXEmGzKP+hDtVhtWsU369JOaW KhNrFfp7k67Ks6KSA8T9QBS6eJHXiod64uy4v9WgD7M0/JV9fy6Rbvkm6WE85tJOc6Xt 3ifpz3+Cd7DLMVg656c1my5B+xD60DNOu/zjbv9t7PN2WU6er7Bvi9huKeCNeRPSJ2XO qQcg==
X-Gm-Message-State: ALoCoQkPxhZP6GkFzwR2Ymfaloz1jFoTdc5E++eEXmoTsQfhB+3ez2DYbEBgNvBEn1hXi52dlslU
MIME-Version: 1.0
X-Received: by 10.66.162.136 with SMTP id ya8mr9477313pab.110.1378992849681; Thu, 12 Sep 2013 06:34:09 -0700 (PDT)
Received: by 10.70.34.44 with HTTP; Thu, 12 Sep 2013 06:34:09 -0700 (PDT)
In-Reply-To: <E045AECD98228444A58C61C200AE1BD84147249C@xmb-rcd-x01.cisco.com>
References: <E045AECD98228444A58C61C200AE1BD84147249C@xmb-rcd-x01.cisco.com>
Date: Thu, 12 Sep 2013 06:34:09 -0700
Message-ID: <CALEMV4ZM8287mXedxmECeOXTCFVv1d6gjihR3cB1CF4R37X39Q@mail.gmail.com>
From: Xavier Vilajosana Guillen <xvilajosana@eecs.berkeley.edu>
To: "Pascal Thubert (pthubert)" <pthubert@cisco.com>
Content-Type: multipart/alternative; boundary=047d7b86e424f4133104e62fcadd
Cc: Thomas Watteyne <watteyne@eecs.berkeley.edu>, 6TSCH <6tsch@ietf.org>, Qin Wang <qinwang@berkeley.edu>
Subject: Re: [6tsch] Rank rounding error, churn and hysteresis [was Zero Objective Function discussion]
X-BeenThere: 6tsch@ietf.org
X-Mailman-Version: 2.1.12
Precedence: list
Reply-To: xvilajosana@eecs.berkeley.edu
List-Id: "Discuss link layer model for Deterministic IPv6 over the TSCH mode of IEEE 802.15.4e, and impacts on RPL and 6LoWPAN such as resource allocation" <6tsch.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/6tsch>, <mailto:6tsch-request@ietf.org?subject=unsubscribe>
List-Archive: <http://www.ietf.org/mail-archive/web/6tsch>
List-Post: <mailto:6tsch@ietf.org>
List-Help: <mailto:6tsch-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/6tsch>, <mailto:6tsch-request@ietf.org?subject=subscribe>
X-List-Received-Date: Thu, 12 Sep 2013 13:34:17 -0000

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) <
pthubert@cisco.com> 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:qinwang@berkeley.edu]
> *Sent:* mercredi 11 septembre 2013 23:58
> *To:* Pascal Thubert (pthubert)
> *Cc:* xvilajosana@eecs.berkeley.edu; 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) <
> pthubert@cisco.com> 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:xvilajosana@eecs.berkeley.edu]
> *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
> 6tsch@ietf.org
> https://www.ietf.org/mailman/listinfo/6tsch****
>
> ** **
>