* OLSR_PRINTF() is now a real C expression
[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.68 2007/04/25 22:08:09 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(void)
83 {
84   return hold_time_neighbor;
85 }
86
87 struct link_entry *
88 get_link_set(void)
89 {
90   return link_set;
91 }
92
93 void
94 olsr_init_link_set(void)
95 {
96
97   /* Timers */
98   hold_time_neighbor = (NEIGHB_HOLD_TIME*1000) / olsr_cnf->system_tick_divider;
99
100   olsr_register_timeout_function(&olsr_time_out_link_set);
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, NULL, 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, NULL, 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, RFC-compliant 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, non-RFC compliant 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 the 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, remote_main, 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   /* Erik Tromp - OOPS! Don't do this! Neighbor entries are hashed through their
571    * neighbor_main_addr field, and when that field is changed, their position
572    * in the hash table is no longer correct, so that the function
573    * olsr_lookup_neighbor_table() can no longer find the neighbor
574    * entry. */
575   /*COPY_IP(&neighbor->neighbor_main_addr, remote_main);*/
576
577   neighbor->linkcount++;
578
579
580   new_link->neighbor = neighbor;
581
582   if(!COMP_IP(remote, remote_main))
583     {
584       /* Add MID alias if not already registered */
585       /* This is kind of sketchy... and not specified
586        * in the RFC. We can only guess a vtime.
587        * We'll go for one that is hopefully long
588        * enough in most cases. 10 seconds
589        */
590
591     /* Erik Tromp - commented out. It is not RFC-compliant. Also, MID aliases
592      * that are not explicitly declared by a node will be removed as soon as
593      * the olsr_prune_aliases(...) function is called.
594      *
595      * OLSR_PRINTF(1, "Adding MID alias main %s ", olsr_ip_to_string(remote_main));
596      * OLSR_PRINTF(1, "-> %s based on HELLO\n\n", olsr_ip_to_string(remote));
597      * insert_mid_alias(remote_main, remote, MID_ALIAS_HACK_VTIME);
598      */
599     }
600
601   return link_set;
602 }
603
604
605 /**
606  *Lookup the status of a link.
607  *
608  *@param int_addr address of the remote interface
609  *
610  *@return 1 of the link is symmertic 0 if not
611  */
612
613 int
614 check_neighbor_link(union olsr_ip_addr *int_addr)
615 {
616   struct link_entry *tmp_link_set;
617
618   tmp_link_set = link_set;
619
620   while(tmp_link_set)
621     {
622       if(COMP_IP(int_addr, &tmp_link_set->neighbor_iface_addr))
623         return lookup_link_status(tmp_link_set);
624       tmp_link_set = tmp_link_set->next;
625     }
626   return UNSPEC_LINK;
627 }
628
629
630 /**
631  *Lookup a link entry
632  *
633  *@param remote the remote interface address
634  *@param remote_main the remote nodes main address
635  *@param local the local interface address
636  *
637  *@return the link entry if found, NULL if not
638  */
639 struct link_entry *
640 lookup_link_entry(union olsr_ip_addr *remote, union olsr_ip_addr *remote_main, struct interface *local)
641 {
642   struct link_entry *tmp_link_set;
643
644   tmp_link_set = link_set;
645
646   while(tmp_link_set)
647     {
648       if(COMP_IP(remote, &tmp_link_set->neighbor_iface_addr) &&
649          (tmp_link_set->if_name
650           ? !strcmp(tmp_link_set->if_name, local->int_name)
651           : COMP_IP(&local->ip_addr, &tmp_link_set->local_iface_addr)
652           ) &&
653          /* check the remote-main address only if there is one given */
654          (remote_main == NULL || COMP_IP(remote_main, &tmp_link_set->neighbor->neighbor_main_addr))
655          )
656         return tmp_link_set;
657       tmp_link_set = tmp_link_set->next;
658     }
659   return NULL;
660
661 }
662
663
664
665
666
667
668
669 /**
670  *Update a link entry. This is the "main entrypoint" in
671  *the link-sensing. This function is calles from the HELLO
672  *parser function.
673  *It makes sure a entry is updated or created.
674  *
675  *@param local the local IP address
676  *@param remote the remote IP address
677  *@param message the HELLO message
678  *@param in_if the interface on which this HELLO was received
679  *
680  *@return the link_entry struct describing this link entry
681  */
682 struct link_entry *
683 update_link_entry(union olsr_ip_addr *local, 
684                   union olsr_ip_addr *remote, 
685                   struct hello_message *message, 
686                   struct interface *in_if)
687 {
688   struct link_entry *entry;
689
690   /* Add if not registered */
691   entry = add_new_entry(local, remote, &message->source_addr, message->vtime, message->htime, in_if);
692
693   /* Update ASYM_time */
694   //printf("Vtime is %f\n", message->vtime);
695   /* L_ASYM_time = current time + validity time */
696   entry->ASYM_time = GET_TIMESTAMP(message->vtime*1000);
697   
698   entry->prev_status = check_link_status(message, in_if);
699   
700   //printf("Status %d\n", status);
701   
702   switch(entry->prev_status)
703     {
704     case(LOST_LINK):
705       /* L_SYM_time = current time - 1 (i.e., expired) */
706       entry->SYM_time = now_times - 1;
707
708       break;
709     case(SYM_LINK):
710     case(ASYM_LINK):
711       /* L_SYM_time = current time + validity time */
712       //printf("updating SYM time for %s\n", olsr_ip_to_string(remote));
713       entry->SYM_time = GET_TIMESTAMP(message->vtime*1000);
714
715       /* L_time = L_SYM_time + NEIGHB_HOLD_TIME */
716       entry->time = entry->SYM_time + hold_time_neighbor;
717
718       break;
719     default:;
720     }
721
722   /* L_time = max(L_time, L_ASYM_time) */
723   if(entry->time < entry->ASYM_time)
724     entry->time = entry->ASYM_time;
725
726
727   /*
728   printf("Updating link LOCAL: %s ", olsr_ip_to_string(local));
729   printf("REMOTE: %s\n", olsr_ip_to_string(remote));
730   printf("VTIME: %f ", message->vtime);
731   printf("STATUS: %d\n", status);
732   */
733
734   /* Update hysteresis values */
735   if(olsr_cnf->use_hysteresis)
736     olsr_process_hysteresis(entry);
737
738   /* Update neighbor */
739   update_neighbor_status(entry->neighbor, get_neighbor_status(remote));
740
741   return entry;  
742 }
743
744
745 /**
746  * Fuction that updates all registered pointers to
747  * one neighbor entry with another pointer
748  * Used by MID updates.
749  *
750  *@old the pointer to replace
751  *@new the pointer to use instead of "old"
752  *
753  *@return the number of entries updated
754  */
755 int
756 replace_neighbor_link_set(struct neighbor_entry *old,
757                           struct neighbor_entry *new)
758 {
759   struct link_entry *tmp_link_set;
760   int retval;
761
762   retval = 0;
763
764   if(link_set == NULL)
765     return retval;
766       
767   tmp_link_set = link_set;
768
769   while(tmp_link_set)
770     {
771
772       if(tmp_link_set->neighbor == old)
773         {
774           tmp_link_set->neighbor = new;
775           retval++;
776         }
777       tmp_link_set = tmp_link_set->next;
778     }
779
780   return retval;
781
782 }
783
784
785 /**
786  *Checks the link status to a neighbor by
787  *looking in a received HELLO message.
788  *
789  *@param message the HELLO message to check
790  *
791  *@return the link status
792  */
793 static int
794 check_link_status(struct hello_message *message, struct interface *in_if)
795 {
796   struct hello_neighbor  *neighbors;
797
798   neighbors = message->neighbors;
799   
800   while(neighbors!=NULL)
801     {
802       if(COMP_IP(&neighbors->address, &in_if->ip_addr))
803         {
804           //printf("ok");
805           return neighbors->link;
806         }
807
808       neighbors = neighbors->next; 
809     }
810
811
812   return UNSPEC_LINK;
813 }
814
815
816 /**
817  *Time out the link set. In other words, the link
818  *set is traversed and all non-valid entries are
819  *deleted.
820  *
821  */
822 static void
823 olsr_time_out_link_set(void)
824 {
825
826   struct link_entry *tmp_link_set, *last_link_entry;
827
828   if(link_set == NULL)
829     return;
830       
831   tmp_link_set = link_set;
832   last_link_entry = NULL;
833
834   while(tmp_link_set)
835     {
836
837       if(TIMED_OUT(tmp_link_set->time))
838         {
839           if(last_link_entry != NULL)
840             {
841               last_link_entry->next = tmp_link_set->next;
842
843               /* Delete neighbor entry */
844               if(tmp_link_set->neighbor->linkcount == 1)
845                 olsr_delete_neighbor_table(&tmp_link_set->neighbor->neighbor_main_addr);
846               else
847                 tmp_link_set->neighbor->linkcount--;
848
849               //olsr_delete_neighbor_if_no_link(&tmp_link_set->neighbor->neighbor_main_addr);
850               changes_neighborhood = OLSR_TRUE;
851               free(tmp_link_set->if_name);
852               free(tmp_link_set);
853               tmp_link_set = last_link_entry;
854             }
855           else
856             {
857               link_set = tmp_link_set->next; /* CHANGED */
858
859               /* Delete neighbor entry */
860               if(tmp_link_set->neighbor->linkcount == 1)
861                 olsr_delete_neighbor_table(&tmp_link_set->neighbor->neighbor_main_addr);
862               else
863                 tmp_link_set->neighbor->linkcount--;
864
865               changes_neighborhood = OLSR_TRUE;
866
867               free(tmp_link_set->if_name);
868               free(tmp_link_set);
869               tmp_link_set = link_set;
870               continue;
871             }       
872         }
873       else if((tmp_link_set->prev_status == SYM_LINK) &&
874               TIMED_OUT(tmp_link_set->SYM_time))
875         {
876           tmp_link_set->prev_status = lookup_link_status(tmp_link_set);
877           update_neighbor_status(tmp_link_set->neighbor, 
878                                  get_neighbor_status(&tmp_link_set->neighbor_iface_addr));
879           changes_neighborhood = OLSR_TRUE;
880         }
881       
882       last_link_entry = tmp_link_set;
883       tmp_link_set = tmp_link_set->next;
884     }
885
886   return;
887 }
888
889
890
891
892 /**
893  *Updates links that we have not received
894  *HELLO from in expected time according to 
895  *hysteresis.
896  *
897  *@return nada
898  */
899 static void
900 olsr_time_out_hysteresis(void)
901 {
902   struct link_entry *tmp_link_set;
903
904   if(link_set == NULL)
905     return;
906
907   tmp_link_set = link_set;
908
909   while(tmp_link_set)
910     {
911       if(TIMED_OUT(tmp_link_set->hello_timeout))
912         {
913           tmp_link_set->L_link_quality = olsr_hyst_calc_instability(tmp_link_set->L_link_quality);
914           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);
915           /* Update hello_timeout - NO SLACK THIS TIME */
916           tmp_link_set->hello_timeout = GET_TIMESTAMP(tmp_link_set->last_htime*1000);
917           /* Recalculate status */
918           /* Update hysteresis values */
919           olsr_process_hysteresis(tmp_link_set);
920           
921           /* update neighbor status */
922
923
924           /* Update neighbor */
925           update_neighbor_status(tmp_link_set->neighbor, 
926                                  get_neighbor_status(&tmp_link_set->neighbor_iface_addr));
927
928           /* Update seqno - not mentioned in the RFC... kind of a hack.. */
929           tmp_link_set->olsr_seqno++;
930         }
931       tmp_link_set = tmp_link_set->next;
932     }
933
934   return;
935 }
936
937 void olsr_print_link_set(void)
938 {
939   struct link_entry *walker;
940   char *fstr;
941
942   OLSR_PRINTF(1, "\n--- %02d:%02d:%02d.%02d ---------------------------------------------------- LINKS\n\n",
943               nowtm->tm_hour,
944               nowtm->tm_min,
945               nowtm->tm_sec,
946               (int)now.tv_usec/10000);
947
948   if (olsr_cnf->ip_version == AF_INET)
949   {
950     OLSR_PRINTF(1, "IP address       hyst   LQ     lost   total  NLQ    ETX\n");
951     fstr = "%-15s  %5.3f  %5.3f  %-3d    %-3d    %5.3f  %.2f\n";
952   }
953
954   else
955   {
956     OLSR_PRINTF(1, "IP address                               hyst   LQ     lost   total  NLQ    ETX\n");
957     fstr = "%-39s  %5.3f  %5.3f  %-3d    %-3d    %5.3f  %.2f\n";
958   }
959
960   for (walker = link_set; walker != NULL; walker = walker->next)
961   {
962     float etx;
963
964     if (walker->loss_link_quality < MIN_LINK_QUALITY ||
965         walker->neigh_link_quality < MIN_LINK_QUALITY)
966       etx = 0.0;
967
968     else
969       etx = 1.0 / (walker->loss_link_quality * walker->neigh_link_quality);
970
971     OLSR_PRINTF(1, fstr, olsr_ip_to_string(&walker->neighbor_iface_addr),
972                 walker->L_link_quality, walker->loss_link_quality,
973                 walker->lost_packets, walker->total_packets,
974                 walker->neigh_link_quality, etx);
975   }
976 }
977
978 static void update_packet_loss_worker(struct link_entry *entry, int lost)
979 {
980   unsigned char mask = 1 << (entry->loss_index & 7);
981   int index = entry->loss_index >> 3;
982   double rel_lq, saved_lq;
983
984   if (lost == 0)
985     {
986       // packet not lost
987
988       if ((entry->loss_bitmap[index] & mask) != 0)
989         {
990           // but the packet that we replace was lost
991           // => decrement packet loss
992
993           entry->loss_bitmap[index] &= ~mask;
994           entry->lost_packets--;
995         }
996     }
997
998   else
999     {
1000       // packet lost
1001
1002       if ((entry->loss_bitmap[index] & mask) == 0)
1003         {
1004           // but the packet that we replace was not lost
1005           // => increment packet loss
1006
1007           entry->loss_bitmap[index] |= mask;
1008           entry->lost_packets++;
1009         }
1010     }
1011
1012   // move to the next packet
1013
1014   entry->loss_index++;
1015
1016   // wrap around at the end of the packet loss window
1017
1018   if (entry->loss_index >= entry->loss_window_size)
1019     entry->loss_index = 0;
1020
1021   // count the total number of handled packets up to the window size
1022
1023   if (entry->total_packets < entry->loss_window_size)
1024     entry->total_packets++;
1025
1026   // the current reference link quality
1027
1028   saved_lq = entry->saved_loss_link_quality;
1029
1030   if (saved_lq == 0.0)
1031     saved_lq = -1.0;
1032
1033   // calculate the new link quality
1034   //
1035   // start slowly: receive the first packet => link quality = 1 / n
1036   //               (n = window size)
1037
1038   entry->loss_link_quality =
1039     (float)(entry->total_packets - entry->lost_packets) /
1040     (float)(entry->loss_window_size < (2 * 4) ? entry->loss_window_size: 
1041     4 * ((entry->loss_window_size / 4 - 1) * entry->total_packets + entry->loss_window_size) / entry->loss_window_size);
1042     
1043   // multiply the calculated link quality with the user-specified multiplier
1044
1045   entry->loss_link_quality *= entry->loss_link_multiplier;
1046
1047   // if the link quality has changed by more than 10 percent,
1048   // print the new link quality table
1049
1050   rel_lq = entry->loss_link_quality / saved_lq;
1051
1052   if (rel_lq > 1.1 || rel_lq < 0.9)
1053     {
1054       entry->saved_loss_link_quality = entry->loss_link_quality;
1055
1056       if (olsr_cnf->lq_dlimit > 0)
1057       {
1058         changes_neighborhood = OLSR_TRUE;
1059         changes_topology = OLSR_TRUE;
1060       }
1061
1062       else
1063         OLSR_PRINTF(3, "Skipping Dijkstra (1)\n");
1064
1065       // create a new ANSN
1066
1067       // XXX - we should check whether we actually
1068       // announce this neighbour
1069
1070       signal_link_changes(OLSR_TRUE);
1071     }
1072 }
1073
1074 void olsr_update_packet_loss_hello_int(struct link_entry *entry,
1075                                        double loss_hello_int)
1076 {
1077   // called for every LQ HELLO message - update the timeout
1078   // with the htime value from the message
1079
1080   entry->loss_hello_int = loss_hello_int;
1081 }
1082
1083 void olsr_update_packet_loss(union olsr_ip_addr *rem, struct interface *loc,
1084                              olsr_u16_t seqno)
1085 {
1086   struct link_entry *entry;
1087
1088   // called for every OLSR packet
1089
1090   entry = lookup_link_entry(rem, NULL, loc);
1091
1092   // it's the very first LQ HELLO message - we do not yet have a link
1093
1094   if (entry == NULL)
1095     return;
1096     
1097   // a) have we seen a packet before, i.e. is the sequence number valid?
1098
1099   // b) heuristically detect a restart (= sequence number reset)
1100   //    of our neighbor
1101
1102   if (entry->loss_seqno_valid != 0 && 
1103       (unsigned short)(seqno - entry->loss_seqno) < 100)
1104     {
1105       // loop through all lost packets
1106
1107       while (entry->loss_seqno != seqno)
1108         {
1109           // have we already considered all lost LQ HELLO messages?
1110
1111           if (entry->loss_missed_hellos == 0)
1112             update_packet_loss_worker(entry, 1);
1113
1114           // if not, then decrement the number of lost LQ HELLOs
1115
1116           else
1117             entry->loss_missed_hellos--;
1118
1119           entry->loss_seqno++;
1120         }
1121     }
1122
1123   // we have received a packet, otherwise this function would not
1124   // have been called
1125
1126   update_packet_loss_worker(entry, 0);
1127
1128   // (re-)initialize
1129
1130   entry->loss_missed_hellos = 0;
1131   entry->loss_seqno = seqno + 1;
1132
1133   // we now have a valid serial number for sure
1134
1135   entry->loss_seqno_valid = 1;
1136
1137   // timeout for the first lost packet is 1.5 x htime
1138
1139   entry->loss_timeout = GET_TIMESTAMP(entry->loss_hello_int * 1500.0);
1140 }
1141
1142 static void olsr_time_out_packet_loss(void)
1143 {
1144   struct link_entry *walker;
1145
1146   // loop through all links
1147
1148   for (walker = link_set; walker != NULL; walker = walker->next)
1149     {
1150       // find a link that has not seen any packets for a very long
1151       // time (first time: 1.5 x htime, subsequently: 1.0 x htime)
1152
1153       if (!TIMED_OUT(walker->loss_timeout))
1154         continue;
1155       
1156       // count the lost packet
1157
1158       update_packet_loss_worker(walker, 1);
1159
1160       // memorize that we've counted the packet, so that we do not
1161       // count it a second time later
1162
1163       walker->loss_missed_hellos++;
1164
1165       // next timeout in 1.0 x htime
1166
1167       walker->loss_timeout = GET_TIMESTAMP(walker->loss_hello_int * 1000.0);
1168     }
1169 }
1170
1171 void olsr_update_dijkstra_link_qualities(void)
1172 {
1173   struct link_entry *walker;
1174
1175   for (walker = link_set; walker != NULL; walker = walker->next)
1176   {
1177     walker->loss_link_quality2 = walker->loss_link_quality;
1178     walker->neigh_link_quality2 = walker->neigh_link_quality;
1179   }
1180 }
1181