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