af8cb5e5d13eb5376d4e506de53eb4bc0c6a82fc
[olsrd.git] / lib / lq_etx_ff / src / lq_plugin_etx_ff.c
1
2 /*
3  * The olsr.org Optimized Link-State Routing daemon(olsrd)
4  * Copyright (c) 2004-2009, the olsr.org team - see HISTORY file
5  * All rights reserved.
6  *
7  * Redistribution and use in source and binary forms, with or without
8  * modification, are permitted provided that the following conditions
9  * are met:
10  *
11  * * Redistributions of source code must retain the above copyright
12  *   notice, this list of conditions and the following disclaimer.
13  * * Redistributions in binary form must reproduce the above copyright
14  *   notice, this list of conditions and the following disclaimer in
15  *   the documentation and/or other materials provided with the
16  *   distribution.
17  * * Neither the name of olsr.org, olsrd nor the names of its
18  *   contributors may be used to endorse or promote products derived
19  *   from this software without specific prior written permission.
20  *
21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
24  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
25  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
26  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
27  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
28  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
29  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
31  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
32  * POSSIBILITY OF SUCH DAMAGE.
33  *
34  * Visit http://www.olsr.org for more information.
35  *
36  * If you find this software useful feel free to make a donation
37  * to the project. For more information see the website or contact
38  * the copyright holders.
39  *
40  */
41
42 #include "tc_set.h"
43 #include "link_set.h"
44 #include "lq_plugin.h"
45 #include "olsr_spf.h"
46 #include "lq_packet.h"
47 #include "olsr.h"
48 #include "lq_plugin_etx_ff.h"
49 #include "parser.h"
50 #include "mid_set.h"
51 #include "scheduler.h"
52 #include "olsr_logging.h"
53 #include "common/string.h"
54 #include "neighbor_table.h"
55
56 #define PLUGIN_DESCR "Freifunk ETX metric based on the original design of Elektra and Thomas Lopatic"
57 #define PLUGIN_AUTHOR "Henning Rogge"
58
59 #define LQ_ALGORITHM_ETX_FF_NAME "etx_ff"
60
61 #define LQ_FF_QUICKSTART_INIT 4
62
63 #define LQ_PLUGIN_RELEVANT_COSTCHANGE_FF 16
64
65 static bool lq_etxff_enable(void);
66
67 static void lq_etxff_initialize(void);
68 static void lq_etxff_deinitialize(void);
69
70 static olsr_linkcost lq_etxff_calc_link_entry_cost(struct link_entry *);
71 static olsr_linkcost lq_etxff_calc_lq_hello_neighbor_cost(struct lq_hello_neighbor *);
72 static olsr_linkcost lq_etxff_calc_tc_edge_entry_cost(struct tc_edge_entry *);
73
74 static void lq_etxff_hello_handler(struct link_entry *, bool);
75
76 static void lq_etxff_memorize_foreign_hello(struct link_entry *, struct lq_hello_neighbor *);
77 static void lq_etxff_copy_link_entry_lq_into_tc_edge_entry(struct tc_edge_entry *target, struct link_entry *source);
78
79 static void lq_etxff_clear_link_entry(struct link_entry *);
80 static void lq_etxff_clear_tc_edge_entry(struct tc_edge_entry *);
81
82 static void lq_etxff_serialize_hello_lq(uint8_t **curr, struct link_entry *link);
83 static void lq_etxff_serialize_tc_lq(uint8_t **curr, struct link_entry *link);
84 static void lq_etxff_deserialize_hello_lq(uint8_t const **curr, struct lq_hello_neighbor *lq);
85 static void lq_etxff_deserialize_tc_lq(uint8_t const **curr, struct tc_edge_entry *lq);
86
87 static int lq_etxff_get_linkentry_data(struct link_entry *, int);
88 static const char *lq_etxff_print_cost(olsr_linkcost cost, char *buffer, size_t bufsize);
89 static const char *lq_etxff_print_link_entry_lq(struct link_entry *entry, int index, char *buffer, size_t bufsize);
90
91 static struct olsr_timer_info *default_lq_ff_timer_info = NULL;
92
93 OLSR_PLUGIN6_NP() {
94   .descr = PLUGIN_DESCR,
95   .author = PLUGIN_AUTHOR,
96   .enable = lq_etxff_enable,
97   .type = PLUGIN_TYPE_LQ
98 };
99
100 /* etx lq plugin (freifunk fpm version) settings */
101 struct lq_linkdata_type lq_etxff_linktypes[] = {
102   { "ETX", 5, 65536, 65536*2, 65536*4, INT32_MAX },
103   { "LQ", 5, 255, 240, 192, 0 },
104   { "NLQ", 5, 255, 240, 192, 0 }
105 };
106
107 struct lq_handler lq_etxff_handler = {
108   "etx (freifunk)",
109
110   &lq_etxff_initialize,
111   &lq_etxff_deinitialize,
112
113   &lq_etxff_calc_link_entry_cost,
114   &lq_etxff_calc_lq_hello_neighbor_cost,
115   &lq_etxff_calc_tc_edge_entry_cost,
116
117   &lq_etxff_hello_handler,
118
119   &lq_etxff_memorize_foreign_hello,
120   &lq_etxff_copy_link_entry_lq_into_tc_edge_entry,
121
122   &lq_etxff_clear_link_entry,
123   NULL,
124   &lq_etxff_clear_tc_edge_entry,
125
126   &lq_etxff_serialize_hello_lq,
127   &lq_etxff_serialize_tc_lq,
128   &lq_etxff_deserialize_hello_lq,
129   &lq_etxff_deserialize_tc_lq,
130
131   &lq_etxff_get_linkentry_data,
132   &lq_etxff_print_cost,
133   &lq_etxff_print_link_entry_lq,
134
135   lq_etxff_linktypes,
136   ARRAYSIZE(lq_etxff_linktypes),
137
138   sizeof(struct lq_etxff_tc_edge),
139   sizeof(struct lq_etxff_lq_hello_neighbor),
140   sizeof(struct lq_etxff_link_entry),
141
142   LQ_HELLO_MESSAGE,
143   LQ_TC_MESSAGE,
144
145   4,4
146 };
147
148 static bool lq_etxff_enable(void) {
149   active_lq_handler = &lq_etxff_handler;
150   return false;
151 }
152
153 static void
154 lq_etxff_packet_parser(struct olsr_packet *pkt, uint8_t *binary __attribute__ ((unused)),
155     struct interface *in_if, union olsr_ip_addr *from_addr)
156 {
157   const union olsr_ip_addr *main_addr;
158   struct lq_etxff_link_entry *lnk;
159   uint32_t seq_diff;
160
161   /* Find main address */
162   main_addr = olsr_lookup_main_addr_by_alias(from_addr);
163
164   /* Loopup link entry */
165   lnk = (struct lq_etxff_link_entry *)lookup_link_entry(from_addr, main_addr, in_if);
166   if (lnk == NULL) {
167     return;
168   }
169
170   if (lnk->last_seq_nr == pkt->seqno) {
171 #ifndef REMOVE_LOG_WARN
172     struct ipaddr_str buf;
173 #endif
174     OLSR_WARN(LOG_LQ_PLUGINS, "Got package with same sequence number from %s, if=%s, seq=0x%04x\n",
175         olsr_ip_to_string(&buf, from_addr), in_if->int_name, pkt->seqno);
176     return;
177   }
178   if (lnk->last_seq_nr > pkt->seqno) {
179     seq_diff = (uint32_t) pkt->seqno + 65536 - lnk->last_seq_nr;
180   } else {
181     seq_diff = pkt->seqno - lnk->last_seq_nr;
182   }
183
184   /* Jump in sequence numbers ? */
185   if (seq_diff > 256) {
186     seq_diff = 1;
187   }
188
189   lnk->received[lnk->activePtr]++;
190   lnk->lost[lnk->activePtr] += (seq_diff - 1);
191
192   lnk->last_seq_nr = pkt->seqno;
193   lnk->missed_seconds = 0;
194 }
195
196 static void
197 lq_etxff_timer(void __attribute__ ((unused)) * context)
198 {
199   struct link_entry *link;
200   struct list_iterator iterator;
201   struct nbr_entry *nbr;
202
203   OLSR_FOR_ALL_LINK_ENTRIES(link, iterator) {
204     struct lq_etxff_link_entry *lq_link;
205     uint32_t ratio;
206     uint16_t i, received, lost;
207
208 #ifndef REMOVE_LOG_DEBUG
209     struct ipaddr_str buf;
210     // struct lqtextbuffer lqbuffer;
211 #endif
212     lq_link = (struct lq_etxff_link_entry *)link;
213
214     OLSR_DEBUG(LOG_LQ_PLUGINS, "LQ-FF new entry for %s: rec: %d lost: %d",
215                olsr_ip_to_string(&buf, &link->neighbor_iface_addr),
216                lq_link->received[lq_link->activePtr], lq_link->lost[lq_link->activePtr]);
217
218     received = 0;
219     lost = 0;
220
221     /* enlarge window if still in quickstart phase */
222     if (lq_link->windowSize < LQ_FF_WINDOW) {
223       lq_link->windowSize++;
224     }
225     for (i = 0; i < lq_link->windowSize; i++) {
226       received += lq_link->received[i];
227       lost += lq_link->lost[i];
228     }
229
230     OLSR_DEBUG(LOG_LQ_PLUGINS, " total-rec: %d total-lost: %d", received, lost);
231
232     /* calculate link quality */
233     if (received + lost == 0) {
234       lq_link->lq.valueLq = 0;
235     } else {
236
237       /* keep missed hello periods in mind (round up hello interval to seconds) */
238       uint32_t missed_hello_cost = lq_link->missed_seconds / ((lq_link->core.link_loss_timer->timer_period + 999) / 1000);
239       lost += missed_hello_cost * missed_hello_cost;
240
241       // start with link-loss-factor
242       ratio = link->loss_link_multiplier;
243
244       // calculate received/(received + loss) factor
245       ratio = ratio * received;
246       ratio = ratio / (received + lost);
247       ratio = (ratio * 255) >> 16;
248
249       lq_link->lq.valueLq = (uint8_t) (ratio);
250     }
251
252     // shift buffer
253     lq_link->activePtr = (lq_link->activePtr + 1) % LQ_FF_WINDOW;
254     lq_link->lost[lq_link->activePtr] = 0;
255     lq_link->received[lq_link->activePtr] = 0;
256     lq_link->missed_seconds++;
257
258     /* update linkcost */
259     link->linkcost = lq_etxff_calc_link_entry_cost(link);
260   }
261
262   OLSR_FOR_ALL_NBR_ENTRIES(nbr, iterator) {
263     olsr_neighbor_cost_may_changed(nbr);
264   }
265 }
266
267 static struct timer_entry *lq_etxff_timer_struct = NULL;
268
269 static void
270 lq_etxff_initialize(void)
271 {
272   /* Some cookies for stats keeping */
273   olsr_packetparser_add_function(&lq_etxff_packet_parser);
274   default_lq_ff_timer_info = olsr_alloc_timerinfo("Default Freifunk LQ",  &lq_etxff_timer, true);
275   lq_etxff_timer_struct = olsr_start_timer(1000, 0, NULL, default_lq_ff_timer_info);
276 }
277
278 static void
279 lq_etxff_deinitialize(void)
280 {
281   olsr_stop_timer(lq_etxff_timer_struct);
282   olsr_packetparser_remove_function(&lq_etxff_packet_parser);
283 }
284
285 static olsr_linkcost
286 lq_etxff_calc_linkcost(struct lq_etxff_linkquality *lq)
287 {
288   olsr_linkcost cost;
289
290   if (lq->valueLq < (unsigned int)(255 * MINIMAL_USEFUL_LQ) || lq->valueNlq < (unsigned int)(255 * MINIMAL_USEFUL_LQ)) {
291     return LINK_COST_BROKEN;
292   }
293
294   cost = 65536 * 255 / (int)lq->valueLq * 255 / (int)lq->valueNlq;
295
296   if (cost > LINK_COST_BROKEN)
297     return LINK_COST_BROKEN;
298   if (cost == 0)
299     return 1;
300   return cost;
301 }
302
303 static olsr_linkcost
304 lq_etxff_calc_link_entry_cost(struct link_entry *link)
305 {
306   struct lq_etxff_link_entry *lq_link = (struct lq_etxff_link_entry *)link;
307
308   return lq_etxff_calc_linkcost(&lq_link->lq);
309 }
310
311 static olsr_linkcost
312 lq_etxff_calc_lq_hello_neighbor_cost(struct lq_hello_neighbor *neigh)
313 {
314   struct lq_etxff_lq_hello_neighbor *lq_neigh = (struct lq_etxff_lq_hello_neighbor *)neigh;
315
316   return lq_etxff_calc_linkcost(&lq_neigh->lq);
317 }
318
319 static olsr_linkcost
320 lq_etxff_calc_tc_edge_entry_cost(struct tc_edge_entry *edge)
321 {
322   struct lq_etxff_tc_edge *lq_edge = (struct lq_etxff_tc_edge *)edge;
323
324   return lq_etxff_calc_linkcost(&lq_edge->lq);
325 }
326
327 static void
328 lq_etxff_hello_handler(struct link_entry *link __attribute__ ((unused)), bool loss __attribute__ ((unused)))
329 {
330 }
331
332 static void
333 lq_etxff_memorize_foreign_hello(struct link_entry *target, struct lq_hello_neighbor *source)
334 {
335   struct lq_etxff_link_entry *lq_target = (struct lq_etxff_link_entry *)target;
336   struct lq_etxff_lq_hello_neighbor *lq_source = (struct lq_etxff_lq_hello_neighbor *)source;
337
338   if (source) {
339     lq_target->lq.valueNlq = lq_source->lq.valueLq;
340   } else {
341     lq_target->lq.valueNlq = 0;
342   }
343
344 }
345
346 static void
347 lq_etxff_copy_link_entry_lq_into_tc_edge_entry(struct tc_edge_entry *target, struct link_entry *source)
348 {
349   struct lq_etxff_tc_edge *lq_target = (struct lq_etxff_tc_edge *)target;
350   struct lq_etxff_link_entry *lq_source = (struct lq_etxff_link_entry *)source;
351
352   lq_target->lq = lq_source->lq;
353 }
354
355 static void
356 lq_etxff_clear_link_entry(struct link_entry *link)
357 {
358   struct lq_etxff_link_entry *lq_link = (struct lq_etxff_link_entry *)link;
359   int i;
360
361   lq_link->windowSize = LQ_FF_QUICKSTART_INIT;
362   for (i = 0; i < LQ_FF_WINDOW; i++) {
363     lq_link->lost[i] = 3;
364   }
365 }
366
367 static void
368 lq_etxff_clear_tc_edge_entry(struct tc_edge_entry *edge) {
369   struct lq_etxff_tc_edge *lq_edge = (struct lq_etxff_tc_edge *)edge;
370
371   memset (&lq_edge->lq, 0, sizeof(lq_edge->lq));
372 }
373
374 static void
375 lq_etxff_serialize_hello_lq(uint8_t **curr, struct link_entry *link)
376 {
377   struct lq_etxff_link_entry *lq_link = (struct lq_etxff_link_entry *)link;
378
379   pkt_put_u8(curr, lq_link->lq.valueLq);
380   pkt_put_u8(curr, lq_link->lq.valueNlq);
381   pkt_put_u16(curr, 0);
382 }
383 static void
384 lq_etxff_serialize_tc_lq(uint8_t **curr, struct link_entry *link)
385 {
386   struct lq_etxff_link_entry *lq_link = (struct lq_etxff_link_entry *)link;
387
388   pkt_put_u8(curr, lq_link->lq.valueLq);
389   pkt_put_u8(curr, lq_link->lq.valueNlq);
390   pkt_put_u16(curr, 0);
391 }
392
393 static void
394 lq_etxff_deserialize_hello_lq(uint8_t const **curr, struct lq_hello_neighbor *neigh)
395 {
396   struct lq_etxff_lq_hello_neighbor *lq_neigh = (struct lq_etxff_lq_hello_neighbor *)neigh;
397
398   pkt_get_u8(curr, &lq_neigh->lq.valueLq);
399   pkt_get_u8(curr, &lq_neigh->lq.valueNlq);
400   pkt_ignore_u16(curr);
401
402 }
403 static void
404 lq_etxff_deserialize_tc_lq(uint8_t const **curr, struct tc_edge_entry *edge)
405 {
406   struct lq_etxff_tc_edge *lq_edge = (struct lq_etxff_tc_edge *)edge;
407
408   pkt_get_u8(curr, &lq_edge->lq.valueLq);
409   pkt_get_u8(curr, &lq_edge->lq.valueNlq);
410   pkt_ignore_u16(curr);
411 }
412
413 static int
414 lq_etxff_get_linkentry_data(struct link_entry *link, int idx) {
415   struct lq_etxff_link_entry *lq = (struct lq_etxff_link_entry *)link;
416   return idx == 1 ? lq->lq.valueLq : lq->lq.valueNlq;
417 }
418
419 static const char *
420 lq_etxff_print_link_entry_lq(struct link_entry *link, int idx, char *buffer, size_t bufsize)
421 {
422   struct lq_etxff_link_entry *lq = (struct lq_etxff_link_entry *)link;
423   uint8_t value;
424
425   if (idx == 1) {
426     value = lq->lq.valueLq;
427   }
428   else {
429     value = lq->lq.valueNlq;
430   }
431
432   if (value == 255) {
433     strscpy(buffer, "1.000", bufsize);
434   } else {
435     snprintf(buffer, bufsize, "0.%03d", (value * 1000) / 255);
436   }
437   return buffer;
438 }
439
440 static const char *
441 lq_etxff_print_cost(olsr_linkcost cost, char *buffer, size_t bufsize)
442 {
443   // must calculate
444   uint32_t roundDown = cost >> 16;
445   uint32_t fraction = ((cost & 0xffff) * 1000) >> 16;
446
447   snprintf(buffer, bufsize, "%u.%03u", roundDown, fraction);
448   return buffer;
449 }
450
451 /*
452  * Local Variables:
453  * c-basic-offset: 2
454  * indent-tabs-mode: nil
455  * End:
456  */