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