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