Contiki-NG
rpl-neighbor.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  * Logic for DAG neighbors in RPL.
39  *
40  * \author Joakim Eriksson <joakime@sics.se>, Nicolas Tsiftes <nvt@sics.se>,
41  * Simon Duquennoy <simon.duquennoy@inria.fr>
42  * Contributors: George Oikonomou <oikonomou@users.sourceforge.net> (multicast)
43  */
44 
45 #include "contiki.h"
46 #include "net/routing/rpl-lite/rpl.h"
47 #include "net/link-stats.h"
48 #include "net/nbr-table.h"
49 #include "net/ipv6/uiplib.h"
50 
51 /* Log configuration */
52 #include "sys/log.h"
53 #define LOG_MODULE "RPL"
54 #define LOG_LEVEL LOG_LEVEL_RPL
55 
56 /* A configurable function called after every RPL parent switch */
57 #ifdef RPL_CALLBACK_PARENT_SWITCH
58 void RPL_CALLBACK_PARENT_SWITCH(rpl_nbr_t *old, rpl_nbr_t *new);
59 #endif /* RPL_CALLBACK_PARENT_SWITCH */
60 
61 static rpl_nbr_t * best_parent(int fresh_only);
62 
63 /*---------------------------------------------------------------------------*/
64 /* Per-neighbor RPL information */
65 NBR_TABLE_GLOBAL(rpl_nbr_t, rpl_neighbors);
66 
67 /*---------------------------------------------------------------------------*/
68 static int
69 max_acceptable_rank(void)
70 {
71  if(curr_instance.max_rankinc == 0) {
72  /* There is no max rank increment */
73  return RPL_INFINITE_RANK;
74  } else {
75  /* Make sure not to exceed RPL_INFINITE_RANK */
76  return MIN((uint32_t)curr_instance.dag.lowest_rank + curr_instance.max_rankinc, RPL_INFINITE_RANK);
77  }
78 }
79 /*---------------------------------------------------------------------------*/
80 /* As per RFC 6550, section 8.2.2.4 */
81 static int
82 acceptable_rank(rpl_rank_t rank)
83 {
84  return rank != RPL_INFINITE_RANK
85  && rank >= ROOT_RANK
86  && rank <= max_acceptable_rank();
87 }
88 /*---------------------------------------------------------------------------*/
89 int
90 rpl_neighbor_snprint(char *buf, int buflen, rpl_nbr_t *nbr)
91 {
92  int index = 0;
93  rpl_nbr_t *best = best_parent(0);
94  const struct link_stats *stats = rpl_neighbor_get_link_stats(nbr);
95  clock_time_t clock_now = clock_time();
96 
97  index += uiplib_ipaddr_snprint(buf+index, buflen-index, rpl_neighbor_get_ipaddr(nbr));
98  if(index >= buflen) {
99  return index;
100  }
101  index += snprintf(buf+index, buflen-index,
102  "%5u, %5u => %5u -- %2u %c%c%c%c%c",
103  nbr->rank,
106  stats != NULL ? stats->freshness : 0,
107  (nbr->rank == ROOT_RANK) ? 'r' : ' ',
108  nbr == best ? 'b' : ' ',
109  (acceptable_rank(rpl_neighbor_rank_via_nbr(nbr)) && rpl_neighbor_is_acceptable_parent(nbr)) ? 'a' : ' ',
110  link_stats_is_fresh(stats) ? 'f' : ' ',
111  nbr == curr_instance.dag.preferred_parent ? 'p' : ' '
112  );
113  if(index >= buflen) {
114  return index;
115  }
116  if(stats->last_tx_time > 0) {
117  index += snprintf(buf+index, buflen-index,
118  " (last tx %u min ago",
119  (unsigned)((clock_now - stats->last_tx_time) / (60 * CLOCK_SECOND)));
120  } else {
121  index += snprintf(buf+index, buflen-index,
122  " (no tx");
123  }
124  if(index >= buflen) {
125  return index;
126  }
127  if(nbr->better_parent_since > 0) {
128  index += snprintf(buf+index, buflen-index,
129  ", better since %u min)",
130  (unsigned)((clock_now - nbr->better_parent_since) / (60 * CLOCK_SECOND)));
131  } else {
132  index += snprintf(buf+index, buflen-index,
133  ")");
134  }
135  return index;
136 }
137 /*---------------------------------------------------------------------------*/
138 void
139 rpl_neighbor_print_list(const char *str)
140 {
141  if(curr_instance.used) {
142  int curr_dio_interval = curr_instance.dag.dio_intcurrent;
143  int curr_rank = curr_instance.dag.rank;
144  rpl_nbr_t *nbr = nbr_table_head(rpl_neighbors);
145 
146  LOG_INFO("nbr: own state, addr ");
147  LOG_INFO_6ADDR(rpl_get_global_address());
148  LOG_INFO_(", DAG state: %s, MOP %u OCP %u rank %u max-rank %u, dioint %u, nbr count %u (%s)\n",
149  rpl_dag_state_to_str(curr_instance.dag.state),
150  curr_instance.mop, curr_instance.of->ocp, curr_rank,
151  max_acceptable_rank(),
152  curr_dio_interval, rpl_neighbor_count(), str);
153  while(nbr != NULL) {
154  char buf[120];
155  rpl_neighbor_snprint(buf, sizeof(buf), nbr);
156  LOG_INFO("nbr: %s\n", buf);
157  nbr = nbr_table_next(rpl_neighbors, nbr);
158  }
159  LOG_INFO("nbr: end of list\n");
160  }
161 }
162 /*---------------------------------------------------------------------------*/
163 int
165 {
166  int count = 0;
167  rpl_nbr_t *nbr = nbr_table_head(rpl_neighbors);
168  for(nbr = nbr_table_head(rpl_neighbors);
169  nbr != NULL;
170  nbr = nbr_table_next(rpl_neighbors, nbr)) {
171  count++;
172  }
173  return count;
174 }
175 /*---------------------------------------------------------------------------*/
176 #if UIP_ND6_SEND_NS
177 static uip_ds6_nbr_t *
178 rpl_get_ds6_nbr(rpl_nbr_t *nbr)
179 {
180  const linkaddr_t *lladdr = rpl_neighbor_get_lladdr(nbr);
181  if(lladdr != NULL) {
182  return nbr_table_get_from_lladdr(ds6_neighbors, lladdr);
183  } else {
184  return NULL;
185  }
186 }
187 #endif /* UIP_ND6_SEND_NS */
188 /*---------------------------------------------------------------------------*/
189 static void
190 remove_neighbor(rpl_nbr_t *nbr)
191 {
192  /* Make sure we don't point to a removed neighbor. Note that we do not need
193  to worry about preferred_parent here, as it is locked in the the table
194  and will never be removed by external modules. */
195  if(nbr == curr_instance.dag.urgent_probing_target) {
196  curr_instance.dag.urgent_probing_target = NULL;
197  }
198  if(nbr == curr_instance.dag.unicast_dio_target) {
199  curr_instance.dag.unicast_dio_target = NULL;
200  }
201  nbr_table_remove(rpl_neighbors, nbr);
202  rpl_timers_schedule_state_update(); /* Updating from here is unsafe; postpone */
203 }
204 /*---------------------------------------------------------------------------*/
205 rpl_nbr_t *
207 {
208  return nbr_table_get_from_lladdr(rpl_neighbors, (linkaddr_t *)addr);
209 }
210 /*---------------------------------------------------------------------------*/
211 int
213 {
214  if(nbr != NULL && curr_instance.of->nbr_is_acceptable_parent != NULL) {
215  return curr_instance.of->nbr_is_acceptable_parent(nbr);
216  }
217  return 0xffff;
218 }
219 /*---------------------------------------------------------------------------*/
220 uint16_t
222 {
223  if(nbr != NULL && curr_instance.of->nbr_link_metric != NULL) {
224  return curr_instance.of->nbr_link_metric(nbr);
225  }
226  return 0xffff;
227 }
228 /*---------------------------------------------------------------------------*/
229 rpl_rank_t
231 {
232  if(nbr != NULL && curr_instance.of->rank_via_nbr != NULL) {
233  return curr_instance.of->rank_via_nbr(nbr);
234  }
235  return RPL_INFINITE_RANK;
236 }
237 /*---------------------------------------------------------------------------*/
238 const linkaddr_t *
240 {
241  return nbr_table_get_lladdr(rpl_neighbors, nbr);
242 }
243 /*---------------------------------------------------------------------------*/
244 uip_ipaddr_t *
246 {
247  const linkaddr_t *lladdr = rpl_neighbor_get_lladdr(nbr);
248  return uip_ds6_nbr_ipaddr_from_lladdr((uip_lladdr_t *)lladdr);
249 }
250 /*---------------------------------------------------------------------------*/
251 const struct link_stats *
253 {
254  const linkaddr_t *lladdr = rpl_neighbor_get_lladdr(nbr);
255  return link_stats_from_lladdr(lladdr);
256 }
257 /*---------------------------------------------------------------------------*/
258 int
260 {
261  const struct link_stats *stats = rpl_neighbor_get_link_stats(nbr);
262  return link_stats_is_fresh(stats);
263 }
264 /*---------------------------------------------------------------------------*/
265 int
267  if(nbr == NULL) {
268  return 0;
269  } else {
270 #if UIP_ND6_SEND_NS
271  uip_ds6_nbr_t *ds6_nbr = rpl_get_ds6_nbr(nbr);
272  /* Exclude links to a neighbor that is not reachable at a NUD level */
273  if(ds6_nbr == NULL || ds6_nbr->state != NBR_REACHABLE) {
274  return 0;
275  }
276 #endif /* UIP_ND6_SEND_NS */
277  /* If we don't have fresh link information, assume the nbr is reachable. */
278  return !rpl_neighbor_is_fresh(nbr) || curr_instance.of->nbr_has_usable_link(nbr);
279  }
280 }
281 /*---------------------------------------------------------------------------*/
282 int
284 {
285  return nbr != NULL && nbr->rank < curr_instance.dag.rank;
286 }
287 /*---------------------------------------------------------------------------*/
288 void
290 {
291  if(curr_instance.dag.preferred_parent != nbr) {
292  LOG_INFO("parent switch: ");
293  LOG_INFO_6ADDR(rpl_neighbor_get_ipaddr(curr_instance.dag.preferred_parent));
294  LOG_INFO_(" -> ");
295  LOG_INFO_6ADDR(rpl_neighbor_get_ipaddr(nbr));
296  LOG_INFO_("\n");
297 
298 #ifdef RPL_CALLBACK_PARENT_SWITCH
299  RPL_CALLBACK_PARENT_SWITCH(curr_instance.dag.preferred_parent, nbr);
300 #endif /* RPL_CALLBACK_PARENT_SWITCH */
301 
302  /* Always keep the preferred parent locked, so it remains in the
303  * neighbor table. */
304  nbr_table_unlock(rpl_neighbors, curr_instance.dag.preferred_parent);
305  nbr_table_lock(rpl_neighbors, nbr);
306 
307  /* Update DS6 default route. Use an infinite lifetime */
308  uip_ds6_defrt_rm(uip_ds6_defrt_lookup(
309  rpl_neighbor_get_ipaddr(curr_instance.dag.preferred_parent)));
310  uip_ds6_defrt_add(rpl_neighbor_get_ipaddr(nbr), 0);
311 
312  curr_instance.dag.preferred_parent = nbr;
313  }
314 }
315 /*---------------------------------------------------------------------------*/
316 /* Remove DAG neighbors with a rank that is at least the same as minimum_rank. */
317 void
319 {
320  rpl_nbr_t *nbr;
321 
322  LOG_INFO("removing all neighbors\n");
323 
324  nbr = nbr_table_head(rpl_neighbors);
325  while(nbr != NULL) {
326  remove_neighbor(nbr);
327  nbr = nbr_table_next(rpl_neighbors, nbr);
328  }
329 
330  /* Update needed immediately so as to ensure preferred_parent becomes NULL,
331  * and no longer points to a de-allocated neighbor. */
333 }
334 /*---------------------------------------------------------------------------*/
335 rpl_nbr_t *
337 {
338  uip_ds6_nbr_t *ds6_nbr = uip_ds6_nbr_lookup(addr);
339  const uip_lladdr_t *lladdr = uip_ds6_nbr_get_ll(ds6_nbr);
340  return nbr_table_get_from_lladdr(rpl_neighbors, (linkaddr_t *)lladdr);
341 }
342 /*---------------------------------------------------------------------------*/
343 static rpl_nbr_t *
344 best_parent(int fresh_only)
345 {
346  rpl_nbr_t *nbr;
347  rpl_nbr_t *best = NULL;
348 
349  if(curr_instance.used == 0) {
350  return NULL;
351  }
352 
353  /* Search for the best parent according to the OF */
354  for(nbr = nbr_table_head(rpl_neighbors); nbr != NULL; nbr = nbr_table_next(rpl_neighbors, nbr)) {
355 
356  if(!acceptable_rank(nbr->rank) || !curr_instance.of->nbr_is_acceptable_parent(nbr)) {
357  /* Exclude neighbors with a rank that is not acceptable) */
358  continue;
359  }
360 
361  if(fresh_only && !rpl_neighbor_is_fresh(nbr)) {
362  /* Filter out non-fresh nerighbors if fresh_only is set */
363  continue;
364  }
365 
366 #if UIP_ND6_SEND_NS
367  {
368  uip_ds6_nbr_t *ds6_nbr = rpl_get_ds6_nbr(nbr);
369  /* Exclude links to a neighbor that is not reachable at a NUD level */
370  if(ds6_nbr == NULL || ds6_nbr->state != NBR_REACHABLE) {
371  continue;
372  }
373  }
374 #endif /* UIP_ND6_SEND_NS */
375 
376  /* Now we have an acceptable parent, check if it is the new best */
377  best = curr_instance.of->best_parent(best, nbr);
378  }
379 
380  return best;
381 }
382 /*---------------------------------------------------------------------------*/
383 rpl_nbr_t *
385 {
386  rpl_nbr_t *best;
387 
388  if(rpl_dag_root_is_root()) {
389  return NULL; /* The root has no parent */
390  }
391 
392  /* Look for best parent (regardless of freshness) */
393  best = best_parent(0);
394 
395 #if RPL_WITH_PROBING
396  if(best != NULL) {
397  if(rpl_neighbor_is_fresh(best)) {
398  /* Unschedule any already scheduled urgent probing */
399  curr_instance.dag.urgent_probing_target = NULL;
400  /* Return best if it is fresh */
401  return best;
402  } else {
403  rpl_nbr_t *best_fresh;
404 
405  /* The best is not fresh. Probe it (unless there is already an urgent
406  probing target). We will be called back after the probing anyway. */
407  if(curr_instance.dag.urgent_probing_target == NULL) {
408  LOG_INFO("best parent is not fresh, schedule urgent probing to ");
409  LOG_INFO_6ADDR(rpl_neighbor_get_ipaddr(best));
410  LOG_INFO_("\n");
411  curr_instance.dag.urgent_probing_target = best;
413  }
414 
415  /* The best is our preferred parent. It is not fresh but used to be,
416  else we would not have selected it in the first place. Stick to it
417  for a little while and rely on urgent probing to make a call. */
418  if(best == curr_instance.dag.preferred_parent) {
419  return best;
420  }
421 
422  /* Look for the best fresh parent. */
423  best_fresh = best_parent(1);
424  if(best_fresh == NULL) {
425  if(curr_instance.dag.preferred_parent == NULL) {
426  /* We will wait to find a fresh node before selecting our first parent */
427  return NULL;
428  } else {
429  /* We already have a parent, now stick to the best and count on
430  urgent probing to get a fresh parent soon */
431  return best;
432  }
433  } else {
434  /* Select best fresh */
435  return best_fresh;
436  }
437  }
438  } else {
439  /* No acceptable parent */
440  return NULL;
441  }
442 #else /* RPL_WITH_PROBING */
443  return best;
444 #endif /* RPL_WITH_PROBING */
445 }
446 /*---------------------------------------------------------------------------*/
447 void
449 {
450  nbr_table_register(rpl_neighbors, (nbr_table_callback *)remove_neighbor);
451 }
452 /** @} */
const linkaddr_t * rpl_neighbor_get_lladdr(rpl_nbr_t *nbr)
Returns a neighbors&#39;s link-layer address.
Definition: rpl-neighbor.c:239
uip_ipaddr_t * rpl_neighbor_get_ipaddr(rpl_nbr_t *nbr)
Returns a neighbor&#39;s (link-local) IPv6 address.
Definition: rpl-neighbor.c:245
static uip_ds6_nbr_t * nbr
Pointer to llao option in uip_buf.
Definition: uip-nd6.c:114
#define ROOT_RANK
Rank of a root node.
Definition: rpl-types.h:78
static uip_ds6_addr_t * addr
Pointer to a nbr cache entry.
Definition: uip-nd6.c:115
void rpl_neighbor_remove_all(void)
Empty the RPL neighbor table.
Definition: rpl-neighbor.c:318
void rpl_schedule_probing_now(void)
Schedule probing within a few seconds.
rpl_nbr_t * rpl_neighbor_get_from_ipaddr(uip_ipaddr_t *addr)
Returns a neighbor from its link-local IPv6 address.
Definition: rpl-neighbor.c:336
int rpl_neighbor_is_fresh(rpl_nbr_t *nbr)
Tells wether we have fresh link information towards a given neighbor.
Definition: rpl-neighbor.c:259
uint16_t rpl_neighbor_get_link_metric(rpl_nbr_t *nbr)
Returns a neighbor&#39;s link metric.
Definition: rpl-neighbor.c:221
int rpl_neighbor_is_parent(rpl_nbr_t *nbr)
Tells whether a neighbor is in the parent set.
Definition: rpl-neighbor.c:283
int rpl_dag_root_is_root(void)
Tells whether we are DAG root or not.
Definition: rpl-dag-root.c:142
int rpl_neighbor_count(void)
Returns the number of nodes in the RPL neighbor table.
Definition: rpl-neighbor.c:164
const char * rpl_dag_state_to_str(enum rpl_dag_state state)
Returns a textual description of the current DAG state.
Definition: rpl-dag.c:66
void rpl_timers_schedule_state_update(void)
Schedule a state update ASAP.
Definition: rpl-timers.c:556
void rpl_neighbor_init(void)
Initialize rpl-dag-neighbor module.
Definition: rpl-neighbor.c:448
#define CLOCK_SECOND
A second, measured in system clock time.
Definition: clock.h:82
Header file for the IP address manipulation library.
const struct link_stats * rpl_neighbor_get_link_stats(rpl_nbr_t *nbr)
Returns a neighbor&#39;s link statistics.
Definition: rpl-neighbor.c:252
All information related to a RPL neighbor.
Definition: rpl-types.h:136
clock_time_t clock_time(void)
Get the current clock time.
Definition: clock.c:118
void rpl_neighbor_print_list(const char *str)
Prints a summary of all RPL neighbors and their properties.
Definition: rpl-neighbor.c:139
const uip_ipaddr_t * rpl_get_global_address(void)
Get one of the node&#39;s global addresses.
Definition: rpl.c:71
void rpl_dag_update_state(void)
Updates RPL internal state: selects preferred parent, updates rank & metreic container, triggers control traffic accordingly and updates uIP6 internal state.
Definition: rpl-dag.c:258
int rpl_neighbor_is_acceptable_parent(rpl_nbr_t *nbr)
Tells whether a nbr is acceptable as per the OF&#39;s definition.
Definition: rpl-neighbor.c:212
rpl_rank_t rpl_neighbor_rank_via_nbr(rpl_nbr_t *nbr)
Returns our rank if selecting a given parent as preferred parent.
Definition: rpl-neighbor.c:230
void rpl_neighbor_set_preferred_parent(rpl_nbr_t *nbr)
Set current RPL preferred parent and update DS6 default route accordingly.
Definition: rpl-neighbor.c:289
Header file for the logging system
rpl_nbr_t * rpl_neighbor_select_best(void)
Returns the best candidate for preferred parent.
Definition: rpl-neighbor.c:384
int rpl_neighbor_snprint(char *buf, int buflen, rpl_nbr_t *nbr)
Print a textual description of RPL neighbor into a string.
Definition: rpl-neighbor.c:90
rpl_nbr_t * rpl_neighbor_get_from_lladdr(uip_lladdr_t *addr)
Returns a neighbor from its link-layer address.
Definition: rpl-neighbor.c:206
An entry in the nbr cache.
Definition: uip-ds6-nbr.h:69
int rpl_neighbor_is_reachable(rpl_nbr_t *nbr)
Tells wether we a given neighbor is reachable.
Definition: rpl-neighbor.c:266
int uiplib_ipaddr_snprint(char *buf, size_t size, const uip_ipaddr_t *addr)
Write at most size - 1 characters of the IP address to the output string.
Definition: uiplib.c:168