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 #define DEBUG DEBUG_NONE
53 #include "net/ipv6/uip-debug.h"
54 
55 /*
56  * Policy for neighbor adds
57  * - one node is locked (default route)
58  * - max X children (nexthops)
59  * - max Y "best parents"
60  * => at least MAX_NBRS - (Y + X + 1) free slots for other.
61  *
62  * NOTE: this policy assumes that all neighbors end up being IPv6
63  * neighbors and are not only MAC neighbors.
64  */
65 #define MAX_CHILDREN (NBR_TABLE_MAX_NEIGHBORS - 2)
66 #define UIP_IP_BUF ((struct uip_ip_hdr *)&uip_buf[UIP_LLH_LEN])
67 
68 static int num_parents; /* any node that are possible parents */
69 static int num_children; /* all children that we have as nexthop */
70 static int num_free;
71 static linkaddr_t *worst_rank_nbr; /* the parent that has the worst rank */
72 static rpl_rank_t worst_rank;
73 /*---------------------------------------------------------------------------*/
74 #if DEBUG == DEBUG_FULL
75 /*
76  * This create a periodic call of the update_nbr function that will print
77  * useful debugging information when in DEBUG_FULL mode
78  */
79 static void update_nbr(void);
80 static struct ctimer periodic_timer;
81 static int timer_init = 0;
82 static void
83 handle_periodic_timer(void *ptr)
84 {
85  update_nbr();
86  ctimer_restart(&periodic_timer);
87 }
88 #endif /* DEBUG == DEBUG_FULL */
89 /*---------------------------------------------------------------------------*/
90 static void
91 update_nbr(void)
92 {
94  rpl_parent_t *parent;
95  int num_used;
96  int is_used;
97  rpl_rank_t rank;
98 
99 #if DEBUG == DEBUG_FULL
100  if(!timer_init) {
101  timer_init = 1;
102  ctimer_set(&periodic_timer, 60 * CLOCK_SECOND,
103  &handle_periodic_timer, NULL);
104  }
105 #endif /* DEBUG == DEBUG_FULL */
106 
107  worst_rank = 0;
108  worst_rank_nbr = NULL;
109  num_used = 0;
110  num_parents = 0;
111  num_children = 0;
112 
113  nbr = nbr_table_head(ds6_neighbors);
114  while(nbr != NULL) {
115  linkaddr_t *lladdr = nbr_table_get_lladdr(ds6_neighbors, nbr);
116  is_used = 0;
117 
118  /*
119  * Check if this neighbor is used as nexthop and therefor being a
120  * RPL child.
121  */
122 
123  if(uip_ds6_route_is_nexthop(&nbr->ipaddr) != 0) {
124  is_used++;
125  num_children++;
126  }
127 
128  parent = rpl_get_parent((uip_lladdr_t *)lladdr);
129  if(parent != NULL) {
130  num_parents++;
131 
132  if(parent->dag != NULL && parent->dag->preferred_parent == parent) {
133  /*
134  * This is the preferred parent for the DAG and must not be removed
135  * Note: this assumes that only RPL adds default routes.
136  */
137  } else if(is_used == 0 && worst_rank < RPL_INFINITE_RANK &&
138  parent->rank > 0 &&
139  parent->dag != NULL &&
140  parent->dag->instance != NULL &&
141  (rank = parent->dag->instance->of->rank_via_parent(parent)) > worst_rank) {
142  /* This is the worst-rank neighbor - this is a good candidate for removal */
143  worst_rank = rank;
144  worst_rank_nbr = lladdr;
145  }
146  /* add to is_used after evaluation of is_used above */
147  is_used++;
148  }
149 
150  if(is_used == 0) {
151  /* This neighbor is neither parent or child and can be safely removed */
152  worst_rank_nbr = lladdr;
153  worst_rank = RPL_INFINITE_RANK;
154  } else if(is_used > 1) {
155  PRINTF("NBR-POLICY: *** Neighbor is both child and candidate parent: ");
156  PRINTLLADDR((uip_lladdr_t *)lladdr);
157  PRINTF("\n");
158  }
159 
160  nbr = nbr_table_next(ds6_neighbors, nbr);
161  num_used++;
162  }
163  /* how many more IP neighbors can be have? */
164  num_free = NBR_TABLE_MAX_NEIGHBORS - num_used;
165 
166  PRINTF("NBR-POLICY: Free: %d, Children: %d, Parents: %d Routes: %d\n",
167  num_free, num_children, num_parents, uip_ds6_route_num_routes());
168 }
169 /*---------------------------------------------------------------------------*/
170 /* Called whenever we get a unicast DIS - e.g. someone that already
171  have this node in its table - since it is a unicast */
172 const linkaddr_t *
173 find_removable_dis(uip_ipaddr_t *from)
174 {
175 
176  update_nbr();
177  if(num_free > 0) {
178  /* there are free entries (e.g. unsused by RPL and ND6) but since it is
179  used by other modules we can not pick these entries for removal. */
180  PRINTF("Num-free > 0 = %d - Other for RPL/ND6 unused NBR entry exists .",
181  num_free);
182  }
183  if(num_children < MAX_CHILDREN) {
184  return worst_rank_nbr;
185  }
186  return NULL;
187 }
188 /*---------------------------------------------------------------------------*/
189 const linkaddr_t *
190 find_removable_dio(uip_ipaddr_t *from, rpl_dio_t *dio)
191 {
192  rpl_instance_t *instance;
193 
194  update_nbr();
195 
196  instance = rpl_get_instance(dio->instance_id);
197  if(instance == NULL || instance->current_dag == NULL) {
198  PRINTF("Did not find instance id: %d\n", dio->instance_id);
199  return NULL;
200  }
201 
202  /* Add the new neighbor only if it is better than the worst parent. */
203  if(dio->rank + instance->min_hoprankinc < worst_rank - instance->min_hoprankinc / 2) {
204  /* Found *great* neighbor - add! */
205  PRINTF("Found better neighbor %d < %d - add to cache...\n",
206  dio->rank, worst_rank);
207 
208  return worst_rank_nbr;
209  }
210 
211  PRINTF("Found worse neighbor with new %d and old %d - NOT add to cache.\n",
212  dio->rank, worst_rank);
213  return NULL;
214 }
215 /*---------------------------------------------------------------------------*/
216 const linkaddr_t *
217 find_removable_dao(uip_ipaddr_t *from, rpl_instance_t *instance)
218 {
219  int max = MAX_CHILDREN;
220  update_nbr();
221 
222  if(instance != NULL) {
223  /* No need to reserve space for parents for RPL ROOT */
224  if(instance->current_dag->rank == ROOT_RANK(instance)) {
225  max = NBR_TABLE_MAX_NEIGHBORS;
226  }
227  }
228 
229  /* Check if this DAO sender is not yet neighbor and there is already too
230  many children. */
231  if(num_children >= max) {
232  PRINTF("Can not add another child - already at max.\n");
233  return NULL;
234  }
235  /* remove the worst ranked nbr */
236  return worst_rank_nbr;
237 }
238 /*---------------------------------------------------------------------------*/
239 const linkaddr_t *
240 rpl_nbr_policy_find_removable(nbr_table_reason_t reason,void * data)
241 {
242  /* When we get the DIO/DAO/DIS we know that UIP contains the
243  incoming packet */
244  switch(reason) {
245  case NBR_TABLE_REASON_RPL_DIO:
246  return find_removable_dio(&UIP_IP_BUF->srcipaddr, data);
247  case NBR_TABLE_REASON_RPL_DAO:
248  return find_removable_dao(&UIP_IP_BUF->srcipaddr, data);
249  case NBR_TABLE_REASON_RPL_DIS:
250  return find_removable_dis(&UIP_IP_BUF->srcipaddr);
251  default:
252  return NULL;
253  }
254 }
255 /*---------------------------------------------------------------------------*/
256 /** @}*/
#define UIP_IP_BUF
Pointer to IP header.
Definition: uip-nd6.c:96
static uip_ds6_nbr_t * nbr
Pointer to llao option in uip_buf.
Definition: uip-nd6.c:114
RPL instance structure.
Definition: rpl.h:219
#define ROOT_RANK
Rank of a root node.
Definition: rpl-types.h:78
IPv6 Neighbor cache (link-layer/IPv6 address mapping)
A set of debugging macros for the IP stack
#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.
An entry in the nbr cache.
Definition: uip-ds6-nbr.h:69