src/lq_plugin_default_ff.c

   1
   2 /*
   3  * The olsr.org Optimized Link-State Routing daemon(olsrd)
   4  * Copyright (c) 2008 Henning Rogge <rogge@fgan.de>
   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 "packet.h"
  48 #include "olsr.h"
  49 #include "lq_plugin_default_ff.h"
  50 #include "parser.h"
  51 #include "fpm.h"
  52 #include "mid_set.h"
  53 #include "scheduler.h"
  54 #include "log.h"
  55
  56 static void default_lq_initialize_ff(void);
  57
  58 static olsr_linkcost default_lq_calc_cost_ff(const void *lq);
  59
  60 static void default_lq_packet_loss_worker_ff(struct link_entry *link, void *lq, bool lost);
  61 static void default_lq_memorize_foreign_hello_ff(void *local, void *foreign);
  62
  63 static int default_lq_serialize_hello_lq_pair_ff(unsigned char *buff, void *lq);
  64 static void default_lq_deserialize_hello_lq_pair_ff(const uint8_t ** curr, void *lq);
  65 static int default_lq_serialize_tc_lq_pair_ff(unsigned char *buff, void *lq);
  66 static void default_lq_deserialize_tc_lq_pair_ff(const uint8_t ** curr, void *lq);
  67
  68 static void default_lq_copy_link2neigh_ff(void *t, void *s);
  69 static void default_lq_copy_link2tc_ff(void *target, void *source);
  70 static void default_lq_clear_ff(void *target);
  71 static void default_lq_clear_ff_hello(void *target);
  72
  73 static const char *default_lq_print_ff(void *ptr, char separator, struct lqtextbuffer *buffer);
  74 static const char *default_lq_print_cost_ff(olsr_linkcost cost, struct lqtextbuffer *buffer);
  75
  76 /* etx lq plugin (freifunk fpm version) settings */
  77 struct lq_handler lq_etx_ff_handler = {
  78   &default_lq_initialize_ff,
  79   &default_lq_calc_cost_ff,
  80   &default_lq_calc_cost_ff,
  81
  82   &default_lq_packet_loss_worker_ff,
  83
  84   &default_lq_memorize_foreign_hello_ff,
  85   &default_lq_copy_link2neigh_ff,
  86   &default_lq_copy_link2tc_ff,
  87   &default_lq_clear_ff_hello,
  88   &default_lq_clear_ff,
  89
  90   &default_lq_serialize_hello_lq_pair_ff,
  91   &default_lq_serialize_tc_lq_pair_ff,
  92   &default_lq_deserialize_hello_lq_pair_ff,
  93   &default_lq_deserialize_tc_lq_pair_ff,
  94
  95   &default_lq_print_ff,
  96   &default_lq_print_ff,
  97   &default_lq_print_cost_ff,
  98
  99   sizeof(struct default_lq_ff_hello),
 100   sizeof(struct default_lq_ff),
 101   4,
 102   4
 103 };
 104
 105 static void
 106 default_lq_ff_handle_lqchange(void) {
 107   struct default_lq_ff_hello *lq;
 108   struct ipaddr_str buf;
 109   struct link_entry *link;
 110
 111   bool triggered = false;
 112
 113   OLSR_FOR_ALL_LINK_ENTRIES(link) {
 114     bool relevant = false;
 115     lq = (struct default_lq_ff_hello *)link->linkquality;
 116
 117 #if 0
 118   fprintf(stderr, "%s: old = %u/%u   new = %u/%u\n", olsr_ip_to_string(&buf, &link->neighbor_iface_addr),
 119       lq->smoothed_lq.valueLq, lq->smoothed_lq.valueNlq,
 120       lq->lq.valueLq, lq->lq.valueNlq);
 121 #endif
 122
 123     if (lq->smoothed_lq.valueLq < lq->lq.valueLq) {
 124       if (lq->lq.valueLq == 255 || lq->lq.valueLq - lq->smoothed_lq.valueLq > lq->smoothed_lq.valueLq/10) {
 125         relevant = true;
 126       }
 127     }
 128     else if (lq->smoothed_lq.valueLq > lq->lq.valueLq) {
 129       if (lq->smoothed_lq.valueLq - lq->lq.valueLq > lq->smoothed_lq.valueLq/10) {
 130         relevant = true;
 131       }
 132     }
 133     if (lq->smoothed_lq.valueNlq < lq->lq.valueNlq) {
 134       if (lq->lq.valueNlq == 255 || lq->lq.valueNlq - lq->smoothed_lq.valueNlq > lq->smoothed_lq.valueNlq/10) {
 135         relevant = true;
 136       }
 137     }
 138     else if (lq->smoothed_lq.valueNlq > lq->lq.valueNlq) {
 139       if (lq->smoothed_lq.valueNlq - lq->lq.valueNlq > lq->smoothed_lq.valueNlq/10) {
 140         relevant = true;
 141       }
 142     }
 143
 144     if (relevant) {
 145       memcpy(&lq->smoothed_lq, &lq->lq, sizeof(struct default_lq_ff));
 146       link->linkcost = default_lq_calc_cost_ff(&lq->smoothed_lq);
 147       triggered = true;
 148     }
 149   } OLSR_FOR_ALL_LINK_ENTRIES_END(link)
 150
 151   if (!triggered) {
 152     return;
 153   }
 154
 155   OLSR_FOR_ALL_LINK_ENTRIES(link) {
 156     lq = (struct default_lq_ff_hello *)link->linkquality;
 157
 158     if (lq->smoothed_lq.valueLq == 255 && lq->smoothed_lq.valueNlq == 255) {
 159       continue;
 160     }
 161
 162     if (lq->smoothed_lq.valueLq == lq->lq.valueLq && lq->smoothed_lq.valueNlq == lq->lq.valueNlq) {
 163       continue;
 164     }
 165
 166     memcpy(&lq->smoothed_lq, &lq->lq, sizeof(struct default_lq_ff));
 167     link->linkcost = default_lq_calc_cost_ff(&lq->smoothed_lq);
 168   } OLSR_FOR_ALL_LINK_ENTRIES_END(link)
 169
 170   olsr_relevant_linkcost_change();
 171 }
 172
 173 static void
 174 default_lq_parser_ff(struct olsr *olsr, struct interface *in_if, union olsr_ip_addr *from_addr)
 175 {
 176   const union olsr_ip_addr *main_addr;
 177   struct link_entry *lnk;
 178   struct default_lq_ff_hello *lq;
 179   uint32_t seq_diff;
 180
 181   /* Find main address */
 182   main_addr = mid_lookup_main_addr(from_addr);
 183
 184   /* Loopup link entry */
 185   lnk = lookup_link_entry(from_addr, main_addr, in_if);
 186   if (lnk == NULL) {
 187     return;
 188   }
 189
 190   lq = (struct default_lq_ff_hello *)lnk->linkquality;
 191
 192   /* ignore double package */
 193   if (lq->last_seq_nr == olsr->olsr_seqno) {
 194     struct ipaddr_str buf;
 195     olsr_syslog(OLSR_LOG_INFO, "detected duplicate packet with seqnr %d from %s on %s (%d Bytes)",
 196                 olsr->olsr_seqno,olsr_ip_to_string(&buf, from_addr),in_if->int_name,ntohs(olsr->olsr_packlen));
 197     return;
 198   }
 199
 200   if (lq->last_seq_nr > olsr->olsr_seqno) {
 201     seq_diff = (uint32_t) olsr->olsr_seqno + 65536 - lq->last_seq_nr;
 202   } else {
 203     seq_diff = olsr->olsr_seqno - lq->last_seq_nr;
 204   }
 205
 206   /* Jump in sequence numbers ? */
 207   if (seq_diff > 256) {
 208     seq_diff = 1;
 209   }
 210
 211   lq->received[lq->activePtr]++;
 212   lq->total[lq->activePtr] += seq_diff;
 213
 214   lq->last_seq_nr = olsr->olsr_seqno;
 215   lq->missed_hellos = 0;
 216 }
 217
 218 static void
 219 default_lq_ff_timer(void __attribute__ ((unused)) * context)
 220 {
 221   struct link_entry *link;
 222
 223   OLSR_FOR_ALL_LINK_ENTRIES(link) {
 224     struct default_lq_ff_hello *tlq = (struct default_lq_ff_hello *)link->linkquality;
 225     fpm ratio;
 226     int i, received, total;
 227
 228     received = 0;
 229     total = 0;
 230
 231     /* enlarge window if still in quickstart phase */
 232     if (tlq->windowSize < LQ_FF_WINDOW) {
 233       tlq->windowSize++;
 234     }
 235     for (i = 0; i < tlq->windowSize; i++) {
 236       received += tlq->received[i];
 237       total += tlq->total[i];
 238     }
 239
 240     /* calculate link quality */
 241     if (total == 0) {
 242       tlq->lq.valueLq = 0;
 243     } else {
 244       // start with link-loss-factor
 245       ratio = fpmidiv(itofpm(link->loss_link_multiplier), LINK_LOSS_MULTIPLIER);
 246
 247       /* keep missed hello periods in mind (round up hello interval to seconds) */
 248       if (tlq->missed_hellos > 1) {
 249         received = received - received * tlq->missed_hellos * link->inter->hello_etime/1000 / LQ_FF_WINDOW;
 250       }
 251
 252       // calculate received/total factor
 253       ratio = fpmmuli(ratio, received);
 254       ratio = fpmidiv(ratio, total);
 255       ratio = fpmmuli(ratio, 255);
 256
 257       tlq->lq.valueLq = (uint8_t) (fpmtoi(ratio));
 258     }
 259
 260     // shift buffer
 261     tlq->activePtr = (tlq->activePtr + 1) % LQ_FF_WINDOW;
 262     tlq->total[tlq->activePtr] = 0;
 263     tlq->received[tlq->activePtr] = 0;
 264   } OLSR_FOR_ALL_LINK_ENTRIES_END(link);
 265
 266   default_lq_ff_handle_lqchange();
 267 }
 268
 269 static void
 270 default_lq_initialize_ff(void)
 271 {
 272   olsr_packetparser_add_function(&default_lq_parser_ff);
 273   olsr_start_timer(1000, 0, OLSR_TIMER_PERIODIC, &default_lq_ff_timer, NULL, 0);
 274 }
 275
 276 static olsr_linkcost
 277 default_lq_calc_cost_ff(const void *ptr)
 278 {
 279   const struct default_lq_ff *lq = ptr;
 280   olsr_linkcost cost;
 281
 282   if (lq->valueLq < (unsigned int)(255 * MINIMAL_USEFUL_LQ) || lq->valueNlq < (unsigned int)(255 * MINIMAL_USEFUL_LQ)) {
 283     return LINK_COST_BROKEN;
 284   }
 285
 286   cost = fpmidiv(itofpm(255 * 255), (int)lq->valueLq * (int)lq->valueNlq);
 287
 288   if (cost > LINK_COST_BROKEN)
 289     return LINK_COST_BROKEN;
 290   if (cost == 0)
 291     return 1;
 292   return cost;
 293 }
 294
 295 static int
 296 default_lq_serialize_hello_lq_pair_ff(unsigned char *buff, void *ptr)
 297 {
 298   struct default_lq_ff *lq = ptr;
 299
 300   buff[0] = (unsigned char)lq->valueLq;
 301   buff[1] = (unsigned char)lq->valueNlq;
 302   buff[2] = (unsigned char)(0);
 303   buff[3] = (unsigned char)(0);
 304
 305   return 4;
 306 }
 307
 308 static void
 309 default_lq_deserialize_hello_lq_pair_ff(const uint8_t ** curr, void *ptr)
 310 {
 311   struct default_lq_ff *lq = ptr;
 312
 313   pkt_get_u8(curr, &lq->valueLq);
 314   pkt_get_u8(curr, &lq->valueNlq);
 315   pkt_ignore_u16(curr);
 316 }
 317
 318 static int
 319 default_lq_serialize_tc_lq_pair_ff(unsigned char *buff, void *ptr)
 320 {
 321   struct default_lq_ff *lq = ptr;
 322
 323   buff[0] = (unsigned char)lq->valueLq;
 324   buff[1] = (unsigned char)lq->valueNlq;
 325   buff[2] = (unsigned char)(0);
 326   buff[3] = (unsigned char)(0);
 327
 328   return 4;
 329 }
 330
 331 static void
 332 default_lq_deserialize_tc_lq_pair_ff(const uint8_t ** curr, void *ptr)
 333 {
 334   struct default_lq_ff *lq = ptr;
 335
 336   pkt_get_u8(curr, &lq->valueLq);
 337   pkt_get_u8(curr, &lq->valueNlq);
 338   pkt_ignore_u16(curr);
 339 }
 340
 341 static void
 342 default_lq_packet_loss_worker_ff(struct link_entry *link,
 343     void __attribute__ ((unused)) *ptr, bool lost)
 344 {
 345   struct default_lq_ff_hello *tlq = (struct default_lq_ff_hello *)link->linkquality;
 346
 347   if (lost) {
 348     tlq->missed_hellos++;
 349   }
 350   return;
 351 }
 352
 353 static void
 354 default_lq_memorize_foreign_hello_ff(void *ptrLocal, void *ptrForeign)
 355 {
 356   struct default_lq_ff_hello *local = ptrLocal;
 357   struct default_lq_ff *foreign = ptrForeign;
 358
 359   if (foreign) {
 360     local->lq.valueNlq = foreign->valueLq;
 361   } else {
 362     local->lq.valueNlq = 0;
 363   }
 364 }
 365
 366 static void
 367 default_lq_copy_link2neigh_ff(void *t, void *s)
 368 {
 369   struct default_lq_ff *target = t;
 370   struct default_lq_ff_hello *source = s;
 371   *target = source->smoothed_lq;
 372 }
 373
 374 static void
 375 default_lq_copy_link2tc_ff(void *t, void *s)
 376 {
 377   struct default_lq_ff *target = t;
 378   struct default_lq_ff_hello *source = s;
 379   *target = source->smoothed_lq;
 380 }
 381
 382 static void
 383 default_lq_clear_ff(void *target)
 384 {
 385   memset(target, 0, sizeof(struct default_lq_ff));
 386 }
 387
 388 static void
 389 default_lq_clear_ff_hello(void *target)
 390 {
 391   struct default_lq_ff_hello *local = target;
 392   int i;
 393
 394   default_lq_clear_ff(&local->lq);
 395   default_lq_clear_ff(&local->smoothed_lq);
 396   local->windowSize = LQ_FF_QUICKSTART_INIT;
 397   for (i = 0; i < LQ_FF_WINDOW; i++) {
 398     local->total[i] = 3;
 399   }
 400 }
 401
 402 static const char *
 403 default_lq_print_ff(void *ptr, char separator, struct lqtextbuffer *buffer)
 404 {
 405   struct default_lq_ff *lq = ptr;
 406
 407   snprintf(buffer->buf, sizeof(buffer->buf), "%s%c%s", fpmtoa(fpmidiv(itofpm((int)lq->valueLq), 255)), separator,
 408            fpmtoa(fpmidiv(itofpm((int)lq->valueNlq), 255)));
 409   return buffer->buf;
 410 }
 411
 412 static const char *
 413 default_lq_print_cost_ff(olsr_linkcost cost, struct lqtextbuffer *buffer)
 414 {
 415   snprintf(buffer->buf, sizeof(buffer->buf), "%s", fpmtoa(cost));
 416   return buffer->buf;
 417 }
 418
 419 /*
 420  * Local Variables:
 421  * c-basic-offset: 2
 422  * indent-tabs-mode: nil
 423  * End:
 424  */