Subject: [6tisch] 6TiSCH Minimal: step_of_rank

From: Simon Duquennoy <[email-masked]>
Date: Tue, 23 Jun 2015 12:54:07 +0200

Hi all,

I was wondering why the 6TiSCH minimal draft sets step_of_rank to 2*ETX
rather than ETX. Given we have a stretch of 0 and a factor of 1, this
should result in the same topology as simply using ETX (only with all ranks
-- minus to root rank -- doubled).

Section (minimal) 9.1.1 states this is in order to prefer shorter routes.
(1) I don't think it does that as there doesn't seem to be any effect on
the topology. (2) I would argue shorter routes are not desirable anyway:
when aiming for reliability, one usually prefers longer routes with stabler
links.

Thoughts are very welcome :)
Simon

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Thu, 25 Jun 2015 15:28:34 +0000

Hello Simon:

To your question about why 2*ETX in minimal. This was a long time ago! Below is the discussion that lead there.
Basically that comes from the OF0 normalization process that allows to compare and merge 2 meshes that do not compute the rank the same way.
OF0 says that 1 is abfab and 9 is baaad. 2*ETX seemed a good value in between.
I also added further discussion on the subject in attachment

Thanks for your fantastic help on closing the minimal annexes, this is really appreciated!

Pascal

From: Pascal Thubert (pthubert)
Sent: vendredi 6 septembre 2013 19:13
To: 'Thomas Watteyne'; 6TSCH
Subject: RE: [6tsch] Zero Objective Function discussion

Hello Thomas:

The idea behind RFC 6552 is that we can say nothing if we do not want to specify anything. Node will interoperate and a rather correct network will form as long as devices use a normalized value for Sp(best = 1, good = 3, worst = 9)

We can make the life simpler for implementers by defining that we use ETX and that the normalization process is, say, 2*ETX as in my example; by RFC 6552 standards would mean that good link is ETX = 1.5 and ETX is acceptable up to 4.5

RFC 6719 provides another OF that can be used without a metric container, see section 3.5. In that case, ETX /2 is used. This gives a larger span to the network but means trouble to map in a join priority or a flow label.

I proposed a general formula Sp = a*ETX + b where a is between 1 and 3 and b is between 0 and 2 or 3. If b is not null, the Rank grows faster with the number of hops so deeper networks are not favored. To be honest I'm not convinced that it is a great idea for data instances or to encourage duocast it could be good.

An example of that would be a=1, b=2, which means that each hop incurs an additional penalty equivalent to an ETX of 2. This would mean that ETX is acceptable up to 7.

Probably specififying that we use OF0 with
Rf = 1
Sp = 2* ETX
Sr = 0

Is not a lot of work is it?

Pascal

From: [email-masked]<mailto:[email-masked]> [mailto:[email-masked]] On Behalf Of Thomas Watteyne
Sent: vendredi 6 septembre 2013 18:18
To: 6TSCH
Subject: [6tsch] Zero Objective Function discussion

Pascal,

Thank you for presenting the OF0 discussion on the call today. I have a quick question about the depth penalty. In your example on the call, you used b=0. Could you detail a case where using a value of b different than 0 is applicable?

Also, do you think there is an alternative to defining our own computation of Sp? Certainly in the minimal draft, it would be good if we could use a OF as-is, without introducing anything new.

Thomas

Subject: Rank rounding error, churn and hysteresis [was Zero Objective Function discussion]
From: "Pascal Thubert (pthubert)" <[email-masked]>
To: Qin Wang <[email-masked]>
Cc: "[email-masked]" <[email-masked]>, "Thomas Watteyne" <[email-masked]>, 6TSCH <[email-masked]>
Date: Thu, 12 Sep 2013 09:36:57 +0000

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:[email-masked]]
Sent: mercredi 11 septembre 2013 23:58
To: Pascal Thubert (pthubert)
Cc: [email-masked]; 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) <[email-masked]<mailto:[email-masked]>> 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:[email-masked]<mailto:[email-masked]>]
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
[email-masked]<mailto:[email-masked]>
https://www.ietf.org/mailman/listinfo/6tsch