Contiki-NG
Loading...
Searching...
No Matches
rpl-mrhof.c
Go to the documentation of this file.
1/*
2 * Copyright (c) 2010, Swedish Institute of Computer Science.
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 * 3. Neither the name of the Institute nor the names of its contributors
14 * may be used to endorse or promote products derived from this software
15 * without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND
18 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 * ARE DISCLAIMED. IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE
21 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27 * SUCH DAMAGE.
28 *
29 * This file is part of the Contiki operating system.
30 *
31 */
32
33/**
34 * \addtogroup rpl-lite
35 * @{
36 *
37 * \file
38 * The Minimum Rank with Hysteresis Objective Function (MRHOF), RFC6719
39 *
40 * This implementation uses the estimated number of
41 * transmissions (ETX) as the additive routing metric,
42 * and also provides stubs for the energy metric.
43 *
44 * \author Joakim Eriksson <joakime@sics.se>, Nicolas Tsiftes <nvt@sics.se>
45 * Simon Duquennoy <simon.duquennoy@inria.fr>
46 */
47
48#include "net/routing/rpl-lite/rpl.h"
49#include "net/nbr-table.h"
50#include "net/link-stats.h"
51
52/* Log configuration */
53#include "sys/log.h"
54#define LOG_MODULE "RPL"
55#define LOG_LEVEL LOG_LEVEL_RPL
56
57/* RFC6551 and RFC6719 do not mandate the use of a specific formula to
58 * compute the ETX value. This MRHOF implementation relies on the value
59 * computed by the link-stats module.It has an optional feature,
60 * RPL_MRHOF_CONF_SQUARED_ETX, that consists in squaring this value.
61 *
62 * Squaring basically penalizes bad links while preserving the semantics of ETX
63 * (1 = perfect link, more = worse link). As a result, MRHOF will favor
64 * good links over short paths. Without this feature, a hop with 50% PRR (ETX=2)
65 * is equivalent to two perfect hops with 100% PRR (ETX=1+1=2). With this
66 * feature, the former path obtains ETX=2*2=4 and the former ETX=1*1+1*1=2.
67 *
68 * While this feature helps achieve extra relaibility, it also results in
69 * added churn. In networks with high congestion or poor links, this can lead
70 * to poor connectivity due to more parent switches, loops, Trickle resets, etc.
71 */
72#ifdef RPL_MRHOF_CONF_SQUARED_ETX
73#define RPL_MRHOF_SQUARED_ETX RPL_MRHOF_CONF_SQUARED_ETX
74#else /* RPL_MRHOF_CONF_SQUARED_ETX */
75#define RPL_MRHOF_SQUARED_ETX 0
76#endif /* RPL_MRHOF_CONF_SQUARED_ETX */
77
78/* Configuration parameters of RFC6719. Reject parents that have a higher
79 * link metric than the following. The default value is 512. */
80#ifdef RPL_MRHOF_CONF_MAX_LINK_METRIC
81#define MAX_LINK_METRIC RPL_MRHOF_CONF_MAX_LINK_METRIC
82#else /* RPL_MRHOF_CONF_MAX_LINK_METRIC */
83#define MAX_LINK_METRIC 512 /* Eq ETX of 4 */
84#endif /* RPL_MRHOF_CONF_MAX_LINK_METRIC */
85
86/* Reject parents that have a higher path cost than the following. */
87#ifdef RPL_MRHOF_CONF_MAX_PATH_COST
88#define MAX_PATH_COST RPL_MRHOF_CONF_MAX_PATH_COST
89#else /* RPL_MRHOF_CONF_MAX_PATH_COST */
90#define MAX_PATH_COST 32768 /* Eq path ETX of 256 */
91#endif /* RPL_MRHOF_CONF_MAX_PATH_COST */
92
93#if !RPL_MRHOF_SQUARED_ETX
94/* Hysteresis of MRHOF: the rank must differ more than PARENT_SWITCH_THRESHOLD_DIV
95 * in order to switch preferred parent. Default in RFC6719: 192, eq ETX of 1.5. */
96#define RANK_THRESHOLD 192 /* Eq ETX of 1.5 */
97#else /* !RPL_MRHOF_SQUARED_ETX */
98#define RANK_THRESHOLD 384 /* Eq ETX of sqrt(3) */
99#endif /* !RPL_MRHOF_SQUARED_ETX */
100
101/* Additional, custom hysteresis based on time. If a neighbor was consistently
102 * better than our preferred parent for at least TIME_THRESHOLD, switch to
103 * this neighbor regardless of RANK_THRESHOLD. */
104#define TIME_THRESHOLD (10 * 60 * CLOCK_SECOND)
105
106/*---------------------------------------------------------------------------*/
107static void
108reset(void)
109{
110 LOG_INFO("reset MRHOF\n");
111}
112/*---------------------------------------------------------------------------*/
113static uint16_t
114nbr_link_metric(rpl_nbr_t *nbr)
115{
116 const struct link_stats *stats = rpl_neighbor_get_link_stats(nbr);
117 return stats != NULL ? stats->etx : 0xffff;
118}
119/*---------------------------------------------------------------------------*/
120static uint16_t
121link_metric_to_rank(uint16_t etx)
122{
123#if RPL_MRHOF_SQUARED_ETX
124 uint32_t squared_etx = ((uint32_t)etx * etx) / LINK_STATS_ETX_DIVISOR;
125 return (uint16_t)MIN(squared_etx, 0xffff);
126#else /* RPL_MRHOF_SQUARED_ETX */
127 return etx;
128#endif /* RPL_MRHOF_SQUARED_ETX */
129}
130/*---------------------------------------------------------------------------*/
131static uint16_t
132nbr_path_cost(rpl_nbr_t *nbr)
133{
134 uint16_t base;
135
136 if(nbr == NULL) {
137 return 0xffff;
138 }
139
140#if RPL_WITH_MC
141 /* Handle the different MC types */
142 switch(curr_instance.mc.type) {
143 case RPL_DAG_MC_ETX:
144 base = nbr->mc.obj.etx;
145 break;
146 case RPL_DAG_MC_ENERGY:
147 base = nbr->mc.obj.energy.energy_est << 8;
148 break;
149 default:
150 base = nbr->rank;
151 break;
152 }
153#else /* RPL_WITH_MC */
154 base = nbr->rank;
155#endif /* RPL_WITH_MC */
156
157 /* path cost upper bound: 0xffff */
158 return MIN((uint32_t)base + link_metric_to_rank(nbr_link_metric(nbr)), 0xffff);
159}
160/*---------------------------------------------------------------------------*/
161static rpl_rank_t
162rank_via_nbr(rpl_nbr_t *nbr)
163{
164 uint16_t min_hoprankinc;
165 uint16_t path_cost;
166
167 if(nbr == NULL) {
168 return RPL_INFINITE_RANK;
169 }
170
171 min_hoprankinc = curr_instance.min_hoprankinc;
172 path_cost = nbr_path_cost(nbr);
173
174 /* Rank lower-bound: nbr rank + min_hoprankinc */
175 return MAX(MIN((uint32_t)nbr->rank + min_hoprankinc, RPL_INFINITE_RANK), path_cost);
176}
177/*---------------------------------------------------------------------------*/
178static int
179nbr_has_usable_link(rpl_nbr_t *nbr)
180{
181 uint16_t link_metric = nbr_link_metric(nbr);
182 /* Exclude links with too high link metrics */
183 return link_metric <= MAX_LINK_METRIC;
184}
185/*---------------------------------------------------------------------------*/
186static int
187nbr_is_acceptable_parent(rpl_nbr_t *nbr)
188{
189 uint16_t path_cost = nbr_path_cost(nbr);
190 /* Exclude links with too high link metrics or path cost (RFC6719, 3.2.2) */
191 return nbr_has_usable_link(nbr) && path_cost <= MAX_PATH_COST;
192}
193/*---------------------------------------------------------------------------*/
194static int
195within_hysteresis(rpl_nbr_t *nbr)
196{
197 uint16_t path_cost = nbr_path_cost(nbr);
198 uint16_t parent_path_cost = nbr_path_cost(curr_instance.dag.preferred_parent);
199
200 int within_rank_hysteresis = path_cost + RANK_THRESHOLD > parent_path_cost;
201 int within_time_hysteresis = nbr->better_parent_since == 0
202 || (clock_time() - nbr->better_parent_since) <= TIME_THRESHOLD;
203
204 /* As we want to consider neighbors that are either beyond the rank or time
205 hystereses, return 1 here iff the neighbor is within both hystereses. */
206 return within_rank_hysteresis && within_time_hysteresis;
207}
208/*---------------------------------------------------------------------------*/
209static rpl_nbr_t *
210best_parent(rpl_nbr_t *nbr1, rpl_nbr_t *nbr2)
211{
212 int nbr1_is_acceptable;
213 int nbr2_is_acceptable;
214
215 nbr1_is_acceptable = nbr1 != NULL && nbr_is_acceptable_parent(nbr1);
216 nbr2_is_acceptable = nbr2 != NULL && nbr_is_acceptable_parent(nbr2);
217
218 if(!nbr1_is_acceptable) {
219 return nbr2_is_acceptable ? nbr2 : NULL;
220 }
221 if(!nbr2_is_acceptable) {
222 return nbr1_is_acceptable ? nbr1 : NULL;
223 }
224
225 /* Maintain stability of the preferred parent. Switch only if the gain
226 is greater than RANK_THRESHOLD, or if the neighbor has been better than the
227 current parent for at more than TIME_THRESHOLD. */
228 if(nbr1 == curr_instance.dag.preferred_parent && within_hysteresis(nbr2)) {
229 return nbr1;
230 }
231 if(nbr2 == curr_instance.dag.preferred_parent && within_hysteresis(nbr1)) {
232 return nbr2;
233 }
234
235 return nbr_path_cost(nbr1) < nbr_path_cost(nbr2) ? nbr1 : nbr2;
236}
237/*---------------------------------------------------------------------------*/
238#if !RPL_WITH_MC
239static void
240update_metric_container(void)
241{
242 curr_instance.mc.type = RPL_DAG_MC_NONE;
243}
244#else /* RPL_WITH_MC */
245static void
246update_metric_container(void)
247{
248 uint16_t path_cost;
249 uint8_t type;
250
251 if(!curr_instance.used) {
252 LOG_WARN("cannot update the metric container when not joined\n");
253 return;
254 }
255
256 if(curr_instance.dag.rank == ROOT_RANK) {
257 /* Configure MC at root only, other nodes are auto-configured when joining */
258 curr_instance.mc.type = RPL_DAG_MC;
259 curr_instance.mc.flags = 0;
260 curr_instance.mc.aggr = RPL_DAG_MC_AGGR_ADDITIVE;
261 curr_instance.mc.prec = 0;
262 path_cost = curr_instance.dag.rank;
263 } else {
264 path_cost = nbr_path_cost(curr_instance.dag.preferred_parent);
265 }
266
267 /* Handle the different MC types */
268 switch(curr_instance.mc.type) {
269 case RPL_DAG_MC_NONE:
270 break;
271 case RPL_DAG_MC_ETX:
272 curr_instance.mc.length = sizeof(curr_instance.mc.obj.etx);
273 curr_instance.mc.obj.etx = path_cost;
274 break;
275 case RPL_DAG_MC_ENERGY:
276 curr_instance.mc.length = sizeof(curr_instance.mc.obj.energy);
277 if(curr_instance.dag.rank == ROOT_RANK) {
278 type = RPL_DAG_MC_ENERGY_TYPE_MAINS;
279 } else {
280 type = RPL_DAG_MC_ENERGY_TYPE_BATTERY;
281 }
282 curr_instance.mc.obj.energy.flags = type << RPL_DAG_MC_ENERGY_TYPE;
283 /* Energy_est is only one byte, use the least significant byte of the path metric. */
284 curr_instance.mc.obj.energy.energy_est = path_cost >> 8;
285 break;
286 default:
287 LOG_WARN("MRHOF, non-supported MC %u\n", curr_instance.mc.type);
288 break;
289 }
290}
291#endif /* RPL_WITH_MC */
292/*---------------------------------------------------------------------------*/
293rpl_of_t rpl_mrhof = {
294 reset,
295 nbr_link_metric,
296 nbr_has_usable_link,
297 nbr_is_acceptable_parent,
298 nbr_path_cost,
299 rank_via_nbr,
300 best_parent,
301 update_metric_container,
302 RPL_OCP_MRHOF
303};
304
305/** @}*/
clock_time_t clock_time(void)
Get the current clock time.
Definition clock.c:118
const struct link_stats * rpl_neighbor_get_link_stats(rpl_nbr_t *nbr)
Returns a neighbor's link statistics.
Header file for the logging system.
All information related to a RPL neighbor.
Definition rpl-types.h:136
API for RPL objective functions (OF)
Definition rpl.h:204
static uip_ds6_nbr_t * nbr
Pointer to llao option in uip_buf.
Definition uip-nd6.c:106