lib/lq_etx_ff/src/lq_plugin_etx_ff.c

   1 /*
   2  * The olsr.org Optimized Link-State Routing daemon(olsrd)
   3  * Copyright (c) 2004-2009, the olsr.org team - see HISTORY file
   4  * All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions
   8  * are met:
   9  *
  10  * * Redistributions of source code must retain the above copyright
  11  *   notice, this list of conditions and the following disclaimer.
  12  * * Redistributions in binary form must reproduce the above copyright
  13  *   notice, this list of conditions and the following disclaimer in
  14  *   the documentation and/or other materials provided with the
  15  *   distribution.
  16  * * Neither the name of olsr.org, olsrd nor the names of its
  17  *   contributors may be used to endorse or promote products derived
  18  *   from this software without specific prior written permission.
  19  *
  20  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  21  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  22  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  23  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
  24  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  25  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
  26  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  27  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  28  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  29  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
  30  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  31  * POSSIBILITY OF SUCH DAMAGE.
  32  *
  33  * Visit http://www.olsr.org for more information.
  34  *
  35  * If you find this software useful feel free to make a donation
  36  * to the project. For more information see the website or contact
  37  * the copyright holders.
  38  *
  39  */
  40
  41 #include "tc_set.h"
  42 #include "link_set.h"
  43 #include "lq_plugin.h"
  44 #include "olsr_spf.h"
  45 #include "lq_packet.h"
  46 #include "olsr.h"
  47 #include "lq_plugin_etx_ff.h"
  48 #include "parser.h"
  49 #include "mid_set.h"
  50 #include "scheduler.h"
  51 #include "olsr_logging.h"
  52
  53 #define LQ_PLUGIN_RELEVANT_COSTCHANGE_FF 16
  54
  55 static void lq_etxff_initialize(void);
  56 static void lq_etxff_deinitialize(void);
  57
  58 static olsr_linkcost lq_etxff_calc_link_entry_cost(struct link_entry *);
  59 static olsr_linkcost lq_etxff_calc_lq_hello_neighbor_cost(
  60     struct lq_hello_neighbor *);
  61 static olsr_linkcost lq_etxff_calc_tc_mpr_addr_cost(struct tc_mpr_addr *);
  62 static olsr_linkcost lq_etxff_calc_tc_edge_entry_cost(struct tc_edge_entry *);
  63
  64 static bool lq_etxff_is_relevant_costchange(olsr_linkcost c1, olsr_linkcost c2);
  65
  66 static olsr_linkcost lq_etxff_packet_loss_handler(struct link_entry *, bool);
  67
  68 static void lq_etxff_memorize_foreign_hello(struct link_entry *,
  69     struct lq_hello_neighbor *);
  70 static void lq_etxff_copy_link_entry_lq_into_tc_mpr_addr(
  71     struct tc_mpr_addr *target, struct link_entry *source);
  72 static void lq_etxff_copy_link_entry_lq_into_tc_edge_entry(
  73     struct tc_edge_entry *target, struct link_entry *source);
  74 static void lq_etxff_copy_link_lq_into_neighbor(struct lq_hello_neighbor *target,
  75     struct link_entry *source);
  76
  77 static void lq_etxff_clear_link_entry(struct link_entry *);
  78
  79 static int lq_etxff_serialize_hello_lq(unsigned char *buff,
  80     struct lq_hello_neighbor *lq);
  81 static int lq_etxff_serialize_tc_lq(unsigned char *buff, struct tc_mpr_addr *lq);
  82 static void lq_etxff_deserialize_hello_lq(uint8_t const ** curr,
  83     struct lq_hello_neighbor *lq);
  84 static void lq_etxff_deserialize_tc_lq(uint8_t const ** curr,
  85     struct tc_edge_entry *lq);
  86
  87 static char *lq_etxff_print_link_entry_lq(struct link_entry *entry, char separator,
  88     struct lqtextbuffer *buffer);
  89 static char *lq_etxff_print_tc_edge_entry_lq(struct tc_edge_entry *ptr,
  90     char separator, struct lqtextbuffer * buffer);
  91 static char *lq_etxff_print_cost(olsr_linkcost cost, struct lqtextbuffer * buffer);
  92
  93 static struct olsr_cookie_info *default_lq_ff_timer_cookie = NULL;
  94
  95 /* etx lq plugin (freifunk fpm version) settings */
  96 struct lq_handler lq_etxff_handler = {
  97   &lq_etxff_initialize,
  98   &lq_etxff_deinitialize,
  99
 100   &lq_etxff_calc_link_entry_cost,
 101   &lq_etxff_calc_lq_hello_neighbor_cost,
 102   &lq_etxff_calc_tc_mpr_addr_cost,
 103   &lq_etxff_calc_tc_edge_entry_cost,
 104
 105   &lq_etxff_is_relevant_costchange,
 106
 107   &lq_etxff_packet_loss_handler,
 108
 109   &lq_etxff_memorize_foreign_hello,
 110   &lq_etxff_copy_link_entry_lq_into_tc_mpr_addr,
 111   &lq_etxff_copy_link_entry_lq_into_tc_edge_entry,
 112   &lq_etxff_copy_link_lq_into_neighbor,
 113
 114   &lq_etxff_clear_link_entry,
 115   NULL,
 116   NULL,
 117   NULL,
 118
 119   &lq_etxff_serialize_hello_lq,
 120   &lq_etxff_serialize_tc_lq,
 121   &lq_etxff_deserialize_hello_lq,
 122   &lq_etxff_deserialize_tc_lq,
 123
 124   &lq_etxff_print_link_entry_lq,
 125   &lq_etxff_print_tc_edge_entry_lq,
 126   &lq_etxff_print_cost,
 127
 128   sizeof(struct lq_etxff_tc_edge),
 129   sizeof(struct lq_etxff_tc_mpr_addr),
 130   sizeof(struct lq_etxff_lq_hello_neighbor),
 131   sizeof(struct lq_etxff_link_entry),
 132
 133   LQ_HELLO_MESSAGE,
 134   LQ_TC_MESSAGE
 135 };
 136
 137 static void lq_etxff_packet_parser(struct olsr *olsr, struct interface *in_if,
 138     union olsr_ip_addr *from_addr) {
 139   const union olsr_ip_addr *main_addr;
 140   struct lq_etxff_link_entry *lnk;
 141   uint32_t seq_diff;
 142
 143   /* Find main address */
 144   main_addr = olsr_lookup_main_addr_by_alias(from_addr);
 145
 146   /* Loopup link entry */
 147   lnk = (struct lq_etxff_link_entry *) lookup_link_entry(from_addr, main_addr,
 148       in_if);
 149   if (lnk == NULL) {
 150     return;
 151   }
 152
 153   if (lnk->last_seq_nr == olsr->olsr_seqno ) {
 154 #ifndef REMOVE_LOG_WARN
 155     struct ipaddr_str buf;
 156 #endif
 157     OLSR_WARN(LOG_LQ_PLUGINS, "Got package with same sequence number from %s\n", olsr_ip_to_string(&buf, from_addr));
 158     return;
 159   }
 160   if (lnk->last_seq_nr > olsr->olsr_seqno) {
 161     seq_diff = (uint32_t) olsr->olsr_seqno + 65536 - lnk->last_seq_nr;
 162   } else {
 163     seq_diff = olsr->olsr_seqno - lnk->last_seq_nr;
 164   }
 165
 166   /* Jump in sequence numbers ? */
 167   if (seq_diff > 256) {
 168     seq_diff = 1;
 169   }
 170
 171   lnk->received[lnk->activePtr]++;
 172   lnk->lost[lnk->activePtr] += (seq_diff - 1);
 173
 174   lnk->last_seq_nr = olsr->olsr_seqno;
 175   lnk->missed_seconds = 0;
 176 }
 177
 178 static void lq_etxff_timer(void __attribute__((unused)) *context) {
 179   struct link_entry *link;
 180   OLSR_FOR_ALL_LINK_ENTRIES(link)
 181   {
 182     struct lq_etxff_link_entry *lq_link;
 183     uint32_t ratio;
 184     uint16_t i, received, lost;
 185
 186 #ifndef REMOVE_LOG_DEBUG
 187     struct ipaddr_str buf;
 188     // struct lqtextbuffer lqbuffer;
 189 #endif
 190     lq_link = (struct lq_etxff_link_entry *)link;
 191
 192     OLSR_DEBUG(LOG_LQ_PLUGINS, "LQ-FF new entry for %s: rec: %d lost: %d",
 193       olsr_ip_to_string(&buf, &link->neighbor_iface_addr),
 194       lq_link->received[lq_link->activePtr], lq_link->lost[lq_link->activePtr]);
 195
 196     received = 0;
 197     lost = 0;
 198
 199     /* enlarge window if still in quickstart phase */
 200     if (lq_link->windowSize < LQ_FF_WINDOW) {
 201       lq_link->windowSize++;
 202     }
 203     for (i=0; i < lq_link->windowSize; i++) {
 204       received += lq_link->received[i];
 205       lost += lq_link->lost[i];
 206     }
 207
 208     OLSR_DEBUG(LOG_LQ_PLUGINS, " total-rec: %d total-lost: %d", received, lost);
 209
 210     /* calculate link quality */
 211     if (received + lost == 0) {
 212       lq_link->lq.valueLq = 0;
 213     }
 214     else {
 215
 216       /* keep missed hello periods in mind (round up hello interval to seconds) */
 217       uint32_t missed_hello_cost = lq_link->missed_seconds / ((lq_link->core.link_loss_timer->timer_period + 999) / 1000);
 218       lost += missed_hello_cost * missed_hello_cost;
 219
 220       // start with link-loss-factor
 221       ratio = link->loss_link_multiplier;
 222
 223       // calculate received/(received + loss) factor
 224       ratio = ratio * received;
 225       ratio = ratio / (received + lost);
 226       ratio = (ratio * 255) >> 16;
 227
 228       lq_link->lq.valueLq = (uint8_t)(ratio);
 229     }
 230
 231     // shift buffer
 232     lq_link->activePtr = (lq_link->activePtr + 1) % LQ_FF_WINDOW;
 233     lq_link->lost[lq_link->activePtr] = 0;
 234     lq_link->received[lq_link->activePtr] = 0;
 235     lq_link->missed_seconds++;
 236   }OLSR_FOR_ALL_LINK_ENTRIES_END(link);
 237 }
 238
 239 static struct timer_entry *lq_etxff_timer_struct = NULL;
 240
 241 static void lq_etxff_initialize(void) {
 242   /* Some cookies for stats keeping */
 243   olsr_packetparser_add_function(&lq_etxff_packet_parser);
 244   default_lq_ff_timer_cookie = olsr_alloc_cookie("Default Freifunk LQ",
 245       OLSR_COOKIE_TYPE_TIMER);
 246   lq_etxff_timer_struct = olsr_start_timer(1000, 0, OLSR_TIMER_PERIODIC,
 247       &lq_etxff_timer, NULL, default_lq_ff_timer_cookie->ci_id);
 248 }
 249
 250 static void lq_etxff_deinitialize(void) {
 251   olsr_stop_timer(lq_etxff_timer_struct);
 252   olsr_packetparser_remove_function(&lq_etxff_packet_parser);
 253 }
 254
 255 static olsr_linkcost lq_etxff_calc_linkcost(struct lq_etxff_linkquality *lq) {
 256   olsr_linkcost cost;
 257
 258   if (lq->valueLq < (unsigned int) (255 * MINIMAL_USEFUL_LQ) || lq->valueNlq
 259       < (unsigned int) (255 * MINIMAL_USEFUL_LQ)) {
 260     return LINK_COST_BROKEN;
 261   }
 262
 263   cost = 65536 * 255/(int)lq->valueLq * 255/(int)lq->valueNlq;
 264
 265   if (cost > LINK_COST_BROKEN)
 266     return LINK_COST_BROKEN;
 267   if (cost == 0)
 268     return 1;
 269   return cost;
 270 }
 271
 272 static olsr_linkcost lq_etxff_calc_link_entry_cost(struct link_entry *link) {
 273   struct lq_etxff_link_entry *lq_link = (struct lq_etxff_link_entry *) link;
 274
 275   return lq_etxff_calc_linkcost(&lq_link->lq);
 276 }
 277
 278 static olsr_linkcost lq_etxff_calc_lq_hello_neighbor_cost(
 279     struct lq_hello_neighbor *neigh) {
 280   struct lq_etxff_lq_hello_neighbor *lq_neigh =
 281       (struct lq_etxff_lq_hello_neighbor *) neigh;
 282
 283   return lq_etxff_calc_linkcost(&lq_neigh->lq);
 284 }
 285
 286 static olsr_linkcost lq_etxff_calc_tc_mpr_addr_cost(struct tc_mpr_addr *mpr) {
 287   struct lq_etxff_tc_mpr_addr *lq_mpr = (struct lq_etxff_tc_mpr_addr *) mpr;
 288
 289   return lq_etxff_calc_linkcost(&lq_mpr->lq);
 290 }
 291
 292 static olsr_linkcost lq_etxff_calc_tc_edge_entry_cost(struct tc_edge_entry *edge) {
 293   struct lq_etxff_tc_edge *lq_edge = (struct lq_etxff_tc_edge *) edge;
 294
 295   return lq_etxff_calc_linkcost(&lq_edge->lq);
 296 }
 297
 298 static bool lq_etxff_is_relevant_costchange(olsr_linkcost c1, olsr_linkcost c2) {
 299   if (c1 > c2) {
 300     return c2 - c1 > LQ_PLUGIN_RELEVANT_COSTCHANGE_FF;
 301   }
 302   return c1 - c2 > LQ_PLUGIN_RELEVANT_COSTCHANGE_FF;
 303 }
 304
 305 static olsr_linkcost lq_etxff_packet_loss_handler(struct link_entry *link,
 306     bool loss __attribute__((unused))) {
 307   return lq_etxff_calc_link_entry_cost(link);
 308 }
 309
 310 static void lq_etxff_memorize_foreign_hello(struct link_entry *target,
 311     struct lq_hello_neighbor *source) {
 312   struct lq_etxff_link_entry *lq_target = (struct lq_etxff_link_entry *) target;
 313   struct lq_etxff_lq_hello_neighbor *lq_source =
 314       (struct lq_etxff_lq_hello_neighbor *) source;
 315
 316   if (source) {
 317     lq_target->lq.valueNlq = lq_source->lq.valueLq;
 318   } else {
 319     lq_target->lq.valueNlq = 0;
 320   }
 321
 322 }
 323
 324 static void lq_etxff_copy_link_entry_lq_into_tc_mpr_addr(
 325     struct tc_mpr_addr *target, struct link_entry *source) {
 326   struct lq_etxff_tc_mpr_addr *lq_target = (struct lq_etxff_tc_mpr_addr *) target;
 327   struct lq_etxff_link_entry *lq_source = (struct lq_etxff_link_entry *) source;
 328
 329   lq_target->lq = lq_source->lq;
 330 }
 331
 332 static void lq_etxff_copy_link_entry_lq_into_tc_edge_entry(
 333     struct tc_edge_entry *target, struct link_entry *source) {
 334   struct lq_etxff_tc_edge *lq_target = (struct lq_etxff_tc_edge *) target;
 335   struct lq_etxff_link_entry *lq_source = (struct lq_etxff_link_entry *) source;
 336
 337   lq_target->lq = lq_source->lq;
 338 }
 339
 340 static void lq_etxff_copy_link_lq_into_neighbor(struct lq_hello_neighbor *target,
 341     struct link_entry *source) {
 342   struct lq_etxff_lq_hello_neighbor *lq_target =
 343       (struct lq_etxff_lq_hello_neighbor *) target;
 344   struct lq_etxff_link_entry *lq_source = (struct lq_etxff_link_entry *) source;
 345
 346   lq_target->lq = lq_source->lq;
 347 }
 348
 349 static void lq_etxff_clear_link_entry(struct link_entry *link) {
 350   struct lq_etxff_link_entry *lq_link = (struct lq_etxff_link_entry *) link;
 351   int i;
 352
 353   lq_link->windowSize = LQ_FF_QUICKSTART_INIT;
 354   for (i = 0; i < LQ_FF_WINDOW; i++) {
 355     lq_link->lost[i] = 3;
 356   }
 357 }
 358
 359 static int lq_etxff_serialize_hello_lq(unsigned char *buff,
 360     struct lq_hello_neighbor *neigh) {
 361   struct lq_etxff_lq_hello_neighbor *lq_neigh =
 362       (struct lq_etxff_lq_hello_neighbor *) neigh;
 363
 364   buff[0] = (unsigned char) lq_neigh->lq.valueLq;
 365   buff[1] = (unsigned char) lq_neigh->lq.valueNlq;
 366   buff[2] = (unsigned char) (0);
 367   buff[3] = (unsigned char) (0);
 368
 369   return 4;
 370 }
 371 static int lq_etxff_serialize_tc_lq(unsigned char *buff, struct tc_mpr_addr *mpr) {
 372   struct lq_etxff_tc_mpr_addr *lq_mpr = (struct lq_etxff_tc_mpr_addr *) mpr;
 373
 374   buff[0] = (unsigned char) lq_mpr->lq.valueLq;
 375   buff[1] = (unsigned char) lq_mpr->lq.valueNlq;
 376   buff[2] = (unsigned char) (0);
 377   buff[3] = (unsigned char) (0);
 378
 379   return 4;
 380 }
 381
 382 static void lq_etxff_deserialize_hello_lq(uint8_t const ** curr,
 383     struct lq_hello_neighbor *neigh) {
 384   struct lq_etxff_lq_hello_neighbor *lq_neigh =
 385       (struct lq_etxff_lq_hello_neighbor *) neigh;
 386
 387   pkt_get_u8(curr, &lq_neigh->lq.valueLq);
 388   pkt_get_u8(curr, &lq_neigh->lq.valueNlq);
 389   pkt_ignore_u16(curr);
 390
 391 }
 392 static void lq_etxff_deserialize_tc_lq(uint8_t const ** curr,
 393     struct tc_edge_entry *edge) {
 394   struct lq_etxff_tc_edge *lq_edge = (struct lq_etxff_tc_edge *) edge;
 395
 396   pkt_get_u8(curr, &lq_edge->lq.valueLq);
 397   pkt_get_u8(curr, &lq_edge->lq.valueNlq);
 398   pkt_ignore_u16(curr);
 399 }
 400
 401 static char *lq_etxff_print_lq(struct lq_etxff_linkquality *lq, char separator,
 402     struct lqtextbuffer *buffer) {
 403   int i = 0;
 404
 405   if (lq->valueLq == 255) {
 406         strcpy(buffer->buf, "1.000");
 407         i += 5;
 408   }
 409   else {
 410     i = sprintf(buffer->buf, "0.%03d", (lq->valueLq * 1000)/255);
 411   }
 412   buffer->buf[i++] = separator;
 413
 414   if (lq->valueNlq == 255) {
 415     strcpy(&buffer->buf[i], "1.000");
 416   }
 417   else {
 418     sprintf(&buffer->buf[i], "0.%03d", (lq->valueNlq * 1000) / 255);
 419   }
 420   return buffer->buf;
 421 }
 422
 423 static char *lq_etxff_print_link_entry_lq(struct link_entry *link, char separator,
 424     struct lqtextbuffer *buffer) {
 425   struct lq_etxff_link_entry *lq_link = (struct lq_etxff_link_entry *) link;
 426
 427   return lq_etxff_print_lq(&lq_link->lq, separator, buffer);
 428 }
 429
 430 static char *lq_etxff_print_tc_edge_entry_lq(struct tc_edge_entry *edge,
 431     char separator, struct lqtextbuffer * buffer) {
 432   struct lq_etxff_tc_edge *lq_edge = (struct lq_etxff_tc_edge *) edge;
 433
 434   return lq_etxff_print_lq(&lq_edge->lq, separator, buffer);
 435 }
 436
 437 static char *lq_etxff_print_cost(olsr_linkcost cost, struct lqtextbuffer * buffer) {
 438   // must calculate
 439   uint32_t roundDown = cost >> 16;
 440   uint32_t fraction = ((cost & 0xffff) * 1000) >> 16;
 441
 442   sprintf(buffer->buf, "%u.%03u", roundDown, fraction);
 443   return buffer->buf;
 444 }
 445
 446 /*
 447  * Local Variables:
 448  * c-basic-offset: 2
 449  * indent-tabs-mode: nil
 450  * End:
 451  */