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