rpl: Sort list of parents by bergzand · Pull Request #7468 · RIOT-OS/RIOT

bergzand · 2017-08-10T14:17:10Z

This PR enhances the RPL code to sort the list of parents instead of only comparing whether a parent is better than the current preferred parent.

The aim of this PR is to make it easier for objective functions to determine the parent set.
If the objective function defines the which_parent function such that the list is sorted based on how good (best rank or whatever the OF defines) the parent list should start automatically with the preferred parent, folowed by the rest of the parent set.

Since the parent set is needed for rank calculation, the calc_rank function can then iterate over the parent set, and assume that the first N parents from the parent list is his parent set, where N is the parent set. If it encounters an unacceptable parent within the first N parent, it can assume that the following parents are also unacceptable.

The advantage is that the calc_rank function only has to iterate over the parent list and not have to determine which parents are in the parent set.

This requires a small API change in the RPL objective function. The which_parent function needs to return an integer in the same way as the strcmp function [-1, 0, 1], based on which parent is better.

smlng · 2017-08-16T13:00:10Z

sys/net/gnrc/routing/rpl/gnrc_rpl_dodag.c

-    LL_FOREACH(dodag->parents, elt) {
-        new_best = dodag->instance->of->which_parent(new_best, elt);
-    }
+    LL_SORT(dodag->parents, dodag->instance->of->which_parent);


this does not update new_best anymore, I would guess that also changes the behaviour of this function, or not?

Ah, you're right there, that wasn't supposed to happen. An new_best = dodag->parents after the LL_SORT should be sufficient to restore the old behaviour

yes, I think that should do

however, I generally like your suggestion/idea of having the parent list sorted right away. But then this should be done on add/del of a parent so there would be no need to this here.

Yes, but for example with MRHOF as an objective function, the sorting of the parents can vary over time because it depends not only on the advertised rank of a parent, but also on the link quality to the parent.

So sorting the parents on add/del works if the parents have a fixed order, but I don't think it works when the relative sorting of the parents change over time.

good point, then it should be done when ever the rank of a parent changes - what could be quite often and would introduce lots of overhead, which we don't want on an embedded node.

OK, I see this is not as easy as I first thought 😉

I would not advise to update this every time the path cost of a parent updates, that could be with every transmitted packet (or other event on which the path cost depends).

Recalculating this based on a timer or an event with some build in hysterisis (only update when the path cost changed by some amount) might be enough to lessen the burden of this.

yes, or only when required, like in this function.

smlng · 2017-08-16T13:16:17Z

sys/include/net/gnrc/rpl/structs.h

    uint16_t ocp;   /**< objective code point */
    uint16_t (*calc_rank)(gnrc_rpl_parent_t *parent, uint16_t base_rank); /**< calculate the rank */
-    gnrc_rpl_parent_t *(*which_parent)(gnrc_rpl_parent_t *, gnrc_rpl_parent_t *); /**< compare for parents */
+    int (*which_parent)(gnrc_rpl_parent_t *, gnrc_rpl_parent_t *); /**< compare for parents */


instead of changing an existing functions (hence the API) wouldn't suffice to add a separate (helper) function, i.e. int parent_cmp(a, b) - which then could also be used by which_parent btw.

yes, will change.

bergzand · 2017-08-17T13:48:54Z

@smlng I've fixed your comments. I still want to run some additional tests to check if it behaves as intended. Is the API change/addition this way as you requested?

smlng · 2017-08-17T13:58:35Z

sys/net/gnrc/routing/rpl/gnrc_rpl_dodag.c

-    LL_FOREACH(dodag->parents, elt) {
-        new_best = dodag->instance->of->which_parent(new_best, elt);
-    }
+    LL_SORT(dodag->parents, dodag->instance->of->parent_cmp);


due to this sort the following is obsolete:

LL_DELETE(dodag->parents, new_best); LL_PREPEND(dodag->parents, new_best);

below lines 320, 321

Ah, should have noticed that, will remove.

smlng · 2017-08-17T14:11:50Z

though it seems like which_parent is obsolete now, I would leave it as is for now. IMHO the new name parent_cmp is more appropriate anyway.

bergzand · 2017-08-17T14:14:36Z

Yes, I noticed earlier that not all functions in that struct are (still) in use. The parent_state_callback also seems obsolete.

smlng · 2017-08-17T14:14:39Z

looks good, please squash

@cgundogan can you have a quick look at this, too?

smlng · 2017-08-17T14:15:55Z

not all functions in that struct are (still) in use

yeah, I think the RPL code needs some general cleanup - let's do this all at once later on in a separate PR.

bergzand · 2017-08-17T14:17:12Z

squashed

smlng · 2017-08-18T07:11:12Z

