Contiki-NG
rpl-nbr-policy.c
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2014-2015, Yanzi Networks AB.
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 are met:
7  * 1. Redistributions of source code must retain the above copyright
8  * notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  * notice, this list of conditions and the following disclaimer in the
11  * documentation and/or other materials provided with the distribution.
12  * 3. Neither the name of the copyright holders nor the
13  * names of its contributors may be used to endorse or promote products
14  * derived from this software without specific prior written permission.
15  *
16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
19  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
20  * COPYRIGHT HOLDERS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
23  * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
24  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
25  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
26  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27  * SUCH DAMAGE.
28  *
29  */
30 /**
31  * \addtogroup uip
32  * @{
33  */
34 
35 
36 /**
37  * \file
38  *
39  * Default RPL NBR policy
40  * decides when to add a new discovered node to the nbr table from RPL.
41  *
42  * \author Joakim Eriksson <joakime@sics.se>
43  * Contributors: Niclas Finne <nfi@sics.se>, Oriol PiƱol <oriol@yanzi.se>,
44  *
45  */
46 
47 #include "net/routing/rpl-classic/rpl-private.h"
48 #include "net/nbr-table.h"
49 #include "net/ipv6/uip-ds6-nbr.h"
50 #include "net/ipv6/uip-ds6-route.h"
51 
52 #include "sys/log.h"
53 
54 #define LOG_MODULE "RPL"
55 #define LOG_LEVEL LOG_LEVEL_RPL
56 
57 /*
58  * Policy for neighbor adds
59  * - one node is locked (default route)
60  * - max X children (nexthops)
61  * - max Y "best parents"
62  * => at least MAX_NBRS - (Y + X + 1) free slots for other.
63  *
64  * NOTE: this policy assumes that all neighbors end up being IPv6
65  * neighbors and are not only MAC neighbors.
66  */
67 #define MAX_CHILDREN (NBR_TABLE_MAX_NEIGHBORS - 2)
68 
69 static int num_parents; /* any node that are possible parents */
70 static int num_children; /* all children that we have as nexthop */
71 static int num_free;
72 static const linkaddr_t *worst_rank_nbr; /* the parent that has the worst rank */
73 static rpl_rank_t worst_rank;
74 /*---------------------------------------------------------------------------*/
75 #if LOG_DBG_ENABLED
76 /*
77  * This create a periodic call of the update_nbr function that will print
78  * useful debugging information when in DEBUG_FULL mode
79  */
80 static void update_nbr(void);
81 static struct ctimer periodic_timer;
82 static int timer_init = 0;
83 static void
84 handle_periodic_timer(void *ptr)
85 {
86  update_nbr();
87  ctimer_restart(&periodic_timer);
88 }
89 #endif /* LOG_DBG_ENABLED */
90 /*---------------------------------------------------------------------------*/
91 static void
92 update_nbr(void)
93 {
95  rpl_parent_t *parent;
96  int num_used;
97  int is_used;
98  rpl_rank_t rank;
99 
100 #if LOG_DBG_ENABLED
101  if(!timer_init) {
102  timer_init = 1;
103  ctimer_set(&periodic_timer, 60 * CLOCK_SECOND,
104  &handle_periodic_timer, NULL);
105  }
106 #endif /* LOG_DBG_ENABLED */
107 
108  worst_rank = 0;
109  worst_rank_nbr = NULL;
110  num_used = 0;
111  num_parents = 0;
112  num_children = 0;
113 
114  nbr = uip_ds6_nbr_head();
115  while(nbr != NULL) {
116  const linkaddr_t *lladdr = (const linkaddr_t *)uip_ds6_nbr_get_ll(nbr);
117  is_used = 0;
118 
119  /*
120  * Check if this neighbor is used as nexthop and therefor being a
121  * RPL child.
122  */
123 
124  if(uip_ds6_route_is_nexthop(&nbr->ipaddr) != 0) {
125  is_used++;
126  num_children++;
127  }
128 
129  parent = rpl_get_parent((const uip_lladdr_t *)lladdr);
130  if(parent != NULL) {
131  num_parents++;
132 
133  if(parent->dag != NULL && parent->dag->preferred_parent == parent) {
134  /*
135  * This is the preferred parent for the DAG and must not be removed
136  * Note: this assumes that only RPL adds default routes.
137  */
138  } else if(is_used == 0 && worst_rank < RPL_INFINITE_RANK &&
139  parent->rank > 0 &&
140  parent->dag != NULL &&
141  parent->dag->instance != NULL &&
142  (rank = parent->dag->instance->of->rank_via_parent(parent)) > worst_rank) {
143  /* This is the worst-rank neighbor - this is a good candidate for removal */
144  worst_rank = rank;
145  worst_rank_nbr = lladdr;
146  }
147  /* add to is_used after evaluation of is_used above */
148  is_used++;
149  }
150 
151  if(is_used == 0) {
152  /* This neighbor is neither parent or child and can be safely removed */
153  worst_rank_nbr = lladdr;
154  worst_rank = RPL_INFINITE_RANK;
155  } else if(is_used > 1) {
156  LOG_DBG("nbr-policy: *** neighbor is both child and candidate parent: ");
157  LOG_DBG_LLADDR(lladdr);
158  LOG_DBG_("\n");
159  }
160 
161  nbr = uip_ds6_nbr_next(nbr);
162  num_used++;
163  }
164  /* how many more IP neighbors can be have? */
165  num_free = NBR_TABLE_MAX_NEIGHBORS - num_used;
166 
167  LOG_DBG("nbr-policy: free: %d, children: %d, parents: %d routes: %d\n",
168  num_free, num_children, num_parents, uip_ds6_route_num_routes());
169 }
170 /*---------------------------------------------------------------------------*/
171 /* Called whenever we get a unicast DIS - e.g. someone that already
172  have this node in its table - since it is a unicast */
173 const linkaddr_t *
174 find_removable_dis(uip_ipaddr_t *from)
175 {
176 
177  update_nbr();
178  if(num_free > 0) {
179  /* there are free entries (e.g. unsused by RPL and ND6) but since it is
180  used by other modules we can not pick these entries for removal. */
181  LOG_DBG("nbr-policy: num-free > 0 = %d - Other for RPL/ND6 unused NBR entry exists.\n",
182  num_free);
183  }
184  if(num_children < MAX_CHILDREN) {
185  return worst_rank_nbr;
186  }
187  return NULL;
188 }
189 /*---------------------------------------------------------------------------*/
190 const linkaddr_t *
191 find_removable_dio(uip_ipaddr_t *from, rpl_dio_t *dio)
192 {
193  rpl_instance_t *instance;
194 
195  update_nbr();
196 
197  instance = rpl_get_instance(dio->instance_id);
198  if(instance == NULL || instance->current_dag == NULL) {
199  LOG_WARN("nbr-policy: did not find instance id: %d\n", dio->instance_id);
200  return NULL;
201  }
202 
203  /* Add the new neighbor only if it is better than the worst parent. */
204  if(dio->rank + instance->min_hoprankinc < worst_rank - instance->min_hoprankinc / 2) {
205  /* Found *great* neighbor - add! */
206  LOG_DBG("nbr-policy: DIO rank %u, worst_rank %u -- add to cache\n",
207  dio->rank, worst_rank);
208 
209  return worst_rank_nbr;
210  }
211 
212  LOG_DBG("nbr-policy: DIO rank %u, worst_rank %u -- do not add to cache\n",
213  dio->rank, worst_rank);
214  return NULL;
215 }
216 /*---------------------------------------------------------------------------*/
217 const linkaddr_t *
218 find_removable_dao(uip_ipaddr_t *from, rpl_instance_t *instance)
219 {
220  int max = MAX_CHILDREN;
221  update_nbr();
222 
223  if(instance != NULL) {
224  /* No need to reserve space for parents for RPL ROOT */
225  if(instance->current_dag->rank == ROOT_RANK(instance)) {
226  max = NBR_TABLE_MAX_NEIGHBORS;
227  }
228  }
229 
230  /* Check if this DAO sender is not yet neighbor and there is already too
231  many children. */
232  if(num_children >= max) {
233  LOG_ERR("nbr-policy: can not add another child - already at max.\n");
234  return NULL;
235  }
236  /* remove the worst ranked nbr */
237  return worst_rank_nbr;
238 }
239 /*---------------------------------------------------------------------------*/
240 const linkaddr_t *
241 rpl_nbr_policy_find_removable(nbr_table_reason_t reason,void * data)
242 {
243  /* When we get the DIO/DAO/DIS we know that UIP contains the
244  incoming packet */
245  switch(reason) {
246  case NBR_TABLE_REASON_RPL_DIO:
247  return find_removable_dio(&UIP_IP_BUF->srcipaddr, data);
248  case NBR_TABLE_REASON_RPL_DAO:
249  return find_removable_dao(&UIP_IP_BUF->srcipaddr, data);
250  case NBR_TABLE_REASON_RPL_DIS:
251  return find_removable_dis(&UIP_IP_BUF->srcipaddr);
252  default:
253  return NULL;
254  }
255 }
256 /*---------------------------------------------------------------------------*/
257 /** @}*/
#define UIP_IP_BUF
Direct access to IPv6 header.
Definition: uip.h:71
static uip_ds6_nbr_t * nbr
Pointer to llao option in uip_buf.
Definition: uip-nd6.c:106
RPL instance structure.
Definition: rpl.h:219
#define ROOT_RANK
Rank of a root node.
Definition: rpl-types.h:78
uip_ds6_nbr_t * uip_ds6_nbr_head(void)
Get the first neighbor cache in nbr_table.
Definition: uip-ds6-nbr.c:429
IPv6 Neighbor cache (link-layer/IPv6 address mapping)
#define CLOCK_SECOND
A second, measured in system clock time.
Definition: clock.h:82
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_restart(struct ctimer *c)
Restart a callback timer from the current point in time.
Definition: ctimer.c:137
Header file for routing table manipulation.
uip_ds6_nbr_t * uip_ds6_nbr_next(uip_ds6_nbr_t *nbr)
Get the next neighbor cache of a specified one.
Definition: uip-ds6-nbr.c:444
const uip_lladdr_t * uip_ds6_nbr_get_ll(const uip_ds6_nbr_t *nbr)
Get the link-layer address associated with a specified nbr cache.
Definition: uip-ds6-nbr.c:392
Header file for the logging system
The default nbr_table entry (when UIP_DS6_NBR_MULTI_IPV6_ADDRS is disabled), that implements nbr cach...
Definition: uip-ds6-nbr.h:105