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