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 #define DEBUG DEBUG_NONE
55 #include "net/ipv6/uip-debug.h"
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 #if !RPL_MRHOF_SQUARED_ETX
79 /* Configuration parameters of RFC6719. Reject parents that have a higher
80  * link metric than the following. The default value is 512 but we use 1024. */
81 #define MAX_LINK_METRIC 1024 /* Eq ETX of 8 */
82 /* Hysteresis of MRHOF: the rank must differ more than PARENT_SWITCH_THRESHOLD_DIV
83  * in order to switch preferred parent. Default in RFC6719: 192, eq ETX of 1.5.
84  * We use a more aggressive setting: 96, eq ETX of 0.75.
85  */
86 #define PARENT_SWITCH_THRESHOLD 96 /* Eq ETX of 0.75 */
87 #else /* !RPL_MRHOF_SQUARED_ETX */
88 #define MAX_LINK_METRIC 2048 /* Eq ETX of 4 */
89 #define PARENT_SWITCH_THRESHOLD 160 /* Eq ETX of 1.25 (results in a churn comparable
90 to the threshold of 96 in the non-squared case) */
91 #endif /* !RPL_MRHOF_SQUARED_ETX */
92 
93 /* Reject parents that have a higher path cost than the following. */
94 #define MAX_PATH_COST 32768 /* Eq path ETX of 256 */
95 
96 /*---------------------------------------------------------------------------*/
97 static void
98 reset(rpl_dag_t *dag)
99 {
100  PRINTF("RPL: Reset MRHOF\n");
101 }
102 /*---------------------------------------------------------------------------*/
103 #if RPL_WITH_DAO_ACK
104 static void
105 dao_ack_callback(rpl_parent_t *p, int status)
106 {
107  if(status == RPL_DAO_ACK_UNABLE_TO_ADD_ROUTE_AT_ROOT) {
108  return;
109  }
110  /* here we need to handle failed DAO's and other stuff */
111  PRINTF("RPL: MRHOF - DAO ACK received with status: %d\n", status);
112  if(status >= RPL_DAO_ACK_UNABLE_TO_ACCEPT) {
113  /* punish the ETX as if this was 10 packets lost */
114  link_stats_packet_sent(rpl_get_parent_lladdr(p), MAC_TX_OK, 10);
115  } else if(status == RPL_DAO_ACK_TIMEOUT) { /* timeout = no ack */
116  /* punish the total lack of ACK with a similar punishment */
117  link_stats_packet_sent(rpl_get_parent_lladdr(p), MAC_TX_OK, 10);
118  }
119 }
120 #endif /* RPL_WITH_DAO_ACK */
121 /*---------------------------------------------------------------------------*/
122 static uint16_t
123 parent_link_metric(rpl_parent_t *p)
124 {
125  const struct link_stats *stats = rpl_get_parent_link_stats(p);
126  if(stats != NULL) {
127 #if RPL_MRHOF_SQUARED_ETX
128  uint32_t squared_etx = ((uint32_t)stats->etx * stats->etx) / LINK_STATS_ETX_DIVISOR;
129  return (uint16_t)MIN(squared_etx, 0xffff);
130 #else /* RPL_MRHOF_SQUARED_ETX */
131  return stats->etx;
132 #endif /* RPL_MRHOF_SQUARED_ETX */
133  }
134  return 0xffff;
135 }
136 /*---------------------------------------------------------------------------*/
137 static uint16_t
138 parent_path_cost(rpl_parent_t *p)
139 {
140  uint16_t base;
141 
142  if(p == NULL || p->dag == NULL || p->dag->instance == NULL) {
143  return 0xffff;
144  }
145 
146 #if RPL_WITH_MC
147  /* Handle the different MC types */
148  switch(p->dag->instance->mc.type) {
149  case RPL_DAG_MC_ETX:
150  base = p->mc.obj.etx;
151  break;
152  case RPL_DAG_MC_ENERGY:
153  base = p->mc.obj.energy.energy_est << 8;
154  break;
155  default:
156  base = p->rank;
157  break;
158  }
159 #else /* RPL_WITH_MC */
160  base = p->rank;
161 #endif /* RPL_WITH_MC */
162 
163  /* path cost upper bound: 0xffff */
164  return MIN((uint32_t)base + parent_link_metric(p), 0xffff);
165 }
166 /*---------------------------------------------------------------------------*/
167 static rpl_rank_t
168 rank_via_parent(rpl_parent_t *p)
169 {
170  uint16_t min_hoprankinc;
171  uint16_t path_cost;
172 
173  if(p == NULL || p->dag == NULL || p->dag->instance == NULL) {
174  return RPL_INFINITE_RANK;
175  }
176 
177  min_hoprankinc = p->dag->instance->min_hoprankinc;
178  path_cost = parent_path_cost(p);
179 
180  /* Rank lower-bound: parent rank + min_hoprankinc */
181  return MAX(MIN((uint32_t)p->rank + min_hoprankinc, 0xffff), path_cost);
182 }
183 /*---------------------------------------------------------------------------*/
184 static int
185 parent_is_acceptable(rpl_parent_t *p)
186 {
187  uint16_t link_metric = parent_link_metric(p);
188  uint16_t path_cost = parent_path_cost(p);
189  /* Exclude links with too high link metrics or path cost (RFC6719, 3.2.2) */
190  return link_metric <= MAX_LINK_METRIC && path_cost <= MAX_PATH_COST;
191 }
192 /*---------------------------------------------------------------------------*/
193 static int
194 parent_has_usable_link(rpl_parent_t *p)
195 {
196  uint16_t link_metric = parent_link_metric(p);
197  /* Exclude links with too high link metrics */
198  return link_metric <= MAX_LINK_METRIC;
199 }
200 /*---------------------------------------------------------------------------*/
201 static rpl_parent_t *
202 best_parent(rpl_parent_t *p1, rpl_parent_t *p2)
203 {
204  rpl_dag_t *dag;
205  uint16_t p1_cost;
206  uint16_t p2_cost;
207  int p1_is_acceptable;
208  int p2_is_acceptable;
209 
210  p1_is_acceptable = p1 != NULL && parent_is_acceptable(p1);
211  p2_is_acceptable = p2 != NULL && parent_is_acceptable(p2);
212 
213  if(!p1_is_acceptable) {
214  return p2_is_acceptable ? p2 : NULL;
215  }
216  if(!p2_is_acceptable) {
217  return p1_is_acceptable ? p1 : NULL;
218  }
219 
220  dag = p1->dag; /* Both parents are in the same DAG. */
221  p1_cost = parent_path_cost(p1);
222  p2_cost = parent_path_cost(p2);
223 
224  /* Maintain stability of the preferred parent in case of similar ranks. */
225  if(p1 == dag->preferred_parent || p2 == dag->preferred_parent) {
226  if(p1_cost < p2_cost + PARENT_SWITCH_THRESHOLD &&
227  p1_cost > p2_cost - PARENT_SWITCH_THRESHOLD) {
228  return dag->preferred_parent;
229  }
230  }
231 
232  return p1_cost < p2_cost ? p1 : p2;
233 }
234 /*---------------------------------------------------------------------------*/
235 static rpl_dag_t *
236 best_dag(rpl_dag_t *d1, rpl_dag_t *d2)
237 {
238  if(d1->grounded != d2->grounded) {
239  return d1->grounded ? d1 : d2;
240  }
241 
242  if(d1->preference != d2->preference) {
243  return d1->preference > d2->preference ? d1 : d2;
244  }
245 
246  return d1->rank < d2->rank ? d1 : d2;
247 }
248 /*---------------------------------------------------------------------------*/
249 #if !RPL_WITH_MC
250 static void
251 update_metric_container(rpl_instance_t *instance)
252 {
253  instance->mc.type = RPL_DAG_MC_NONE;
254 }
255 #else /* RPL_WITH_MC */
256 static void
257 update_metric_container(rpl_instance_t *instance)
258 {
259  rpl_dag_t *dag;
260  uint16_t path_cost;
261  uint8_t type;
262 
263  dag = instance->current_dag;
264  if(dag == NULL || !dag->joined) {
265  PRINTF("RPL: Cannot update the metric container when not joined\n");
266  return;
267  }
268 
269  if(dag->rank == ROOT_RANK(instance)) {
270  /* Configure MC at root only, other nodes are auto-configured when joining */
271  instance->mc.type = RPL_DAG_MC;
272  instance->mc.flags = 0;
273  instance->mc.aggr = RPL_DAG_MC_AGGR_ADDITIVE;
274  instance->mc.prec = 0;
275  path_cost = dag->rank;
276  } else {
277  path_cost = parent_path_cost(dag->preferred_parent);
278  }
279 
280  /* Handle the different MC types */
281  switch(instance->mc.type) {
282  case RPL_DAG_MC_NONE:
283  break;
284  case RPL_DAG_MC_ETX:
285  instance->mc.length = sizeof(instance->mc.obj.etx);
286  instance->mc.obj.etx = path_cost;
287  break;
288  case RPL_DAG_MC_ENERGY:
289  instance->mc.length = sizeof(instance->mc.obj.energy);
290  if(dag->rank == ROOT_RANK(instance)) {
291  type = RPL_DAG_MC_ENERGY_TYPE_MAINS;
292  } else {
293  type = RPL_DAG_MC_ENERGY_TYPE_BATTERY;
294  }
295  instance->mc.obj.energy.flags = type << RPL_DAG_MC_ENERGY_TYPE;
296  /* Energy_est is only one byte, use the least significant byte of the path metric. */
297  instance->mc.obj.energy.energy_est = path_cost >> 8;
298  break;
299  default:
300  PRINTF("RPL: MRHOF, non-supported MC %u\n", instance->mc.type);
301  break;
302  }
303 }
304 #endif /* RPL_WITH_MC */
305 /*---------------------------------------------------------------------------*/
306 rpl_of_t rpl_mrhof = {
307  reset,
308 #if RPL_WITH_DAO_ACK
309  dao_ack_callback,
310 #endif
311  parent_link_metric,
312  parent_has_usable_link,
313  parent_path_cost,
314  rank_via_parent,
315  best_parent,
316  best_dag,
317  update_metric_container,
318  RPL_OCP_MRHOF
319 };
320 
321 /** @}*/
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
A set of debugging macros for the IP stack
The MAC layer transmission was OK.
Definition: mac.h:84
API for RPL objective functions (OF)
Definition: rpl.h:201