Contiki-NG
rpl-of0.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 * An implementation of RPL's objective function 0, RFC6552
33 *
34 * \author Joakim Eriksson <joakime@sics.se>, Nicolas Tsiftes <nvt@sics.se>
35 */
36
37/**
38 * \addtogroup uip
39 * @{
40 */
41
42#include "net/routing/rpl-classic/rpl.h"
43#include "net/routing/rpl-classic/rpl-private.h"
44#include "net/nbr-table.h"
45#include "net/link-stats.h"
46
47#include "sys/log.h"
48
49#define LOG_MODULE "RPL"
50#define LOG_LEVEL LOG_LEVEL_RPL
51
52/* Constants from RFC6552. We use the default values. */
53#define RANK_STRETCH 0 /* Must be in the range [0;5] */
54#define RANK_FACTOR 1 /* Must be in the range [1;4] */
55
56#define MIN_STEP_OF_RANK 1
57#define MAX_STEP_OF_RANK 9
58
59/*
60 * OF0 computes rank increase as follows:
61 *
62 * rank_increase = (RANK_FACTOR * STEP_OF_RANK + RANK_STRETCH) *
63 * min_hop_rank_increase
64 *
65 * STEP_OF_RANK is an implementation-specific scalar value in the
66 * range [1;9]. RFC6552 provides a default value of 3, but recommends
67 * to use a dynamic link metric such as ETX. */
68
69#define RPL_OF0_FIXED_SR 0
70#define RPL_OF0_ETX_BASED_SR 1
71/* Select RPL_OF0_FIXED_SR or RPL_OF0_ETX_BASED_SR */
72#ifdef RPL_OF0_CONF_SR
73#define RPL_OF0_SR RPL_OF0_CONF_SR
74#else /* RPL_OF0_CONF_SR */
75#define RPL_OF0_SR RPL_OF0_ETX_BASED_SR
76#endif /* RPL_OF0_CONF_SR */
77
78#if RPL_OF0_SR == RPL_OF0_FIXED_SR
79#define STEP_OF_RANK(p) (3)
80#elif RPL_OF0_SR == RPL_OF0_ETX_BASED_SR
81/* Numbers suggested by P. Thubert for in the 6TiSCH WG. Anything that
82 maps ETX to a step between 1 and 9 works. */
83#define STEP_OF_RANK(p) (((3 * parent_link_metric(p)) / LINK_STATS_ETX_DIVISOR) - 2)
84#endif /* RPL_OF0_SR */
85
86/*---------------------------------------------------------------------------*/
87static void
88reset(rpl_dag_t *dag)
89{
90 LOG_INFO("Reset OF0\n");
91}
92/*---------------------------------------------------------------------------*/
93#if RPL_WITH_DAO_ACK
94static void
95dao_ack_callback(rpl_parent_t *p, int status)
96{
97 if(status == RPL_DAO_ACK_UNABLE_TO_ADD_ROUTE_AT_ROOT) {
98 return;
99 }
100 /* Here we need to handle failed DAO's and other stuff. */
101 LOG_DBG("OF0 - DAO ACK received with status: %d\n", status);
102 if(status >= RPL_DAO_ACK_UNABLE_TO_ACCEPT) {
103 /* Punish the ETX as if this was 10 packets lost. */
104 link_stats_packet_sent(rpl_get_parent_lladdr(p), MAC_TX_OK, 10);
105 } else if(status == RPL_DAO_ACK_TIMEOUT) { /* timeout = no ack */
106 /* Punish the total lack of ACK with a similar punishment. */
107 link_stats_packet_sent(rpl_get_parent_lladdr(p), MAC_TX_OK, 10);
108 }
109}
110#endif /* RPL_WITH_DAO_ACK */
111/*---------------------------------------------------------------------------*/
112static uint16_t
113parent_link_metric(rpl_parent_t *p)
114{
115 /* OF0 operates without metric container; the only metric we have is ETX. */
116 const struct link_stats *stats = rpl_get_parent_link_stats(p);
117 return stats != NULL ? stats->etx : 0xffff;
118}
119/*---------------------------------------------------------------------------*/
120static uint16_t
121parent_rank_increase(rpl_parent_t *p)
122{
123 uint16_t min_hoprankinc;
124 if(p == NULL || p->dag == NULL || p->dag->instance == NULL) {
125 return RPL_INFINITE_RANK;
126 }
127 min_hoprankinc = p->dag->instance->min_hoprankinc;
128 return (RANK_FACTOR * STEP_OF_RANK(p) + RANK_STRETCH) * min_hoprankinc;
129}
130/*---------------------------------------------------------------------------*/
131static uint16_t
132parent_path_cost(rpl_parent_t *p)
133{
134 if(p == NULL) {
135 return 0xffff;
136 }
137 /* Path cost upper bound: 0xffff */
138 return MIN((uint32_t)p->rank + parent_link_metric(p), 0xffff);
139}
140/*---------------------------------------------------------------------------*/
141static rpl_rank_t
142rank_via_parent(rpl_parent_t *p)
143{
144 if(p == NULL) {
145 return RPL_INFINITE_RANK;
146 } else {
147 return MIN((uint32_t)p->rank + parent_rank_increase(p), RPL_INFINITE_RANK);
148 }
149}
150/*---------------------------------------------------------------------------*/
151static int
152parent_is_acceptable(rpl_parent_t *p)
153{
154 return STEP_OF_RANK(p) >= MIN_STEP_OF_RANK
155 && STEP_OF_RANK(p) <= MAX_STEP_OF_RANK;
156}
157/*---------------------------------------------------------------------------*/
158static int
159parent_has_usable_link(rpl_parent_t *p)
160{
161 return parent_is_acceptable(p);
162}
163/*---------------------------------------------------------------------------*/
164static rpl_parent_t *
165best_parent(rpl_parent_t *p1, rpl_parent_t *p2)
166{
167 rpl_dag_t *dag;
168 uint16_t p1_cost;
169 uint16_t p2_cost;
170 int p1_is_acceptable;
171 int p2_is_acceptable;
172
173 p1_is_acceptable = p1 != NULL && parent_is_acceptable(p1);
174 p2_is_acceptable = p2 != NULL && parent_is_acceptable(p2);
175
176 if(!p1_is_acceptable) {
177 return p2_is_acceptable ? p2 : NULL;
178 }
179 if(!p2_is_acceptable) {
180 return p1_is_acceptable ? p1 : NULL;
181 }
182
183 dag = p1->dag; /* Both parents are in the same DAG. */
184 p1_cost = parent_path_cost(p1);
185 p2_cost = parent_path_cost(p2);
186
187 /* Coarse-grained path costs (multiple of min_hoprankinc), we
188 operate without hysteresis. */
189 if(p1_cost != p2_cost) {
190 /* Pick parent with lowest path cost */
191 return p1_cost < p2_cost ? p1 : p2;
192 } else {
193 /* We have a tie! Stick to the current preferred parent if possible. */
194 if(p1 == dag->preferred_parent || p2 == dag->preferred_parent) {
195 return dag->preferred_parent;
196 }
197 /* None of the nodes is the current preferred parent; choose the
198 parent with best link metric. */
199 return parent_link_metric(p1) < parent_link_metric(p2) ? p1 : p2;
200 }
201}
202/*---------------------------------------------------------------------------*/
203static rpl_dag_t *
204best_dag(rpl_dag_t *d1, rpl_dag_t *d2)
205{
206 if(d1->grounded != d2->grounded) {
207 return d1->grounded ? d1 : d2;
208 }
209
210 if(d1->preference != d2->preference) {
211 return d1->preference > d2->preference ? d1 : d2;
212 }
213
214 return d1->rank < d2->rank ? d1 : d2;
215}
216/*---------------------------------------------------------------------------*/
217static void
218update_metric_container(rpl_instance_t *instance)
219{
220 instance->mc.type = RPL_DAG_MC_NONE;
221}
222/*---------------------------------------------------------------------------*/
223rpl_of_t rpl_of0 = {
224 reset,
225#if RPL_WITH_DAO_ACK
226 dao_ack_callback,
227#endif
228 parent_link_metric,
229 parent_has_usable_link,
230 parent_path_cost,
231 rank_via_parent,
232 best_parent,
233 best_dag,
234 update_metric_container,
235 RPL_OCP_OF0
236};
237
238/** @}*/
Header file for the logging system.
@ MAC_TX_OK
The MAC layer transmission was OK.
Definition: mac.h:87
RPL DAG structure.
Definition: rpl.h:138
RPL instance structure.
Definition: rpl.h:222
API for RPL objective functions (OF)
Definition: rpl.h:204