src/link_set.c

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