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