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