3 * The olsr.org Optimized Link-State Routing daemon(olsrd)
4 * Copyright (c) 2004-2009, the olsr.org team - see HISTORY file
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
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
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.
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.
34 * Visit http://www.olsr.org for more information.
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.
44 #include "lq_plugin.h"
46 #include "lq_packet.h"
48 #include "lq_plugin_etx_ff.h"
51 #include "scheduler.h"
52 #include "olsr_logging.h"
54 #define LQ_PLUGIN_RELEVANT_COSTCHANGE_FF 16
56 static int lq_etxff_post_init(void);
58 static void lq_etxff_initialize(void);
59 static void lq_etxff_deinitialize(void);
61 static olsr_linkcost lq_etxff_calc_link_entry_cost(struct link_entry *);
62 static olsr_linkcost lq_etxff_calc_lq_hello_neighbor_cost(struct lq_hello_neighbor *);
63 static olsr_linkcost lq_etxff_calc_tc_mpr_addr_cost(struct tc_mpr_addr *);
64 static olsr_linkcost lq_etxff_calc_tc_edge_entry_cost(struct tc_edge_entry *);
66 static bool lq_etxff_is_relevant_costchange(olsr_linkcost c1, olsr_linkcost c2);
68 static olsr_linkcost lq_etxff_packet_loss_handler(struct link_entry *, bool);
70 static void lq_etxff_memorize_foreign_hello(struct link_entry *, struct lq_hello_neighbor *);
71 static void lq_etxff_copy_link_entry_lq_into_tc_mpr_addr(struct tc_mpr_addr *target, struct link_entry *source);
72 static void lq_etxff_copy_link_entry_lq_into_tc_edge_entry(struct tc_edge_entry *target, struct link_entry *source);
73 static void lq_etxff_copy_link_lq_into_neighbor(struct lq_hello_neighbor *target, struct link_entry *source);
75 static void lq_etxff_clear_link_entry(struct link_entry *);
77 static int lq_etxff_serialize_hello_lq(unsigned char *buff, struct lq_hello_neighbor *lq);
78 static int lq_etxff_serialize_tc_lq(unsigned char *buff, struct tc_mpr_addr *lq);
79 static void lq_etxff_deserialize_hello_lq(uint8_t const **curr, struct lq_hello_neighbor *lq);
80 static void lq_etxff_deserialize_tc_lq(uint8_t const **curr, struct tc_edge_entry *lq);
82 static char *lq_etxff_print_link_entry_lq(struct link_entry *entry, char separator, struct lqtextbuffer *buffer);
83 static char *lq_etxff_print_tc_edge_entry_lq(struct tc_edge_entry *ptr, char separator, struct lqtextbuffer *buffer);
84 static char *lq_etxff_print_cost(olsr_linkcost cost, struct lqtextbuffer *buffer);
86 static struct olsr_cookie_info *default_lq_ff_timer_cookie = NULL;
88 DEFINE_PLUGIN6_NP(PLUGIN_DESCR, PLUGIN_AUTHOR, NULL, lq_etxff_post_init, NULL, NULL, true)
90 /* etx lq plugin (freifunk fpm version) settings */
91 struct lq_handler lq_etxff_handler = {
95 &lq_etxff_deinitialize,
97 &lq_etxff_calc_link_entry_cost,
98 &lq_etxff_calc_lq_hello_neighbor_cost,
99 &lq_etxff_calc_tc_mpr_addr_cost,
100 &lq_etxff_calc_tc_edge_entry_cost,
102 &lq_etxff_is_relevant_costchange,
104 &lq_etxff_packet_loss_handler,
106 &lq_etxff_memorize_foreign_hello,
107 &lq_etxff_copy_link_entry_lq_into_tc_mpr_addr,
108 &lq_etxff_copy_link_entry_lq_into_tc_edge_entry,
109 &lq_etxff_copy_link_lq_into_neighbor,
111 &lq_etxff_clear_link_entry,
116 &lq_etxff_serialize_hello_lq,
117 &lq_etxff_serialize_tc_lq,
118 &lq_etxff_deserialize_hello_lq,
119 &lq_etxff_deserialize_tc_lq,
121 &lq_etxff_print_link_entry_lq,
122 &lq_etxff_print_tc_edge_entry_lq,
123 &lq_etxff_print_cost,
125 sizeof(struct lq_etxff_tc_edge),
126 sizeof(struct lq_etxff_tc_mpr_addr),
127 sizeof(struct lq_etxff_lq_hello_neighbor),
128 sizeof(struct lq_etxff_link_entry),
134 static int lq_etxff_post_init(void) {
135 active_lq_handler = &lq_etxff_handler;
140 lq_etxff_packet_parser(struct olsr *olsr, struct interface *in_if, union olsr_ip_addr *from_addr)
142 const union olsr_ip_addr *main_addr;
143 struct lq_etxff_link_entry *lnk;
146 /* Find main address */
147 main_addr = olsr_lookup_main_addr_by_alias(from_addr);
149 /* Loopup link entry */
150 lnk = (struct lq_etxff_link_entry *)lookup_link_entry(from_addr, main_addr, in_if);
155 if (lnk->last_seq_nr == olsr->olsr_seqno) {
156 #ifndef REMOVE_LOG_WARN
157 struct ipaddr_str buf;
159 OLSR_WARN(LOG_LQ_PLUGINS, "Got package with same sequence number from %s\n", olsr_ip_to_string(&buf, from_addr));
162 if (lnk->last_seq_nr > olsr->olsr_seqno) {
163 seq_diff = (uint32_t) olsr->olsr_seqno + 65536 - lnk->last_seq_nr;
165 seq_diff = olsr->olsr_seqno - lnk->last_seq_nr;
168 /* Jump in sequence numbers ? */
169 if (seq_diff > 256) {
173 lnk->received[lnk->activePtr]++;
174 lnk->lost[lnk->activePtr] += (seq_diff - 1);
176 lnk->last_seq_nr = olsr->olsr_seqno;
177 lnk->missed_seconds = 0;
181 lq_etxff_timer(void __attribute__ ((unused)) * context)
183 struct link_entry *link;
184 OLSR_FOR_ALL_LINK_ENTRIES(link) {
185 struct lq_etxff_link_entry *lq_link;
187 uint16_t i, received, lost;
189 #ifndef REMOVE_LOG_DEBUG
190 struct ipaddr_str buf;
191 // struct lqtextbuffer lqbuffer;
193 lq_link = (struct lq_etxff_link_entry *)link;
195 OLSR_DEBUG(LOG_LQ_PLUGINS, "LQ-FF new entry for %s: rec: %d lost: %d",
196 olsr_ip_to_string(&buf, &link->neighbor_iface_addr),
197 lq_link->received[lq_link->activePtr], lq_link->lost[lq_link->activePtr]);
202 /* enlarge window if still in quickstart phase */
203 if (lq_link->windowSize < LQ_FF_WINDOW) {
204 lq_link->windowSize++;
206 for (i = 0; i < lq_link->windowSize; i++) {
207 received += lq_link->received[i];
208 lost += lq_link->lost[i];
211 OLSR_DEBUG(LOG_LQ_PLUGINS, " total-rec: %d total-lost: %d", received, lost);
213 /* calculate link quality */
214 if (received + lost == 0) {
215 lq_link->lq.valueLq = 0;
218 /* keep missed hello periods in mind (round up hello interval to seconds) */
219 uint32_t missed_hello_cost = lq_link->missed_seconds / ((lq_link->core.link_loss_timer->timer_period + 999) / 1000);
220 lost += missed_hello_cost * missed_hello_cost;
222 // start with link-loss-factor
223 ratio = link->loss_link_multiplier;
225 // calculate received/(received + loss) factor
226 ratio = ratio * received;
227 ratio = ratio / (received + lost);
228 ratio = (ratio * 255) >> 16;
230 lq_link->lq.valueLq = (uint8_t) (ratio);
234 lq_link->activePtr = (lq_link->activePtr + 1) % LQ_FF_WINDOW;
235 lq_link->lost[lq_link->activePtr] = 0;
236 lq_link->received[lq_link->activePtr] = 0;
237 lq_link->missed_seconds++;
239 OLSR_FOR_ALL_LINK_ENTRIES_END(link);
242 static struct timer_entry *lq_etxff_timer_struct = NULL;
245 lq_etxff_initialize(void)
247 /* Some cookies for stats keeping */
248 olsr_packetparser_add_function(&lq_etxff_packet_parser);
249 default_lq_ff_timer_cookie = olsr_alloc_cookie("Default Freifunk LQ", OLSR_COOKIE_TYPE_TIMER);
250 lq_etxff_timer_struct = olsr_start_timer(1000, 0, OLSR_TIMER_PERIODIC, &lq_etxff_timer, NULL, default_lq_ff_timer_cookie);
254 lq_etxff_deinitialize(void)
256 olsr_stop_timer(lq_etxff_timer_struct);
257 olsr_packetparser_remove_function(&lq_etxff_packet_parser);
261 lq_etxff_calc_linkcost(struct lq_etxff_linkquality *lq)
265 if (lq->valueLq < (unsigned int)(255 * MINIMAL_USEFUL_LQ) || lq->valueNlq < (unsigned int)(255 * MINIMAL_USEFUL_LQ)) {
266 return LINK_COST_BROKEN;
269 cost = 65536 * 255 / (int)lq->valueLq * 255 / (int)lq->valueNlq;
271 if (cost > LINK_COST_BROKEN)
272 return LINK_COST_BROKEN;
279 lq_etxff_calc_link_entry_cost(struct link_entry *link)
281 struct lq_etxff_link_entry *lq_link = (struct lq_etxff_link_entry *)link;
283 return lq_etxff_calc_linkcost(&lq_link->lq);
287 lq_etxff_calc_lq_hello_neighbor_cost(struct lq_hello_neighbor *neigh)
289 struct lq_etxff_lq_hello_neighbor *lq_neigh = (struct lq_etxff_lq_hello_neighbor *)neigh;
291 return lq_etxff_calc_linkcost(&lq_neigh->lq);
295 lq_etxff_calc_tc_mpr_addr_cost(struct tc_mpr_addr *mpr)
297 struct lq_etxff_tc_mpr_addr *lq_mpr = (struct lq_etxff_tc_mpr_addr *)mpr;
299 return lq_etxff_calc_linkcost(&lq_mpr->lq);
303 lq_etxff_calc_tc_edge_entry_cost(struct tc_edge_entry *edge)
305 struct lq_etxff_tc_edge *lq_edge = (struct lq_etxff_tc_edge *)edge;
307 return lq_etxff_calc_linkcost(&lq_edge->lq);
311 lq_etxff_is_relevant_costchange(olsr_linkcost c1, olsr_linkcost c2)
314 return c2 - c1 > LQ_PLUGIN_RELEVANT_COSTCHANGE_FF;
316 return c1 - c2 > LQ_PLUGIN_RELEVANT_COSTCHANGE_FF;
320 lq_etxff_packet_loss_handler(struct link_entry *link, bool loss __attribute__ ((unused)))
322 return lq_etxff_calc_link_entry_cost(link);
326 lq_etxff_memorize_foreign_hello(struct link_entry *target, struct lq_hello_neighbor *source)
328 struct lq_etxff_link_entry *lq_target = (struct lq_etxff_link_entry *)target;
329 struct lq_etxff_lq_hello_neighbor *lq_source = (struct lq_etxff_lq_hello_neighbor *)source;
332 lq_target->lq.valueNlq = lq_source->lq.valueLq;
334 lq_target->lq.valueNlq = 0;
340 lq_etxff_copy_link_entry_lq_into_tc_mpr_addr(struct tc_mpr_addr *target, struct link_entry *source)
342 struct lq_etxff_tc_mpr_addr *lq_target = (struct lq_etxff_tc_mpr_addr *)target;
343 struct lq_etxff_link_entry *lq_source = (struct lq_etxff_link_entry *)source;
345 lq_target->lq = lq_source->lq;
349 lq_etxff_copy_link_entry_lq_into_tc_edge_entry(struct tc_edge_entry *target, struct link_entry *source)
351 struct lq_etxff_tc_edge *lq_target = (struct lq_etxff_tc_edge *)target;
352 struct lq_etxff_link_entry *lq_source = (struct lq_etxff_link_entry *)source;
354 lq_target->lq = lq_source->lq;
358 lq_etxff_copy_link_lq_into_neighbor(struct lq_hello_neighbor *target, struct link_entry *source)
360 struct lq_etxff_lq_hello_neighbor *lq_target = (struct lq_etxff_lq_hello_neighbor *)target;
361 struct lq_etxff_link_entry *lq_source = (struct lq_etxff_link_entry *)source;
363 lq_target->lq = lq_source->lq;
367 lq_etxff_clear_link_entry(struct link_entry *link)
369 struct lq_etxff_link_entry *lq_link = (struct lq_etxff_link_entry *)link;
372 lq_link->windowSize = LQ_FF_QUICKSTART_INIT;
373 for (i = 0; i < LQ_FF_WINDOW; i++) {
374 lq_link->lost[i] = 3;
379 lq_etxff_serialize_hello_lq(unsigned char *buff, struct lq_hello_neighbor *neigh)
381 struct lq_etxff_lq_hello_neighbor *lq_neigh = (struct lq_etxff_lq_hello_neighbor *)neigh;
383 buff[0] = (unsigned char)lq_neigh->lq.valueLq;
384 buff[1] = (unsigned char)lq_neigh->lq.valueNlq;
385 buff[2] = (unsigned char)(0);
386 buff[3] = (unsigned char)(0);
391 lq_etxff_serialize_tc_lq(unsigned char *buff, struct tc_mpr_addr *mpr)
393 struct lq_etxff_tc_mpr_addr *lq_mpr = (struct lq_etxff_tc_mpr_addr *)mpr;
395 buff[0] = (unsigned char)lq_mpr->lq.valueLq;
396 buff[1] = (unsigned char)lq_mpr->lq.valueNlq;
397 buff[2] = (unsigned char)(0);
398 buff[3] = (unsigned char)(0);
404 lq_etxff_deserialize_hello_lq(uint8_t const **curr, struct lq_hello_neighbor *neigh)
406 struct lq_etxff_lq_hello_neighbor *lq_neigh = (struct lq_etxff_lq_hello_neighbor *)neigh;
408 pkt_get_u8(curr, &lq_neigh->lq.valueLq);
409 pkt_get_u8(curr, &lq_neigh->lq.valueNlq);
410 pkt_ignore_u16(curr);
414 lq_etxff_deserialize_tc_lq(uint8_t const **curr, struct tc_edge_entry *edge)
416 struct lq_etxff_tc_edge *lq_edge = (struct lq_etxff_tc_edge *)edge;
418 pkt_get_u8(curr, &lq_edge->lq.valueLq);
419 pkt_get_u8(curr, &lq_edge->lq.valueNlq);
420 pkt_ignore_u16(curr);
424 lq_etxff_print_lq(struct lq_etxff_linkquality *lq, char separator, struct lqtextbuffer *buffer)
428 if (lq->valueLq == 255) {
429 strcpy(buffer->buf, "1.000");
432 i = sprintf(buffer->buf, "0.%03d", (lq->valueLq * 1000) / 255);
434 buffer->buf[i++] = separator;
436 if (lq->valueNlq == 255) {
437 strcpy(&buffer->buf[i], "1.000");
439 sprintf(&buffer->buf[i], "0.%03d", (lq->valueNlq * 1000) / 255);
445 lq_etxff_print_link_entry_lq(struct link_entry *link, char separator, struct lqtextbuffer *buffer)
447 struct lq_etxff_link_entry *lq_link = (struct lq_etxff_link_entry *)link;
449 return lq_etxff_print_lq(&lq_link->lq, separator, buffer);
453 lq_etxff_print_tc_edge_entry_lq(struct tc_edge_entry *edge, char separator, struct lqtextbuffer *buffer)
455 struct lq_etxff_tc_edge *lq_edge = (struct lq_etxff_tc_edge *)edge;
457 return lq_etxff_print_lq(&lq_edge->lq, separator, buffer);
461 lq_etxff_print_cost(olsr_linkcost cost, struct lqtextbuffer *buffer)
464 uint32_t roundDown = cost >> 16;
465 uint32_t fraction = ((cost & 0xffff) * 1000) >> 16;
467 sprintf(buffer->buf, "%u.%03u", roundDown, fraction);
474 * indent-tabs-mode: nil