src/link_set.c

   1 /*
   2  * The olsr.org Optimized Link-State Routing daemon(olsrd)
   3  * Copyright (c) 2004, Andreas Tønnesen(andreto@olsr.org)
   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  * $Id: link_set.c,v 1.80 2007/12/02 19:00:27 bernd67 Exp $
  40  */
  41
  42
  43 /*
  44  * Link sensing database for the OLSR routing daemon
  45  */
  46
  47 #include "defs.h"
  48 #include "link_set.h"
  49 #include "hysteresis.h"
  50 #include "mid_set.h"
  51 #include "mpr.h"
  52 #include "neighbor_table.h"
  53 #include "olsr.h"
  54 #include "scheduler.h"
  55 #include "lq_route.h"
  56 #include "net_olsr.h"
  57 #include "ipcalc.h"
  58
  59
  60 static clock_t hold_time_neighbor;
  61
  62 struct link_entry *link_set;
  63
  64
  65 static int
  66 check_link_status(const struct hello_message *message, const struct interface *in_if);
  67
  68 static void
  69 olsr_time_out_hysteresis(void);
  70
  71 static void olsr_time_out_packet_loss(void);
  72
  73 static struct link_entry *
  74 add_link_entry(const union olsr_ip_addr *, const union olsr_ip_addr *, const union olsr_ip_addr *, double, double, const struct interface *);
  75
  76 static void
  77 olsr_time_out_link_set(void);
  78
  79 static int
  80 get_neighbor_status(const union olsr_ip_addr *);
  81
  82
  83 clock_t
  84 get_hold_time_neighbor(void)
  85 {
  86   return hold_time_neighbor;
  87 }
  88
  89 struct link_entry *
  90 get_link_set(void)
  91 {
  92   return link_set;
  93 }
  94
  95 void
  96 olsr_init_link_set(void)
  97 {
  98
  99   /* Timers */
 100   hold_time_neighbor = (NEIGHB_HOLD_TIME*1000) / olsr_cnf->system_tick_divider;
 101
 102   olsr_register_timeout_function(&olsr_time_out_link_set, OLSR_TRUE);
 103   if(olsr_cnf->use_hysteresis)
 104     {
 105       olsr_register_timeout_function(&olsr_time_out_hysteresis, OLSR_TRUE);
 106     }
 107
 108   if (olsr_cnf->lq_level > 0)
 109     {
 110       olsr_register_timeout_function(&olsr_time_out_packet_loss, OLSR_TRUE);
 111     }
 112 }
 113
 114
 115
 116 /**
 117  * Get the status of a link. The status is based upon different
 118  * timeouts in the link entry.
 119  *
 120  *@param remote address of the remote interface
 121  *
 122  *@return the link status of the link
 123  */
 124 int
 125 lookup_link_status(const struct link_entry *entry)
 126 {
 127
 128   if(entry == NULL || link_set == NULL)
 129     return UNSPEC_LINK;
 130
 131   /*
 132    * Hysteresis
 133    */
 134   if(olsr_cnf->use_hysteresis)
 135     {
 136       /*
 137         if L_LOST_LINK_time is not expired, the link is advertised
 138         with a link type of LOST_LINK.
 139       */
 140
 141       if(!TIMED_OUT(entry->L_LOST_LINK_time))
 142         return LOST_LINK;
 143       /*
 144         otherwise, if L_LOST_LINK_time is expired and L_link_pending
 145         is set to "true", the link SHOULD NOT be advertised at all;
 146       */
 147       if(entry->L_link_pending == 1)
 148         {
 149 #ifndef NODEBUG
 150           struct ipaddr_str buf;
 151           OLSR_PRINTF(3, "HYST[%s]: Setting to HIDE\n", olsr_ip_to_string(&buf, &entry->neighbor_iface_addr));
 152 #endif
 153           return HIDE_LINK;
 154         }
 155       /*
 156         otherwise, if L_LOST_LINK_time is expired and L_link_pending
 157         is set to "false", the link is advertised as described
 158         previously in section 6.
 159       */
 160     }
 161
 162   if(!TIMED_OUT(entry->SYM_time))
 163     return SYM_LINK;
 164
 165   if(!TIMED_OUT(entry->ASYM_time))
 166     return ASYM_LINK;
 167
 168   return LOST_LINK;
 169
 170
 171 }
 172
 173
 174
 175
 176
 177
 178 /**
 179  *Find the "best" link status to a
 180  *neighbor
 181  *
 182  *@param address the address to check for
 183  *
 184  *@return SYM_LINK if a symmetric link exists 0 if not
 185  */
 186 static int
 187 get_neighbor_status(const union olsr_ip_addr *address)
 188 {
 189   const union olsr_ip_addr *main_addr;
 190   struct interface   *ifs;
 191
 192   //printf("GET_NEIGHBOR_STATUS\n");
 193
 194   /* Find main address */
 195   if(!(main_addr = mid_lookup_main_addr(address)))
 196     main_addr = address;
 197
 198   //printf("\tmain: %s\n", olsr_ip_to_string(main_addr));
 199
 200   /* Loop trough local interfaces to check all possebilities */
 201   for(ifs = ifnet; ifs != NULL; ifs = ifs->int_next)
 202     {
 203       struct mid_address   *aliases;
 204       struct link_entry  *lnk = lookup_link_entry(main_addr, NULL, ifs);
 205
 206       //printf("\tChecking %s->", olsr_ip_to_string(&ifs->ip_addr));
 207       //printf("%s : ", olsr_ip_to_string(main_addr));
 208       if(lnk != NULL)
 209         {
 210           //printf("%d\n", lookup_link_status(link));
 211           if(lookup_link_status(lnk) == SYM_LINK)
 212             return SYM_LINK;
 213         }
 214       /* Get aliases */
 215       for(aliases = mid_lookup_aliases(main_addr);
 216           aliases != NULL;
 217           aliases = aliases->next_alias)
 218         {
 219           //printf("\tChecking %s->", olsr_ip_to_string(&ifs->ip_addr));
 220           //printf("%s : ", olsr_ip_to_string(&aliases->address));
 221             lnk = lookup_link_entry(&aliases->alias, NULL, ifs);
 222             if(lnk != NULL)
 223             {
 224               //printf("%d\n", lookup_link_status(link));
 225
 226               if(lookup_link_status(lnk) == SYM_LINK)
 227                 return SYM_LINK;
 228             }
 229         }
 230     }
 231
 232   return 0;
 233 }
 234
 235 /**
 236  * Find best link to a neighbor
 237  */
 238
 239 struct link_entry *
 240 get_best_link_to_neighbor(const union olsr_ip_addr *remote)
 241 {
 242   const union olsr_ip_addr *main_addr;
 243   struct link_entry *walker, *good_link, *backup_link;
 244   int curr_metric = MAX_IF_METRIC;
 245   float curr_lq = -1.0;
 246
 247   // main address lookup
 248
 249   main_addr = mid_lookup_main_addr(remote);
 250
 251   // "remote" *already is* the main address
 252
 253   if (main_addr == NULL)
 254     main_addr = remote;
 255
 256   // we haven't selected any links, yet
 257
 258   good_link = NULL;
 259   backup_link = NULL;
 260
 261   // loop through all links that we have
 262
 263   for (walker = link_set; walker != NULL; walker = walker->next)
 264   {
 265     // if this is not a link to the neighour in question, skip
 266
 267     if (!ipequal(&walker->neighbor->neighbor_main_addr, main_addr))
 268       continue;
 269
 270     // handle the non-LQ, RFC-compliant case
 271
 272     if (olsr_cnf->lq_level == 0)
 273     {
 274       struct interface *tmp_if;
 275
 276       // find the interface for the link - we select the link with the
 277       // best local interface metric
 278       tmp_if = walker->if_name ? if_ifwithname(walker->if_name) :
 279               if_ifwithaddr(&walker->local_iface_addr);
 280
 281       if(!tmp_if)
 282         continue;
 283
 284       // is this interface better than anything we had before?
 285
 286       if ((tmp_if->int_metric < curr_metric) ||
 287           // use the requested remote interface address as a tie-breaker
 288           ((tmp_if->int_metric == curr_metric) &&
 289            ipequal(&walker->local_iface_addr, remote)))
 290       {
 291         // memorize the interface's metric
 292
 293         curr_metric = tmp_if->int_metric;
 294
 295         // prefer symmetric links over asymmetric links
 296
 297         if (lookup_link_status(walker) == SYM_LINK)
 298           good_link = walker;
 299
 300         else
 301           backup_link = walker;
 302       }
 303     }
 304
 305     // handle the LQ, non-RFC compliant case
 306
 307     else
 308     {
 309       float tmp_lq;
 310
 311       // calculate the bi-directional link quality - we select the link
 312       // with the best link quality
 313
 314       tmp_lq = walker->loss_link_quality * walker->neigh_link_quality;
 315
 316       // is this link better than anything we had before?
 317
 318       if((tmp_lq > curr_lq) ||
 319          // use the requested remote interface address as a tie-breaker
 320          ((tmp_lq == curr_lq) && ipequal(&walker->local_iface_addr, remote)))
 321       {
 322         // memorize the link quality
 323
 324         curr_lq = tmp_lq;
 325
 326         // prefer symmetric links over asymmetric links
 327
 328         if(lookup_link_status(walker) == SYM_LINK)
 329           good_link = walker;
 330
 331         else
 332           backup_link = walker;
 333       }
 334     }
 335   }
 336
 337   // if we haven't found any symmetric links, try to return an
 338   // asymmetric link
 339
 340   return good_link ? good_link : backup_link;
 341 }
 342
 343 static void set_loss_link_multiplier(struct link_entry *entry)
 344 {
 345   struct interface *inter;
 346   struct olsr_if *cfg_inter;
 347   struct olsr_lq_mult *mult;
 348   float val = -1.0;
 349   union olsr_ip_addr null_addr;
 350
 351   // find the interface for the link
 352
 353   inter = if_ifwithaddr(&entry->local_iface_addr);
 354
 355   // find the interface configuration for the interface
 356
 357   for (cfg_inter = olsr_cnf->interfaces; cfg_inter != NULL;
 358        cfg_inter = cfg_inter->next)
 359     if (cfg_inter->interf == inter)
 360       break;
 361
 362   // create a null address for comparison
 363
 364   memset(&null_addr, 0, sizeof (union olsr_ip_addr));
 365
 366   // loop through the multiplier entries
 367
 368   for (mult = cfg_inter->cnf->lq_mult; mult != NULL; mult = mult->next)
 369   {
 370     // use the default multiplier only if there isn't any entry that
 371     // has a matching IP address
 372
 373     if ((ipequal(&mult->addr, &null_addr) && val < 0.0) ||
 374         ipequal(&mult->addr, &entry->neighbor_iface_addr))
 375       val = mult->val;
 376   }
 377
 378   // if we have not found an entry, then use the default multiplier
 379
 380   if (val < 0)
 381     val = 1.0;
 382
 383   // store the multiplier
 384
 385   entry->loss_link_multiplier = val;
 386 }
 387
 388 /**
 389  *Delete all interface link entries
 390  *
 391  *@param interface ip address
 392  */
 393
 394 void
 395 del_if_link_entries(const union olsr_ip_addr *int_addr)
 396 {
 397   struct link_entry *tmp_link_set, *last_link_entry;
 398
 399   if(link_set == NULL)
 400     return;
 401
 402   tmp_link_set = link_set;
 403   last_link_entry = NULL;
 404
 405   while(tmp_link_set)
 406     {
 407
 408       if(ipequal(int_addr, &tmp_link_set->local_iface_addr))
 409         {
 410           if(last_link_entry != NULL)
 411             {
 412               last_link_entry->next = tmp_link_set->next;
 413
 414               /* Delete neighbor entry */
 415               if(tmp_link_set->neighbor->linkcount == 1)
 416                 olsr_delete_neighbor_table(&tmp_link_set->neighbor->neighbor_main_addr);
 417               else
 418                 tmp_link_set->neighbor->linkcount--;
 419
 420               //olsr_delete_neighbor_if_no_link(&tmp_link_set->neighbor->neighbor_main_addr);
 421               changes_neighborhood = OLSR_TRUE;
 422
 423               free(tmp_link_set);
 424               tmp_link_set = last_link_entry;
 425             }
 426           else
 427             {
 428               link_set = tmp_link_set->next; /* CHANGED */
 429
 430               /* Delete neighbor entry */
 431               if(tmp_link_set->neighbor->linkcount == 1)
 432                 olsr_delete_neighbor_table(&tmp_link_set->neighbor->neighbor_main_addr);
 433               else
 434                 tmp_link_set->neighbor->linkcount--;
 435
 436               changes_neighborhood = OLSR_TRUE;
 437
 438               free(tmp_link_set);
 439               tmp_link_set = link_set;
 440               continue;
 441             }
 442         }
 443
 444       last_link_entry = tmp_link_set;
 445       tmp_link_set = tmp_link_set->next;
 446     }
 447
 448   return;
 449 }
 450
 451 /**
 452  *Nothing mysterious here.
 453  *Adding a new link entry to the link set.
 454  *
 455  *@param local the local IP address
 456  *@param remote the remote IP address
 457  *@param remote_main the remote nodes main address
 458  *@param vtime the validity time of the entry
 459  *@param htime the HELLO interval of the remote node
 460  *@param local_if the local interface
 461  */
 462
 463 static struct link_entry *
 464 add_link_entry(const union olsr_ip_addr *local,
 465                const union olsr_ip_addr *remote,
 466                const union olsr_ip_addr *remote_main,
 467                double vtime,
 468                double htime,
 469                const struct interface *local_if)
 470 {
 471   struct link_entry *new_link;
 472   struct neighbor_entry *neighbor;
 473   struct link_entry *tmp_link_set = lookup_link_entry(remote, remote_main, local_if);
 474   if (tmp_link_set) {
 475     return tmp_link_set;
 476   }
 477   /*
 478    * if there exists no link tuple with
 479    * L_neighbor_iface_addr == Source Address
 480    */
 481
 482 #ifdef DEBUG
 483   {
 484 #ifndef NODEBUG
 485     struct ipaddr_str localbuf, rembuf;
 486 #endif
 487     OLSR_PRINTF(1, "Adding %s=>%s to link set\n", olsr_ip_to_string(&localbuf, local), olsr_ip_to_string(&rembuf, remote));
 488   }
 489 #endif
 490
 491   /* a new tuple is created with... */
 492
 493   new_link = olsr_malloc(sizeof(struct link_entry), "new link entry");
 494
 495   memset(new_link, 0 , sizeof(struct link_entry));
 496
 497   /* copy if_name, if it is defined */
 498   if (local_if->int_name)
 499     {
 500       new_link->if_name = olsr_malloc(strlen(local_if->int_name)+1, "target of if_name in new link entry");
 501       strcpy(new_link->if_name, local_if->int_name);
 502     } else
 503       new_link->if_name = NULL;
 504
 505   /*
 506    * L_local_iface_addr = Address of the interface
 507    * which received the HELLO message
 508    */
 509   //printf("\tLocal IF: %s\n", olsr_ip_to_string(local));
 510   new_link->local_iface_addr = *local;
 511   /* L_neighbor_iface_addr = Source Address */
 512   new_link->neighbor_iface_addr = *remote;
 513
 514   /* L_SYM_time            = current time - 1 (expired) */
 515   new_link->SYM_time = now_times - 1;
 516
 517   /* L_time = current time + validity time */
 518   new_link->time = GET_TIMESTAMP(vtime*1000);
 519
 520   new_link->prev_status = ASYM_LINK;
 521
 522   /* HYSTERESIS */
 523   if(olsr_cnf->use_hysteresis)
 524     {
 525       new_link->L_link_pending = 1;
 526       new_link->L_LOST_LINK_time = GET_TIMESTAMP(vtime*1000);
 527       new_link->hello_timeout = GET_TIMESTAMP(htime*1500);
 528       new_link->last_htime = htime;
 529       new_link->olsr_seqno = 0;
 530       new_link->olsr_seqno_valid = OLSR_FALSE;
 531     }
 532
 533   new_link->L_link_quality = 0.0;
 534
 535   if (olsr_cnf->lq_level > 0)
 536     {
 537       new_link->loss_hello_int = htime;
 538
 539       new_link->loss_timeout = GET_TIMESTAMP(htime * 1500.0);
 540
 541       new_link->loss_seqno = 0;
 542       new_link->loss_seqno_valid = 0;
 543       new_link->loss_missed_hellos = 0;
 544
 545       new_link->lost_packets = 0;
 546       new_link->total_packets = 0;
 547
 548       new_link->loss_index = 0;
 549
 550       memset(new_link->loss_bitmap, 0, sizeof (new_link->loss_bitmap));
 551
 552       set_loss_link_multiplier(new_link);
 553     }
 554
 555   new_link->loss_link_quality = 0.0;
 556   new_link->neigh_link_quality = 0.0;
 557
 558   new_link->loss_link_quality2 = 0.0;
 559   new_link->neigh_link_quality2 = 0.0;
 560
 561   new_link->saved_loss_link_quality = 0.0;
 562   new_link->saved_neigh_link_quality = 0.0;
 563
 564   /* Add to queue */
 565   new_link->next = link_set;
 566   link_set = new_link;
 567
 568
 569   /*
 570    * Create the neighbor entry
 571    */
 572
 573   /* Neighbor MUST exist! */
 574   neighbor = olsr_lookup_neighbor_table(remote_main);
 575   if(neighbor == NULL)
 576     {
 577 #ifdef DEBUG
 578 #ifndef NODEBUG
 579       struct ipaddr_str buf;
 580 #endif
 581       OLSR_PRINTF(3, "ADDING NEW NEIGHBOR ENTRY %s FROM LINK SET\n", olsr_ip_to_string(&buf, remote_main));
 582 #endif
 583       neighbor = olsr_insert_neighbor_table(remote_main);
 584     }
 585
 586   neighbor->linkcount++;
 587   new_link->neighbor = neighbor;
 588   if(!ipequal(remote, remote_main))
 589     {
 590       /* Add MID alias if not already registered */
 591       /* This is kind of sketchy... and not specified
 592        * in the RFC. We can only guess a vtime.
 593        * We'll go for one that is hopefully long
 594        * enough in most cases. 10 seconds
 595        */
 596
 597     /* Erik Tromp - commented out. It is not RFC-compliant. Also, MID aliases
 598      * that are not explicitly declared by a node will be removed as soon as
 599      * the olsr_prune_aliases(...) function is called.
 600      *
 601      * OLSR_PRINTF(1, "Adding MID alias main %s ", olsr_ip_to_string(remote_main));
 602      * OLSR_PRINTF(1, "-> %s based on HELLO\n\n", olsr_ip_to_string(remote));
 603      * insert_mid_alias(remote_main, remote, MID_ALIAS_HACK_VTIME);
 604      */
 605     }
 606
 607   return link_set;
 608 }
 609
 610
 611 /**
 612  *Lookup the status of a link.
 613  *
 614  *@param int_addr address of the remote interface
 615  *
 616  *@return 1 of the link is symmertic 0 if not
 617  */
 618
 619 int
 620 check_neighbor_link(const union olsr_ip_addr *int_addr)
 621 {
 622   struct link_entry *tmp_link_set;
 623
 624   tmp_link_set = link_set;
 625
 626   while(tmp_link_set)
 627     {
 628       if(ipequal(int_addr, &tmp_link_set->neighbor_iface_addr))
 629         return lookup_link_status(tmp_link_set);
 630       tmp_link_set = tmp_link_set->next;
 631     }
 632   return UNSPEC_LINK;
 633 }
 634
 635
 636 /**
 637  *Lookup a link entry
 638  *
 639  *@param remote the remote interface address
 640  *@param remote_main the remote nodes main address
 641  *@param local the local interface address
 642  *
 643  *@return the link entry if found, NULL if not
 644  */
 645 struct link_entry *
 646 lookup_link_entry(const union olsr_ip_addr *remote, const union olsr_ip_addr *remote_main, const struct interface *local)
 647 {
 648   struct link_entry *tmp_link_set;
 649
 650   tmp_link_set = link_set;
 651
 652   while(tmp_link_set)
 653     {
 654       if(ipequal(remote, &tmp_link_set->neighbor_iface_addr) &&
 655          (tmp_link_set->if_name
 656           ? !strcmp(tmp_link_set->if_name, local->int_name)
 657           : ipequal(&local->ip_addr, &tmp_link_set->local_iface_addr)
 658           ) &&
 659          /* check the remote-main address only if there is one given */
 660          (remote_main == NULL || ipequal(remote_main, &tmp_link_set->neighbor->neighbor_main_addr))
 661          )
 662         return tmp_link_set;
 663       tmp_link_set = tmp_link_set->next;
 664     }
 665   return NULL;
 666
 667 }
 668
 669
 670
 671
 672
 673
 674
 675 /**
 676  *Update a link entry. This is the "main entrypoint" in
 677  *the link-sensing. This function is called from the HELLO
 678  *parser function.
 679  *It makes sure a entry is updated or created.
 680  *
 681  *@param local the local IP address
 682  *@param remote the remote IP address
 683  *@param message the HELLO message
 684  *@param in_if the interface on which this HELLO was received
 685  *
 686  *@return the link_entry struct describing this link entry
 687  */
 688 struct link_entry *
 689 update_link_entry(const union olsr_ip_addr *local,
 690                   const union olsr_ip_addr *remote,
 691                   const struct hello_message *message,
 692                   const struct interface *in_if)
 693 {
 694   struct link_entry *entry;
 695
 696   /* Add if not registered */
 697   entry = add_link_entry(local, remote, &message->source_addr, message->vtime, message->htime, in_if);
 698
 699   /* Update ASYM_time */
 700   //printf("Vtime is %f\n", message->vtime);
 701   /* L_ASYM_time = current time + validity time */
 702   entry->ASYM_time = GET_TIMESTAMP(message->vtime*1000);
 703
 704   entry->prev_status = check_link_status(message, in_if);
 705
 706   //printf("Status %d\n", status);
 707
 708   switch(entry->prev_status)
 709     {
 710     case(LOST_LINK):
 711       /* L_SYM_time = current time - 1 (i.e., expired) */
 712       entry->SYM_time = now_times - 1;
 713
 714       break;
 715     case(SYM_LINK):
 716     case(ASYM_LINK):
 717       /* L_SYM_time = current time + validity time */
 718       //printf("updating SYM time for %s\n", olsr_ip_to_string(remote));
 719       entry->SYM_time = GET_TIMESTAMP(message->vtime*1000);
 720
 721       /* L_time = L_SYM_time + NEIGHB_HOLD_TIME */
 722       entry->time = entry->SYM_time + hold_time_neighbor;
 723
 724       break;
 725     default:;
 726     }
 727
 728   /* L_time = max(L_time, L_ASYM_time) */
 729   if(entry->time < entry->ASYM_time)
 730     entry->time = entry->ASYM_time;
 731
 732
 733   /*
 734   printf("Updating link LOCAL: %s ", olsr_ip_to_string(local));
 735   printf("REMOTE: %s\n", olsr_ip_to_string(remote));
 736   printf("VTIME: %f ", message->vtime);
 737   printf("STATUS: %d\n", status);
 738   */
 739
 740   /* Update hysteresis values */
 741   if(olsr_cnf->use_hysteresis)
 742     olsr_process_hysteresis(entry);
 743
 744   /* Update neighbor */
 745   update_neighbor_status(entry->neighbor, get_neighbor_status(remote));
 746
 747   return entry;
 748 }
 749
 750
 751 /**
 752  * Fuction that updates all registered pointers to
 753  * one neighbor entry with another pointer
 754  * Used by MID updates.
 755  *
 756  *@old the pointer to replace
 757  *@new the pointer to use instead of "old"
 758  *
 759  *@return the number of entries updated
 760  */
 761 int
 762 replace_neighbor_link_set(const struct neighbor_entry *old,
 763                           struct neighbor_entry *new)
 764 {
 765   struct link_entry *tmp_link_set;
 766   int retval;
 767
 768   retval = 0;
 769
 770   if(link_set == NULL)
 771     return retval;
 772
 773   tmp_link_set = link_set;
 774
 775   while(tmp_link_set)
 776     {
 777
 778       if(tmp_link_set->neighbor == old)
 779         {
 780           tmp_link_set->neighbor = new;
 781           retval++;
 782         }
 783       tmp_link_set = tmp_link_set->next;
 784     }
 785
 786   return retval;
 787
 788 }
 789
 790
 791 /**
 792  *Checks the link status to a neighbor by
 793  *looking in a received HELLO message.
 794  *
 795  *@param message the HELLO message to check
 796  *
 797  *@return the link status
 798  */
 799 static int
 800 check_link_status(const struct hello_message *message, const struct interface *in_if)
 801 {
 802   int ret = UNSPEC_LINK;
 803   struct hello_neighbor  *neighbors;
 804
 805   neighbors = message->neighbors;
 806
 807   while(neighbors!=NULL)
 808     {
 809       /*
 810        * Note: If a neigh has 2 cards we can reach, the neigh
 811        * will send a Hello with the same IP mentined twice
 812        */
 813       if(ipequal(&neighbors->address, &in_if->ip_addr))
 814         {
 815           //printf("ok");
 816           ret = neighbors->link;
 817           if (SYM_LINK == ret) break;
 818         }
 819
 820       neighbors = neighbors->next;
 821     }
 822
 823
 824   return ret;
 825 }
 826
 827
 828 /**
 829  *Time out the link set. In other words, the link
 830  *set is traversed and all non-valid entries are
 831  *deleted.
 832  *
 833  */
 834 static void
 835 olsr_time_out_link_set(void)
 836 {
 837
 838   struct link_entry *tmp_link_set, *last_link_entry;
 839
 840   if(link_set == NULL)
 841     return;
 842
 843   tmp_link_set = link_set;
 844   last_link_entry = NULL;
 845
 846   while(tmp_link_set)
 847     {
 848
 849       if(TIMED_OUT(tmp_link_set->time))
 850         {
 851           if(last_link_entry != NULL)
 852             {
 853               last_link_entry->next = tmp_link_set->next;
 854
 855               /* Delete neighbor entry */
 856               if(tmp_link_set->neighbor->linkcount == 1)
 857                 olsr_delete_neighbor_table(&tmp_link_set->neighbor->neighbor_main_addr);
 858               else
 859                 tmp_link_set->neighbor->linkcount--;
 860
 861               //olsr_delete_neighbor_if_no_link(&tmp_link_set->neighbor->neighbor_main_addr);
 862               changes_neighborhood = OLSR_TRUE;
 863               free(tmp_link_set->if_name);
 864               free(tmp_link_set);
 865               tmp_link_set = last_link_entry;
 866             }
 867           else
 868             {
 869               link_set = tmp_link_set->next; /* CHANGED */
 870
 871               /* Delete neighbor entry */
 872               if(tmp_link_set->neighbor->linkcount == 1)
 873                 olsr_delete_neighbor_table(&tmp_link_set->neighbor->neighbor_main_addr);
 874               else
 875                 tmp_link_set->neighbor->linkcount--;
 876
 877               changes_neighborhood = OLSR_TRUE;
 878
 879               free(tmp_link_set->if_name);
 880               free(tmp_link_set);
 881               tmp_link_set = link_set;
 882               continue;
 883             }
 884         }
 885       else if((tmp_link_set->prev_status == SYM_LINK) &&
 886               TIMED_OUT(tmp_link_set->SYM_time))
 887         {
 888           tmp_link_set->prev_status = lookup_link_status(tmp_link_set);
 889           update_neighbor_status(tmp_link_set->neighbor,
 890                                  get_neighbor_status(&tmp_link_set->neighbor_iface_addr));
 891           changes_neighborhood = OLSR_TRUE;
 892         }
 893
 894       last_link_entry = tmp_link_set;
 895       tmp_link_set = tmp_link_set->next;
 896     }
 897
 898   return;
 899 }
 900
 901
 902
 903
 904 /**
 905  *Updates links that we have not received
 906  *HELLO from in expected time according to
 907  *hysteresis.
 908  *
 909  *@return nada
 910  */
 911 static void
 912 olsr_time_out_hysteresis(void)
 913 {
 914   struct link_entry *tmp_link_set;
 915
 916   if(link_set == NULL)
 917     return;
 918
 919   tmp_link_set = link_set;
 920
 921   while(tmp_link_set)
 922     {
 923       if(TIMED_OUT(tmp_link_set->hello_timeout))
 924         {
 925 #ifndef NODEBUG
 926           struct ipaddr_str buf;
 927 #endif
 928           tmp_link_set->L_link_quality = olsr_hyst_calc_instability(tmp_link_set->L_link_quality);
 929           OLSR_PRINTF(1, "HYST[%s] HELLO timeout %0.3f\n", olsr_ip_to_string(&buf, &tmp_link_set->neighbor_iface_addr), tmp_link_set->L_link_quality);
 930           /* Update hello_timeout - NO SLACK THIS TIME */
 931           tmp_link_set->hello_timeout = GET_TIMESTAMP(tmp_link_set->last_htime*1000);
 932           /* Recalculate status */
 933           /* Update hysteresis values */
 934           olsr_process_hysteresis(tmp_link_set);
 935
 936           /* update neighbor status */
 937
 938
 939           /* Update neighbor */
 940           update_neighbor_status(tmp_link_set->neighbor,
 941                                  get_neighbor_status(&tmp_link_set->neighbor_iface_addr));
 942
 943           /* Update seqno - not mentioned in the RFC... kind of a hack.. */
 944           tmp_link_set->olsr_seqno++;
 945         }
 946       tmp_link_set = tmp_link_set->next;
 947     }
 948
 949   return;
 950 }
 951
 952 void olsr_print_link_set(void)
 953 {
 954 #ifndef NODEBUG
 955   /* The whole function makes no sense without it. */
 956   struct link_entry *walker;
 957   const int addrsize = olsr_cnf->ip_version == AF_INET ? 15 : 39;
 958
 959   OLSR_PRINTF(0, "\n--- %02d:%02d:%02d.%02d ---------------------------------------------------- LINKS\n\n",
 960               nowtm->tm_hour,
 961               nowtm->tm_min,
 962               nowtm->tm_sec,
 963               (int)now.tv_usec/10000U);
 964   OLSR_PRINTF(1, "%-*s  %-6s %-6s %-6s %-6s %-6s %s\n", addrsize, "IP address", "hyst", "LQ", "lost", "total","NLQ", "ETX");
 965
 966   for (walker = link_set; walker != NULL; walker = walker->next)
 967   {
 968     struct ipaddr_str buf;
 969     float etx;
 970
 971     if (walker->loss_link_quality < MIN_LINK_QUALITY || walker->neigh_link_quality < MIN_LINK_QUALITY)
 972       etx = 0.0;
 973     else
 974       etx = 1.0 / (walker->loss_link_quality * walker->neigh_link_quality);
 975
 976     OLSR_PRINTF(1, "%-*s  %5.3f  %5.3f  %-3d    %-3d    %5.3f  %.2f\n",
 977                 addrsize, olsr_ip_to_string(&buf, &walker->neighbor_iface_addr),
 978                 walker->L_link_quality,
 979                 walker->loss_link_quality,
 980                 walker->lost_packets,
 981                 walker->total_packets,
 982                 walker->neigh_link_quality,
 983                 etx);
 984   }
 985 #endif
 986 }
 987
 988 static void update_packet_loss_worker(struct link_entry *entry, int lost)
 989 {
 990   unsigned char mask = 1 << (entry->loss_index & 7);
 991   const int idx = entry->loss_index >> 3;
 992   double rel_lq, saved_lq;
 993
 994   if (lost == 0)
 995     {
 996       // packet not lost
 997
 998       if ((entry->loss_bitmap[idx] & mask) != 0)
 999         {
1000           // but the packet that we replace was lost
1001           // => decrement packet loss
1002
1003           entry->loss_bitmap[idx] &= ~mask;
1004           entry->lost_packets--;
1005         }
1006     }
1007
1008   else
1009     {
1010       // packet lost
1011
1012       if ((entry->loss_bitmap[idx] & mask) == 0)
1013         {
1014           // but the packet that we replace was not lost
1015           // => increment packet loss
1016
1017           entry->loss_bitmap[idx] |= mask;
1018           entry->lost_packets++;
1019         }
1020     }
1021
1022   // move to the next packet
1023
1024   entry->loss_index++;
1025
1026   // wrap around at the end of the packet loss window
1027
1028   if (entry->loss_index >= olsr_cnf->lq_wsize)
1029     entry->loss_index = 0;
1030
1031   // count the total number of handled packets up to the window size
1032
1033   if (entry->total_packets < olsr_cnf->lq_wsize)
1034     entry->total_packets++;
1035
1036   // the current reference link quality
1037
1038   saved_lq = entry->saved_loss_link_quality;
1039
1040   if (saved_lq == 0.0)
1041     saved_lq = -1.0;
1042
1043   // calculate the new link quality
1044   //
1045   // start slowly: receive the first packet => link quality = 1 / n
1046   //               (n = window size)
1047   entry->loss_link_quality =
1048     (float)(entry->total_packets - entry->lost_packets) /
1049     (float)(olsr_cnf->lq_wsize < (2 * 4) ? olsr_cnf->lq_wsize:
1050     4 * (((float)olsr_cnf->lq_wsize / 4 - 1) * entry->total_packets + olsr_cnf->lq_wsize) / olsr_cnf->lq_wsize);
1051
1052   // multiply the calculated link quality with the user-specified multiplier
1053
1054   entry->loss_link_quality *= entry->loss_link_multiplier;
1055
1056   // if the link quality has changed by more than 10 percent,
1057   // print the new link quality table
1058
1059   rel_lq = entry->loss_link_quality / saved_lq;
1060
1061   if (rel_lq > 1.1 || rel_lq < 0.9)
1062     {
1063       entry->saved_loss_link_quality = entry->loss_link_quality;
1064
1065       if (olsr_cnf->lq_dlimit > 0)
1066       {
1067         changes_neighborhood = OLSR_TRUE;
1068         changes_topology = OLSR_TRUE;
1069       }
1070
1071       else
1072         OLSR_PRINTF(3, "Skipping Dijkstra (1)\n");
1073
1074       // create a new ANSN
1075
1076       // XXX - we should check whether we actually
1077       // announce this neighbour
1078
1079       signal_link_changes(OLSR_TRUE);
1080     }
1081 }
1082
1083 void olsr_update_packet_loss_hello_int(struct link_entry *entry,
1084                                        double loss_hello_int)
1085 {
1086   // called for every LQ HELLO message - update the timeout
1087   // with the htime value from the message
1088
1089   entry->loss_hello_int = loss_hello_int;
1090 }
1091
1092 void olsr_update_packet_loss(const union olsr_ip_addr *rem, const struct interface *loc,
1093                              olsr_u16_t seqno)
1094 {
1095   struct link_entry *entry;
1096
1097   // called for every OLSR packet
1098
1099   entry = lookup_link_entry(rem, NULL, loc);
1100
1101   // it's the very first LQ HELLO message - we do not yet have a link
1102
1103   if (entry == NULL)
1104     return;
1105
1106   // a) have we seen a packet before, i.e. is the sequence number valid?
1107
1108   // b) heuristically detect a restart (= sequence number reset)
1109   //    of our neighbor
1110
1111   if (entry->loss_seqno_valid != 0 &&
1112       (unsigned short)(seqno - entry->loss_seqno) < 100)
1113     {
1114       // loop through all lost packets
1115
1116       while (entry->loss_seqno != seqno)
1117         {
1118           // have we already considered all lost LQ HELLO messages?
1119
1120           if (entry->loss_missed_hellos == 0)
1121             update_packet_loss_worker(entry, 1);
1122
1123           // if not, then decrement the number of lost LQ HELLOs
1124
1125           else
1126             entry->loss_missed_hellos--;
1127
1128           entry->loss_seqno++;
1129         }
1130     }
1131
1132   // we have received a packet, otherwise this function would not
1133   // have been called
1134
1135   update_packet_loss_worker(entry, 0);
1136
1137   // (re-)initialize
1138
1139   entry->loss_missed_hellos = 0;
1140   entry->loss_seqno = seqno + 1;
1141
1142   // we now have a valid serial number for sure
1143
1144   entry->loss_seqno_valid = 1;
1145
1146   // timeout for the first lost packet is 1.5 x htime
1147
1148   entry->loss_timeout = GET_TIMESTAMP(entry->loss_hello_int * 1500.0);
1149 }
1150
1151 static void olsr_time_out_packet_loss(void)
1152 {
1153   struct link_entry *walker;
1154
1155   // loop through all links
1156
1157   for (walker = link_set; walker != NULL; walker = walker->next)
1158     {
1159       // find a link that has not seen any packets for a very long
1160       // time (first time: 1.5 x htime, subsequently: 1.0 x htime)
1161
1162       if (!TIMED_OUT(walker->loss_timeout))
1163         continue;
1164
1165       // count the lost packet
1166
1167       update_packet_loss_worker(walker, 1);
1168
1169       // memorize that we've counted the packet, so that we do not
1170       // count it a second time later
1171
1172       walker->loss_missed_hellos++;
1173
1174       // next timeout in 1.0 x htime
1175
1176       walker->loss_timeout = GET_TIMESTAMP(walker->loss_hello_int * 1000.0);
1177     }
1178 }
1179
1180 void olsr_update_dijkstra_link_qualities(void)
1181 {
1182   struct link_entry *walker;
1183
1184   for (walker = link_set; walker != NULL; walker = walker->next)
1185   {
1186     walker->loss_link_quality2 = walker->loss_link_quality;
1187     walker->neigh_link_quality2 = walker->neigh_link_quality;
1188   }
1189 }
1190
1191 float olsr_calc_link_etx(const struct link_entry *link)
1192 {
1193   return link->loss_link_quality < MIN_LINK_QUALITY ||
1194          link->neigh_link_quality < MIN_LINK_QUALITY
1195              ? 0.0
1196              : 1.0 / (link->loss_link_quality * link->neigh_link_quality);
1197 }