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