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