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