Embed:
(wiki syntax)
Show/hide line numbers
rpl_of0.c
00001 /* 00002 * Copyright (c) 2015-2017, 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 #include "net_interface.h" 00027 00028 #include "NWK_INTERFACE/Include/protocol_abstract.h" 00029 #include "Common_Protocols/ipv6_resolution.h" 00030 #include "Service_Libs/etx/etx.h" 00031 00032 #include "RPL/rpl_protocol.h" 00033 #include "RPL/rpl_objective.h" 00034 #include "RPL/rpl_upward.h" 00035 #include "RPL/rpl_downward.h" 00036 #include "RPL/rpl_policy.h" 00037 #include "RPL/rpl_structures.h" 00038 #include "RPL/rpl_of0.h" 00039 00040 #define TRACE_GROUP "rpl0" 00041 00042 static void rpl_of0_parent_selection(rpl_instance_t *instance); 00043 static uint16_t rpl_of0_rank_through_neighbour(const rpl_neighbour_t *neighbour); 00044 static bool rpl_of0_neighbour_acceptable(const rpl_instance_t *instance, const rpl_neighbour_t *neighbour); 00045 00046 static rpl_objective_t rpl_of0 = { 00047 .ocp = RPL_OCP_OF0, 00048 .parent_selection = rpl_of0_parent_selection, 00049 .path_cost = rpl_of0_rank_through_neighbour, 00050 .neighbour_acceptable = rpl_of0_neighbour_acceptable, 00051 }; 00052 00053 #define DEFAULT_STEP_OF_RANK 3 00054 #define MINIMUM_STEP_OF_RANK 1 00055 #define MAXIMUM_STEP_OF_RANK 9 00056 #define SUITABLE_STEP_OF_RANK 8 00057 #define DEFAULT_RANK_STRETCH 0 00058 #define MAXIMUM_RANK_STRETCH 5 00059 #define DEFAULT_RANK_FACTOR 1 00060 #define MINIMUM_RANK_FACTOR 1 00061 #define MAXIMUM_RANK_FACTOR 4 00062 00063 typedef struct rpl_of0_params { 00064 uint8_t stretch_of_rank; 00065 uint8_t rank_factor; 00066 } rpl_of0_params; 00067 00068 void rpl_of0_init(void) 00069 { 00070 rpl_objective_register(&rpl_of0); 00071 } 00072 00073 static uint8_t rpl_of0_step_of_rank(const rpl_neighbour_t *neighbour) 00074 { 00075 uint16_t etx88 = ipv6_map_ip_to_ll_and_call_ll_addr_handler(NULL, neighbour->interface_id, NULL, neighbour->ll_address, etx_read); 00076 if (etx88 < 0x100) { /* "Unknown" */ 00077 return DEFAULT_STEP_OF_RANK; 00078 } 00079 00080 #if MINIMUM_STEP_OF_RANK != 1 || MAXIMUM_STEP_OF_RANK != 9 00081 #error "This assumes step 1-9" 00082 #endif 00083 /* So 0x100 = 1, 0x101-0x107=2, ... 0x201-0x400=8, 0x401-0xFFFE = 9, 0xFFFF = 10 */ 00084 static const uint16_t etx_thresholds[] = { 00085 0x100, 0x108, 0x110, 0x120, 0x140, 0x180, 0x200, 0x400, 0xFFFE, 0xFFFF 00086 }; 00087 00088 uint8_t step = 1; 00089 while (etx88 > etx_thresholds[step - 1]) { 00090 step++; 00091 } 00092 return step; 00093 } 00094 00095 static bool rpl_of0_neighbour_acceptable(const rpl_instance_t *instance, const rpl_neighbour_t *neighbour) 00096 { 00097 (void)instance; 00098 00099 return rpl_of0_step_of_rank(neighbour) <= SUITABLE_STEP_OF_RANK; 00100 } 00101 00102 static uint16_t rpl_of0_rank_increase(const rpl_neighbour_t *neighbour) 00103 { 00104 uint8_t step = rpl_of0_step_of_rank(neighbour); 00105 if (step > MAXIMUM_STEP_OF_RANK) { 00106 return 0xFFFF; 00107 } 00108 const rpl_domain_t *domain = neighbour->dodag_version->dodag->instance->domain; 00109 uint_fast8_t rank_factor = rpl_policy_of0_rank_factor(domain); 00110 return (rank_factor * step) * neighbour->dodag_version->dodag->config.min_hop_rank_increase; 00111 } 00112 00113 static uint16_t rpl_of0_rank_through_neighbour(const rpl_neighbour_t *neighbour) 00114 { 00115 return rpl_rank_add(neighbour->rank, rpl_of0_rank_increase(neighbour)); 00116 } 00117 00118 /* Given a preferred parent, we are only permitted to stretch our above the 00119 * path cost through that parent by a certain (policy) amount to accommodate a 00120 * bigger parent set. 00121 */ 00122 static uint16_t rpl_of0_max_stretched_rank(const rpl_neighbour_t *pref_parent) 00123 { 00124 uint16_t base_rank = rpl_of0_rank_through_neighbour(pref_parent); 00125 rpl_dodag_t *dodag = pref_parent->dodag_version->dodag; 00126 uint16_t max_stretch = rpl_policy_of0_stretch_of_rank(dodag->instance->domain) * dodag->config.min_hop_rank_increase; 00127 uint16_t max_stretched = rpl_rank_add(base_rank, max_stretch); 00128 if (max_stretched > pref_parent->dodag_version->greediness_rank_limit) { 00129 max_stretched = pref_parent->dodag_version->greediness_rank_limit; 00130 } 00131 return max_stretched; 00132 } 00133 00134 /* RFC 6552 4.2.2. Selection of the Backup Feasible Successor 00135 * This implementation can be called multiple times to select multiple successors, and can be used 00136 * to check the backup for a potential parent. 00137 */ 00138 static rpl_neighbour_t *rpl_of0_select_backup_parent(rpl_instance_t *instance, rpl_neighbour_t *pref, uint16_t max_rank) 00139 { 00140 rpl_neighbour_t *best = NULL; 00141 uint8_t best_step = 0xFF; 00142 00143 ns_list_foreach(rpl_neighbour_t, c, &instance->candidate_neighbours) { 00144 /* 1. New backup must not be (potential) preferred parent or already be a parent */ 00145 if (c == pref || c->dodag_parent) { 00146 continue; 00147 } 00148 00149 /* 2. Backup must be in the same DODAG version or later */ 00150 rpl_dodag_t *dodag = c->dodag_version->dodag; 00151 if (dodag != pref->dodag_version->dodag) { 00152 continue; 00153 } 00154 rpl_cmp_t cmp = rpl_seq_compare(c->dodag_version->number, pref->dodag_version->number); 00155 if (!(cmp & (RPL_CMP_GREATER | RPL_CMP_EQUAL))) { 00156 continue; 00157 } 00158 00159 /* 3. It must have lower DAGRank than our maximum permitted (we haven´t 00160 * necessarily chosen our rank yet, but we do have an upper bound). 00161 * NB neither RPL core nor OF0 requires our rank to indicate 00162 * /step in rank/ through other parents - they just need to have 00163 * /lesser/ rank. 00164 */ 00165 cmp = rpl_rank_compare(dodag, c->rank, max_rank); 00166 if (!(cmp & RPL_CMP_LESS)) { 00167 continue; 00168 } 00169 00170 uint8_t step = rpl_of0_step_of_rank(c); 00171 /* Ignore totally unreachable */ 00172 if (step > MAXIMUM_STEP_OF_RANK) { 00173 continue; 00174 } 00175 00176 if (!best) { 00177 goto new_best; 00178 } 00179 00180 /* 4. Prefer lesser rank */ 00181 cmp = rpl_rank_compare(dodag, c->rank, best->rank); 00182 if (cmp & RPL_CMP_LESS) { 00183 goto new_best; 00184 } else if (cmp & RPL_CMP_GREATER) { 00185 continue; 00186 } 00187 00188 /* 5. Prefer suitable link quality */ 00189 if (step <= SUITABLE_STEP_OF_RANK && best_step > SUITABLE_STEP_OF_RANK) { 00190 goto new_best; 00191 } else if (step > SUITABLE_STEP_OF_RANK && best_step <= SUITABLE_STEP_OF_RANK) { 00192 continue; 00193 } 00194 00195 /* 6. Prefer certain interfaces (not implemented) */ 00196 00197 /* 7. Prefer router previously in use */ 00198 if (c->was_dodag_parent && !best->was_dodag_parent) { 00199 goto new_best; 00200 } else if (!c->was_dodag_parent && best->was_dodag_parent) { 00201 continue; 00202 } 00203 00204 /* If it's a tie at this point, prefer the first in the list, which will 00205 * retain any previous parent ordering. 00206 */ 00207 continue; 00208 00209 new_best: 00210 best = c; 00211 best_step = step; 00212 } 00213 00214 return best; 00215 } 00216 00217 /* RFC 6552 4.2.1. Selection of the Preferred Parent */ 00218 /* As part of its work, it can also return the first backup if desired. */ 00219 static rpl_neighbour_t *rpl_of0_select_preferred_parent(rpl_instance_t *instance, const rpl_neighbour_t *prev_preferred, rpl_neighbour_t **backup_out, uint16_t *rank_out) 00220 { 00221 rpl_neighbour_t *best = NULL; 00222 uint16_t best_rank = RPL_RANK_INFINITE; 00223 uint8_t best_step = 0xFF; 00224 rpl_neighbour_t *best_backup = NULL; 00225 00226 ns_list_foreach(rpl_neighbour_t, c, &instance->candidate_neighbours) { 00227 rpl_dodag_t *dodag = c->dodag_version->dodag; 00228 uint8_t step = rpl_of0_step_of_rank(c); 00229 uint16_t new_rank = rpl_of0_rank_through_neighbour(c); 00230 rpl_cmp_t cmp; 00231 00232 /* Ignore totally unreachable */ 00233 if (step > MAXIMUM_STEP_OF_RANK) { 00234 continue; 00235 } 00236 00237 /* 1. Selection mustn't cause our Rank to increase excessively */ 00238 if (new_rank > c->dodag_version->hard_rank_limit) { 00239 new_rank = RPL_RANK_INFINITE; 00240 } 00241 00242 rpl_neighbour_t *c_backup = rpl_of0_select_backup_parent(instance, c, rpl_of0_max_stretched_rank(c)); 00243 00244 if (!best) { 00245 goto new_best; 00246 } 00247 00248 /* 2. Ignore totally unreachable, then prefer suitable connectivity- ignore totally unre */ 00249 if (step <= SUITABLE_STEP_OF_RANK && best_step > SUITABLE_STEP_OF_RANK) { 00250 goto new_best; 00251 } else if (step > SUITABLE_STEP_OF_RANK && best_step <= SUITABLE_STEP_OF_RANK) { 00252 continue; 00253 } 00254 00255 /* 3. Prefer certain interfaces (not implemented) */ 00256 00257 /* 4. Go by DODAG preference, if policy says this supersedes grounded check */ 00258 cmp = rpl_dodag_pref_compare(dodag, best->dodag_version->dodag); 00259 if (rpl_policy_of0_dodag_preference_supersedes_grounded(instance->domain)) { 00260 if (cmp == RPL_CMP_GREATER) { 00261 goto new_best; 00262 } else if (cmp == RPL_CMP_LESS) { 00263 continue; 00264 } 00265 } 00266 00267 /* 5. Prefer connection to a grounded DODAG */ 00268 if ((dodag->g_mop_prf & RPL_GROUNDED) != (best->dodag_version->dodag->g_mop_prf & RPL_GROUNDED)) { 00269 if (dodag->g_mop_prf & RPL_GROUNDED) { 00270 goto new_best; 00271 } else { 00272 continue; 00273 } 00274 } 00275 00276 /* 6. Go by DODAG preference (if we didn't already at 4) - comparison result still in cmp */ 00277 if (cmp == RPL_CMP_GREATER) { 00278 goto new_best; 00279 } else if (cmp == RPL_CMP_LESS) { 00280 continue; 00281 } 00282 00283 /* 7. Prefer newer DODAG Version if same DODAG */ 00284 if (dodag == best->dodag_version->dodag) { 00285 cmp = rpl_seq_compare(c->dodag_version->number, best->dodag_version->number); 00286 if (cmp & RPL_CMP_GREATER) { 00287 goto new_best; 00288 } else if (cmp & RPL_CMP_LESS) { 00289 continue; 00290 } 00291 } 00292 00293 /* 8. Prefer lesser resulting rank (note there should be no fractional part for OF0) */ 00294 cmp = rpl_rank_compare(dodag, new_rank, best_rank); 00295 if (cmp & RPL_CMP_LESS) { 00296 goto new_best; 00297 } else if (cmp & RPL_CMP_GREATER) { 00298 continue; 00299 } 00300 00301 /* 9. Prefer parent that gives us a backup parent */ 00302 if (c_backup && !best_backup) { 00303 goto new_best; 00304 } else if (!c_backup && best_backup) { 00305 continue; 00306 } 00307 00308 /* 10. Stick with previous preferred parent */ 00309 if (c == prev_preferred) { 00310 goto new_best; 00311 } else if (best == prev_preferred) { 00312 continue; 00313 } 00314 00315 /* 11. Prefer parent that most recently sent a DIO */ 00316 if (c->dio_timestamp != best->dio_timestamp) { 00317 if (common_serial_number_greater_32(c->dio_timestamp, best->dio_timestamp)) { 00318 goto new_best; 00319 } else { 00320 continue; 00321 } 00322 } 00323 00324 new_best: 00325 best_backup = c_backup; 00326 best_rank = new_rank; 00327 best_step = step; 00328 best = c; 00329 } 00330 00331 if (rank_out) { 00332 *rank_out = best_rank; 00333 } 00334 00335 if (backup_out) { 00336 *backup_out = best_backup; 00337 } 00338 00339 return best; 00340 } 00341 00342 00343 00344 /* 00345 * Parent selection is a serious business. This runs periodically - it need not 00346 * be fast. 00347 * 00348 * Its job is to reorder the instance's candidate neighbour list, placing 00349 * members of the parent set at the front, in preference order. Those neighbours 00350 * must have dodag_parent set, and dodag_pref filled in. 00351 * 00352 * Before entry, "was_dodag_parent" is set to "dodag_parent", and "dodag_parent" 00353 * is cleared. "was_dodag_parent" must not be modified. 00354 * 00355 * Parent selection must not delete candidate neighbours. 00356 * 00357 * For each DODAGVersion, target_max_rank is the RPL core's desired maximum 00358 * This will be >= the current rank. This allows distinction between different 00359 * states in a DODAG: 00360 * 00361 * 1) Wanting to hold rank 00362 * 2) Wanting to hold DAGRank 00363 * 3) Willing to increase DAGRank, but not exceeding MaxDagRankIncrease 00364 * 4) Willing to take any rank (new version) 00365 * 00366 * instance->current_dodag_version and instance->current_rank should be updated 00367 * on exit. 00368 * 00369 * No other instance data structures should be modified - core will re-evaluate 00370 * by examining the reordered candidate list. 00371 */ 00372 static void rpl_of0_parent_selection(rpl_instance_t *instance) 00373 { 00374 rpl_neighbour_t *old_pref_parent = rpl_instance_preferred_parent(instance); 00375 rpl_neighbour_t *backup; 00376 uint16_t rank; 00377 rpl_neighbour_t *pref_parent = rpl_of0_select_preferred_parent(instance, old_pref_parent, &backup, &rank); 00378 uint8_t last_pref; 00379 rpl_neighbour_list_t NS_LIST_NAME_INIT(parent_list); 00380 rpl_dodag_version_t *version; 00381 rpl_dodag_t *dodag; 00382 00383 if (!pref_parent) { 00384 tr_debug("No pref_parent (of0) -> set RPL_RANK_INFINITE"); 00385 rank = RPL_RANK_INFINITE; 00386 version = NULL; 00387 dodag = NULL; 00388 goto finish_up; 00389 } 00390 00391 version = pref_parent->dodag_version; 00392 dodag = version->dodag; 00393 00394 rpl_dodag_version_raise_greediness(version, rank); 00395 00396 pref_parent->dodag_parent = true; 00397 pref_parent->dodag_pref = last_pref = 0; 00398 00399 /* Move the preferred parent onto head of our empty parent list */ 00400 ns_list_remove(&instance->candidate_neighbours, pref_parent); 00401 ns_list_add_to_end(&parent_list, pref_parent); 00402 00403 /* Note that we only stretch to accommodate CURRENT candidate backups - not 00404 * ones that appear later. Thus nodes entering a version earlier may end up 00405 * with lower rank and less stretch. Losing our only backup may mean we 00406 * lower our rank, and can't increase again to accommodate the backup. 00407 * 00408 * This may need revisiting. 00409 */ 00410 uint_fast8_t more_successors = rpl_policy_of0_max_backup_successors(instance->domain); 00411 uint16_t last_cost = rank; 00412 uint16_t max_stretched_rank = rpl_of0_max_stretched_rank(pref_parent); 00413 while (backup) { 00414 /* Stretch rank to accommodate this backup */ 00415 if (rpl_rank_compare(dodag, backup->rank, rank) & (RPL_CMP_GREATER|RPL_CMP_EQUAL)) { 00416 rank = rpl_rank_next_level(dodag, backup->rank); 00417 if (rank != RPL_RANK_INFINITE && rank > version->greediness_rank_limit) { 00418 tr_error("Rank excess during stretch %"PRIu16" > %"PRIu16, rank, version->greediness_rank_limit); 00419 rank = version->greediness_rank_limit; 00420 break; 00421 } 00422 } 00423 /* Indicate preference levels - we require exact cost match for equal preference */ 00424 uint16_t backup_cost = rpl_of0_rank_through_neighbour(backup); 00425 if (backup_cost != last_cost && last_pref < 15) { 00426 last_pref++; 00427 last_cost = backup_cost; 00428 } 00429 backup->dodag_parent = true; 00430 backup->dodag_pref = last_pref; 00431 ns_list_remove(&instance->candidate_neighbours, backup); 00432 ns_list_add_to_end(&parent_list, backup); 00433 if (--more_successors) { 00434 backup = rpl_of0_select_backup_parent(instance, pref_parent, max_stretched_rank); 00435 } else { 00436 backup = NULL; 00437 } 00438 } 00439 00440 /* Two-step shuffle: move remaining unselected neighbours onto end of our list */ 00441 ns_list_concatenate(&parent_list, &instance->candidate_neighbours); 00442 00443 /* Then transfer whole list back to instance */ 00444 ns_list_concatenate(&instance->candidate_neighbours, &parent_list); 00445 00446 finish_up: 00447 rpl_instance_set_dodag_version(instance, version, rank); 00448 00449 /* Use default DAO path control */ 00450 rpl_downward_convert_dodag_preferences_to_dao_path_control(dodag); 00451 } 00452 00453 #endif /* HAVE_RPL */
Generated on Tue Jul 12 2022 12:22:19 by
1.7.2