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