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
30/**
31 * \file
32 * RPL timer management.
33 *
34 * \author Joakim Eriksson <joakime@sics.se>, Nicolas Tsiftes <nvt@sics.se>
35 */
36
37/**
38 * \addtogroup uip
39 * @{
40 */
41
42#include "contiki.h"
43#include "net/routing/rpl-classic/rpl-private.h"
44#include "net/link-stats.h"
46#include "net/ipv6/uip-sr.h"
47#include "lib/random.h"
48#include "sys/ctimer.h"
49#include "sys/log.h"
50
51#define LOG_MODULE "RPL"
52#define LOG_LEVEL LOG_LEVEL_RPL
53
54/* A configurable function called after update of the RPL DIO interval. */
55#ifdef RPL_CALLBACK_NEW_DIO_INTERVAL
56void RPL_CALLBACK_NEW_DIO_INTERVAL(clock_time_t dio_interval);
57#endif /* RPL_CALLBACK_NEW_DIO_INTERVAL */
58
59#ifdef RPL_PROBING_SELECT_FUNC
60rpl_parent_t *RPL_PROBING_SELECT_FUNC(rpl_dag_t *dag);
61#endif /* RPL_PROBING_SELECT_FUNC */
62
63#ifdef RPL_PROBING_DELAY_FUNC
64clock_time_t RPL_PROBING_DELAY_FUNC(rpl_dag_t *dag);
65#endif /* RPL_PROBING_DELAY_FUNC */
66
67/*---------------------------------------------------------------------------*/
68static struct ctimer periodic_timer;
69
70static void handle_periodic_timer(void *ptr);
71static void new_dio_interval(rpl_instance_t *instance);
72static void handle_dio_timer(void *ptr);
73
74static uint16_t next_dis;
75
76/* dio_send_ok is true if the node is ready to send DIOs. */
77static uint8_t dio_send_ok;
78
79/*---------------------------------------------------------------------------*/
80static void
81handle_periodic_timer(void *ptr)
82{
84
85 rpl_purge_dags();
86 if(dag != NULL) {
87 if(RPL_IS_STORING(dag->instance)) {
88 rpl_purge_routes();
89 }
90 if(RPL_IS_NON_STORING(dag->instance)) {
92 }
93 }
94 rpl_recalculate_ranks();
95
96 /* Handle DIS. */
97#if RPL_DIS_SEND
98 next_dis++;
99 if((dag == NULL || dag->instance->current_dag->rank == RPL_INFINITE_RANK)
100 && next_dis >= RPL_DIS_INTERVAL) {
101 next_dis = 0;
102 dis_output(NULL);
103 }
104#endif
105 ctimer_reset(&periodic_timer);
106}
107/*---------------------------------------------------------------------------*/
108static void
109new_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 LOG_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 LOG_INFO("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/*---------------------------------------------------------------------------*/
157static void
158handle_dio_timer(void *ptr)
159{
160 rpl_instance_t *instance = (rpl_instance_t *)ptr;
161
162 LOG_DBG("DIO Timer triggered\n");
163 if(!dio_send_ok) {
164 if(uip_ds6_get_link_local(ADDR_PREFERRED) != NULL) {
165 dio_send_ok = 1;
166 } else {
167 LOG_WARN("Postponing DIO transmission since link local address is not ok\n");
168 ctimer_set(&instance->dio_timer, CLOCK_SECOND, &handle_dio_timer, instance);
169 return;
170 }
171 }
172
173 if(instance->dio_send) {
174 /* Send DIO if counter is less than desired redundancy. */
175 if(instance->dio_redundancy == 0 || instance->dio_counter < instance->dio_redundancy) {
176#if RPL_CONF_STATS
177 instance->dio_totsend++;
178#endif /* RPL_CONF_STATS */
179 dio_output(instance, NULL);
180 } else {
181 LOG_DBG("Suppressing DIO transmission (%d >= %d)\n",
182 instance->dio_counter, instance->dio_redundancy);
183 }
184 instance->dio_send = 0;
185 LOG_DBG("Scheduling DIO timer %lu ticks in future (sent)\n",
186 instance->dio_next_delay);
187 ctimer_set(&instance->dio_timer, instance->dio_next_delay,
188 handle_dio_timer, instance);
189 } else {
190 /* Check if we need to double interval. */
191 if(instance->dio_intcurrent <
192 instance->dio_intmin + instance->dio_intdoubl) {
193 instance->dio_intcurrent++;
194 LOG_DBG("DIO Timer interval doubled %d\n", instance->dio_intcurrent);
195 }
196 new_dio_interval(instance);
197 }
198
199 if(LOG_DBG_ENABLED) {
200 rpl_print_neighbor_list();
201 }
202}
203/*---------------------------------------------------------------------------*/
204void
205rpl_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. */
214void
215rpl_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/*---------------------------------------------------------------------------*/
231static void handle_dao_timer(void *ptr);
232static void
233set_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
244 /*
245 * If the lifetime is 0, we simply set the expiration time to
246 * half a second to get an interval that corresponds to a
247 * lifetime of 1 and a lifetime unit of 1.
248 */
249 if(instance->default_lifetime == 0 || instance->lifetime_unit == 0) {
250 expiration_time = CLOCK_SECOND / 2;
251 } else {
252 expiration_time = (clock_time_t)instance->default_lifetime *
253 (clock_time_t)instance->lifetime_unit * CLOCK_SECOND / 2;
254 }
255
256 /* Make the time for the re-registration to be between 1/2 and 3/4 of
257 the lifetime. */
258 expiration_time = expiration_time + (random_rand() % (expiration_time / 2));
259 LOG_DBG("Scheduling DAO lifetime timer %u ticks in the future\n",
260 (unsigned)expiration_time);
261 ctimer_set(&instance->dao_lifetime_timer, expiration_time,
262 handle_dao_timer, instance);
263 }
264}
265/*---------------------------------------------------------------------------*/
266static void
267handle_dao_timer(void *ptr)
268{
269 rpl_instance_t *instance = (rpl_instance_t *)ptr;
270
271#if RPL_WITH_MULTICAST
272 uip_mcast6_route_t *mcast_route;
273 uint8_t i;
274#endif
275
276 if(!dio_send_ok && uip_ds6_get_link_local(ADDR_PREFERRED) == NULL) {
277 LOG_INFO("Postpone DAO transmission\n");
278 ctimer_set(&instance->dao_timer, CLOCK_SECOND, handle_dao_timer, instance);
279 return;
280 }
281
282 /* Send the DAO to the DAO parent set -- the preferred parent in our case. */
283 if(instance->current_dag->preferred_parent != NULL) {
284 LOG_INFO("handle_dao_timer - sending DAO\n");
285 /* Set the route lifetime to the default value. */
286 dao_output(instance->current_dag->preferred_parent,
287 instance->default_lifetime);
288
289#if RPL_WITH_MULTICAST
290 /* Send DAOs for multicast prefixes only if the instance is in MOP 3. */
291 if(instance->mop == RPL_MOP_STORING_MULTICAST) {
292 /* Send a DAO for own multicast addresses. */
293 for(i = 0; i < UIP_DS6_MADDR_NB; i++) {
294 if(uip_ds6_if.maddr_list[i].isused
295 && uip_is_addr_mcast_global(&uip_ds6_if.maddr_list[i].ipaddr)) {
296 dao_output_target(instance->current_dag->preferred_parent,
297 &uip_ds6_if.maddr_list[i].ipaddr, instance->default_lifetime);
298 }
299 }
300
301 /* Iterate over multicast routes and send DAOs */
302 mcast_route = uip_mcast6_route_list_head();
303 while(mcast_route != NULL) {
304 /* Don't send if it's also our own address, done that already. */
305 if(uip_ds6_maddr_lookup(&mcast_route->group) == NULL) {
306 dao_output_target(instance->current_dag->preferred_parent,
307 &mcast_route->group, instance->default_lifetime);
308 }
309 mcast_route = list_item_next(mcast_route);
310 }
311 }
312#endif
313 } else {
314 LOG_INFO("No suitable DAO parent\n");
315 }
316
317 ctimer_stop(&instance->dao_timer);
318
319 if(etimer_expired(&instance->dao_lifetime_timer.etimer)) {
320 set_dao_lifetime_timer(instance);
321 }
322}
323/*---------------------------------------------------------------------------*/
324static void
325schedule_dao(rpl_instance_t *instance, clock_time_t latency)
326{
327 clock_time_t expiration_time;
328
329 if(rpl_get_mode() == RPL_MODE_FEATHER) {
330 return;
331 }
332
333 expiration_time = etimer_expiration_time(&instance->dao_timer.etimer);
334
335 if(!etimer_expired(&instance->dao_timer.etimer)) {
336 LOG_DBG("DAO timer already scheduled\n");
337 } else {
338 if(latency != 0) {
339 expiration_time = latency / 2 +
340 (random_rand() % (latency));
341 } else {
342 expiration_time = 0;
343 }
344 LOG_DBG("Scheduling DAO timer %u ticks in the future\n",
345 (unsigned)expiration_time);
346 ctimer_set(&instance->dao_timer, expiration_time,
347 handle_dao_timer, instance);
348
349 set_dao_lifetime_timer(instance);
350 }
351}
352/*---------------------------------------------------------------------------*/
353void
354rpl_schedule_dao(rpl_instance_t *instance)
355{
356 schedule_dao(instance, RPL_DAO_DELAY);
357}
358/*---------------------------------------------------------------------------*/
359void
360rpl_schedule_dao_immediately(rpl_instance_t *instance)
361{
362 schedule_dao(instance, 0);
363}
364/*---------------------------------------------------------------------------*/
365void
366rpl_cancel_dao(rpl_instance_t *instance)
367{
368 ctimer_stop(&instance->dao_timer);
369 ctimer_stop(&instance->dao_lifetime_timer);
370}
371/*---------------------------------------------------------------------------*/
372static void
373handle_unicast_dio_timer(void *ptr)
374{
375 rpl_instance_t *instance = (rpl_instance_t *)ptr;
376 uip_ipaddr_t *target_ipaddr = rpl_parent_get_ipaddr(instance->unicast_dio_target);
377
378 if(target_ipaddr != NULL) {
379 dio_output(instance, target_ipaddr);
380 }
381}
382/*---------------------------------------------------------------------------*/
383void
384rpl_schedule_unicast_dio_immediately(rpl_instance_t *instance)
385{
386 ctimer_set(&instance->unicast_dio_timer, 0,
387 handle_unicast_dio_timer, instance);
388}
389/*---------------------------------------------------------------------------*/
390#if RPL_WITH_PROBING
391clock_time_t
392get_probing_delay(rpl_dag_t *dag)
393{
394 return ((RPL_PROBING_INTERVAL) / 2) + random_rand() % (RPL_PROBING_INTERVAL);
395}
396/*---------------------------------------------------------------------------*/
397rpl_parent_t *
398get_probing_target(rpl_dag_t *dag)
399{
400 /*
401 * Returns the next probing target. The current implementation
402 * probes the urgent probing target if any, or the preferred parent
403 * if its link statistics need refresh.
404 *
405 * Otherwise, it picks at random between:
406 * (1) selecting the best parent with non-fresh link statistics.
407 * (2) selecting the least recently updated parent.
408 */
409
410 rpl_parent_t *p;
411 rpl_parent_t *probing_target = NULL;
412 rpl_rank_t probing_target_rank = RPL_INFINITE_RANK;
413 clock_time_t probing_target_age = 0;
414 clock_time_t clock_now = clock_time();
415
416 if(dag == NULL || dag->instance == NULL) {
417 return NULL;
418 }
419
420 /* There is an urgent probing target. */
421 if(dag->instance->urgent_probing_target != NULL) {
422 return dag->instance->urgent_probing_target;
423 }
424
425 /* The preferred parent needs probing. */
426 if(dag->preferred_parent != NULL
427 && !rpl_parent_is_fresh(dag->preferred_parent)) {
428 return dag->preferred_parent;
429 }
430
431 /* With 50% probability: probe best non-fresh parent. */
432 if(random_rand() % 2 == 0) {
433 p = nbr_table_head(rpl_parents);
434 while(p != NULL) {
435 if(p->dag == dag && !rpl_parent_is_fresh(p)) {
436 /* p is in our DAG and needs probing. */
437 rpl_rank_t p_rank = rpl_rank_via_parent(p);
438 if(probing_target == NULL || p_rank < probing_target_rank) {
439 probing_target = p;
440 probing_target_rank = p_rank;
441 }
442 }
443 p = nbr_table_next(rpl_parents, p);
444 }
445 }
446
447 /* If we still do not have a probing target:
448 pick the least recently updated parent. */
449 if(probing_target == NULL) {
450 p = nbr_table_head(rpl_parents);
451 while(p != NULL) {
452 const struct link_stats *stats = rpl_get_parent_link_stats(p);
453 if(p->dag == dag && stats != NULL) {
454 if(probing_target == NULL
455 || clock_now - stats->last_tx_time > probing_target_age) {
456 probing_target = p;
457 probing_target_age = clock_now - stats->last_tx_time;
458 }
459 }
460 p = nbr_table_next(rpl_parents, p);
461 }
462 }
463
464 return probing_target;
465}
466/*---------------------------------------------------------------------------*/
467static rpl_dag_t *
468get_next_dag(rpl_instance_t *instance)
469{
470 rpl_dag_t *dag = NULL;
471 int new_dag = instance->last_dag;
472
473 do {
474 new_dag++;
475 if(new_dag >= RPL_MAX_DAG_PER_INSTANCE) {
476 new_dag = 0;
477 }
478 if(instance->dag_table[new_dag].used) {
479 dag = &instance->dag_table[new_dag];
480 }
481 } while(new_dag != instance->last_dag && dag == NULL);
482 instance->last_dag = new_dag;
483 return dag;
484}
485/*---------------------------------------------------------------------------*/
486static void
487handle_probing_timer(void *ptr)
488{
489 rpl_instance_t *instance = (rpl_instance_t *)ptr;
490 rpl_parent_t *probing_target = RPL_PROBING_SELECT_FUNC(get_next_dag(instance));
491 uip_ipaddr_t *target_ipaddr = rpl_parent_get_ipaddr(probing_target);
492
493 /* Perform probing. */
494 if(target_ipaddr != NULL) {
495 const struct link_stats *stats = rpl_get_parent_link_stats(probing_target);
496 const linkaddr_t *lladdr = rpl_get_parent_lladdr(probing_target);
497 LOG_INFO("probing %u %s last tx %u min ago\n",
498 lladdr != NULL ? lladdr->u8[7] : 0x0,
499 instance->urgent_probing_target != NULL ? "(urgent)" : "",
500 probing_target != NULL && stats != NULL ?
501 (unsigned)((clock_time() - stats->last_tx_time) / (60 * CLOCK_SECOND)) : 0
502 );
503
504 /* Send probe, e.g., a unicast DIO or DIS. */
505 RPL_PROBING_SEND_FUNC(instance, target_ipaddr);
506 }
507
508 /* Schedule next probing. */
509 rpl_schedule_probing(instance);
510
511 if(LOG_DBG_ENABLED) {
512 rpl_print_neighbor_list();
513 }
514}
515/*---------------------------------------------------------------------------*/
516void
518{
519 ctimer_set(&instance->probing_timer,
520 RPL_PROBING_DELAY_FUNC(instance->current_dag),
521 handle_probing_timer, instance);
522}
523/*---------------------------------------------------------------------------*/
524void
526{
527 ctimer_set(&instance->probing_timer, random_rand() % (CLOCK_SECOND * 4),
528 handle_probing_timer, instance);
529}
530#endif /* RPL_WITH_PROBING */
531
532/** @}*/
Header file for the callback timer.
clock_time_t clock_time(void)
Get the current clock time.
Definition: clock.c:118
unsigned short random_rand(void)
Generates a new random number using the cc2538 RNG.
Definition: random.c:58
#define CLOCK_SECOND
A second, measured in system clock time.
Definition: clock.h:82
void ctimer_stop(struct ctimer *c)
Stop a pending callback timer.
Definition: ctimer.c:149
void ctimer_set(struct ctimer *c, clock_time_t t, void(*f)(void *), void *ptr)
Set a callback timer.
Definition: ctimer.c:99
void ctimer_reset(struct ctimer *c)
Reset a callback timer with the same interval as was previously set.
Definition: ctimer.c:125
int etimer_expired(struct etimer *et)
Check if an event timer has expired.
Definition: etimer.c:213
clock_time_t etimer_expiration_time(struct etimer *et)
Get the expiration time for the event timer.
Definition: etimer.c:219
void * list_item_next(const void *item)
Get the next item following this item.
Definition: list.c:203
void rpl_schedule_probing(void)
Schedule probing with delay RPL_PROBING_DELAY_FUNC()
void rpl_schedule_probing_now(void)
Schedule probing within a few seconds.
#define DAG_RANK(fixpt_rank)
Return DAG RANK as per RFC 6550 (rank divided by min_hoprankinc)
Definition: rpl-types.h:81
#define ROOT_RANK
Rank of a root node.
Definition: rpl-types.h:78
uip_mcast6_route_t * uip_mcast6_route_list_head(void)
Retrieve a pointer to the start of the multicast routes list.
rpl_dag_t * rpl_get_any_dag(void)
Returns pointer to any DAG (for compatibility with legagy RPL code)
Definition: rpl-dag.c:1090
enum rpl_mode rpl_get_mode(void)
Get the RPL mode.
Definition: rpl.c:68
void uip_sr_periodic(unsigned seconds)
A function called periodically.
Definition: uip-sr.c:211
#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:1876
uip_ds6_netif_t uip_ds6_if
The single interface.
Definition: uip-ds6.c:75
Header file for the logging system.
RPL DAG structure.
Definition: rpl.h:138
RPL instance structure.
Definition: rpl.h:222
An entry in the multicast routing table.
uip_ipaddr_t group
The multicast group.
This header file contains configuration directives for uIPv6 multicast support.
Source routing support.