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