Convert etx_lq_fpm plugin to new plugin interface
[olsrd.git] / lib / lq_etx_fpm / src / lq_plugin_etx_fpm.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 "olsr_spf.h"
45 #include "lq_packet.h"
46 #include "olsr.h"
47 #include "lq_plugin_etx_fpm.h"
48 #include "olsr_logging.h"
49
50 #define PLUGIN_DESCR    "Integer arithmetic based ETX metric with exponential aging"
51 #define PLUGIN_AUTHOR   "Sven-Ola Tücke and Henning Rogge"
52
53 #define LQ_FPM_INTERNAL_MULTIPLIER 65535
54 #define LQ_FPM_LINKCOST_MULTIPLIER 65535
55
56 #define LQ_FPM_DEFAULT_AGING       3276        /* 65536 * 0.05 */
57 #define LQ_FPM_QUICKSTART_AGING    16384       /* 65536 * 0.25 */
58 #define LQ_QUICKSTART_STEPS        12
59
60 static int set_plugin_aging(const char *, void *, set_plugin_parameter_addon);
61
62 static olsr_linkcost lq_etxfpm_calc_link_entry_cost(struct link_entry *);
63 static olsr_linkcost lq_etxfpm_calc_lq_hello_neighbor_cost(struct lq_hello_neighbor *);
64 static olsr_linkcost lq_etxfpm_calc_tc_mpr_addr_cost(struct tc_mpr_addr *);
65 static olsr_linkcost lq_etxfpm_calc_tc_edge_entry_cost(struct tc_edge_entry *);
66
67 static bool lq_etxfpm_is_relevant_costchange(olsr_linkcost c1, olsr_linkcost c2);
68
69 static olsr_linkcost lq_etxfpm_packet_loss_handler(struct link_entry *, bool);
70
71 static void lq_etxfpm_memorize_foreign_hello(struct link_entry *, struct lq_hello_neighbor *);
72 static void lq_etxfpm_copy_link_entry_lq_into_tc_mpr_addr(struct tc_mpr_addr *target, struct link_entry *source);
73 static void lq_etxfpm_copy_link_entry_lq_into_tc_edge_entry(struct tc_edge_entry *target, struct link_entry *source);
74 static void lq_etxfpm_copy_link_lq_into_neighbor(struct lq_hello_neighbor *target, struct link_entry *source);
75
76 static int lq_etxfpm_serialize_hello_lq(unsigned char *buff, struct lq_hello_neighbor *lq);
77 static int lq_etxfpm_serialize_tc_lq(unsigned char *buff, struct tc_mpr_addr *lq);
78 static void lq_etxfpm_deserialize_hello_lq(uint8_t const **curr, struct lq_hello_neighbor *lq);
79 static void lq_etxfpm_deserialize_tc_lq(uint8_t const **curr, struct tc_edge_entry *lq);
80
81 static char *lq_etxfpm_print_link_entry_lq(struct link_entry *entry, char separator, struct lqtextbuffer *buffer);
82 static char *lq_etxfpm_print_tc_edge_entry_lq(struct tc_edge_entry *ptr, char separator, struct lqtextbuffer *buffer);
83 static char *lq_etxfpm_print_cost(olsr_linkcost cost, struct lqtextbuffer *buffer);
84
85 /* etx lq plugin (freifunk fpm version) settings */
86 struct lq_handler lq_etxfpm_handler = {
87   "etx (fpm)",
88
89   NULL,
90   NULL,
91
92   &lq_etxfpm_calc_link_entry_cost,
93   &lq_etxfpm_calc_lq_hello_neighbor_cost,
94   &lq_etxfpm_calc_tc_mpr_addr_cost,
95   &lq_etxfpm_calc_tc_edge_entry_cost,
96
97   &lq_etxfpm_is_relevant_costchange,
98
99   &lq_etxfpm_packet_loss_handler,
100
101   &lq_etxfpm_memorize_foreign_hello,
102   &lq_etxfpm_copy_link_entry_lq_into_tc_mpr_addr,
103   &lq_etxfpm_copy_link_entry_lq_into_tc_edge_entry,
104   &lq_etxfpm_copy_link_lq_into_neighbor,
105
106   NULL,
107   NULL,
108   NULL,
109   NULL,
110
111   &lq_etxfpm_serialize_hello_lq,
112   &lq_etxfpm_serialize_tc_lq,
113   &lq_etxfpm_deserialize_hello_lq,
114   &lq_etxfpm_deserialize_tc_lq,
115
116   &lq_etxfpm_print_link_entry_lq,
117   &lq_etxfpm_print_tc_edge_entry_lq,
118   &lq_etxfpm_print_cost,
119
120   sizeof(struct lq_etxfpm_tc_edge),
121   sizeof(struct lq_etxfpm_tc_mpr_addr),
122   sizeof(struct lq_etxfpm_lq_hello_neighbor),
123   sizeof(struct lq_etxfpm_link_entry),
124
125   LQ_HELLO_MESSAGE,
126   LQ_TC_MESSAGE
127 };
128
129 static uint32_t aging_factor_new = LQ_FPM_DEFAULT_AGING;
130 static uint32_t aging_factor_old = LQ_FPM_INTERNAL_MULTIPLIER - LQ_FPM_DEFAULT_AGING;
131 static uint32_t aging_quickstart_new = LQ_FPM_QUICKSTART_AGING;
132 static uint32_t aging_quickstart_old = LQ_FPM_INTERNAL_MULTIPLIER - LQ_FPM_QUICKSTART_AGING;
133
134 static const struct olsrd_plugin_parameters plugin_parameters[] = {
135   {.name = "LinkQualityAging",.set_plugin_parameter = &set_plugin_aging,.data = NULL}
136 };
137
138 DEFINE_PLUGIN6(PLUGIN_DESCR, PLUGIN_AUTHOR, NULL, NULL, NULL, NULL, false, plugin_parameters)
139
140 static int
141 set_plugin_aging(const char *value, void *data  __attribute__ ((unused)),
142     set_plugin_parameter_addon addon __attribute__ ((unused)))
143 {
144   uint32_t aging;
145
146   if (value[0] != '0' || value[1] != '.') {
147     OLSR_ERROR(LOG_PLUGINS, "LQ aging value must be between 0 and 1.\n");
148     return 1;
149   }
150
151   aging = strtoul(&value[2], NULL, 10);
152   /* support only 4 digits after . */
153   while (aging >= 10000) {
154     aging /= 10;
155   }
156
157   aging_factor_new = aging * LQ_FPM_INTERNAL_MULTIPLIER;
158
159   while (aging > 0) {
160     aging /= 10;
161     aging_factor_new /= 10;
162   }
163
164   aging_factor_old = LQ_FPM_INTERNAL_MULTIPLIER - aging_factor_new;
165   return 0;
166 }
167
168 static olsr_linkcost
169 lq_etxfpm_calc_linkcost(struct lq_etxfpm_linkquality *lq)
170 {
171   olsr_linkcost cost;
172
173   if (lq->valueLq < (unsigned int)(255 * MINIMAL_USEFUL_LQ) || lq->valueNlq < (unsigned int)(255 * MINIMAL_USEFUL_LQ)) {
174     return LINK_COST_BROKEN;
175   }
176
177   cost = LQ_FPM_LINKCOST_MULTIPLIER * 255 / (int)lq->valueLq * 255 / (int)lq->valueNlq;
178
179   if (cost > LINK_COST_BROKEN)
180     return LINK_COST_BROKEN;
181   if (cost == 0)
182     return 1;
183   return cost;
184 }
185
186 static olsr_linkcost
187 lq_etxfpm_calc_link_entry_cost(struct link_entry *link)
188 {
189   struct lq_etxfpm_link_entry *lq_link = (struct lq_etxfpm_link_entry *)link;
190
191   return lq_etxfpm_calc_linkcost(&lq_link->lq);
192 }
193
194 static olsr_linkcost
195 lq_etxfpm_calc_lq_hello_neighbor_cost(struct lq_hello_neighbor *neigh)
196 {
197   struct lq_etxfpm_lq_hello_neighbor *lq_neigh = (struct lq_etxfpm_lq_hello_neighbor *)neigh;
198
199   return lq_etxfpm_calc_linkcost(&lq_neigh->lq);
200 }
201
202 static olsr_linkcost
203 lq_etxfpm_calc_tc_mpr_addr_cost(struct tc_mpr_addr *mpr)
204 {
205   struct lq_etxfpm_tc_mpr_addr *lq_mpr = (struct lq_etxfpm_tc_mpr_addr *)mpr;
206
207   return lq_etxfpm_calc_linkcost(&lq_mpr->lq);
208 }
209
210 static olsr_linkcost
211 lq_etxfpm_calc_tc_edge_entry_cost(struct tc_edge_entry *edge)
212 {
213   struct lq_etxfpm_tc_edge *lq_edge = (struct lq_etxfpm_tc_edge *)edge;
214
215   return lq_etxfpm_calc_linkcost(&lq_edge->lq);
216 }
217
218 static bool
219 lq_etxfpm_is_relevant_costchange(olsr_linkcost c1, olsr_linkcost c2)
220 {
221   if (c1 > c2) {
222     return c2 - c1 > LQ_PLUGIN_RELEVANT_COSTCHANGE;
223   }
224   return c1 - c2 > LQ_PLUGIN_RELEVANT_COSTCHANGE;
225 }
226
227 static olsr_linkcost
228 lq_etxfpm_packet_loss_handler(struct link_entry *link, bool loss)
229 {
230   struct lq_etxfpm_link_entry *lq_link = (struct lq_etxfpm_link_entry *)link;
231
232   uint32_t alpha_old = aging_factor_old;
233   uint32_t alpha_new = aging_factor_new;
234
235   uint32_t value;
236   // fpm link_loss_factor = fpmidiv(itofpm(link->loss_link_multiplier), 65536);
237
238   if (lq_link->quickstart < LQ_QUICKSTART_STEPS) {
239     alpha_new = aging_quickstart_new;
240     alpha_old = aging_quickstart_old;
241     lq_link->quickstart++;
242   }
243   // exponential moving average
244   value = (uint32_t) (lq_link->lq.valueLq) * LQ_FPM_INTERNAL_MULTIPLIER / 255;
245
246   value = (value * alpha_old + LQ_FPM_INTERNAL_MULTIPLIER - 1) / LQ_FPM_INTERNAL_MULTIPLIER;
247
248   if (!loss) {
249     uint32_t ratio;
250
251     ratio = (alpha_new * link->loss_link_multiplier + LINK_LOSS_MULTIPLIER - 1) / LINK_LOSS_MULTIPLIER;
252     value += ratio;
253   }
254   lq_link->lq.valueLq = (value * 255 + LQ_FPM_INTERNAL_MULTIPLIER - 1) / LQ_FPM_INTERNAL_MULTIPLIER;
255
256   return lq_etxfpm_calc_linkcost(&lq_link->lq);
257 }
258
259 static void
260 lq_etxfpm_memorize_foreign_hello(struct link_entry *target, struct lq_hello_neighbor *source)
261 {
262   struct lq_etxfpm_link_entry *lq_target = (struct lq_etxfpm_link_entry *)target;
263   struct lq_etxfpm_lq_hello_neighbor *lq_source = (struct lq_etxfpm_lq_hello_neighbor *)source;
264
265   if (source) {
266     lq_target->lq.valueNlq = lq_source->lq.valueLq;
267   } else {
268     lq_target->lq.valueNlq = 0;
269   }
270
271 }
272
273 static void
274 lq_etxfpm_copy_link_entry_lq_into_tc_mpr_addr(struct tc_mpr_addr *target, struct link_entry *source)
275 {
276   struct lq_etxfpm_tc_mpr_addr *lq_target = (struct lq_etxfpm_tc_mpr_addr *)target;
277   struct lq_etxfpm_link_entry *lq_source = (struct lq_etxfpm_link_entry *)source;
278
279   lq_target->lq = lq_source->lq;
280 }
281
282 static void
283 lq_etxfpm_copy_link_entry_lq_into_tc_edge_entry(struct tc_edge_entry *target, struct link_entry *source)
284 {
285   struct lq_etxfpm_tc_edge *lq_target = (struct lq_etxfpm_tc_edge *)target;
286   struct lq_etxfpm_link_entry *lq_source = (struct lq_etxfpm_link_entry *)source;
287
288   lq_target->lq = lq_source->lq;
289 }
290
291 static void
292 lq_etxfpm_copy_link_lq_into_neighbor(struct lq_hello_neighbor *target, struct link_entry *source)
293 {
294   struct lq_etxfpm_lq_hello_neighbor *lq_target = (struct lq_etxfpm_lq_hello_neighbor *)target;
295   struct lq_etxfpm_link_entry *lq_source = (struct lq_etxfpm_link_entry *)source;
296
297   lq_target->lq = lq_source->lq;
298 }
299
300 static int
301 lq_etxfpm_serialize_hello_lq(unsigned char *buff, struct lq_hello_neighbor *neigh)
302 {
303   struct lq_etxfpm_lq_hello_neighbor *lq_neigh = (struct lq_etxfpm_lq_hello_neighbor *)neigh;
304
305   buff[0] = (unsigned char)lq_neigh->lq.valueLq;
306   buff[1] = (unsigned char)lq_neigh->lq.valueNlq;
307   buff[2] = (unsigned char)(0);
308   buff[3] = (unsigned char)(0);
309
310   return 4;
311 }
312 static int
313 lq_etxfpm_serialize_tc_lq(unsigned char *buff, struct tc_mpr_addr *mpr)
314 {
315   struct lq_etxfpm_tc_mpr_addr *lq_mpr = (struct lq_etxfpm_tc_mpr_addr *)mpr;
316
317   buff[0] = (unsigned char)lq_mpr->lq.valueLq;
318   buff[1] = (unsigned char)lq_mpr->lq.valueNlq;
319   buff[2] = (unsigned char)(0);
320   buff[3] = (unsigned char)(0);
321
322   return 4;
323 }
324
325 static void
326 lq_etxfpm_deserialize_hello_lq(uint8_t const **curr, struct lq_hello_neighbor *neigh)
327 {
328   struct lq_etxfpm_lq_hello_neighbor *lq_neigh = (struct lq_etxfpm_lq_hello_neighbor *)neigh;
329
330   pkt_get_u8(curr, &lq_neigh->lq.valueLq);
331   pkt_get_u8(curr, &lq_neigh->lq.valueNlq);
332   pkt_ignore_u16(curr);
333
334 }
335 static void
336 lq_etxfpm_deserialize_tc_lq(uint8_t const **curr, struct tc_edge_entry *edge)
337 {
338   struct lq_etxfpm_tc_edge *lq_edge = (struct lq_etxfpm_tc_edge *)edge;
339
340   pkt_get_u8(curr, &lq_edge->lq.valueLq);
341   pkt_get_u8(curr, &lq_edge->lq.valueNlq);
342   pkt_ignore_u16(curr);
343 }
344
345 static char *
346 lq_etxfpm_print_lq(struct lq_etxfpm_linkquality *lq, char separator, struct lqtextbuffer *buffer)
347 {
348   int i = 0;
349
350   if (lq->valueLq == 255) {
351     strcpy(buffer->buf, "1.000");
352     i += 5;
353   } else {
354     i = sprintf(buffer->buf, "0.%03d", (lq->valueLq * 1000) / 255);
355   }
356   buffer->buf[i++] = separator;
357
358   if (lq->valueNlq == 255) {
359     strcpy(&buffer->buf[i], "1.000");
360   } else {
361     sprintf(&buffer->buf[i], "0.%03d", (lq->valueNlq * 1000) / 255);
362   }
363   return buffer->buf;
364 }
365
366 static char *
367 lq_etxfpm_print_link_entry_lq(struct link_entry *link, char separator, struct lqtextbuffer *buffer)
368 {
369   struct lq_etxfpm_link_entry *lq_link = (struct lq_etxfpm_link_entry *)link;
370
371   return lq_etxfpm_print_lq(&lq_link->lq, separator, buffer);
372 }
373
374 static char *
375 lq_etxfpm_print_tc_edge_entry_lq(struct tc_edge_entry *edge, char separator, struct lqtextbuffer *buffer)
376 {
377   struct lq_etxfpm_tc_edge *lq_edge = (struct lq_etxfpm_tc_edge *)edge;
378
379   return lq_etxfpm_print_lq(&lq_edge->lq, separator, buffer);
380 }
381
382 static char *
383 lq_etxfpm_print_cost(olsr_linkcost cost, struct lqtextbuffer *buffer)
384 {
385   // must calculate
386   uint32_t roundDown = cost >> 16;
387   uint32_t fraction = ((cost & 0xffff) * 1000) >> 16;
388
389   sprintf(buffer->buf, "%u.%03u", roundDown, fraction);
390   return buffer->buf;
391 }
392
393 /*
394  * Local Variables:
395  * c-basic-offset: 2
396  * indent-tabs-mode: nil
397  * End:
398  */