4849a21ab14cebf6dd8084926a75a8aa1344a821
[olsrd.git] / src / lq_plugin_default_ffeth.c
1
2 /*
3  * The olsr.org Optimized Link-State Routing daemon(olsrd)
4  * Copyright (c) 2008 Henning Rogge <rogge@fgan.de>
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 "packet.h"
48 #include "olsr.h"
49 #include "lq_plugin_default_ffeth.h"
50 #include "parser.h"
51 #include "fpm.h"
52 #include "mid_set.h"
53 #include "scheduler.h"
54 #include "log.h"
55
56 #define LQ_PLUGIN_LC_MULTIPLIER 1024
57 #define LQ_PLUGIN_RELEVANT_COSTCHANGE_FF 16
58
59 static void default_lq_initialize_ffeth(void);
60
61 static olsr_linkcost default_lq_calc_cost_ffeth(const void *lq);
62
63 static void default_lq_packet_loss_worker_ffeth(struct link_entry *link, void *lq, bool lost);
64 static void default_lq_memorize_foreign_hello_ffeth(void *local, void *foreign);
65
66 static int default_lq_serialize_hello_lq_pair_ffeth(unsigned char *buff, void *lq);
67 static void default_lq_deserialize_hello_lq_pair_ffeth(const uint8_t ** curr, void *lq);
68 static int default_lq_serialize_tc_lq_pair_ffeth(unsigned char *buff, void *lq);
69 static void default_lq_deserialize_tc_lq_pair_ffeth(const uint8_t ** curr, void *lq);
70
71 static void default_lq_copy_link2neigh_ffeth(void *t, void *s);
72 static void default_lq_copy_link2tc_ffeth(void *target, void *source);
73 static void default_lq_clear_ffeth(void *target);
74 static void default_lq_clear_ffeth_hello(void *target);
75
76 static const char *default_lq_print_ffeth(void *ptr, char separator, struct lqtextbuffer *buffer);
77 static const char *default_lq_print_cost_ffeth(olsr_linkcost cost, struct lqtextbuffer *buffer);
78
79 /* etx lq plugin (freifunk fpm version) settings */
80 struct lq_handler lq_etx_ffeth_handler = {
81   &default_lq_initialize_ffeth,
82   &default_lq_calc_cost_ffeth,
83   &default_lq_calc_cost_ffeth,
84
85   &default_lq_packet_loss_worker_ffeth,
86
87   &default_lq_memorize_foreign_hello_ffeth,
88   &default_lq_copy_link2neigh_ffeth,
89   &default_lq_copy_link2tc_ffeth,
90   &default_lq_clear_ffeth_hello,
91   &default_lq_clear_ffeth,
92
93   &default_lq_serialize_hello_lq_pair_ffeth,
94   &default_lq_serialize_tc_lq_pair_ffeth,
95   &default_lq_deserialize_hello_lq_pair_ffeth,
96   &default_lq_deserialize_tc_lq_pair_ffeth,
97
98   &default_lq_print_ffeth,
99   &default_lq_print_ffeth,
100   &default_lq_print_cost_ffeth,
101
102   sizeof(struct default_lq_ffeth_hello),
103   sizeof(struct default_lq_ffeth),
104   4,
105   4
106 };
107
108 static void
109 default_lq_ffeth_handle_lqchange(void) {
110   struct default_lq_ffeth_hello *lq;
111   struct ipaddr_str buf;
112   struct link_entry *link;
113
114   bool triggered = false;
115
116   OLSR_FOR_ALL_LINK_ENTRIES(link) {
117     bool relevant = false;
118     lq = (struct default_lq_ffeth_hello *)link->linkquality;
119
120 #if 0
121   fprintf(stderr, "%s: old = %u/%u   new = %u/%u\n", olsr_ip_to_string(&buf, &link->neighbor_iface_addr),
122       lq->smoothed_lq.valueLq, lq->smoothed_lq.valueNlq,
123       lq->lq.valueLq, lq->lq.valueNlq);
124 #endif
125
126     if (lq->smoothed_lq.valueLq < lq->lq.valueLq) {
127       if (lq->lq.valueLq >= 254 || lq->lq.valueLq - lq->smoothed_lq.valueLq > lq->smoothed_lq.valueLq/10) {
128         relevant = true;
129       }
130     }
131     else if (lq->smoothed_lq.valueLq > lq->lq.valueLq) {
132       if (lq->smoothed_lq.valueLq - lq->lq.valueLq > lq->smoothed_lq.valueLq/10) {
133         relevant = true;
134       }
135     }
136     if (lq->smoothed_lq.valueNlq < lq->lq.valueNlq) {
137       if (lq->lq.valueNlq >= 254 || lq->lq.valueNlq - lq->smoothed_lq.valueNlq > lq->smoothed_lq.valueNlq/10) {
138         relevant = true;
139       }
140     }
141     else if (lq->smoothed_lq.valueNlq > lq->lq.valueNlq) {
142       if (lq->smoothed_lq.valueNlq - lq->lq.valueNlq > lq->smoothed_lq.valueNlq/10) {
143         relevant = true;
144       }
145     }
146
147     if (relevant) {
148       memcpy(&lq->smoothed_lq, &lq->lq, sizeof(struct default_lq_ffeth));
149       link->linkcost = default_lq_calc_cost_ffeth(&lq->smoothed_lq);
150       triggered = true;
151     }
152   } OLSR_FOR_ALL_LINK_ENTRIES_END(link)
153
154   if (!triggered) {
155     return;
156   }
157
158   OLSR_FOR_ALL_LINK_ENTRIES(link) {
159     lq = (struct default_lq_ffeth_hello *)link->linkquality;
160
161     if (lq->smoothed_lq.valueLq >= 254 && lq->smoothed_lq.valueNlq >= 254) {
162       continue;
163     }
164
165     if (lq->smoothed_lq.valueLq == lq->lq.valueLq && lq->smoothed_lq.valueNlq == lq->lq.valueNlq) {
166       continue;
167     }
168
169     memcpy(&lq->smoothed_lq, &lq->lq, sizeof(struct default_lq_ffeth));
170     link->linkcost = default_lq_calc_cost_ffeth(&lq->smoothed_lq);
171   } OLSR_FOR_ALL_LINK_ENTRIES_END(link)
172
173   olsr_relevant_linkcost_change();
174 }
175
176 static void
177 default_lq_parser_ffeth(struct olsr *olsr, struct interface *in_if, union olsr_ip_addr *from_addr)
178 {
179   const union olsr_ip_addr *main_addr;
180   struct link_entry *lnk;
181   struct default_lq_ffeth_hello *lq;
182   uint32_t seq_diff;
183
184   /* Find main address */
185   main_addr = mid_lookup_main_addr(from_addr);
186
187   /* Loopup link entry */
188   lnk = lookup_link_entry(from_addr, main_addr, in_if);
189   if (lnk == NULL) {
190     return;
191   }
192
193   lq = (struct default_lq_ffeth_hello *)lnk->linkquality;
194
195   /* ignore double package */
196   if (lq->last_seq_nr == olsr->olsr_seqno) {
197     struct ipaddr_str buf;
198     olsr_syslog(OLSR_LOG_INFO, "detected duplicate packet with seqnr %d from %s on %s (%d Bytes)",
199                 olsr->olsr_seqno,olsr_ip_to_string(&buf, from_addr),in_if->int_name,ntohs(olsr->olsr_packlen));
200     return;
201   }
202
203   if (lq->last_seq_nr > olsr->olsr_seqno) {
204     seq_diff = (uint32_t) olsr->olsr_seqno + 65536 - lq->last_seq_nr;
205   } else {
206     seq_diff = olsr->olsr_seqno - lq->last_seq_nr;
207   }
208
209   /* Jump in sequence numbers ? */
210   if (seq_diff > 256) {
211     seq_diff = 1;
212   }
213
214   lq->received[lq->activePtr]++;
215   lq->total[lq->activePtr] += seq_diff;
216
217   lq->last_seq_nr = olsr->olsr_seqno;
218   lq->missed_hellos = 0;
219 }
220
221 static void
222 default_lq_ffeth_timer(void __attribute__ ((unused)) * context)
223 {
224   struct link_entry *link;
225
226   OLSR_FOR_ALL_LINK_ENTRIES(link) {
227     struct default_lq_ffeth_hello *tlq = (struct default_lq_ffeth_hello *)link->linkquality;
228     fpm ratio;
229     int i, received, total;
230
231     received = 0;
232     total = 0;
233
234     /* enlarge window if still in quickstart phase */
235     if (tlq->windowSize < LQ_FFETH_WINDOW) {
236       tlq->windowSize++;
237     }
238     for (i = 0; i < tlq->windowSize; i++) {
239       received += tlq->received[i];
240       total += tlq->total[i];
241     }
242
243     /* calculate link quality */
244     if (total == 0) {
245       tlq->lq.valueLq = 0;
246     } else {
247       // start with link-loss-factor
248       ratio = fpmidiv(itofpm(link->loss_link_multiplier), LINK_LOSS_MULTIPLIER);
249
250       /* keep missed hello periods in mind (round up hello interval to seconds) */
251       if (tlq->missed_hellos > 1) {
252         received = received - received * tlq->missed_hellos * link->inter->hello_etime/1000 / LQ_FFETH_WINDOW;
253       }
254
255       // calculate received/total factor
256       ratio = fpmmuli(ratio, received);
257       ratio = fpmidiv(ratio, total);
258       ratio = fpmmuli(ratio, 255);
259
260       tlq->lq.valueLq = (uint8_t) (fpmtoi(ratio));
261     }
262
263     /* ethernet booster */
264     if (link->inter->mode == IF_MODE_ETHER) {
265       if (tlq->lq.valueLq > (uint8_t)(0.95 * 255)) {
266         tlq->perfect_eth = true;
267       }
268       else if (tlq->lq.valueLq > (uint8_t)(0.90 * 255)) {
269         tlq->perfect_eth = false;
270       }
271
272       if (tlq->perfect_eth) {
273         tlq->lq.valueLq = 255;
274       }
275     }
276     else if (link->inter->mode != IF_MODE_ETHER && tlq->lq.valueLq > 0) {
277       tlq->lq.valueLq--;
278     }
279
280     // shift buffer
281     tlq->activePtr = (tlq->activePtr + 1) % LQ_FFETH_WINDOW;
282     tlq->total[tlq->activePtr] = 0;
283     tlq->received[tlq->activePtr] = 0;
284   } OLSR_FOR_ALL_LINK_ENTRIES_END(link);
285
286   default_lq_ffeth_handle_lqchange();
287 }
288
289 static void
290 default_lq_initialize_ffeth(void)
291 {
292   if (olsr_cnf->lq_nat_thresh < 1.0) {
293     fprintf(stderr, "Warning, nat_treshold < 1.0 is more likely to produce loops with etx_ffeth\n");
294   }
295   olsr_packetparser_add_function(&default_lq_parser_ffeth);
296   olsr_start_timer(1000, 0, OLSR_TIMER_PERIODIC, &default_lq_ffeth_timer, NULL, 0);
297 }
298
299 static olsr_linkcost
300 default_lq_calc_cost_ffeth(const void *ptr)
301 {
302   const struct default_lq_ffeth *lq = ptr;
303   olsr_linkcost cost;
304   bool ether;
305   int lq_int, nlq_int;
306
307   if (lq->valueLq < (unsigned int)(255 * MINIMAL_USEFUL_LQ) || lq->valueNlq < (unsigned int)(255 * MINIMAL_USEFUL_LQ)) {
308     return LINK_COST_BROKEN;
309   }
310
311   ether = lq->valueLq == 255 && lq->valueNlq == 255;
312
313   lq_int = (int)lq->valueLq;
314   if (lq_int > 0 && lq_int < 255) {
315     lq_int++;
316   }
317
318   nlq_int = (int)lq->valueNlq;
319   if (nlq_int > 0 && nlq_int < 255) {
320     nlq_int++;
321   }
322   cost = fpmidiv(itofpm(255 * 255), lq_int * nlq_int);
323   if (ether) {
324     /* ethernet boost */
325     cost /= 10;
326   }
327
328   if (cost > LINK_COST_BROKEN)
329     return LINK_COST_BROKEN;
330   if (cost == 0)
331     return 1;
332   return cost;
333 }
334
335 static int
336 default_lq_serialize_hello_lq_pair_ffeth(unsigned char *buff, void *ptr)
337 {
338   struct default_lq_ffeth *lq = ptr;
339
340   buff[0] = (unsigned char)(0);
341   buff[1] = (unsigned char)(0);
342   buff[2] = (unsigned char)lq->valueLq;
343   buff[3] = (unsigned char)lq->valueNlq;
344
345   return 4;
346 }
347
348 static void
349 default_lq_deserialize_hello_lq_pair_ffeth(const uint8_t ** curr, void *ptr)
350 {
351   struct default_lq_ffeth *lq = ptr;
352
353   pkt_ignore_u16(curr);
354   pkt_get_u8(curr, &lq->valueLq);
355   pkt_get_u8(curr, &lq->valueNlq);
356 }
357
358 static int
359 default_lq_serialize_tc_lq_pair_ffeth(unsigned char *buff, void *ptr)
360 {
361   struct default_lq_ffeth *lq = ptr;
362
363   buff[0] = (unsigned char)(0);
364   buff[1] = (unsigned char)(0);
365   buff[2] = (unsigned char)lq->valueLq;
366   buff[3] = (unsigned char)lq->valueNlq;
367
368   return 4;
369 }
370
371 static void
372 default_lq_deserialize_tc_lq_pair_ffeth(const uint8_t ** curr, void *ptr)
373 {
374   struct default_lq_ffeth *lq = ptr;
375
376   pkt_ignore_u16(curr);
377   pkt_get_u8(curr, &lq->valueLq);
378   pkt_get_u8(curr, &lq->valueNlq);
379 }
380
381 static void
382 default_lq_packet_loss_worker_ffeth(struct link_entry *link,
383     void __attribute__ ((unused)) *ptr, bool lost)
384 {
385   struct default_lq_ffeth_hello *tlq = (struct default_lq_ffeth_hello *)link->linkquality;
386
387   if (lost) {
388     tlq->missed_hellos++;
389   }
390   return;
391 }
392
393 static void
394 default_lq_memorize_foreign_hello_ffeth(void *ptrLocal, void *ptrForeign)
395 {
396   struct default_lq_ffeth_hello *local = ptrLocal;
397   struct default_lq_ffeth *foreign = ptrForeign;
398
399   if (foreign) {
400     local->lq.valueNlq = foreign->valueLq;
401   } else {
402     local->lq.valueNlq = 0;
403   }
404 }
405
406 static void
407 default_lq_copy_link2neigh_ffeth(void *t, void *s)
408 {
409   struct default_lq_ffeth *target = t;
410   struct default_lq_ffeth_hello *source = s;
411   *target = source->smoothed_lq;
412 }
413
414 static void
415 default_lq_copy_link2tc_ffeth(void *t, void *s)
416 {
417   struct default_lq_ffeth *target = t;
418   struct default_lq_ffeth_hello *source = s;
419   *target = source->smoothed_lq;
420 }
421
422 static void
423 default_lq_clear_ffeth(void *target)
424 {
425   memset(target, 0, sizeof(struct default_lq_ffeth));
426 }
427
428 static void
429 default_lq_clear_ffeth_hello(void *target)
430 {
431   struct default_lq_ffeth_hello *local = target;
432   int i;
433
434   default_lq_clear_ffeth(&local->lq);
435   default_lq_clear_ffeth(&local->smoothed_lq);
436   local->windowSize = LQ_FFETH_QUICKSTART_INIT;
437   for (i = 0; i < LQ_FFETH_WINDOW; i++) {
438     local->total[i] = 3;
439   }
440 }
441
442 static const char *
443 default_lq_print_ffeth(void *ptr, char separator, struct lqtextbuffer *buffer)
444 {
445   struct default_lq_ffeth *lq = ptr;
446   int lq_int, nlq_int;
447
448   lq_int = (int)lq->valueLq;
449   if (lq_int > 0 && lq_int < 255) {
450     lq_int++;
451   }
452
453   nlq_int = (int)lq->valueNlq;
454   if (nlq_int > 0 && nlq_int < 255) {
455     nlq_int++;
456   }
457
458   snprintf(buffer->buf, sizeof(buffer->buf), "%s%c%s", fpmtoa(fpmidiv(itofpm(lq_int), 255)), separator,
459            fpmtoa(fpmidiv(itofpm(nlq_int), 255)));
460   return buffer->buf;
461 }
462
463 static const char *
464 default_lq_print_cost_ffeth(olsr_linkcost cost, struct lqtextbuffer *buffer)
465 {
466   snprintf(buffer->buf, sizeof(buffer->buf), "%s", fpmtoa(cost));
467   return buffer->buf;
468 }
469
470 /*
471  * Local Variables:
472  * c-basic-offset: 2
473  * indent-tabs-mode: nil
474  * End:
475  */