rpl_mrhof.c

00001 /*
00002  * Copyright (c) 2015-2018, Arm Limited and affiliates.
00003  * SPDX-License-Identifier: Apache-2.0
00004  *
00005  * Licensed under the Apache License, Version 2.0 (the "License");
00006  * you may not use this file except in compliance with the License.
00007  * You may obtain a copy of the License at
00008  *
00009  *     http://www.apache.org/licenses/LICENSE-2.0
00010  *
00011  * Unless required by applicable law or agreed to in writing, software
00012  * distributed under the License is distributed on an "AS IS" BASIS,
00013  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
00014  * See the License for the specific language governing permissions and
00015  * limitations under the License.
00016  */
00017 #include "nsconfig.h"
00018 
00019 #ifdef HAVE_RPL
00020 
00021 #include "ns_types.h"
00022 #include "ns_trace.h"
00023 #include "common_functions.h"
00024 
00025 #include "net_rpl.h"
00026 
00027 #include "NWK_INTERFACE/Include/protocol_abstract.h"
00028 #include "Common_Protocols/ipv6_resolution.h"
00029 #include "Service_Libs/etx/etx.h"
00030 
00031 #include "RPL/rpl_protocol.h"
00032 #include "RPL/rpl_objective.h"
00033 #include "RPL/rpl_upward.h"
00034 #include "RPL/rpl_downward.h"
00035 #include "RPL/rpl_policy.h"
00036 #include "RPL/rpl_structures.h"
00037 #include "RPL/rpl_mrhof.h"
00038 
00039 #define TRACE_GROUP "rplm"
00040 
00041 /* Current implementation assumes ETX (and no metric container) - need to
00042  * ensure that we behave appropriately if a metric container is present.
00043  */
00044 
00045 static void rpl_mrhof_parent_selection(rpl_instance_t *instance);
00046 static uint16_t rpl_mrhof_path_cost_through_neighbour(const rpl_neighbour_t *neighbour);
00047 static bool rpl_mrhof_neighbour_acceptable(const rpl_instance_t *instance, const rpl_neighbour_t *neighbour);
00048 
00049 static rpl_objective_t rpl_mrhof = {
00050     .ocp = RPL_OCP_MRHOF,
00051     .parent_selection = rpl_mrhof_parent_selection,
00052     .path_cost = rpl_mrhof_path_cost_through_neighbour,
00053     .neighbour_acceptable = rpl_mrhof_neighbour_acceptable,
00054 };
00055 
00056 typedef struct rpl_of0_params {
00057     uint8_t stretch_of_rank;
00058     uint8_t rank_factor;
00059 } rpl_of0_params;
00060 
00061 void rpl_mrhof_init(void)
00062 {
00063     rpl_objective_register(&rpl_mrhof);
00064 }
00065 
00066 /* Return ETX in RFC 6551 metric form (*128), 0xFFFF = infinite */
00067 static uint16_t rpl_mrhof_etx(const rpl_neighbour_t *neighbour)
00068 {
00069     uint16_t etx88 = ipv6_map_ip_to_ll_and_call_ll_addr_handler(NULL, neighbour->interface_id, NULL, neighbour->ll_address, etx_read);
00070     switch (etx88) {
00071         case 0x0000: /* Unknown - assume poor */
00072             return 2 * 128;
00073         case 0x0001: /* Interface has no ETX - assume good */
00074             return 1 * 128;
00075         case 0xFFFF: /* Not associated */
00076             return RPL_RANK_INFINITE;
00077         default:
00078             return etx88 >> 1;
00079     }
00080 }
00081 
00082 static uint16_t rpl_mrhof_link_metric_to_neighbour(const rpl_neighbour_t *neighbour)
00083 {
00084     return rpl_mrhof_etx(neighbour);
00085 }
00086 
00087 static uint16_t rpl_mrhof_path_cost_through_neighbour(const rpl_neighbour_t *neighbour)
00088 {
00089     return rpl_rank_add(neighbour->rank, rpl_mrhof_link_metric_to_neighbour(neighbour));
00090 }
00091 
00092 static bool rpl_mrhof_neighbour_acceptable(const rpl_instance_t *instance, const rpl_neighbour_t *neighbour)
00093 {
00094     return rpl_mrhof_link_metric_to_neighbour(neighbour) <= rpl_policy_mrhof_max_link_metric(instance->domain);
00095 }
00096 
00097 
00098 /* Given a preferred parent, we are only permitted to stretch our above the
00099  * path cost through that parent by a certain (policy) amount to accommodate a
00100  * bigger parent set.
00101  */
00102 static uint16_t rpl_mrhof_max_stretched_rank(const rpl_dodag_version_t *version, uint16_t base_rank)
00103 {
00104     uint16_t max_stretch = rpl_policy_mrhof_max_rank_stretch_for_extra_parents(version->dodag->instance->domain);
00105     uint16_t max_stretched = rpl_rank_add(base_rank, max_stretch);
00106     if (max_stretched > version->greediness_rank_limit) {
00107         max_stretched = version->greediness_rank_limit;
00108     }
00109     return max_stretched;
00110 }
00111 
00112 
00113 
00114 /* RFC 6552 4.2.2. Selection of the Backup Feasible Successor
00115  * This implementation can be called multiple times to select multiple successors, and can be used
00116  * to check the backup for a potential parent.
00117  */
00118 static rpl_neighbour_t *rpl_mrhof_select_backup_parent(rpl_instance_t *instance, rpl_neighbour_t *pref, uint16_t *rank, uint16_t max_rank)
00119 {
00120     rpl_neighbour_t *best = NULL;
00121     uint16_t best_rank = RPL_RANK_INFINITE;
00122     uint16_t best_path_cost = RPL_RANK_INFINITE;
00123 
00124     ns_list_foreach(rpl_neighbour_t, c, &instance->candidate_neighbours) {
00125         /* New backup must not be (potential) preferred parent or already be a parent */
00126         if (c == pref || c->dodag_parent) {
00127             continue;
00128         }
00129 
00130         /* Backup must be in the same DODAG version (keep it simple) */
00131         if (c->dodag_version != pref->dodag_version) {
00132             continue;
00133         }
00134 
00135         rpl_dodag_t *dodag = c->dodag_version->dodag;
00136         if (dodag != pref->dodag_version->dodag) {
00137             continue;
00138         }
00139 
00140         /* Ignore high-link-metric neighbours */
00141         if (rpl_mrhof_link_metric_to_neighbour(c) > rpl_policy_mrhof_max_link_metric(instance->domain)) {
00142             continue;
00143         }
00144 
00145         /* It must not cause our rank to go up too much (rank affected by rules
00146          * 2 and 3 of RFC 6719 3.3.)
00147          */
00148         uint16_t path_cost = rpl_mrhof_path_cost_through_neighbour(c);
00149         uint16_t next_rank_rule2 = rpl_rank_next_level(dodag, c->rank);
00150         uint16_t path_cost_rule3 = rpl_rank_sub(path_cost, dodag->config.dag_max_rank_increase);
00151         uint16_t new_rank = next_rank_rule2 > path_cost_rule3 ? next_rank_rule2 : path_cost_rule3;
00152         if (new_rank > max_rank) {
00153             continue;
00154         }
00155 
00156         if (!best) {
00157             goto new_best;
00158         }
00159 
00160         /* Prefer lesser path cost */
00161         if (path_cost < best_path_cost) {
00162             goto new_best;
00163         } else if (path_cost > best_path_cost) {
00164             continue;
00165         }
00166 
00167         /* If it's a tie at this point, prefer the first in the list, which will
00168          * retain any previous parent ordering.
00169          */
00170         continue;
00171 
00172 new_best:
00173         best = c;
00174         best_path_cost = path_cost;
00175         best_rank = new_rank;
00176     }
00177 
00178     if (best) {
00179         if (best_rank > *rank) {
00180             *rank = best_rank;
00181         }
00182     }
00183 
00184     return best;
00185 }
00186 
00187 /* RFC 6719 3.2.2. Selection of the parent with lowest path cost */
00188 static rpl_neighbour_t *rpl_mrhof_select_best_parent(rpl_instance_t *instance, const rpl_neighbour_t *prev_preferred, uint16_t *rank_out)
00189 {
00190     rpl_neighbour_t *best = NULL;
00191     uint16_t best_rank = RPL_RANK_INFINITE;
00192     uint16_t best_path_cost = RPL_RANK_INFINITE;
00193     uint16_t best_link_metric = RPL_RANK_INFINITE;
00194     uint16_t prev_preferred_path_cost = RPL_RANK_INFINITE;
00195     const uint16_t metric_threshold = rpl_policy_mrhof_max_link_metric(instance->domain);
00196 
00197     /* Previous preferred parent, if any, will be at the start of the list */
00198     /* We can use this to simplify some logic */
00199     if (prev_preferred) {
00200         prev_preferred_path_cost = rpl_mrhof_path_cost_through_neighbour(prev_preferred);
00201         // Path cost might be not much worse than alternate parents, but it might push
00202         // us over our DAGMaxRankIncrease limit. In that case, makes sense to treat
00203         // the path cost as "infinite", allowing immediate switch to an alternative,
00204         // defeating hysteresis.
00205         if (prev_preferred_path_cost > prev_preferred->dodag_version->hard_rank_limit) {
00206             prev_preferred_path_cost = RPL_RANK_INFINITE;
00207         }
00208     }
00209 
00210     ns_list_foreach(rpl_neighbour_t, c, &instance->candidate_neighbours) {
00211         rpl_dodag_t *dodag = c->dodag_version->dodag;
00212 
00213         /* Check link, and ignore totally unreachable neighbours */
00214         uint16_t link_metric = rpl_mrhof_link_metric_to_neighbour(c);
00215         if (link_metric == RPL_RANK_INFINITE) {
00216             continue;
00217         }
00218 
00219         /* For ETX, rank is the path cost, then make sure we increase by MinHopRankIncrease */
00220         /* (Normally, MinHopRankIncrease will be 0x80, so this would be superfluous) */
00221         uint16_t path_cost = rpl_mrhof_path_cost_through_neighbour(c);
00222         uint16_t new_rank = path_cost;
00223         uint16_t min_rank = rpl_rank_add(c->rank, dodag->config.min_hop_rank_increase);
00224         if (new_rank < min_rank) {
00225             new_rank = min_rank;
00226         }
00227 
00228         if (new_rank > c->dodag_version->hard_rank_limit) {
00229             new_rank = RPL_RANK_INFINITE;
00230         }
00231 
00232         if (!best) {
00233             goto new_best;
00234         }
00235 
00236         /* Avoid using high-link-metric neighbours (but allow if we have no alternative) */
00237         if (link_metric <= metric_threshold && best_link_metric > metric_threshold) {
00238             goto new_best;
00239         } else if (link_metric > metric_threshold && best_link_metric <= metric_threshold) {
00240             continue;
00241         }
00242 
00243         /* MRHOF RFC is fuzzy about versions and DODAG selection; it seems
00244          * in many ways to assume we're choosing parents only within a
00245          * DODAG Version, whereas we also need to choose the DODAG and Version.
00246          *
00247          * Therefore we retain some of the logic for selecting DODAG from OF0.
00248          */
00249 
00250         /* Prefer connection to a grounded DODAG */
00251         if ((dodag->g_mop_prf & RPL_GROUNDED) != (best->dodag_version->dodag->g_mop_prf & RPL_GROUNDED)) {
00252             if (dodag->g_mop_prf & RPL_GROUNDED) {
00253                 goto new_best;
00254             } else {
00255                 continue;
00256             }
00257         }
00258 
00259         /* Go by DODAG preference */
00260         rpl_cmp_t cmp = rpl_dodag_pref_compare(dodag, best->dodag_version->dodag);
00261         if (cmp == RPL_CMP_GREATER) {
00262             goto new_best;
00263         } else if (cmp == RPL_CMP_LESS) {
00264             continue;
00265         }
00266 
00267         /* No explicit version preference - versions should flow naturally
00268          * from the root without one?
00269          */
00270 
00271         /* Hysteresis path cost test, if we are thinking of switching parents */
00272         if (best == prev_preferred) {
00273             /* Do not switch away from current parent, until threshold met */
00274             /* Note that any current parent will be first in the list - we
00275              * don't need to worry about hitting it and giving it preference as
00276              * a candidate later.
00277              */
00278             if (rpl_rank_add(path_cost, rpl_policy_mrhof_parent_switch_threshold(instance->domain)) <= prev_preferred_path_cost) {
00279                 goto new_best;
00280             } else {
00281                 continue;
00282             }
00283         }
00284 
00285         /* Prefer lesser resulting path cost */
00286         if (path_cost < best_path_cost) {
00287             goto new_best;
00288         } else if (path_cost > best_path_cost) {
00289             continue;
00290         }
00291 
00292         /* Prefer parent that most recently sent a DIO */
00293         if (c->dio_timestamp != best->dio_timestamp) {
00294             if (common_serial_number_greater_32(c->dio_timestamp, best->dio_timestamp)) {
00295                 goto new_best;
00296             } else {
00297                 continue;
00298             }
00299         }
00300 
00301 
00302 new_best:
00303         best_rank = new_rank;
00304         best_path_cost = path_cost;
00305         best_link_metric = link_metric;
00306         best = c;
00307     }
00308 
00309     if (rank_out) {
00310         *rank_out = best_rank;
00311     }
00312 
00313     return best;
00314 }
00315 
00316 
00317 
00318 /*
00319  * Parent selection is a serious business. This runs periodically - it need not
00320  * be fast.
00321  *
00322  * Its job is to reorder the instance's candidate neighbour list, placing
00323  * members of the parent set at the front, in preference order. Those neighbours
00324  * must have dodag_parent set, and dodag_pref filled in.
00325  *
00326  * Before entry, "was_dodag_parent" is set to "dodag_parent", and "dodag_parent"
00327  * is cleared. "was_dodag_parent" must not be modified.
00328  *
00329  * Parent selection must not delete candidate neighbours.
00330  *
00331  * For each DODAGVersion, target_max_rank is the RPL core's desired maximum
00332  * This will be >= the current rank. This allows distinction between different
00333  * states in a DODAG:
00334  *
00335  * 1) Wanting to hold rank
00336  * 2) Wanting to hold DAGRank
00337  * 3) Willing to increase DAGRank, but not exceeding MaxDagRankIncrease
00338  * 4) Willing to take any rank (new version)
00339  *
00340  * instance->current_dodag_version and instance->current_rank should be updated
00341  * on exit.
00342  *
00343  * No other instance data structures should be modified - core will re-evaluate
00344  * by examining the reordered candidate list.
00345  */
00346 static void rpl_mrhof_parent_selection(rpl_instance_t *instance)
00347 {
00348     rpl_neighbour_t *old_pref_parent = rpl_instance_preferred_parent(instance);
00349     uint16_t rank;
00350     rpl_neighbour_t *pref_parent = rpl_mrhof_select_best_parent(instance, old_pref_parent, &rank);
00351     uint8_t last_pref;
00352     rpl_neighbour_list_t NS_LIST_NAME_INIT(parent_list);
00353     rpl_dodag_version_t *version;
00354     rpl_dodag_t *dodag;
00355 
00356     if (!pref_parent) {
00357         tr_debug("No pref_parent (mrhof) -> set RPL_RANK_INFINITE");
00358         rank = RPL_RANK_INFINITE;
00359         version = NULL;
00360         dodag = NULL;
00361         goto finish_up;
00362     }
00363 
00364     version = pref_parent->dodag_version;
00365     dodag = version->dodag;
00366 
00367     rpl_dodag_version_raise_greediness(version, rank);
00368 
00369     pref_parent->dodag_parent = true;
00370     pref_parent->dodag_pref = last_pref = 0;
00371 
00372     /* Move the preferred parent onto head of our empty parent list */
00373     ns_list_remove(&instance->candidate_neighbours, pref_parent);
00374     ns_list_add_to_end(&parent_list, pref_parent);
00375 
00376     uint_fast8_t more_successors = rpl_policy_mrhof_parent_set_size(instance->domain) - 1;
00377     uint16_t last_cost = rpl_mrhof_path_cost_through_neighbour(pref_parent);
00378     uint16_t max_rank = rpl_mrhof_max_stretched_rank(pref_parent->dodag_version, rank);
00379     while (more_successors--) {
00380         rpl_neighbour_t *backup = rpl_mrhof_select_backup_parent(instance, pref_parent, &rank, max_rank);
00381         if (!backup) {
00382             break;
00383         }
00384 
00385         if (rank != RPL_RANK_INFINITE && rank > version->greediness_rank_limit) {
00386             tr_error("Rank excess during stretch %"PRIu16" > %"PRIu16, rank, version->greediness_rank_limit);
00387             rank = version->greediness_rank_limit;
00388             break;
00389         }
00390 
00391         /* Indicate preference levels, comparing path cost. If the preferred
00392          * parent has a higher cost than the backups, due to hysteresis, all
00393          * the others will end up with the same "preference" level.
00394          */
00395         uint16_t backup_cost = rpl_mrhof_path_cost_through_neighbour(backup);
00396         if (backup_cost > last_cost && last_pref < 15) {
00397             last_pref++;
00398             last_cost = backup_cost;
00399         }
00400         backup->dodag_parent = true;
00401         backup->dodag_pref = last_pref;
00402         ns_list_remove(&instance->candidate_neighbours, backup);
00403         ns_list_add_to_end(&parent_list, backup);
00404     }
00405 
00406     /* Two-step shuffle: move remaining unselected neighbours onto end of our list */
00407     ns_list_concatenate(&parent_list, &instance->candidate_neighbours);
00408 
00409     /* Then transfer whole list back to instance */
00410     ns_list_concatenate(&instance->candidate_neighbours, &parent_list);
00411 
00412 finish_up:
00413     rpl_instance_set_dodag_version(instance, version, rank);
00414 
00415     /* Use default DAO path control */
00416     rpl_downward_convert_dodag_preferences_to_dao_path_control(dodag);
00417 }
00418 
00419 #endif /* HAVE_RPL */