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