sys/net/gnrc/routing/rpl/of0.c

 {
-    if (p1->rank <= p2->rank) {
-        return p1;
+    if(parent_cmp(p1, p2) == 1) {


I would recommend to use if(parent_cmp(p1, p2) > 1) instead of strict equality here, this leaves more freedom on the implementation of parent_cmp. For instance, it might be that parent_cmp returns the actual rank difference. Quoting from the man memcmp:

The memcmp() function returns zero if the two strings are identical, otherwise returns the difference between the first two differing bytes (treated as unsigned char values, so that \200' is greater than \0', for example). Zero-length strings are always identical. This behavior is not required by C and portable code
should only depend on the sign of the returned value.

the last part is what I'm referring to.

Can't argue against that :)

oops > 1 should be > 0, my bad

bergzand · 2017-08-18T08:53:05Z

Remark is fixed. Do you want it squashed again, assuming no further remarks?

smlng · 2017-08-18T08:56:12Z

sys/net/gnrc/routing/rpl/of0.c

 {
-    if (p1->rank <= p2->rank) {
-        return p1;
+    if (parent_cmp(p1, p2)) {


I need to insist on if (parent_cmp(p1, p2) > 0) { because -1 will also eval as true, only 0 is false

Yes, my bad.

smlng · 2017-08-18T08:57:42Z

please squash directly

bergzand · 2017-08-18T09:05:34Z

With this comparison fixed, I can reduce the parent_cmp() of of0.c to:
return p2->rank - p1->rank;
(right?)

smlng · 2017-08-18T09:12:51Z

return p2->rank - p1->rank;

I would be careful with that, because rank is of type uint16_t and parent_cmpreturns int, for which the size depends on the platform used, i.e. the result might not fit. I think its safer to use '-1', '0' and '1' for now. But also make no assumption on that when using parent_cmp in which_parent.

bergzand · 2017-08-18T09:16:17Z

Okay, that makes sense. Thanks for the comments so far.

smlng · 2017-08-18T10:16:25Z

I'd like to get an opinion on this by @cgundogan or @BytesGalore before merge, they the RPL gurus of RIOT 🤓

cgundogan · 2017-08-21T08:19:07Z

sys/include/net/gnrc/rpl/structs.h

    uint16_t (*calc_rank)(gnrc_rpl_parent_t *parent, uint16_t base_rank); /**< calculate the rank */
-    gnrc_rpl_parent_t *(*which_parent)(gnrc_rpl_parent_t *, gnrc_rpl_parent_t *); /**< compare for parents */
+    gnrc_rpl_parent_t *(*which_parent)(gnrc_rpl_parent_t *, gnrc_rpl_parent_t *); /**< retrieve the better parent */
+    int (*parent_cmp)(gnrc_rpl_parent_t *, gnrc_rpl_parent_t *); /**< compare for parents */


I know it hasn't been done before for the other function pointers in this file, but can you add – somehow – a documentation on how to interpret the return value of this function pointer? Is it possible to document function pointers in structs as if they were normal functinos with @param, @return etc.? Would be awesome.

smlng · 2017-08-21T08:32:38Z

Is it possible to document function pointers in structs as if they were normal functinos with @param, @return etc.? Would be awesome.

yes thats possible, and done in other places already, e.g. #7370 here. But I also think, enhancing the documentation is a separate PR.

cgundogan · 2017-08-21T08:42:54Z

IMO the documentation for this function is as important as the function itself, at least. Separating them is a bit too liberal-minded for me (:

smlng · 2017-08-21T08:52:37Z

my point was not against documentation, but rather that documenting just the new function will look strange too, while documenting all functions (even the unrelated once) would bloat this PR.

cgundogan · 2017-08-21T09:13:37Z

but rather that documenting just the new function will look strange to

To the contrary, IMO providing a documentation just for this new function makes the commit diff more consistent on its own. The documentation for other functions can still be applied by a separate commit or PR. Although, I would not object if they also happen to be in this PR (:

smlng · 2017-08-21T09:17:40Z

okay then @bergzand please add proper doc for parent_cmp as requested/suggested by @cgundogan. Regarding the other functions: some of them are unused (which_dodag) or obsolete (which_parent) anyway, so as already said: there is room for cleanup RPL, too.

bergzand · 2017-08-21T17:57:52Z

That's fine with me, I should have time tomorrow to do the documentation and maybe even some cleanup.

bergzand · 2017-08-22T08:41:56Z

Documentation added. I couldn't get doxygen to understand unnamed function parameters, so they now have names.

smlng · 2017-08-22T09:12:42Z

sys/include/net/gnrc/rpl/structs.h

+     * @param[in] parent1 First parent to compare.
+     * @param[in] parent2 Second parent to compare.
+     *
+     * @return      Zero if the parents are of equal preference,


please make each case a separate @return, i.e., for <0, 0, and >0.

smlng · 2017-08-22T09:18:58Z

sys/include/net/gnrc/rpl/structs.h

+     *
+     * This function is used to determine the parent list order. The parents
+     * are ordered from the preferred parent to the least preferred parent.
+     * This function should compare two parents based on the criteria of the


the last sentence is rather vague (should?), be explicit: Compares two parents based on the rank calculated by the objective function. Btw. this sentence should be the first, followed by the other explaining the (possible) usage.

smlng · 2017-08-22T09:20:37Z

sys/include/net/gnrc/rpl/structs.h

+     *              positive result if the second parent is prefered,
+     *              negative result if the first parent is prefered.
+     */
+    int (*parent_cmp)(gnrc_rpl_parent_t *parent1, gnrc_rpl_parent_t *parent2);


IMHO parameter names p1 and p2 were fine, too - and match with actual implementation in of0.c below.

I don't mind changing it back to p1, p2. In my opinion this is a bit more clear and I rather change the implementation in of0 to match this

bergzand · 2017-08-22T10:31:04Z

@smlng I've resolved most of your comments. I'd rather have the first sentence of the explanation without mentioning rank because an objective function can have different criteria than rank comparison (metric containers).

Do you have any preference for parent# vs p# for the parent_cmp? I can change either the declaration or the implementation to match the other.

smlng · 2017-08-22T13:27:05Z

without mentioning rank because an objective function can have different criteria than rank comparison (metric containers).

I don't understand, IIRC RPL uses rank only to choose its parent, hence we compare parents by rank. You are right, that an OF may have different/multiple metrics to choose from which to derive the rank. However, in the end RPL needs a rank which way ever that is calculated. Using OF0 the rank is relative to hop-count while using MRHOF it would be relative to ETX, for instance - still both (hop-count or ETX) are converted to a rank, or not.

Do you have any preference for parent# vs p# for the parent_cmp?

just a (non-blocking) personal preference by me, I'm fine with naming as is - your choice 😉

bergzand · 2017-08-22T14:09:51Z

I looked it up and I have to agree with you. I've changed the sentence to your suggestion.

smlng · 2017-08-22T14:09:53Z

@cgundogan fine for you, too; ready to merge?

cgundogan · 2017-08-23T09:39:18Z

@smlng @bergzand looks good as it is now. ACK and GO

bergzand mentioned this pull request Aug 10, 2017

WIP: gnrc/rpl mrhof #7450

Closed

6 tasks

smlng suggested changes Aug 16, 2017

View reviewed changes

smlng reviewed Aug 17, 2017

View reviewed changes

smlng requested a review from cgundogan August 17, 2017 14:09

smlng approved these changes Aug 17, 2017

View reviewed changes

bergzand force-pushed the rpl/parent-sort branch from 0fc7ae5 to a8b41f8 Compare August 17, 2017 14:16

bergzand force-pushed the rpl/parent-sort branch from a8b41f8 to ea6d00e Compare August 17, 2017 14:20

smlng suggested changes Aug 18, 2017

View reviewed changes

bergzand force-pushed the rpl/parent-sort branch from 6422181 to 25762eb Compare August 18, 2017 09:08

smlng approved these changes Aug 18, 2017

View reviewed changes

cgundogan reviewed Aug 21, 2017

View reviewed changes

bergzand force-pushed the rpl/parent-sort branch 3 times, most recently from 6494769 to 047ad11 Compare August 22, 2017 08:41

smlng suggested changes Aug 22, 2017

View reviewed changes

smlng assigned bergzand Aug 22, 2017

smlng added this to the Release 2017.10 milestone Aug 22, 2017

bergzand force-pushed the rpl/parent-sort branch from 047ad11 to 6f2904f Compare August 22, 2017 10:26

bergzand mentioned this pull request Aug 22, 2017

RPL: API update suggestions #7498

Closed

rpl: Sort list of parents

426e978

bergzand force-pushed the rpl/parent-sort branch from 6f2904f to 426e978 Compare August 22, 2017 14:03

smlng approved these changes Aug 22, 2017

View reviewed changes

cgundogan merged commit 5c4000c into RIOT-OS:master Aug 23, 2017

bergzand deleted the rpl/parent-sort branch September 29, 2017 09:14

benpicco mentioned this pull request May 21, 2019

RPL: API update suggestions #11560

Merged

Conversation

bergzand commented Aug 10, 2017

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

bergzand commented Aug 17, 2017

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

smlng commented Aug 17, 2017

Uh oh!

bergzand commented Aug 17, 2017

Uh oh!

smlng commented Aug 17, 2017

Uh oh!

smlng commented Aug 17, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

bergzand commented Aug 17, 2017

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

bergzand commented Aug 18, 2017

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

smlng commented Aug 18, 2017

Uh oh!

bergzand commented Aug 18, 2017

Uh oh!

smlng commented Aug 18, 2017

Uh oh!

bergzand commented Aug 18, 2017

Uh oh!

smlng commented Aug 18, 2017

Uh oh!

Choose a reason for hiding this comment

Uh oh!

smlng commented Aug 21, 2017

Uh oh!

cgundogan commented Aug 21, 2017

Uh oh!

smlng commented Aug 21, 2017

Uh oh!

cgundogan commented Aug 21, 2017

Uh oh!

smlng commented Aug 21, 2017

Uh oh!

bergzand commented Aug 21, 2017

Uh oh!

bergzand commented Aug 22, 2017

Uh oh!

smlng commented Aug 17, 2017 •

edited

Loading

bergzand commented Aug 22, 2017 •

edited

Loading