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 /**
32  * \addtogroup rpl-lite
33  * @{
34  *
35  * \file
36  *
37  * Default RPL NBR policy
38  * decides when to add a new discovered node to the nbr table from RPL.
39  *
40  * \author Joakim Eriksson <joakime@sics.se>
41  * Contributors: Niclas Finne <nfi@sics.se>, Oriol PiƱol <oriol@yanzi.se>,
42  *
43  */
44 
45 #include "net/routing/rpl-lite/rpl.h"
46 #include "net/nbr-table.h"
47 
48 /* Log configuration */
49 #include "sys/log.h"
50 #define LOG_MODULE "RPL"
51 #define LOG_LEVEL LOG_LEVEL_RPL
52 
53 /*
54  * Policy for neighbor addition
55  * - one node is locked (default route)
56  * - max X "best parents"
57  * => at least MAX_NBRS - (X + 1) free slots for other.
58  *
59  * NOTE: this policy assumes that all neighbors end up being IPv6
60  * neighbors and are not only MAC neighbors.
61  */
62 
63 static int num_parents; /* all nodes that are possible parents */
64 static int num_free;
65 static const linkaddr_t *worst_rank_nbr_lladdr; /* lladdr of the the neighbor with the worst rank */
66 static rpl_rank_t worst_rank;
67 
68 /*---------------------------------------------------------------------------*/
69 static void
70 update_state(void)
71 {
72  uip_ds6_nbr_t *ds6_nbr;
74  rpl_rank_t nbr_rank;
75  int num_used = 0;
76 
77  worst_rank = 0;
78  worst_rank_nbr_lladdr = NULL;
79  num_parents = 0;
80 
81  ds6_nbr = uip_ds6_nbr_head();
82  while(ds6_nbr != NULL) {
83 
84  const linkaddr_t *nbr_lladdr = (const linkaddr_t *)uip_ds6_nbr_get_ll(ds6_nbr);
85  rpl_nbr = rpl_neighbor_get_from_lladdr((uip_lladdr_t *)nbr_lladdr);
86 
87  if(rpl_nbr != NULL && rpl_neighbor_is_parent(rpl_nbr)) {
88  num_parents++;
89  }
90 
91  nbr_rank = rpl_neighbor_rank_via_nbr(rpl_nbr);
92  /* Select worst-rank neighbor */
93  if(rpl_nbr != curr_instance.dag.preferred_parent
94  && nbr_rank > worst_rank) {
95  /* This is the worst-rank neighbor - this is a good candidate for removal */
96  worst_rank = nbr_rank;
97  worst_rank_nbr_lladdr = nbr_lladdr;
98  }
99 
100  ds6_nbr = uip_ds6_nbr_next(ds6_nbr);
101  num_used++;
102  }
103  /* how many more IP neighbors can be have? */
104  num_free = NBR_TABLE_MAX_NEIGHBORS - num_used;
105 
106  LOG_DBG("nbr-policy: free: %d, parents: %d\n", num_free, num_parents);
107 }
108 /*---------------------------------------------------------------------------*/
109 static const linkaddr_t *
110 find_worst_rank_nbr_lladdr(void)
111 {
112  update_state();
113  return worst_rank_nbr_lladdr;
114 }
115 /*---------------------------------------------------------------------------*/
116 static const linkaddr_t *
117 find_removable_dio(uip_ipaddr_t *from, rpl_dio_t *dio)
118 {
119  update_state();
120 
121  if(!curr_instance.used || curr_instance.instance_id != dio->instance_id) {
122  LOG_WARN("nbr-policy: did not find instance id: %d\n", dio->instance_id);
123  return NULL;
124  }
125 
126  /* Add the new neighbor only if it is better than the current worst. */
127  if(dio->rank + curr_instance.min_hoprankinc < worst_rank - curr_instance.min_hoprankinc / 2) {
128  /* Found *great* neighbor - add! */
129  LOG_DBG("nbr-policy: DIO rank %u, worst_rank %u -- add to cache\n",
130  dio->rank, worst_rank);
131  return worst_rank_nbr_lladdr;
132  }
133 
134  LOG_DBG("nbr-policy: DIO rank %u, worst_rank %u -- do not add to cache\n",
135  dio->rank, worst_rank);
136  return NULL;
137 }
138 /*---------------------------------------------------------------------------*/
139 const linkaddr_t *
140 rpl_nbr_policy_find_removable(nbr_table_reason_t reason, void *data)
141 {
142  /* When we get the DIO/DAO/DIS we know that UIP contains the
143  incoming packet */
144  switch(reason) {
145  case NBR_TABLE_REASON_RPL_DIO:
146  return find_removable_dio(&UIP_IP_BUF->srcipaddr, data);
147  case NBR_TABLE_REASON_RPL_DIS:
148  return find_worst_rank_nbr_lladdr();
149  case NBR_TABLE_REASON_IPV6_ND_AUTOFILL:
150  return find_worst_rank_nbr_lladdr();
151  default:
152  return NULL;
153  }
154 }
155 /*---------------------------------------------------------------------------*/
156 /** @}*/
#define UIP_IP_BUF
Direct access to IPv6 header.
Definition: uip.h:71
uip_ds6_nbr_t * uip_ds6_nbr_head(void)
Get the first neighbor cache in nbr_table.
Definition: uip-ds6-nbr.c:429
int rpl_neighbor_is_parent(rpl_nbr_t *nbr)
Tells whether a neighbor is in the parent set.
Definition: rpl-neighbor.c:290
All information related to a RPL neighbor.
Definition: rpl-types.h:136
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
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:237
Header file for the logging system
rpl_nbr_t * rpl_neighbor_get_from_lladdr(uip_lladdr_t *addr)
Returns a neighbor from its link-layer address.
Definition: rpl-neighbor.c:213
The default nbr_table entry (when UIP_DS6_NBR_MULTI_IPV6_ADDRS is disabled), that implements nbr cach...
Definition: uip-ds6-nbr.h:105