Contiki-NG
link-stats.c
1/*
2 * Copyright (c) 2015, SICS Swedish ICT.
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 * Authors: Simon Duquennoy <simonduq@sics.se>
31 * Atis Elsts <atis.elsts@edi.lv>
32 */
33
34#include "contiki.h"
35#include "sys/clock.h"
36#include "net/packetbuf.h"
37#include "net/nbr-table.h"
38#include "net/link-stats.h"
39#include <stdio.h>
40
41/* Log configuration */
42#include "sys/log.h"
43#define LOG_MODULE "Link Stats"
44#define LOG_LEVEL LOG_LEVEL_MAC
45
46/* Maximum value for the Tx count counter */
47#define TX_COUNT_MAX 32
48
49/* Statistics with no update in FRESHNESS_EXPIRATION_TIMEOUT is not fresh */
50#define FRESHNESS_EXPIRATION_TIME (10 * 60 * (clock_time_t)CLOCK_SECOND)
51/* Half time for the freshness counter */
52#define FRESHNESS_HALF_LIFE (15 * 60 * (clock_time_t)CLOCK_SECOND)
53/* Statistics are fresh if the freshness counter is FRESHNESS_TARGET or more */
54#define FRESHNESS_TARGET 4
55/* Maximum value for the freshness counter */
56#define FRESHNESS_MAX 16
57
58/* EWMA (exponential moving average) used to maintain statistics over time */
59#define EWMA_SCALE 100
60#define EWMA_ALPHA 10
61#define EWMA_BOOTSTRAP_ALPHA 25
62
63/* ETX fixed point divisor. 128 is the value used by RPL (RFC 6551 and RFC 6719) */
64#define ETX_DIVISOR LINK_STATS_ETX_DIVISOR
65/* In case of no-ACK, add ETX_NOACK_PENALTY to the real Tx count, as a penalty */
66#define ETX_NOACK_PENALTY 12
67/* Initial ETX value */
68#define ETX_DEFAULT 2
69
70#define RSSI_DIFF (LINK_STATS_RSSI_HIGH - LINK_STATS_RSSI_LOW)
71
72/* Generate error on incorrect link stats configuration values */
73#if RSSI_DIFF <= 0
74#error "RSSI_HIGH must be greater then RSSI_LOW"
75#endif
76
77/* Generate error if the initial ETX calculation would overflow uint16_t */
78#if ETX_DIVISOR * RSSI_DIFF >= 0x10000
79#error "RSSI math overflow"
80#endif
81
82/* Per-neighbor link statistics table */
83NBR_TABLE(struct link_stats, link_stats);
84
85/* Called at a period of FRESHNESS_HALF_LIFE */
86struct ctimer periodic_timer;
87
88/*---------------------------------------------------------------------------*/
89/* Returns the neighbor's link stats */
90const struct link_stats *
91link_stats_from_lladdr(const linkaddr_t *lladdr)
92{
93 return nbr_table_get_from_lladdr(link_stats, lladdr);
94}
95/*---------------------------------------------------------------------------*/
96/* Returns the neighbor's address given a link stats item */
97const linkaddr_t *
98link_stats_get_lladdr(const struct link_stats *stat)
99{
100 return nbr_table_get_lladdr(link_stats, stat);
101}
102/*---------------------------------------------------------------------------*/
103/* Are the statistics fresh? */
104int
105link_stats_is_fresh(const struct link_stats *stats)
106{
107 return (stats != NULL)
108 && clock_time() - stats->last_tx_time < FRESHNESS_EXPIRATION_TIME
109 && stats->freshness >= FRESHNESS_TARGET;
110}
111/*---------------------------------------------------------------------------*/
112#if LINK_STATS_INIT_ETX_FROM_RSSI
113/*
114 * Returns initial ETX value from an RSSI value.
115 * RSSI >= RSSI_HIGH -> use default ETX
116 * RSSI_LOW < RSSI < RSSI_HIGH -> ETX is a linear function of RSSI
117 * RSSI <= RSSI_LOW -> use minimal initial ETX
118 **/
119static uint16_t
120guess_etx_from_rssi(const struct link_stats *stats)
121{
122 if(stats != NULL) {
123 if(stats->rssi == LINK_STATS_RSSI_UNKNOWN) {
124 return ETX_DEFAULT * ETX_DIVISOR;
125 } else {
126 const int16_t rssi_delta = stats->rssi - LINK_STATS_RSSI_LOW;
127 const int16_t bounded_rssi_delta = BOUND(rssi_delta, 0, RSSI_DIFF);
128 /* Penalty is in the range from 0 to ETX_DIVISOR */
129 const uint16_t penalty = ETX_DIVISOR * bounded_rssi_delta / RSSI_DIFF;
130 /* ETX is the default ETX value + penalty */
131 const uint16_t etx = ETX_DIVISOR * ETX_DEFAULT + penalty;
132 return MIN(etx, LINK_STATS_ETX_INIT_MAX * ETX_DIVISOR);
133 }
134 }
135 return 0xffff;
136}
137#endif /* LINK_STATS_INIT_ETX_FROM_RSSI */
138/*---------------------------------------------------------------------------*/
139/* Packet sent callback. Updates stats for transmissions to lladdr */
140void
141link_stats_packet_sent(const linkaddr_t *lladdr, int status, int numtx)
142{
143 struct link_stats *stats;
144#if !LINK_STATS_ETX_FROM_PACKET_COUNT
145 uint16_t packet_etx;
146 uint8_t ewma_alpha;
147#endif /* !LINK_STATS_ETX_FROM_PACKET_COUNT */
148
149 if(status != MAC_TX_OK && status != MAC_TX_NOACK && status != MAC_TX_QUEUE_FULL) {
150 /* Do not penalize the ETX when collisions or transmission errors occur. */
151 return;
152 }
153
154 stats = nbr_table_get_from_lladdr(link_stats, lladdr);
155 if(stats == NULL) {
156 /* If transmission failed, do not add the neighbor, as the neighbor might not exist anymore */
157 if(status != MAC_TX_OK) {
158 return;
159 }
160
161 /* Add the neighbor */
162 stats = nbr_table_add_lladdr(link_stats, lladdr, NBR_TABLE_REASON_LINK_STATS, NULL);
163 if(stats == NULL) {
164 return; /* No space left, return */
165 }
166 stats->rssi = LINK_STATS_RSSI_UNKNOWN;
167 }
168
169 if(status == MAC_TX_QUEUE_FULL) {
170#if LINK_STATS_PACKET_COUNTERS
171 stats->cnt_current.num_queue_drops += 1;
172#endif
173 /* Do not penalize the ETX when the packet is dropped due to a full queue */
174 return;
175 }
176
177 /* Update last timestamp and freshness */
178 stats->last_tx_time = clock_time();
179 stats->freshness = MIN(stats->freshness + numtx, FRESHNESS_MAX);
180
181#if LINK_STATS_PACKET_COUNTERS
182 /* Update paket counters */
183 stats->cnt_current.num_packets_tx += numtx;
184 if(status == MAC_TX_OK) {
185 stats->cnt_current.num_packets_acked++;
186 }
187#endif
188
189 /* Add penalty in case of no-ACK */
190 if(status == MAC_TX_NOACK) {
191 numtx += ETX_NOACK_PENALTY;
192 }
193
194#if LINK_STATS_ETX_FROM_PACKET_COUNT
195 /* Compute ETX from packet and ACK count */
196 /* Halve both counter after TX_COUNT_MAX */
197 if(stats->tx_count + numtx > TX_COUNT_MAX) {
198 stats->tx_count /= 2;
199 stats->ack_count /= 2;
200 }
201 /* Update tx_count and ack_count */
202 stats->tx_count += numtx;
203 if(status == MAC_TX_OK) {
204 stats->ack_count++;
205 }
206 /* Compute ETX */
207 if(stats->ack_count > 0) {
208 stats->etx = ((uint16_t)stats->tx_count * ETX_DIVISOR) / stats->ack_count;
209 } else {
210 stats->etx = (uint16_t)MAX(ETX_NOACK_PENALTY, stats->tx_count) * ETX_DIVISOR;
211 }
212#else /* LINK_STATS_ETX_FROM_PACKET_COUNT */
213 /* Compute ETX using an EWMA */
214
215 /* ETX used for this update */
216 packet_etx = numtx * ETX_DIVISOR;
217 /* ETX alpha used for this update */
218 ewma_alpha = link_stats_is_fresh(stats) ? EWMA_ALPHA : EWMA_BOOTSTRAP_ALPHA;
219
220 if(stats->etx == 0) {
221 /* Initialize ETX */
222 stats->etx = packet_etx;
223 } else {
224 /* Compute EWMA and update ETX */
225 stats->etx = ((uint32_t)stats->etx * (EWMA_SCALE - ewma_alpha) +
226 (uint32_t)packet_etx * ewma_alpha) / EWMA_SCALE;
227 }
228#endif /* LINK_STATS_ETX_FROM_PACKET_COUNT */
229}
230/*---------------------------------------------------------------------------*/
231/* Packet input callback. Updates statistics for receptions on a given link */
232void
233link_stats_input_callback(const linkaddr_t *lladdr)
234{
235 struct link_stats *stats;
236 int16_t packet_rssi = packetbuf_attr(PACKETBUF_ATTR_RSSI);
237
238 stats = nbr_table_get_from_lladdr(link_stats, lladdr);
239 if(stats == NULL) {
240 /* Add the neighbor */
241 stats = nbr_table_add_lladdr(link_stats, lladdr, NBR_TABLE_REASON_LINK_STATS, NULL);
242 if(stats == NULL) {
243 return; /* No space left, return */
244 }
245 stats->rssi = LINK_STATS_RSSI_UNKNOWN;
246 }
247
248 if(stats->rssi == LINK_STATS_RSSI_UNKNOWN) {
249 /* Initialize RSSI */
250 stats->rssi = packet_rssi;
251 } else {
252 /* Update RSSI EWMA */
253 stats->rssi = ((int32_t)stats->rssi * (EWMA_SCALE - EWMA_ALPHA) +
254 (int32_t)packet_rssi * EWMA_ALPHA) / EWMA_SCALE;
255 }
256
257 if(stats->etx == 0) {
258 /* Initialize ETX */
259#if LINK_STATS_INIT_ETX_FROM_RSSI
260 stats->etx = guess_etx_from_rssi(stats);
261#else /* LINK_STATS_INIT_ETX_FROM_RSSI */
262 stats->etx = ETX_DEFAULT * ETX_DIVISOR;
263#endif /* LINK_STATS_INIT_ETX_FROM_RSSI */
264 }
265
266#if LINK_STATS_PACKET_COUNTERS
267 stats->cnt_current.num_packets_rx++;
268#endif
269}
270/*---------------------------------------------------------------------------*/
271#if LINK_STATS_PACKET_COUNTERS
272/*---------------------------------------------------------------------------*/
273static void
274print_and_update_counters(void)
275{
276 struct link_stats *stats;
277
278 for(stats = nbr_table_head(link_stats); stats != NULL;
279 stats = nbr_table_next(link_stats, stats)) {
280
281 struct link_packet_counter *c = &stats->cnt_current;
282
283 LOG_INFO("num packets: tx=%u ack=%u rx=%u queue_drops=%u to=",
284 c->num_packets_tx, c->num_packets_acked,
285 c->num_packets_rx, c->num_queue_drops);
286 LOG_INFO_LLADDR(link_stats_get_lladdr(stats));
287 LOG_INFO_("\n");
288
289 stats->cnt_total.num_packets_tx += stats->cnt_current.num_packets_tx;
290 stats->cnt_total.num_packets_acked += stats->cnt_current.num_packets_acked;
291 stats->cnt_total.num_packets_rx += stats->cnt_current.num_packets_rx;
292 stats->cnt_total.num_queue_drops += stats->cnt_current.num_queue_drops;
293 memset(&stats->cnt_current, 0, sizeof(stats->cnt_current));
294 }
295}
296/*---------------------------------------------------------------------------*/
297#endif /* LINK_STATS_PACKET_COUNTERS */
298/*---------------------------------------------------------------------------*/
299/* Periodic timer called at a period of FRESHNESS_HALF_LIFE */
300static void
301periodic(void *ptr)
302{
303 /* Age (by halving) freshness counter of all neighbors */
304 struct link_stats *stats;
305 ctimer_reset(&periodic_timer);
306 for(stats = nbr_table_head(link_stats); stats != NULL; stats = nbr_table_next(link_stats, stats)) {
307 stats->freshness >>= 1;
308 }
309
310#if LINK_STATS_PACKET_COUNTERS
311 print_and_update_counters();
312#endif
313}
314/*---------------------------------------------------------------------------*/
315/* Resets link-stats module */
316void
317link_stats_reset(void)
318{
319 struct link_stats *stats;
320 stats = nbr_table_head(link_stats);
321 while(stats != NULL) {
322 nbr_table_remove(link_stats, stats);
323 stats = nbr_table_next(link_stats, stats);
324 }
325}
326/*---------------------------------------------------------------------------*/
327/* Initializes link-stats module */
328void
329link_stats_init(void)
330{
331 nbr_table_register(link_stats, NULL);
332 ctimer_set(&periodic_timer, FRESHNESS_HALF_LIFE, periodic, NULL);
333}
clock_time_t clock_time(void)
Get the current clock time.
Definition: clock.c:118
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_reset(struct ctimer *c)
Reset a callback timer with the same interval as was previously set.
Definition: ctimer.c:125
Header file for the logging system.
@ MAC_TX_OK
The MAC layer transmission was OK.
Definition: mac.h:87
@ MAC_TX_NOACK
The MAC layer deferred the transmission for a later time.
Definition: mac.h:94
Header file for the Packet buffer (packetbuf) management.