serialized LQ data is not always 4 bytes long, so we need a function to precalculate...
[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   4,4
129 };
130
131 static uint32_t aging_factor_new = LQ_FPM_DEFAULT_AGING;
132 static uint32_t aging_factor_old = LQ_FPM_INTERNAL_MULTIPLIER - LQ_FPM_DEFAULT_AGING;
133 static uint32_t aging_quickstart_new = LQ_FPM_QUICKSTART_AGING;
134 static uint32_t aging_quickstart_old = LQ_FPM_INTERNAL_MULTIPLIER - LQ_FPM_QUICKSTART_AGING;
135
136 static const struct olsrd_plugin_parameters plugin_parameters[] = {
137   {.name = "LinkQualityAging",.set_plugin_parameter = &set_plugin_aging,.data = NULL}
138 };
139
140 DEFINE_PLUGIN6(PLUGIN_DESCR, PLUGIN_AUTHOR, NULL, NULL, NULL, NULL, false, plugin_parameters)
141
142 static int
143 set_plugin_aging(const char *value, void *data  __attribute__ ((unused)),
144     set_plugin_parameter_addon addon __attribute__ ((unused)))
145 {
146   uint32_t aging;
147
148   if (value[0] != '0' || value[1] != '.') {
149     OLSR_ERROR(LOG_PLUGINS, "LQ aging value must be between 0 and 1.\n");
150     return 1;
151   }
152
153   aging = strtoul(&value[2], NULL, 10);
154   /* support only 4 digits after . */
155   while (aging >= 10000) {
156     aging /= 10;
157   }
158
159   aging_factor_new = aging * LQ_FPM_INTERNAL_MULTIPLIER;
160
161   while (aging > 0) {
162     aging /= 10;
163     aging_factor_new /= 10;
164   }
165
166   aging_factor_old = LQ_FPM_INTERNAL_MULTIPLIER - aging_factor_new;
167   return 0;
168 }
169
170 static olsr_linkcost
171 lq_etxfpm_calc_linkcost(struct lq_etxfpm_linkquality *lq)
172 {
173   olsr_linkcost cost;
174
175   if (lq->valueLq < (unsigned int)(255 * MINIMAL_USEFUL_LQ) || lq->valueNlq < (unsigned int)(255 * MINIMAL_USEFUL_LQ)) {
176     return LINK_COST_BROKEN;
177   }
178
179   cost = LQ_FPM_LINKCOST_MULTIPLIER * 255 / (int)lq->valueLq * 255 / (int)lq->valueNlq;
180
181   if (cost > LINK_COST_BROKEN)
182     return LINK_COST_BROKEN;
183   if (cost == 0)
184     return 1;
185   return cost;
186 }
187
188 static olsr_linkcost
189 lq_etxfpm_calc_link_entry_cost(struct link_entry *link)
190 {
191   struct lq_etxfpm_link_entry *lq_link = (struct lq_etxfpm_link_entry *)link;
192
193   return lq_etxfpm_calc_linkcost(&lq_link->lq);
194 }
195
196 static olsr_linkcost
197 lq_etxfpm_calc_lq_hello_neighbor_cost(struct lq_hello_neighbor *neigh)
198 {
199   struct lq_etxfpm_lq_hello_neighbor *lq_neigh = (struct lq_etxfpm_lq_hello_neighbor *)neigh;
200
201   return lq_etxfpm_calc_linkcost(&lq_neigh->lq);
202 }
203
204 static olsr_linkcost
205 lq_etxfpm_calc_tc_mpr_addr_cost(struct tc_mpr_addr *mpr)
206 {
207   struct lq_etxfpm_tc_mpr_addr *lq_mpr = (struct lq_etxfpm_tc_mpr_addr *)mpr;
208
209   return lq_etxfpm_calc_linkcost(&lq_mpr->lq);
210 }
211
212 static olsr_linkcost
213 lq_etxfpm_calc_tc_edge_entry_cost(struct tc_edge_entry *edge)
214 {
215   struct lq_etxfpm_tc_edge *lq_edge = (struct lq_etxfpm_tc_edge *)edge;
216
217   return lq_etxfpm_calc_linkcost(&lq_edge->lq);
218 }
219
220 static bool
221 lq_etxfpm_is_relevant_costchange(olsr_linkcost c1, olsr_linkcost c2)
222 {
223   if (c1 > c2) {
224     return c2 - c1 > LQ_PLUGIN_RELEVANT_COSTCHANGE;
225   }
226   return c1 - c2 > LQ_PLUGIN_RELEVANT_COSTCHANGE;
227 }
228
229 static olsr_linkcost
230 lq_etxfpm_packet_loss_handler(struct link_entry *link, bool loss)
231 {
232   struct lq_etxfpm_link_entry *lq_link = (struct lq_etxfpm_link_entry *)link;
233
234   uint32_t alpha_old = aging_factor_old;
235   uint32_t alpha_new = aging_factor_new;
236
237   uint32_t value;
238   // fpm link_loss_factor = fpmidiv(itofpm(link->loss_link_multiplier), 65536);
239
240   if (lq_link->quickstart < LQ_QUICKSTART_STEPS) {
241     alpha_new = aging_quickstart_new;
242     alpha_old = aging_quickstart_old;
243     lq_link->quickstart++;
244   }
245   // exponential moving average
246   value = (uint32_t) (lq_link->lq.valueLq) * LQ_FPM_INTERNAL_MULTIPLIER / 255;
247
248   value = (value * alpha_old + LQ_FPM_INTERNAL_MULTIPLIER - 1) / LQ_FPM_INTERNAL_MULTIPLIER;
249
250   if (!loss) {
251     uint32_t ratio;
252
253     ratio = (alpha_new * link->loss_link_multiplier + LINK_LOSS_MULTIPLIER - 1) / LINK_LOSS_MULTIPLIER;
254     value += ratio;
255   }
256   lq_link->lq.valueLq = (value * 255 + LQ_FPM_INTERNAL_MULTIPLIER - 1) / LQ_FPM_INTERNAL_MULTIPLIER;
257
258   return lq_etxfpm_calc_linkcost(&lq_link->lq);
259 }
260
261 static void
262 lq_etxfpm_memorize_foreign_hello(struct link_entry *target, struct lq_hello_neighbor *source)
263 {
264   struct lq_etxfpm_link_entry *lq_target = (struct lq_etxfpm_link_entry *)target;
265   struct lq_etxfpm_lq_hello_neighbor *lq_source = (struct lq_etxfpm_lq_hello_neighbor *)source;
266
267   if (source) {
268     lq_target->lq.valueNlq = lq_source->lq.valueLq;
269   } else {
270     lq_target->lq.valueNlq = 0;
271   }
272
273 }
274
275 static void
276 lq_etxfpm_copy_link_entry_lq_into_tc_mpr_addr(struct tc_mpr_addr *target, struct link_entry *source)
277 {
278   struct lq_etxfpm_tc_mpr_addr *lq_target = (struct lq_etxfpm_tc_mpr_addr *)target;
279   struct lq_etxfpm_link_entry *lq_source = (struct lq_etxfpm_link_entry *)source;
280
281   lq_target->lq = lq_source->lq;
282 }
283
284 static void
285 lq_etxfpm_copy_link_entry_lq_into_tc_edge_entry(struct tc_edge_entry *target, struct link_entry *source)
286 {
287   struct lq_etxfpm_tc_edge *lq_target = (struct lq_etxfpm_tc_edge *)target;
288   struct lq_etxfpm_link_entry *lq_source = (struct lq_etxfpm_link_entry *)source;
289
290   lq_target->lq = lq_source->lq;
291 }
292
293 static void
294 lq_etxfpm_copy_link_lq_into_neighbor(struct lq_hello_neighbor *target, struct link_entry *source)
295 {
296   struct lq_etxfpm_lq_hello_neighbor *lq_target = (struct lq_etxfpm_lq_hello_neighbor *)target;
297   struct lq_etxfpm_link_entry *lq_source = (struct lq_etxfpm_link_entry *)source;
298
299   lq_target->lq = lq_source->lq;
300 }
301
302 static int
303 lq_etxfpm_serialize_hello_lq(unsigned char *buff, struct lq_hello_neighbor *neigh)
304 {
305   struct lq_etxfpm_lq_hello_neighbor *lq_neigh = (struct lq_etxfpm_lq_hello_neighbor *)neigh;
306
307   buff[0] = (unsigned char)lq_neigh->lq.valueLq;
308   buff[1] = (unsigned char)lq_neigh->lq.valueNlq;
309   buff[2] = (unsigned char)(0);
310   buff[3] = (unsigned char)(0);
311
312   return 4;
313 }
314 static int
315 lq_etxfpm_serialize_tc_lq(unsigned char *buff, struct tc_mpr_addr *mpr)
316 {
317   struct lq_etxfpm_tc_mpr_addr *lq_mpr = (struct lq_etxfpm_tc_mpr_addr *)mpr;
318
319   buff[0] = (unsigned char)lq_mpr->lq.valueLq;
320   buff[1] = (unsigned char)lq_mpr->lq.valueNlq;
321   buff[2] = (unsigned char)(0);
322   buff[3] = (unsigned char)(0);
323
324   return 4;
325 }
326
327 static void
328 lq_etxfpm_deserialize_hello_lq(uint8_t const **curr, struct lq_hello_neighbor *neigh)
329 {
330   struct lq_etxfpm_lq_hello_neighbor *lq_neigh = (struct lq_etxfpm_lq_hello_neighbor *)neigh;
331
332   pkt_get_u8(curr, &lq_neigh->lq.valueLq);
333   pkt_get_u8(curr, &lq_neigh->lq.valueNlq);
334   pkt_ignore_u16(curr);
335
336 }
337 static void
338 lq_etxfpm_deserialize_tc_lq(uint8_t const **curr, struct tc_edge_entry *edge)
339 {
340   struct lq_etxfpm_tc_edge *lq_edge = (struct lq_etxfpm_tc_edge *)edge;
341
342   pkt_get_u8(curr, &lq_edge->lq.valueLq);
343   pkt_get_u8(curr, &lq_edge->lq.valueNlq);
344   pkt_ignore_u16(curr);
345 }
346
347 static char *
348 lq_etxfpm_print_lq(struct lq_etxfpm_linkquality *lq, char separator, struct lqtextbuffer *buffer)
349 {
350   int i = 0;
351
352   if (lq->valueLq == 255) {
353     strcpy(buffer->buf, "1.000");
354     i += 5;
355   } else {
356     i = sprintf(buffer->buf, "0.%03d", (lq->valueLq * 1000) / 255);
357   }
358   buffer->buf[i++] = separator;
359
360   if (lq->valueNlq == 255) {
361     strcpy(&buffer->buf[i], "1.000");
362   } else {
363     sprintf(&buffer->buf[i], "0.%03d", (lq->valueNlq * 1000) / 255);
364   }
365   return buffer->buf;
366 }
367
368 static char *
369 lq_etxfpm_print_link_entry_lq(struct link_entry *link, char separator, struct lqtextbuffer *buffer)
370 {
371   struct lq_etxfpm_link_entry *lq_link = (struct lq_etxfpm_link_entry *)link;
372
373   return lq_etxfpm_print_lq(&lq_link->lq, separator, buffer);
374 }
375
376 static char *
377 lq_etxfpm_print_tc_edge_entry_lq(struct tc_edge_entry *edge, char separator, struct lqtextbuffer *buffer)
378 {
379   struct lq_etxfpm_tc_edge *lq_edge = (struct lq_etxfpm_tc_edge *)edge;
380
381   return lq_etxfpm_print_lq(&lq_edge->lq, separator, buffer);
382 }
383
384 static char *
385 lq_etxfpm_print_cost(olsr_linkcost cost, struct lqtextbuffer *buffer)
386 {
387   // must calculate
388   uint32_t roundDown = cost >> 16;
389   uint32_t fraction = ((cost & 0xffff) * 1000) >> 16;
390
391   sprintf(buffer->buf, "%u.%03u", roundDown, fraction);
392   return buffer->buf;
393 }
394
395 /*
396  * Local Variables:
397  * c-basic-offset: 2
398  * indent-tabs-mode: nil
399  * End:
400  */