Contiki-NG
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  * \file
35  * The Minimum Rank with Hysteresis Objective Function (MRHOF), RFC6719
36  *
37  * This implementation uses the estimated number of
38  * transmissions (ETX) as the additive routing metric,
39  * and also provides stubs for the energy metric.
40  *
41  * \author Joakim Eriksson <joakime@sics.se>, Nicolas Tsiftes <nvt@sics.se>
42  */
43 
44 /**
45  * \addtogroup uip
46  * @{
47  */
48 
49 #include "net/routing/rpl-classic/rpl.h"
50 #include "net/routing/rpl-classic/rpl-private.h"
51 #include "net/nbr-table.h"
52 #include "net/link-stats.h"
53 
54 #include "sys/log.h"
55 
56 #define LOG_MODULE "RPL"
57 #define LOG_LEVEL LOG_LEVEL_RPL
58 
59 /* RFC6551 and RFC6719 do not mandate the use of a specific formula to
60  * compute the ETX value. This MRHOF implementation relies on the value
61  * computed by the link-stats module.It has an optional feature,
62  * RPL_MRHOF_CONF_SQUARED_ETX, that consists in squaring this value.
63  *
64  * Squaring basically penalizes bad links while preserving the semantics of ETX
65  * (1 = perfect link, more = worse link). As a result, MRHOF will favor
66  * good links over short paths. Without this feature, a hop with 50% PRR (ETX=2)
67  * is equivalent to two perfect hops with 100% PRR (ETX=1+1=2). With this
68  * feature, the former path obtains ETX=2*2=4 and the former ETX=1*1+1*1=2.
69  *
70  * While this feature helps achieve extra relaibility, it also results in
71  * added churn. In networks with high congestion or poor links, this can lead
72  * to poor connectivity due to more parent switches, loops, Trickle resets, etc.
73  */
74 #ifdef RPL_MRHOF_CONF_SQUARED_ETX
75 #define RPL_MRHOF_SQUARED_ETX RPL_MRHOF_CONF_SQUARED_ETX
76 #else /* RPL_MRHOF_CONF_SQUARED_ETX */
77 #define RPL_MRHOF_SQUARED_ETX 0
78 #endif /* RPL_MRHOF_CONF_SQUARED_ETX */
79 
80 #if !RPL_MRHOF_SQUARED_ETX
81 /* Configuration parameters of RFC6719. Reject parents that have a higher
82  * link metric than the following. The default value is 512 but we use 1024. */
83 #define MAX_LINK_METRIC 1024 /* Eq ETX of 8 */
84 /* Hysteresis of MRHOF: the rank must differ more than PARENT_SWITCH_THRESHOLD_DIV
85  * in order to switch preferred parent. Default in RFC6719: 192, eq ETX of 1.5.
86  * We use a more aggressive setting: 96, eq ETX of 0.75.
87  */
88 #define PARENT_SWITCH_THRESHOLD 96 /* Eq ETX of 0.75 */
89 #else /* !RPL_MRHOF_SQUARED_ETX */
90 #define MAX_LINK_METRIC 2048 /* Eq ETX of 4 */
91 #define PARENT_SWITCH_THRESHOLD 160 /* Eq ETX of 1.25 (results in a churn comparable
92 to the threshold of 96 in the non-squared case) */
93 #endif /* !RPL_MRHOF_SQUARED_ETX */
94 
95 /* Reject parents that have a higher path cost than the following. */
96 #define MAX_PATH_COST 32768 /* Eq path ETX of 256 */
97 
98 /*---------------------------------------------------------------------------*/
99 static void
100 reset(rpl_dag_t *dag)
101 {
102  LOG_INFO("Reset MRHOF\n");
103 }
104 /*---------------------------------------------------------------------------*/
105 #if RPL_WITH_DAO_ACK
106 static void
107 dao_ack_callback(rpl_parent_t *p, int status)
108 {
109  if(status == RPL_DAO_ACK_UNABLE_TO_ADD_ROUTE_AT_ROOT) {
110  return;
111  }
112  /* here we need to handle failed DAO's and other stuff */
113  LOG_DBG("MRHOF - DAO ACK received with status: %d\n", status);
114  if(status >= RPL_DAO_ACK_UNABLE_TO_ACCEPT) {
115  /* punish the ETX as if this was 10 packets lost */
116  link_stats_packet_sent(rpl_get_parent_lladdr(p), MAC_TX_OK, 10);
117  } else if(status == RPL_DAO_ACK_TIMEOUT) { /* timeout = no ack */
118  /* punish the total lack of ACK with a similar punishment */
119  link_stats_packet_sent(rpl_get_parent_lladdr(p), MAC_TX_OK, 10);
120  }
121 }
122 #endif /* RPL_WITH_DAO_ACK */
123 /*---------------------------------------------------------------------------*/
124 static uint16_t
125 parent_link_metric(rpl_parent_t *p)
126 {
127  const struct link_stats *stats = rpl_get_parent_link_stats(p);
128  if(stats != NULL) {
129 #if RPL_MRHOF_SQUARED_ETX
130  uint32_t squared_etx = ((uint32_t)stats->etx * stats->etx) / LINK_STATS_ETX_DIVISOR;
131  return (uint16_t)MIN(squared_etx, 0xffff);
132 #else /* RPL_MRHOF_SQUARED_ETX */
133  return stats->etx;
134 #endif /* RPL_MRHOF_SQUARED_ETX */
135  }
136  return 0xffff;
137 }
138 /*---------------------------------------------------------------------------*/
139 static uint16_t
140 parent_path_cost(rpl_parent_t *p)
141 {
142  uint16_t base;
143 
144  if(p == NULL || p->dag == NULL || p->dag->instance == NULL) {
145  return 0xffff;
146  }
147 
148 #if RPL_WITH_MC
149  /* Handle the different MC types */
150  switch(p->dag->instance->mc.type) {
151  case RPL_DAG_MC_ETX:
152  base = p->mc.obj.etx;
153  break;
154  case RPL_DAG_MC_ENERGY:
155  base = p->mc.obj.energy.energy_est << 8;
156  break;
157  default:
158  base = p->rank;
159  break;
160  }
161 #else /* RPL_WITH_MC */
162  base = p->rank;
163 #endif /* RPL_WITH_MC */
164 
165  /* path cost upper bound: 0xffff */
166  return MIN((uint32_t)base + parent_link_metric(p), 0xffff);
167 }
168 /*---------------------------------------------------------------------------*/
169 static rpl_rank_t
170 rank_via_parent(rpl_parent_t *p)
171 {
172  uint16_t min_hoprankinc;
173  uint16_t path_cost;
174 
175  if(p == NULL || p->dag == NULL || p->dag->instance == NULL) {
176  return RPL_INFINITE_RANK;
177  }
178 
179  min_hoprankinc = p->dag->instance->min_hoprankinc;
180  path_cost = parent_path_cost(p);
181 
182  /* Rank lower-bound: parent rank + min_hoprankinc */
183  return MAX(MIN((uint32_t)p->rank + min_hoprankinc, 0xffff), path_cost);
184 }
185 /*---------------------------------------------------------------------------*/
186 static int
187 parent_is_acceptable(rpl_parent_t *p)
188 {
189  uint16_t link_metric = parent_link_metric(p);
190  uint16_t path_cost = parent_path_cost(p);
191  /* Exclude links with too high link metrics or path cost (RFC6719, 3.2.2) */
192  return link_metric <= MAX_LINK_METRIC && path_cost <= MAX_PATH_COST;
193 }
194 /*---------------------------------------------------------------------------*/
195 static int
196 parent_has_usable_link(rpl_parent_t *p)
197 {
198  uint16_t link_metric = parent_link_metric(p);
199  /* Exclude links with too high link metrics */
200  return link_metric <= MAX_LINK_METRIC;
201 }
202 /*---------------------------------------------------------------------------*/
203 static rpl_parent_t *
204 best_parent(rpl_parent_t *p1, rpl_parent_t *p2)
205 {
206  rpl_dag_t *dag;
207  uint16_t p1_cost;
208  uint16_t p2_cost;
209  int p1_is_acceptable;
210  int p2_is_acceptable;
211 
212  p1_is_acceptable = p1 != NULL && parent_is_acceptable(p1);
213  p2_is_acceptable = p2 != NULL && parent_is_acceptable(p2);
214 
215  if(!p1_is_acceptable) {
216  return p2_is_acceptable ? p2 : NULL;
217  }
218  if(!p2_is_acceptable) {
219  return p1_is_acceptable ? p1 : NULL;
220  }
221 
222  dag = p1->dag; /* Both parents are in the same DAG. */
223  p1_cost = parent_path_cost(p1);
224  p2_cost = parent_path_cost(p2);
225 
226  /* Maintain stability of the preferred parent in case of similar ranks. */
227  if(p1 == dag->preferred_parent || p2 == dag->preferred_parent) {
228  if(p1_cost < p2_cost + PARENT_SWITCH_THRESHOLD &&
229  p1_cost > p2_cost - PARENT_SWITCH_THRESHOLD) {
230  return dag->preferred_parent;
231  }
232  }
233 
234  return p1_cost < p2_cost ? p1 : p2;
235 }
236 /*---------------------------------------------------------------------------*/
237 static rpl_dag_t *
238 best_dag(rpl_dag_t *d1, rpl_dag_t *d2)
239 {
240  if(d1->grounded != d2->grounded) {
241  return d1->grounded ? d1 : d2;
242  }
243 
244  if(d1->preference != d2->preference) {
245  return d1->preference > d2->preference ? d1 : d2;
246  }
247 
248  return d1->rank < d2->rank ? d1 : d2;
249 }
250 /*---------------------------------------------------------------------------*/
251 #if !RPL_WITH_MC
252 static void
253 update_metric_container(rpl_instance_t *instance)
254 {
255  instance->mc.type = RPL_DAG_MC_NONE;
256 }
257 #else /* RPL_WITH_MC */
258 static void
259 update_metric_container(rpl_instance_t *instance)
260 {
261  rpl_dag_t *dag;
262  uint16_t path_cost;
263  uint8_t type;
264 
265  dag = instance->current_dag;
266  if(dag == NULL || !dag->joined) {
267  LOG_WARN("Cannot update the metric container when not joined\n");
268  return;
269  }
270 
271  if(dag->rank == ROOT_RANK(instance)) {
272  /* Configure MC at root only, other nodes are auto-configured when joining */
273  instance->mc.type = RPL_DAG_MC;
274  instance->mc.flags = 0;
275  instance->mc.aggr = RPL_DAG_MC_AGGR_ADDITIVE;
276  instance->mc.prec = 0;
277  path_cost = dag->rank;
278  } else {
279  path_cost = parent_path_cost(dag->preferred_parent);
280  }
281 
282  /* Handle the different MC types */
283  switch(instance->mc.type) {
284  case RPL_DAG_MC_NONE:
285  break;
286  case RPL_DAG_MC_ETX:
287  instance->mc.length = sizeof(instance->mc.obj.etx);
288  instance->mc.obj.etx = path_cost;
289  break;
290  case RPL_DAG_MC_ENERGY:
291  instance->mc.length = sizeof(instance->mc.obj.energy);
292  if(dag->rank == ROOT_RANK(instance)) {
293  type = RPL_DAG_MC_ENERGY_TYPE_MAINS;
294  } else {
295  type = RPL_DAG_MC_ENERGY_TYPE_BATTERY;
296  }
297  instance->mc.obj.energy.flags = type << RPL_DAG_MC_ENERGY_TYPE;
298  /* Energy_est is only one byte, use the least significant byte of the path metric. */
299  instance->mc.obj.energy.energy_est = path_cost >> 8;
300  break;
301  default:
302  LOG_WARN("MRHOF, non-supported MC %u\n", instance->mc.type);
303  break;
304  }
305 }
306 #endif /* RPL_WITH_MC */
307 /*---------------------------------------------------------------------------*/
308 rpl_of_t rpl_mrhof = {
309  reset,
310 #if RPL_WITH_DAO_ACK
311  dao_ack_callback,
312 #endif
313  parent_link_metric,
314  parent_has_usable_link,
315  parent_path_cost,
316  rank_via_parent,
317  best_parent,
318  best_dag,
319  update_metric_container,
320  RPL_OCP_MRHOF
321 };
322 
323 /** @}*/
RPL DAG structure.
Definition: rpl.h:135
RPL instance structure.
Definition: rpl.h:219
#define ROOT_RANK
Rank of a root node.
Definition: rpl-types.h:78
API for RPL objective functions (OF)
Definition: rpl.h:201
The MAC layer transmission was OK.
Definition: mac.h:87
Header file for the logging system