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

Qin Wang <qinwang@berkeley.edu> Fri, 13 September 2013 02:18 UTC

Return-Path: <qinwang@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 98F0721F9D12 for <6tsch@ietfa.amsl.com>; Thu, 12 Sep 2013 19:18:18 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.555
X-Spam-Level:
X-Spam-Status: No, score=-2.555 tagged_above=-999 required=5 tests=[AWL=0.421, BAYES_00=-2.599, FM_FORGED_GMAIL=0.622, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_LOW=-1]
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 G82r9IM8q9Lj for <6tsch@ietfa.amsl.com>; Thu, 12 Sep 2013 19:18:14 -0700 (PDT)
Received: from mail-ie0-f182.google.com (mail-ie0-f182.google.com [209.85.223.182]) by ietfa.amsl.com (Postfix) with ESMTP id B4FE211E8163 for <6tsch@ietf.org>; Thu, 12 Sep 2013 19:18:13 -0700 (PDT)
Received: by mail-ie0-f182.google.com with SMTP id aq17so1355430iec.27 for <6tsch@ietf.org>; Thu, 12 Sep 2013 19:18:13 -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:in-reply-to:references:date :message-id:subject:from:to:cc:content-type; bh=Y7uGid4aTKki/WO31SPgqxwt1MQEUlGGHvZdjW9e27g=; b=NuURIK9b+FRqMYLdTZkI8Tfx36nTiFL+U3MWfgJruspokcAzA4+FZ91NoecDFCA2Xt fOoSND+PI2Uf59QVQGyX+4joBy2sNlC8LPfFD2JMCj8Iw4c5raYfpoeVNFsJmACJCJke /ljXBT5d3CBsLWB0o9Osvk2HHPAZ9F2BuZMB6TZZjo10sSYo8tV1kpAg1Ih20PeuUrUK +HhhXqWAZpcI9Raf97XMiHIT8GYS/mlqDX35umbhMBJyZhLJ9W7UWFiPsBzw8NjNyqiV hVaO1OiOc1uYys/1RBQ1McUcy14axsdji5z6+4VD712QYD1pODb8Jsn0/wCyTSdjbLQv GszQ==
X-Gm-Message-State: ALoCoQmkjAHbU4NqDeQ41vY30yhj4Mn2lbny3zv0PhMfdoxysnvUGNondfzhlGauwkjFcldT1NRt
MIME-Version: 1.0
X-Received: by 10.50.13.104 with SMTP id g8mr307831igc.30.1379038693088; Thu, 12 Sep 2013 19:18:13 -0700 (PDT)
Received: by 10.64.139.234 with HTTP; Thu, 12 Sep 2013 19:18:13 -0700 (PDT)
In-Reply-To: <CALEMV4ZM8287mXedxmECeOXTCFVv1d6gjihR3cB1CF4R37X39Q@mail.gmail.com>
References: <E045AECD98228444A58C61C200AE1BD84147249C@xmb-rcd-x01.cisco.com> <CALEMV4ZM8287mXedxmECeOXTCFVv1d6gjihR3cB1CF4R37X39Q@mail.gmail.com>
Date: Fri, 13 Sep 2013 10:18:13 +0800
Message-ID: <CAAzoce48_xieiYR0FhmB96L-Z9pu9pt3=jTbP32ovTqWjn1TMQ@mail.gmail.com>
From: Qin Wang <qinwang@berkeley.edu>
To: Xavier Vilajosana Guillen <xvilajosana@eecs.berkeley.edu>
Content-Type: multipart/alternative; boundary=089e013c69c66f005004e63a77ae
Cc: Thomas Watteyne <watteyne@eecs.berkeley.edu>, "Pascal Thubert \(pthubert\)" <pthubert@cisco.com>, 6TSCH <6tsch@ietf.org>
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
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: Fri, 13 Sep 2013 02:18:18 -0000

Hi Pascal and Xavi,

I agree with you that comparing the variation in ETX, rounding error can be
ignored.

Regarding to ETX, is there some guideline for determining the length of
window to calculate ETX, especially when the duty cycle is very low?

Thanks
Qin




On Thu, Sep 12, 2013 at 9:34 PM, Xavier Vilajosana Guillen <
xvilajosana@eecs.berkeley.edu> wrote:

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