serialized LQ data is not always 4 bytes long, so we need a function to precalculate...
[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
54 #define PLUGIN_DESCR "Freifunk ETX metric based on the original design of Elektra and Thomas Lopatic"
55 #define PLUGIN_AUTHOR "Henning Rogge"
56
57 #define LQ_ALGORITHM_ETX_FF_NAME "etx_ff"
58
59 #define LQ_FF_QUICKSTART_INIT 4
60
61 #define LQ_PLUGIN_RELEVANT_COSTCHANGE_FF 16
62
63 static int lq_etxff_post_init(void);
64
65 static void lq_etxff_initialize(void);
66 static void lq_etxff_deinitialize(void);
67
68 static olsr_linkcost lq_etxff_calc_link_entry_cost(struct link_entry *);
69 static olsr_linkcost lq_etxff_calc_lq_hello_neighbor_cost(struct lq_hello_neighbor *);
70 static olsr_linkcost lq_etxff_calc_tc_mpr_addr_cost(struct tc_mpr_addr *);
71 static olsr_linkcost lq_etxff_calc_tc_edge_entry_cost(struct tc_edge_entry *);
72
73 static bool lq_etxff_is_relevant_costchange(olsr_linkcost c1, olsr_linkcost c2);
74
75 static olsr_linkcost lq_etxff_packet_loss_handler(struct link_entry *, bool);
76
77 static void lq_etxff_memorize_foreign_hello(struct link_entry *, struct lq_hello_neighbor *);
78 static void lq_etxff_copy_link_entry_lq_into_tc_mpr_addr(struct tc_mpr_addr *target, struct link_entry *source);
79 static void lq_etxff_copy_link_entry_lq_into_tc_edge_entry(struct tc_edge_entry *target, struct link_entry *source);
80 static void lq_etxff_copy_link_lq_into_neighbor(struct lq_hello_neighbor *target, struct link_entry *source);
81
82 static void lq_etxff_clear_link_entry(struct link_entry *);
83
84 static int lq_etxff_serialize_hello_lq(unsigned char *buff, struct lq_hello_neighbor *lq);
85 static int lq_etxff_serialize_tc_lq(unsigned char *buff, struct tc_mpr_addr *lq);
86 static void lq_etxff_deserialize_hello_lq(uint8_t const **curr, struct lq_hello_neighbor *lq);
87 static void lq_etxff_deserialize_tc_lq(uint8_t const **curr, struct tc_edge_entry *lq);
88
89 static char *lq_etxff_print_link_entry_lq(struct link_entry *entry, char separator, struct lqtextbuffer *buffer);
90 static char *lq_etxff_print_tc_edge_entry_lq(struct tc_edge_entry *ptr, char separator, struct lqtextbuffer *buffer);
91 static char *lq_etxff_print_cost(olsr_linkcost cost, struct lqtextbuffer *buffer);
92
93 static struct olsr_cookie_info *default_lq_ff_timer_cookie = NULL;
94
95 DEFINE_PLUGIN6_NP(PLUGIN_DESCR, PLUGIN_AUTHOR, NULL, lq_etxff_post_init, NULL, NULL, false)
96
97 /* etx lq plugin (freifunk fpm version) settings */
98 struct lq_handler lq_etxff_handler = {
99   "etx (freifunk)",
100
101   &lq_etxff_initialize,
102   &lq_etxff_deinitialize,
103
104   &lq_etxff_calc_link_entry_cost,
105   &lq_etxff_calc_lq_hello_neighbor_cost,
106   &lq_etxff_calc_tc_mpr_addr_cost,
107   &lq_etxff_calc_tc_edge_entry_cost,
108
109   &lq_etxff_is_relevant_costchange,
110
111   &lq_etxff_packet_loss_handler,
112
113   &lq_etxff_memorize_foreign_hello,
114   &lq_etxff_copy_link_entry_lq_into_tc_mpr_addr,
115   &lq_etxff_copy_link_entry_lq_into_tc_edge_entry,
116   &lq_etxff_copy_link_lq_into_neighbor,
117
118   &lq_etxff_clear_link_entry,
119   NULL,
120   NULL,
121   NULL,
122
123   &lq_etxff_serialize_hello_lq,
124   &lq_etxff_serialize_tc_lq,
125   &lq_etxff_deserialize_hello_lq,
126   &lq_etxff_deserialize_tc_lq,
127
128   &lq_etxff_print_link_entry_lq,
129   &lq_etxff_print_tc_edge_entry_lq,
130   &lq_etxff_print_cost,
131
132   sizeof(struct lq_etxff_tc_edge),
133   sizeof(struct lq_etxff_tc_mpr_addr),
134   sizeof(struct lq_etxff_lq_hello_neighbor),
135   sizeof(struct lq_etxff_link_entry),
136
137   LQ_HELLO_MESSAGE,
138   LQ_TC_MESSAGE,
139
140   4,4
141 };
142
143 static int lq_etxff_post_init(void) {
144   active_lq_handler = &lq_etxff_handler;
145   return 0;
146 }
147
148 static void
149 lq_etxff_packet_parser(struct olsr *olsr, struct interface *in_if, union olsr_ip_addr *from_addr)
150 {
151   const union olsr_ip_addr *main_addr;
152   struct lq_etxff_link_entry *lnk;
153   uint32_t seq_diff;
154
155   /* Find main address */
156   main_addr = olsr_lookup_main_addr_by_alias(from_addr);
157
158   /* Loopup link entry */
159   lnk = (struct lq_etxff_link_entry *)lookup_link_entry(from_addr, main_addr, in_if);
160   if (lnk == NULL) {
161     return;
162   }
163
164   if (lnk->last_seq_nr == olsr->olsr_seqno) {
165 #ifndef REMOVE_LOG_WARN
166     struct ipaddr_str buf;
167 #endif
168     OLSR_WARN(LOG_LQ_PLUGINS, "Got package with same sequence number from %s\n", olsr_ip_to_string(&buf, from_addr));
169     return;
170   }
171   if (lnk->last_seq_nr > olsr->olsr_seqno) {
172     seq_diff = (uint32_t) olsr->olsr_seqno + 65536 - lnk->last_seq_nr;
173   } else {
174     seq_diff = olsr->olsr_seqno - lnk->last_seq_nr;
175   }
176
177   /* Jump in sequence numbers ? */
178   if (seq_diff > 256) {
179     seq_diff = 1;
180   }
181
182   lnk->received[lnk->activePtr]++;
183   lnk->lost[lnk->activePtr] += (seq_diff - 1);
184
185   lnk->last_seq_nr = olsr->olsr_seqno;
186   lnk->missed_seconds = 0;
187 }
188
189 static void
190 lq_etxff_timer(void __attribute__ ((unused)) * context)
191 {
192   struct link_entry *link;
193   OLSR_FOR_ALL_LINK_ENTRIES(link) {
194     struct lq_etxff_link_entry *lq_link;
195     uint32_t ratio;
196     uint16_t i, received, lost;
197
198 #ifndef REMOVE_LOG_DEBUG
199     struct ipaddr_str buf;
200     // struct lqtextbuffer lqbuffer;
201 #endif
202     lq_link = (struct lq_etxff_link_entry *)link;
203
204     OLSR_DEBUG(LOG_LQ_PLUGINS, "LQ-FF new entry for %s: rec: %d lost: %d",
205                olsr_ip_to_string(&buf, &link->neighbor_iface_addr),
206                lq_link->received[lq_link->activePtr], lq_link->lost[lq_link->activePtr]);
207
208     received = 0;
209     lost = 0;
210
211     /* enlarge window if still in quickstart phase */
212     if (lq_link->windowSize < LQ_FF_WINDOW) {
213       lq_link->windowSize++;
214     }
215     for (i = 0; i < lq_link->windowSize; i++) {
216       received += lq_link->received[i];
217       lost += lq_link->lost[i];
218     }
219
220     OLSR_DEBUG(LOG_LQ_PLUGINS, " total-rec: %d total-lost: %d", received, lost);
221
222     /* calculate link quality */
223     if (received + lost == 0) {
224       lq_link->lq.valueLq = 0;
225     } else {
226
227       /* keep missed hello periods in mind (round up hello interval to seconds) */
228       uint32_t missed_hello_cost = lq_link->missed_seconds / ((lq_link->core.link_loss_timer->timer_period + 999) / 1000);
229       lost += missed_hello_cost * missed_hello_cost;
230
231       // start with link-loss-factor
232       ratio = link->loss_link_multiplier;
233
234       // calculate received/(received + loss) factor
235       ratio = ratio * received;
236       ratio = ratio / (received + lost);
237       ratio = (ratio * 255) >> 16;
238
239       lq_link->lq.valueLq = (uint8_t) (ratio);
240     }
241
242     // shift buffer
243     lq_link->activePtr = (lq_link->activePtr + 1) % LQ_FF_WINDOW;
244     lq_link->lost[lq_link->activePtr] = 0;
245     lq_link->received[lq_link->activePtr] = 0;
246     lq_link->missed_seconds++;
247   }
248   OLSR_FOR_ALL_LINK_ENTRIES_END(link);
249 }
250
251 static struct timer_entry *lq_etxff_timer_struct = NULL;
252
253 static void
254 lq_etxff_initialize(void)
255 {
256   /* Some cookies for stats keeping */
257   olsr_packetparser_add_function(&lq_etxff_packet_parser);
258   default_lq_ff_timer_cookie = olsr_alloc_cookie("Default Freifunk LQ", OLSR_COOKIE_TYPE_TIMER);
259   lq_etxff_timer_struct = olsr_start_timer(1000, 0, OLSR_TIMER_PERIODIC, &lq_etxff_timer, NULL, default_lq_ff_timer_cookie);
260 }
261
262 static void
263 lq_etxff_deinitialize(void)
264 {
265   olsr_stop_timer(lq_etxff_timer_struct);
266   olsr_packetparser_remove_function(&lq_etxff_packet_parser);
267 }
268
269 static olsr_linkcost
270 lq_etxff_calc_linkcost(struct lq_etxff_linkquality *lq)
271 {
272   olsr_linkcost cost;
273
274   if (lq->valueLq < (unsigned int)(255 * MINIMAL_USEFUL_LQ) || lq->valueNlq < (unsigned int)(255 * MINIMAL_USEFUL_LQ)) {
275     return LINK_COST_BROKEN;
276   }
277
278   cost = 65536 * 255 / (int)lq->valueLq * 255 / (int)lq->valueNlq;
279
280   if (cost > LINK_COST_BROKEN)
281     return LINK_COST_BROKEN;
282   if (cost == 0)
283     return 1;
284   return cost;
285 }
286
287 static olsr_linkcost
288 lq_etxff_calc_link_entry_cost(struct link_entry *link)
289 {
290   struct lq_etxff_link_entry *lq_link = (struct lq_etxff_link_entry *)link;
291
292   return lq_etxff_calc_linkcost(&lq_link->lq);
293 }
294
295 static olsr_linkcost
296 lq_etxff_calc_lq_hello_neighbor_cost(struct lq_hello_neighbor *neigh)
297 {
298   struct lq_etxff_lq_hello_neighbor *lq_neigh = (struct lq_etxff_lq_hello_neighbor *)neigh;
299
300   return lq_etxff_calc_linkcost(&lq_neigh->lq);
301 }
302
303 static olsr_linkcost
304 lq_etxff_calc_tc_mpr_addr_cost(struct tc_mpr_addr *mpr)
305 {
306   struct lq_etxff_tc_mpr_addr *lq_mpr = (struct lq_etxff_tc_mpr_addr *)mpr;
307
308   return lq_etxff_calc_linkcost(&lq_mpr->lq);
309 }
310
311 static olsr_linkcost
312 lq_etxff_calc_tc_edge_entry_cost(struct tc_edge_entry *edge)
313 {
314   struct lq_etxff_tc_edge *lq_edge = (struct lq_etxff_tc_edge *)edge;
315
316   return lq_etxff_calc_linkcost(&lq_edge->lq);
317 }
318
319 static bool
320 lq_etxff_is_relevant_costchange(olsr_linkcost c1, olsr_linkcost c2)
321 {
322   if (c1 > c2) {
323     return c2 - c1 > LQ_PLUGIN_RELEVANT_COSTCHANGE_FF;
324   }
325   return c1 - c2 > LQ_PLUGIN_RELEVANT_COSTCHANGE_FF;
326 }
327
328 static olsr_linkcost
329 lq_etxff_packet_loss_handler(struct link_entry *link, bool loss __attribute__ ((unused)))
330 {
331   return lq_etxff_calc_link_entry_cost(link);
332 }
333
334 static void
335 lq_etxff_memorize_foreign_hello(struct link_entry *target, struct lq_hello_neighbor *source)
336 {
337   struct lq_etxff_link_entry *lq_target = (struct lq_etxff_link_entry *)target;
338   struct lq_etxff_lq_hello_neighbor *lq_source = (struct lq_etxff_lq_hello_neighbor *)source;
339
340   if (source) {
341     lq_target->lq.valueNlq = lq_source->lq.valueLq;
342   } else {
343     lq_target->lq.valueNlq = 0;
344   }
345
346 }
347
348 static void
349 lq_etxff_copy_link_entry_lq_into_tc_mpr_addr(struct tc_mpr_addr *target, struct link_entry *source)
350 {
351   struct lq_etxff_tc_mpr_addr *lq_target = (struct lq_etxff_tc_mpr_addr *)target;
352   struct lq_etxff_link_entry *lq_source = (struct lq_etxff_link_entry *)source;
353
354   lq_target->lq = lq_source->lq;
355 }
356
357 static void
358 lq_etxff_copy_link_entry_lq_into_tc_edge_entry(struct tc_edge_entry *target, struct link_entry *source)
359 {
360   struct lq_etxff_tc_edge *lq_target = (struct lq_etxff_tc_edge *)target;
361   struct lq_etxff_link_entry *lq_source = (struct lq_etxff_link_entry *)source;
362
363   lq_target->lq = lq_source->lq;
364 }
365
366 static void
367 lq_etxff_copy_link_lq_into_neighbor(struct lq_hello_neighbor *target, struct link_entry *source)
368 {
369   struct lq_etxff_lq_hello_neighbor *lq_target = (struct lq_etxff_lq_hello_neighbor *)target;
370   struct lq_etxff_link_entry *lq_source = (struct lq_etxff_link_entry *)source;
371
372   lq_target->lq = lq_source->lq;
373 }
374
375 static void
376 lq_etxff_clear_link_entry(struct link_entry *link)
377 {
378   struct lq_etxff_link_entry *lq_link = (struct lq_etxff_link_entry *)link;
379   int i;
380
381   lq_link->windowSize = LQ_FF_QUICKSTART_INIT;
382   for (i = 0; i < LQ_FF_WINDOW; i++) {
383     lq_link->lost[i] = 3;
384   }
385 }
386
387 static int
388 lq_etxff_serialize_hello_lq(unsigned char *buff, struct lq_hello_neighbor *neigh)
389 {
390   struct lq_etxff_lq_hello_neighbor *lq_neigh = (struct lq_etxff_lq_hello_neighbor *)neigh;
391
392   buff[0] = (unsigned char)lq_neigh->lq.valueLq;
393   buff[1] = (unsigned char)lq_neigh->lq.valueNlq;
394   buff[2] = (unsigned char)(0);
395   buff[3] = (unsigned char)(0);
396
397   return 4;
398 }
399 static int
400 lq_etxff_serialize_tc_lq(unsigned char *buff, struct tc_mpr_addr *mpr)
401 {
402   struct lq_etxff_tc_mpr_addr *lq_mpr = (struct lq_etxff_tc_mpr_addr *)mpr;
403
404   buff[0] = (unsigned char)lq_mpr->lq.valueLq;
405   buff[1] = (unsigned char)lq_mpr->lq.valueNlq;
406   buff[2] = (unsigned char)(0);
407   buff[3] = (unsigned char)(0);
408
409   return 4;
410 }
411
412 static void
413 lq_etxff_deserialize_hello_lq(uint8_t const **curr, struct lq_hello_neighbor *neigh)
414 {
415   struct lq_etxff_lq_hello_neighbor *lq_neigh = (struct lq_etxff_lq_hello_neighbor *)neigh;
416
417   pkt_get_u8(curr, &lq_neigh->lq.valueLq);
418   pkt_get_u8(curr, &lq_neigh->lq.valueNlq);
419   pkt_ignore_u16(curr);
420
421 }
422 static void
423 lq_etxff_deserialize_tc_lq(uint8_t const **curr, struct tc_edge_entry *edge)
424 {
425   struct lq_etxff_tc_edge *lq_edge = (struct lq_etxff_tc_edge *)edge;
426
427   pkt_get_u8(curr, &lq_edge->lq.valueLq);
428   pkt_get_u8(curr, &lq_edge->lq.valueNlq);
429   pkt_ignore_u16(curr);
430 }
431
432 static char *
433 lq_etxff_print_lq(struct lq_etxff_linkquality *lq, char separator, struct lqtextbuffer *buffer)
434 {
435   int i = 0;
436
437   if (lq->valueLq == 255) {
438     strcpy(buffer->buf, "1.000");
439     i += 5;
440   } else {
441     i = sprintf(buffer->buf, "0.%03d", (lq->valueLq * 1000) / 255);
442   }
443   buffer->buf[i++] = separator;
444
445   if (lq->valueNlq == 255) {
446     strcpy(&buffer->buf[i], "1.000");
447   } else {
448     sprintf(&buffer->buf[i], "0.%03d", (lq->valueNlq * 1000) / 255);
449   }
450   return buffer->buf;
451 }
452
453 static char *
454 lq_etxff_print_link_entry_lq(struct link_entry *link, char separator, struct lqtextbuffer *buffer)
455 {
456   struct lq_etxff_link_entry *lq_link = (struct lq_etxff_link_entry *)link;
457
458   return lq_etxff_print_lq(&lq_link->lq, separator, buffer);
459 }
460
461 static char *
462 lq_etxff_print_tc_edge_entry_lq(struct tc_edge_entry *edge, char separator, struct lqtextbuffer *buffer)
463 {
464   struct lq_etxff_tc_edge *lq_edge = (struct lq_etxff_tc_edge *)edge;
465
466   return lq_etxff_print_lq(&lq_edge->lq, separator, buffer);
467 }
468
469 static char *
470 lq_etxff_print_cost(olsr_linkcost cost, struct lqtextbuffer *buffer)
471 {
472   // must calculate
473   uint32_t roundDown = cost >> 16;
474   uint32_t fraction = ((cost & 0xffff) * 1000) >> 16;
475
476   sprintf(buffer->buf, "%u.%03u", roundDown, fraction);
477   return buffer->buf;
478 }
479
480 /*
481  * Local Variables:
482  * c-basic-offset: 2
483  * indent-tabs-mode: nil
484  * End:
485  */