Contiki-NG
rpl-timers.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  * \file
34  * RPL timer management.
35  *
36  * \author Joakim Eriksson <joakime@sics.se>, Nicolas Tsiftes <nvt@sics.se>
37  */
38 
39 /**
40  * \addtogroup uip
41  * @{
42  */
43 
44 #include "contiki.h"
45 #include "net/routing/rpl-classic/rpl-private.h"
46 #include "net/link-stats.h"
48 #include "net/ipv6/uip-sr.h"
49 #include "lib/random.h"
50 #include "sys/ctimer.h"
51 
52 #define DEBUG DEBUG_NONE
53 #include "net/ipv6/uip-debug.h"
54 
55 /* A configurable function called after update of the RPL DIO interval */
56 #ifdef RPL_CALLBACK_NEW_DIO_INTERVAL
57 void RPL_CALLBACK_NEW_DIO_INTERVAL(clock_time_t dio_interval);
58 #endif /* RPL_CALLBACK_NEW_DIO_INTERVAL */
59 
60 #ifdef RPL_PROBING_SELECT_FUNC
61 rpl_parent_t *RPL_PROBING_SELECT_FUNC(rpl_dag_t *dag);
62 #endif /* RPL_PROBING_SELECT_FUNC */
63 
64 #ifdef RPL_PROBING_DELAY_FUNC
65 clock_time_t RPL_PROBING_DELAY_FUNC(rpl_dag_t *dag);
66 #endif /* RPL_PROBING_DELAY_FUNC */
67 
68 /*---------------------------------------------------------------------------*/
69 static struct ctimer periodic_timer;
70 
71 static void handle_periodic_timer(void *ptr);
72 static void new_dio_interval(rpl_instance_t *instance);
73 static void handle_dio_timer(void *ptr);
74 
75 static uint16_t next_dis;
76 
77 /* dio_send_ok is true if the node is ready to send DIOs */
78 static uint8_t dio_send_ok;
79 
80 /*---------------------------------------------------------------------------*/
81 static void
82 handle_periodic_timer(void *ptr)
83 {
84  rpl_dag_t *dag = rpl_get_any_dag();
85 
86  rpl_purge_dags();
87  if(dag != NULL) {
88  if(RPL_IS_STORING(dag->instance)) {
89  rpl_purge_routes();
90  }
91  if(RPL_IS_NON_STORING(dag->instance)) {
92  uip_sr_periodic(1);
93  }
94  }
95  rpl_recalculate_ranks();
96 
97  /* handle DIS */
98 #if RPL_DIS_SEND
99  next_dis++;
100  if(dag == NULL && next_dis >= RPL_DIS_INTERVAL) {
101  next_dis = 0;
102  dis_output(NULL);
103  }
104 #endif
105  ctimer_reset(&periodic_timer);
106 }
107 /*---------------------------------------------------------------------------*/
108 static void
109 new_dio_interval(rpl_instance_t *instance)
110 {
111  uint32_t time;
112  clock_time_t ticks;
113 
114  /* TODO: too small timer intervals for many cases */
115  time = 1UL << instance->dio_intcurrent;
116 
117  /* Convert from milliseconds to CLOCK_TICKS. */
118  ticks = (time * CLOCK_SECOND) / 1000;
119  instance->dio_next_delay = ticks;
120 
121  /* random number between I/2 and I */
122  ticks = ticks / 2 + (ticks / 2 * (uint32_t)random_rand()) / RANDOM_RAND_MAX;
123 
124  /*
125  * The intervals must be equally long among the nodes for Trickle to
126  * operate efficiently. Therefore we need to calculate the delay between
127  * the randomized time and the start time of the next interval.
128  */
129  instance->dio_next_delay -= ticks;
130  instance->dio_send = 1;
131 
132 #if RPL_CONF_STATS
133  /* keep some stats */
134  instance->dio_totint++;
135  instance->dio_totrecv += instance->dio_counter;
136  ANNOTATE("#A rank=%u.%u(%u),stats=%d %d %d %d,color=%s\n",
137  DAG_RANK(instance->current_dag->rank, instance),
138  (10 * (instance->current_dag->rank % instance->min_hoprankinc)) / instance->min_hoprankinc,
139  instance->current_dag->version,
140  instance->dio_totint, instance->dio_totsend,
141  instance->dio_totrecv,instance->dio_intcurrent,
142  instance->current_dag->rank == ROOT_RANK(instance) ? "BLUE" : "ORANGE");
143 #endif /* RPL_CONF_STATS */
144 
145  /* reset the redundancy counter */
146  instance->dio_counter = 0;
147 
148  /* schedule the timer */
149  PRINTF("RPL: Scheduling DIO timer %lu ticks in future (Interval)\n", ticks);
150  ctimer_set(&instance->dio_timer, ticks, &handle_dio_timer, instance);
151 
152 #ifdef RPL_CALLBACK_NEW_DIO_INTERVAL
153  RPL_CALLBACK_NEW_DIO_INTERVAL((CLOCK_SECOND * 1UL << instance->dio_intcurrent) / 1000);
154 #endif /* RPL_CALLBACK_NEW_DIO_INTERVAL */
155 }
156 /*---------------------------------------------------------------------------*/
157 static void
158 handle_dio_timer(void *ptr)
159 {
160  rpl_instance_t *instance;
161 
162  instance = (rpl_instance_t *)ptr;
163 
164  PRINTF("RPL: DIO Timer triggered\n");
165  if(!dio_send_ok) {
166  if(uip_ds6_get_link_local(ADDR_PREFERRED) != NULL) {
167  dio_send_ok = 1;
168  } else {
169  PRINTF("RPL: Postponing DIO transmission since link local address is not ok\n");
170  ctimer_set(&instance->dio_timer, CLOCK_SECOND, &handle_dio_timer, instance);
171  return;
172  }
173  }
174 
175  if(instance->dio_send) {
176  /* send DIO if counter is less than desired redundancy */
177  if(instance->dio_redundancy == 0 || instance->dio_counter < instance->dio_redundancy) {
178 #if RPL_CONF_STATS
179  instance->dio_totsend++;
180 #endif /* RPL_CONF_STATS */
181  dio_output(instance, NULL);
182  } else {
183  PRINTF("RPL: Suppressing DIO transmission (%d >= %d)\n",
184  instance->dio_counter, instance->dio_redundancy);
185  }
186  instance->dio_send = 0;
187  PRINTF("RPL: Scheduling DIO timer %lu ticks in future (sent)\n",
188  instance->dio_next_delay);
189  ctimer_set(&instance->dio_timer, instance->dio_next_delay, handle_dio_timer, instance);
190  } else {
191  /* check if we need to double interval */
192  if(instance->dio_intcurrent < instance->dio_intmin + instance->dio_intdoubl) {
193  instance->dio_intcurrent++;
194  PRINTF("RPL: DIO Timer interval doubled %d\n", instance->dio_intcurrent);
195  }
196  new_dio_interval(instance);
197  }
198 
199 #if DEBUG
200  rpl_print_neighbor_list();
201 #endif
202 }
203 /*---------------------------------------------------------------------------*/
204 void
205 rpl_reset_periodic_timer(void)
206 {
207  next_dis = RPL_DIS_INTERVAL / 2 +
208  ((uint32_t)RPL_DIS_INTERVAL * (uint32_t)random_rand()) / RANDOM_RAND_MAX -
209  RPL_DIS_START_DELAY;
210  ctimer_set(&periodic_timer, CLOCK_SECOND, handle_periodic_timer, NULL);
211 }
212 /*---------------------------------------------------------------------------*/
213 /* Resets the DIO timer in the instance to its minimal interval. */
214 void
215 rpl_reset_dio_timer(rpl_instance_t *instance)
216 {
217 #if !RPL_LEAF_ONLY
218  /* Do not reset if we are already on the minimum interval,
219  unless forced to do so. */
220  if(instance->dio_intcurrent > instance->dio_intmin) {
221  instance->dio_counter = 0;
222  instance->dio_intcurrent = instance->dio_intmin;
223  new_dio_interval(instance);
224  }
225 #if RPL_CONF_STATS
226  rpl_stats.resets++;
227 #endif /* RPL_CONF_STATS */
228 #endif /* RPL_LEAF_ONLY */
229 }
230 /*---------------------------------------------------------------------------*/
231 static void handle_dao_timer(void *ptr);
232 static void
233 set_dao_lifetime_timer(rpl_instance_t *instance)
234 {
235  if(rpl_get_mode() == RPL_MODE_FEATHER) {
236  return;
237  }
238 
239  /* Set up another DAO within half the expiration time, if such a
240  time has been configured */
241  if(instance->default_lifetime != RPL_INFINITE_LIFETIME) {
242  clock_time_t expiration_time;
243  expiration_time = (clock_time_t)instance->default_lifetime *
244  (clock_time_t)instance->lifetime_unit *
245  CLOCK_SECOND / 2;
246  /* make the time for the re registration be betwen 1/2 - 3/4 of lifetime */
247  expiration_time = expiration_time + (random_rand() % (expiration_time / 2));
248  PRINTF("RPL: Scheduling DAO lifetime timer %u ticks in the future\n",
249  (unsigned)expiration_time);
250  ctimer_set(&instance->dao_lifetime_timer, expiration_time,
251  handle_dao_timer, instance);
252  }
253 }
254 /*---------------------------------------------------------------------------*/
255 static void
256 handle_dao_timer(void *ptr)
257 {
258  rpl_instance_t *instance;
259 #if RPL_WITH_MULTICAST
260  uip_mcast6_route_t *mcast_route;
261  uint8_t i;
262 #endif
263 
264  instance = (rpl_instance_t *)ptr;
265 
266  if(!dio_send_ok && uip_ds6_get_link_local(ADDR_PREFERRED) == NULL) {
267  PRINTF("RPL: Postpone DAO transmission\n");
268  ctimer_set(&instance->dao_timer, CLOCK_SECOND, handle_dao_timer, instance);
269  return;
270  }
271 
272  /* Send the DAO to the DAO parent set -- the preferred parent in our case. */
273  if(instance->current_dag->preferred_parent != NULL) {
274  PRINTF("RPL: handle_dao_timer - sending DAO\n");
275  /* Set the route lifetime to the default value. */
276  dao_output(instance->current_dag->preferred_parent, instance->default_lifetime);
277 
278 #if RPL_WITH_MULTICAST
279  /* Send DAOs for multicast prefixes only if the instance is in MOP 3 */
280  if(instance->mop == RPL_MOP_STORING_MULTICAST) {
281  /* Send a DAO for own multicast addresses */
282  for(i = 0; i < UIP_DS6_MADDR_NB; i++) {
283  if(uip_ds6_if.maddr_list[i].isused
284  && uip_is_addr_mcast_global(&uip_ds6_if.maddr_list[i].ipaddr)) {
285  dao_output_target(instance->current_dag->preferred_parent,
286  &uip_ds6_if.maddr_list[i].ipaddr, instance->default_lifetime);
287  }
288  }
289 
290  /* Iterate over multicast routes and send DAOs */
291  mcast_route = uip_mcast6_route_list_head();
292  while(mcast_route != NULL) {
293  /* Don't send if it's also our own address, done that already */
294  if(uip_ds6_maddr_lookup(&mcast_route->group) == NULL) {
295  dao_output_target(instance->current_dag->preferred_parent,
296  &mcast_route->group, instance->default_lifetime);
297  }
298  mcast_route = list_item_next(mcast_route);
299  }
300  }
301 #endif
302  } else {
303  PRINTF("RPL: No suitable DAO parent\n");
304  }
305 
306  ctimer_stop(&instance->dao_timer);
307 
308  if(etimer_expired(&instance->dao_lifetime_timer.etimer)) {
309  set_dao_lifetime_timer(instance);
310  }
311 }
312 /*---------------------------------------------------------------------------*/
313 static void
314 schedule_dao(rpl_instance_t *instance, clock_time_t latency)
315 {
316  clock_time_t expiration_time;
317 
318  if(rpl_get_mode() == RPL_MODE_FEATHER) {
319  return;
320  }
321 
322  expiration_time = etimer_expiration_time(&instance->dao_timer.etimer);
323 
324  if(!etimer_expired(&instance->dao_timer.etimer)) {
325  PRINTF("RPL: DAO timer already scheduled\n");
326  } else {
327  if(latency != 0) {
328  expiration_time = latency / 2 +
329  (random_rand() % (latency));
330  } else {
331  expiration_time = 0;
332  }
333  PRINTF("RPL: Scheduling DAO timer %u ticks in the future\n",
334  (unsigned)expiration_time);
335  ctimer_set(&instance->dao_timer, expiration_time,
336  handle_dao_timer, instance);
337 
338  set_dao_lifetime_timer(instance);
339  }
340 }
341 /*---------------------------------------------------------------------------*/
342 void
343 rpl_schedule_dao(rpl_instance_t *instance)
344 {
345  schedule_dao(instance, RPL_DAO_DELAY);
346 }
347 /*---------------------------------------------------------------------------*/
348 void
349 rpl_schedule_dao_immediately(rpl_instance_t *instance)
350 {
351  schedule_dao(instance, 0);
352 }
353 /*---------------------------------------------------------------------------*/
354 void
355 rpl_cancel_dao(rpl_instance_t *instance)
356 {
357  ctimer_stop(&instance->dao_timer);
358  ctimer_stop(&instance->dao_lifetime_timer);
359 }
360 /*---------------------------------------------------------------------------*/
361 static void
362 handle_unicast_dio_timer(void *ptr)
363 {
364  rpl_instance_t *instance = (rpl_instance_t *)ptr;
365  uip_ipaddr_t *target_ipaddr = rpl_parent_get_ipaddr(instance->unicast_dio_target);
366 
367  if(target_ipaddr != NULL) {
368  dio_output(instance, target_ipaddr);
369  }
370 }
371 /*---------------------------------------------------------------------------*/
372 void
373 rpl_schedule_unicast_dio_immediately(rpl_instance_t *instance)
374 {
375  ctimer_set(&instance->unicast_dio_timer, 0,
376  handle_unicast_dio_timer, instance);
377 }
378 /*---------------------------------------------------------------------------*/
379 #if RPL_WITH_PROBING
380 clock_time_t
381 get_probing_delay(rpl_dag_t *dag)
382 {
383  return ((RPL_PROBING_INTERVAL) / 2) + random_rand() % (RPL_PROBING_INTERVAL);
384 }
385 /*---------------------------------------------------------------------------*/
386 rpl_parent_t *
387 get_probing_target(rpl_dag_t *dag)
388 {
389  /* Returns the next probing target. The current implementation probes the urgent
390  * probing target if any, or the preferred parent if its link statistics need refresh.
391  * Otherwise, it picks at random between:
392  * (1) selecting the best parent with non-fresh link statistics
393  * (2) selecting the least recently updated parent
394  */
395 
396  rpl_parent_t *p;
397  rpl_parent_t *probing_target = NULL;
398  rpl_rank_t probing_target_rank = RPL_INFINITE_RANK;
399  clock_time_t probing_target_age = 0;
400  clock_time_t clock_now = clock_time();
401 
402  if(dag == NULL ||
403  dag->instance == NULL) {
404  return NULL;
405  }
406 
407  /* There is an urgent probing target */
408  if(dag->instance->urgent_probing_target != NULL) {
409  return dag->instance->urgent_probing_target;
410  }
411 
412  /* The preferred parent needs probing */
413  if(dag->preferred_parent != NULL && !rpl_parent_is_fresh(dag->preferred_parent)) {
414  return dag->preferred_parent;
415  }
416 
417  /* With 50% probability: probe best non-fresh parent */
418  if(random_rand() % 2 == 0) {
419  p = nbr_table_head(rpl_parents);
420  while(p != NULL) {
421  if(p->dag == dag && !rpl_parent_is_fresh(p)) {
422  /* p is in our dag and needs probing */
423  rpl_rank_t p_rank = rpl_rank_via_parent(p);
424  if(probing_target == NULL
425  || p_rank < probing_target_rank) {
426  probing_target = p;
427  probing_target_rank = p_rank;
428  }
429  }
430  p = nbr_table_next(rpl_parents, p);
431  }
432  }
433 
434  /* If we still do not have a probing target: pick the least recently updated parent */
435  if(probing_target == NULL) {
436  p = nbr_table_head(rpl_parents);
437  while(p != NULL) {
438  const struct link_stats *stats =rpl_get_parent_link_stats(p);
439  if(p->dag == dag && stats != NULL) {
440  if(probing_target == NULL
441  || clock_now - stats->last_tx_time > probing_target_age) {
442  probing_target = p;
443  probing_target_age = clock_now - stats->last_tx_time;
444  }
445  }
446  p = nbr_table_next(rpl_parents, p);
447  }
448  }
449 
450  return probing_target;
451 }
452 /*---------------------------------------------------------------------------*/
453 static rpl_dag_t *
454 get_next_dag(rpl_instance_t *instance)
455 {
456  rpl_dag_t *dag = NULL;
457  int new_dag = instance->last_dag;
458  do {
459  new_dag++;
460  if(new_dag >= RPL_MAX_DAG_PER_INSTANCE) {
461  new_dag = 0;
462  }
463  if(instance->dag_table[new_dag].used) {
464  dag = &instance->dag_table[new_dag];
465  }
466  } while(new_dag != instance->last_dag && dag == NULL);
467  instance->last_dag = new_dag;
468  return dag;
469 }
470 /*---------------------------------------------------------------------------*/
471 static void
472 handle_probing_timer(void *ptr)
473 {
474  rpl_instance_t *instance = (rpl_instance_t *)ptr;
475  rpl_parent_t *probing_target = RPL_PROBING_SELECT_FUNC(get_next_dag(instance));
476  uip_ipaddr_t *target_ipaddr = rpl_parent_get_ipaddr(probing_target);
477 
478  /* Perform probing */
479  if(target_ipaddr != NULL) {
480  const struct link_stats *stats = rpl_get_parent_link_stats(probing_target);
481  (void)stats;
482  PRINTF("RPL: probing %u %s last tx %u min ago\n",
483  rpl_get_parent_lladdr(probing_target)->u8[7],
484  instance->urgent_probing_target != NULL ? "(urgent)" : "",
485  probing_target != NULL ?
486  (unsigned)((clock_time() - stats->last_tx_time) / (60 * CLOCK_SECOND)) : 0
487  );
488  /* Send probe, e.g. unicast DIO or DIS */
489  RPL_PROBING_SEND_FUNC(instance, target_ipaddr);
490  }
491 
492  /* Schedule next probing */
493  rpl_schedule_probing(instance);
494 
495 #if DEBUG
496  rpl_print_neighbor_list();
497 #endif
498 }
499 /*---------------------------------------------------------------------------*/
500 void
502 {
503  ctimer_set(&instance->probing_timer, RPL_PROBING_DELAY_FUNC(instance->current_dag),
504  handle_probing_timer, instance);
505 }
506 /*---------------------------------------------------------------------------*/
507 void
509 {
510  ctimer_set(&instance->probing_timer, random_rand() % (CLOCK_SECOND * 4),
511  handle_probing_timer, instance);
512 }
513 #endif /* RPL_WITH_PROBING */
514 /** @}*/
void ctimer_stop(struct ctimer *c)
Stop a pending callback timer.
Definition: ctimer.c:149
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
#define uip_is_addr_mcast_global(a)
is address a global multicast address (FFxE::/16), a is of type uip_ip6addr_t*
Definition: uip.h:2114
void rpl_schedule_probing_now(void)
Schedule probing within a few seconds.
enum rpl_mode rpl_get_mode(void)
Get the RPL mode.
Definition: rpl.c:68
A set of debugging macros for the IP stack
void ctimer_reset(struct ctimer *c)
Reset a callback timer with the same interval as was previously set.
Definition: ctimer.c:125
Source routing support.
This header file contains configuration directives for uIPv6 multicast support.
#define CLOCK_SECOND
A second, measured in system clock time.
Definition: clock.h:82
#define DAG_RANK(fixpt_rank)
Return DAG RANK as per RFC 6550 (rank divided by min_hoprankinc)
Definition: rpl-types.h:81
Header file for the callback timer
void uip_sr_periodic(unsigned seconds)
A function called periodically.
Definition: uip-sr.c:206
void ctimer_set(struct ctimer *c, clock_time_t t, void(*f)(void *), void *ptr)
Set a callback timer.
Definition: ctimer.c:99
rpl_dag_t * rpl_get_any_dag(void)
Returns pointer to any DAG (for compatibility with legagy RPL code)
Definition: rpl-dag.c:1051
clock_time_t clock_time(void)
Get the current clock time.
Definition: clock.c:118
int etimer_expired(struct etimer *et)
Check if an event timer has expired.
Definition: etimer.c:213
An entry in the multicast routing table.
uip_ds6_netif_t uip_ds6_if
The single interface.
Definition: uip-ds6.c:75
unsigned short random_rand(void)
Generates a new random number using the cc2538 RNG.
Definition: random.c:58
uip_ipaddr_t group
The multicast group.
void * list_item_next(void *item)
Get the next item following this item.
Definition: list.c:322
uip_mcast6_route_t * uip_mcast6_route_list_head(void)
Retrieve a pointer to the start of the multicast routes list.
void rpl_schedule_probing(void)
Schedule probing with delay RPL_PROBING_DELAY_FUNC()
clock_time_t etimer_expiration_time(struct etimer *et)
Get the expiration time for the event timer.
Definition: etimer.c:219