Use real (bi-directional) ETX.
[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.34 2004/11/28 13:43:59 tlopatic Exp $
40  */
41
42
43 /*
44  * Link sensing database for the OLSR routing daemon
45  */
46
47 #include "link_set.h"
48 #include "hysteresis.h"
49 #include "mid_set.h"
50 #include "mpr.h"
51 #include "olsr.h"
52 #include "scheduler.h"
53 #include "link_layer.h"
54 #include "lq_route.h"
55
56 /* 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, curr;
316 #endif
317
318   if_to_use = NULL;
319   backup_if = NULL;
320
321 #if defined USE_LINK_QUALITY
322   link_quality = -1.0;
323   backup_link_quality = -1.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 ||
357                       if_to_use->int_metric > tmp_if->int_metric)
358                     if_to_use = tmp_if;
359 #if defined USE_LINK_QUALITY
360                 }
361
362               else
363                 {
364                   curr = tmp_link_set->loss_link_quality *
365                     tmp_link_set->neigh_link_quality;
366
367                   if (curr > link_quality)
368                     {
369                       if_to_use = tmp_if;
370                       link_quality = curr;
371                     }
372                 }
373 #endif
374             }
375           /* Backup solution in case the links have timed out */
376           else
377             {
378 #if defined USE_LINK_QUALITY
379               if (olsr_cnf->lq_level == 0)
380                 {
381 #endif
382                   if (if_to_use == NULL &&
383                       (backup_if == NULL ||
384                        backup_if->int_metric > tmp_if->int_metric))
385                     backup_if = tmp_if;
386 #if defined USE_LINK_QUALITY
387                 }
388
389               else 
390                 {
391                   curr = tmp_link_set->loss_link_quality *
392                     tmp_link_set->neigh_link_quality;
393
394                   if (if_to_use == NULL && curr > backup_link_quality)
395                     {
396                       backup_if = tmp_if;
397                       backup_link_quality = curr;
398                     }
399 #endif
400                 }
401             }
402         }
403       
404       tmp_link_set = tmp_link_set->next;
405     }
406   
407   /* Not found */
408   if(if_to_use == NULL)
409     return backup_if;
410   
411   return if_to_use;
412 }
413
414
415
416 /**
417  *Nothing mysterious here.
418  *Adding a new link entry to the link set.
419  *
420  *@param local the local IP address
421  *@param remote the remote IP address
422  *@param remote_main teh remote nodes main address
423  *@param vtime the validity time of the entry
424  *@param htime the HELLO interval of the remote node
425  */
426
427 static struct link_entry *
428 add_new_entry(union olsr_ip_addr *local, union olsr_ip_addr *remote, union olsr_ip_addr *remote_main, double vtime, double htime)
429 {
430   struct link_entry *tmp_link_set, *new_link;
431   struct neighbor_entry *neighbor;
432 #ifdef linux
433   struct interface *local_if;
434 #endif
435
436   tmp_link_set = link_set;
437
438   while(tmp_link_set)
439     {
440       if(COMP_IP(remote, &tmp_link_set->neighbor_iface_addr))
441         return tmp_link_set;
442       tmp_link_set = tmp_link_set->next;
443     }
444
445   /*
446    * if there exists no link tuple with
447    * L_neighbor_iface_addr == Source Address
448    */
449
450 #ifdef DEBUG
451   olsr_printf(3, "Adding %s to link set\n", olsr_ip_to_string(remote));
452 #endif
453
454   /* a new tuple is created with... */
455
456   new_link = olsr_malloc(sizeof(struct link_entry), "new link entry");
457
458   memset(new_link, 0 , sizeof(struct link_entry));
459   /*
460    * L_local_iface_addr = Address of the interface
461    * which received the HELLO message
462    */
463   //printf("\tLocal IF: %s\n", olsr_ip_to_string(local));
464   COPY_IP(&new_link->local_iface_addr, local);
465   /* L_neighbor_iface_addr = Source Address */
466   COPY_IP(&new_link->neighbor_iface_addr, remote);
467
468   /* L_SYM_time            = current time - 1 (expired) */
469   new_link->SYM_time = now;
470   /* Subtract 1 */
471   new_link->SYM_time.tv_sec -= 1;
472
473   /* L_time = current time + validity time */
474   olsr_get_timestamp((olsr_u32_t) vtime*1000, &new_link->time);
475
476
477   /* HYSTERESIS */
478   if(olsr_cnf->use_hysteresis)
479     {
480       new_link->L_link_pending = 1;
481       olsr_get_timestamp((olsr_u32_t) vtime*1000, &new_link->L_LOST_LINK_time);
482       olsr_get_timestamp((olsr_u32_t) htime*1500, &new_link->hello_timeout);
483       new_link->last_htime = htime;
484       new_link->olsr_seqno = 0;
485     }
486
487   new_link->L_link_quality = 0.0;
488
489 #if defined USE_LINK_QUALITY
490   if (olsr_cnf->lq_level > 0)
491     {
492       new_link->loss_hello_int = htime;
493
494       olsr_get_timestamp((olsr_u32_t)(htime * 1500.0),
495                          &new_link->loss_timeout);
496
497       new_link->loss_seqno = 0;
498       new_link->loss_seqno_valid = 0;
499       new_link->loss_missed_hellos = 0;
500
501       new_link->lost_packets = 0;
502       new_link->total_packets = 0;
503
504       new_link->loss_window_size = olsr_cnf->lq_wsize;
505       new_link->loss_index = 0;
506
507       memset(new_link->loss_bitmap, 0, sizeof (new_link->loss_bitmap));
508     }
509
510   new_link->loss_link_quality = 0.0;
511   new_link->neigh_link_quality = 0.0;
512
513   new_link->saved_loss_link_quality = 0.0;
514   new_link->saved_neigh_link_quality = 0.0;
515 #endif
516
517   /* Add to queue */
518   new_link->next = link_set;
519   link_set = new_link;
520
521
522   /*
523    * Create the neighbor entry
524    */
525
526   /* Neighbor MUST exist! */
527   if(NULL == (neighbor = olsr_lookup_neighbor_table(remote_main)))
528     {
529       neighbor = olsr_insert_neighbor_table(remote_main);
530       /* Copy the main address */
531       COPY_IP(&neighbor->neighbor_main_addr, remote_main);
532 #ifdef DEBUG
533       olsr_printf(3, "ADDING NEW NEIGHBOR ENTRY %s FROM LINK SET\n", olsr_ip_to_string(remote_main));
534 #endif
535     }
536
537   neighbor->linkcount++;
538
539
540   new_link->neighbor = neighbor;
541
542   if(!COMP_IP(remote, remote_main))
543     {
544       /* Add MID alias if not already registered */
545       /* This is kind of sketchy... and not specified
546        * in the RFC. We can only guess a vtime.
547        * We'll go for one that is hopefully long
548        * enough in most cases. 20 seconds
549        */
550       olsr_printf(1, "Adding MID alias main %s ", olsr_ip_to_string(remote_main));
551       olsr_printf(1, "-> %s based on HELLO\n\n", olsr_ip_to_string(remote));
552       insert_mid_alias(remote_main, remote, 20.0);
553     }
554
555   /* Add to link-layer spy list */
556 #ifdef linux
557   if(llinfo)
558     {
559       local_if = if_ifwithaddr(local);
560       
561       olsr_printf(1, "Adding %s to spylist of interface %s\n", olsr_ip_to_string(remote), local_if->int_name);
562
563       if((local_if != NULL) && (add_spy_node(remote, local_if->int_name)))
564         new_link->spy_activated = 1;
565     }
566 #endif
567
568   return link_set;
569 }
570
571
572 /**
573  *Lookup the status of a link.
574  *
575  *@param int_addr address of the remote interface
576  *
577  *@return 1 of the link is symmertic 0 if not
578  */
579
580 int
581 check_neighbor_link(union olsr_ip_addr *int_addr)
582 {
583   struct link_entry *tmp_link_set;
584
585   tmp_link_set = link_set;
586
587   while(tmp_link_set)
588     {
589       if(COMP_IP(int_addr, &tmp_link_set->neighbor_iface_addr))
590         return lookup_link_status(tmp_link_set);
591       tmp_link_set = tmp_link_set->next;
592     }
593   return UNSPEC_LINK;
594 }
595
596
597 /**
598  *Lookup a link entry
599  *
600  *@param remote the remote interface address
601  *@param local the local interface address
602  *
603  *@return the link entry if found, NULL if not
604  */
605 struct link_entry *
606 lookup_link_entry(union olsr_ip_addr *remote, union olsr_ip_addr *local)
607 {
608   struct link_entry *tmp_link_set;
609
610   tmp_link_set = link_set;
611
612   while(tmp_link_set)
613     {
614       if(COMP_IP(remote, &tmp_link_set->neighbor_iface_addr) &&
615          COMP_IP(local, &tmp_link_set->local_iface_addr))
616         return tmp_link_set;
617       tmp_link_set = tmp_link_set->next;
618     }
619   return NULL;
620
621 }
622
623
624
625
626
627
628
629 /**
630  *Update a link entry. This is the "main entrypoint" in
631  *the link-sensing. This function is calles from the HELLO
632  *parser function.
633  *It makes sure a entry is updated or created.
634  *
635  *@param local the local IP address
636  *@param remote the remote IP address
637  *@param message the HELLO message
638  *@param in_if the interface on which this HELLO was received
639  *
640  *@return the link_entry struct describing this link entry
641  */
642 struct link_entry *
643 update_link_entry(union olsr_ip_addr *local, union olsr_ip_addr *remote, struct hello_message *message, struct interface *in_if)
644 {
645   int status;
646   struct link_entry *entry;
647 #ifdef linux
648   struct interface *local_if;
649 #endif
650
651   /* Time out entries */
652   //timeout_link_set();
653
654   /* Add if not registered */
655   entry = add_new_entry(local, remote, &message->source_addr, message->vtime, message->htime);
656
657   /* Update link layer info */
658   /* Add to link-layer spy list */
659 #ifdef linux
660   if(llinfo && !entry->spy_activated)
661     {
662       local_if = if_ifwithaddr(local);
663       
664       olsr_printf(1, "Adding %s to spylist of interface %s\n", olsr_ip_to_string(remote), local_if->int_name);
665
666       if((local_if != NULL) && (add_spy_node(remote, local_if->int_name)))
667         entry->spy_activated = 1;
668     }
669 #endif
670
671   /* Update ASYM_time */
672   //printf("Vtime is %f\n", message->vtime);
673   /* L_ASYM_time = current time + validity time */
674   olsr_get_timestamp((olsr_u32_t) (message->vtime*1000), &entry->ASYM_time);
675
676
677   status = check_link_status(message);
678
679   //printf("Status %d\n", status);
680
681   switch(status)
682     {
683     case(LOST_LINK):
684       /* L_SYM_time = current time - 1 (i.e., expired) */
685       entry->SYM_time = now;
686       entry->SYM_time.tv_sec -= 1;
687
688       break;
689     case(SYM_LINK):
690     case(ASYM_LINK):
691       /* L_SYM_time = current time + validity time */
692       //printf("updating SYM time for %s\n", olsr_ip_to_string(remote));
693       olsr_get_timestamp((olsr_u32_t) (message->vtime*1000), &entry->SYM_time);
694         //timeradd(&now, &tmp_timer, &entry->SYM_time);
695
696       /* L_time = L_SYM_time + NEIGHB_HOLD_TIME */
697       timeradd(&entry->SYM_time, &hold_time_neighbor, &entry->time);
698
699       break;
700     default:;
701     }
702
703   /* L_time = max(L_time, L_ASYM_time) */
704   if(timercmp(&entry->time, &entry->ASYM_time, <))
705     entry->time = entry->ASYM_time;
706
707
708   /*
709   printf("Updating link LOCAL: %s ", olsr_ip_to_string(local));
710   printf("REMOTE: %s\n", olsr_ip_to_string(remote));
711   printf("VTIME: %f ", message->vtime);
712   printf("STATUS: %d\n", status);
713   */
714
715   /* Update hysteresis values */
716   if(olsr_cnf->use_hysteresis)
717     olsr_process_hysteresis(entry);
718
719   /* update neighbor status */
720   /* Return link status */
721   //status = lookup_link_status(entry);
722   /* UPDATED ! */
723   status = get_neighbor_status(remote);
724
725   /* Update neighbor */
726   update_neighbor_status(entry->neighbor, status);
727   //update_neighbor_status(entry->neighbor);
728
729   return entry;  
730 }
731
732
733 /**
734  * Fuction that updates all registered pointers to
735  * one neighbor entry with another pointer
736  * Used by MID updates.
737  *
738  *@old the pointer to replace
739  *@new the pointer to use instead of "old"
740  *
741  *@return the number of entries updated
742  */
743 int
744 replace_neighbor_link_set(struct neighbor_entry *old,
745                           struct neighbor_entry *new)
746 {
747   struct link_entry *tmp_link_set, *last_link_entry;
748   int retval;
749
750   retval = 0;
751
752   if(link_set == NULL)
753     return retval;
754       
755   tmp_link_set = link_set;
756   last_link_entry = NULL;
757
758   while(tmp_link_set)
759     {
760
761       if(tmp_link_set->neighbor == old)
762         {
763           tmp_link_set->neighbor = new;
764           retval++;
765         }
766       tmp_link_set = tmp_link_set->next;
767     }
768
769   return retval;
770
771 }
772
773
774 /**
775  *Checks the link status to a neighbor by
776  *looking in a received HELLO message.
777  *
778  *@param message the HELLO message to check
779  *
780  *@return the link status
781  */
782 static int
783 check_link_status(struct hello_message *message)
784 {
785
786   struct hello_neighbor  *neighbors;
787   struct interface *ifd;
788
789   neighbors = message->neighbors;
790   
791   while(neighbors!=NULL)
792     {  
793       //printf("(linkstatus)Checking %s ",olsr_ip_to_string(&neighbors->address));
794       //printf("against %s\n",olsr_ip_to_string(&main_addr));
795
796       /* Check all interfaces */          
797       for (ifd = ifnet; ifd ; ifd = ifd->int_next) 
798         {
799           if(COMP_IP(&neighbors->address, &ifd->ip_addr))
800             {
801               //printf("ok");
802               return neighbors->link;
803             }
804         }
805
806       neighbors = neighbors->next; 
807     }
808
809
810   return UNSPEC_LINK;
811 }
812
813
814 /**
815  *Time out the link set. In other words, the link
816  *set is traversed and all non-valid entries are
817  *deleted.
818  *
819  */
820 static void
821 olsr_time_out_link_set()
822 {
823
824   struct link_entry *tmp_link_set, *last_link_entry;
825
826   if(link_set == NULL)
827     return;
828       
829   tmp_link_set = link_set;
830   last_link_entry = NULL;
831
832   while(tmp_link_set)
833     {
834
835       if(TIMED_OUT(&tmp_link_set->time))
836         {
837           if(last_link_entry != NULL)
838             {
839               last_link_entry->next = tmp_link_set->next;
840
841               /* Delete neighbor entry */
842               if(tmp_link_set->neighbor->linkcount == 1)
843                 olsr_delete_neighbor_table(&tmp_link_set->neighbor->neighbor_main_addr);
844               else
845                 tmp_link_set->neighbor->linkcount--;
846
847               //olsr_delete_neighbor_if_no_link(&tmp_link_set->neighbor->neighbor_main_addr);
848               changes_neighborhood = OLSR_TRUE;
849
850               free(tmp_link_set);
851               tmp_link_set = last_link_entry;
852             }
853           else
854             {
855               link_set = tmp_link_set->next; /* CHANGED */
856
857               /* Delete neighbor entry */
858               if(tmp_link_set->neighbor->linkcount == 1)
859                 olsr_delete_neighbor_table(&tmp_link_set->neighbor->neighbor_main_addr);
860               else
861                 tmp_link_set->neighbor->linkcount--;
862               //olsr_delete_neighbor_if_no_link(&tmp_link_set->neighbor->neighbor_main_addr);
863
864               changes_neighborhood = OLSR_TRUE;
865
866               free(tmp_link_set);
867               tmp_link_set = link_set;
868               continue;
869             }       
870         }
871       
872       last_link_entry = tmp_link_set;
873       tmp_link_set = tmp_link_set->next;
874     }
875
876   return;
877 }
878
879
880
881
882 /**
883  *Updates links that we have not received
884  *HELLO from in expected time according to 
885  *hysteresis.
886  *
887  *@return nada
888  */
889 static void
890 olsr_time_out_hysteresis()
891 {
892
893   struct link_entry *tmp_link_set;
894   int status;
895
896   if(link_set == NULL)
897     return;
898
899   tmp_link_set = link_set;
900
901   while(tmp_link_set)
902     {
903       if(TIMED_OUT(&tmp_link_set->hello_timeout))
904         {
905           tmp_link_set->L_link_quality = olsr_hyst_calc_instability(tmp_link_set->L_link_quality);
906           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);
907           /* Update hello_timeout - NO SLACK THIS TIME */
908           olsr_get_timestamp((olsr_u32_t) tmp_link_set->last_htime*1000, &tmp_link_set->hello_timeout);
909
910           /* Recalculate status */
911           /* Update hysteresis values */
912           olsr_process_hysteresis(tmp_link_set);
913           
914           /* update neighbor status */
915           //status = lookup_link_status(tmp_link_set);
916           /* UPDATED ! */
917           status = get_neighbor_status(&tmp_link_set->neighbor_iface_addr);
918
919
920           /* Update neighbor */
921           update_neighbor_status(tmp_link_set->neighbor, status);
922           //update_neighbor_status(tmp_link_set->neighbor);
923
924           /* Update seqno - not mentioned in the RFC... kind of a hack.. */
925           tmp_link_set->olsr_seqno++;
926         }
927       tmp_link_set = tmp_link_set->next;
928     }
929
930   return;
931 }
932
933 #if defined USE_LINK_QUALITY
934 void olsr_print_link_set(void)
935 {
936   struct link_entry *walker;
937   char *fstr;
938   float etx;
939
940   olsr_printf(1, "\n--- %02d:%02d:%02d.%02d ---------------------------------------------------- LINKS\n\n",
941               nowtm->tm_hour,
942               nowtm->tm_min,
943               nowtm->tm_sec,
944               now.tv_usec/10000);
945
946   if (olsr_cnf->ip_version == AF_INET)
947   {
948     olsr_printf(1, "IP address       hyst   LQ     lost   total  NLQ    ETX\n");
949     fstr = "%-15s  %5.3f  %5.3f  %-3d    %-3d    %5.3f  %.2f\n";
950   }
951
952   else
953   {
954     olsr_printf(1, "IP address                               hyst   LQ     lost   total  NLQ    ETX\n");
955     fstr = "%-39s  %5.3f  %5.3f  %-3d    %-3d    %5.3f  %.2f\n";
956   }
957
958   for (walker = link_set; walker != NULL; walker = walker->next)
959   {
960     if (walker->loss_link_quality < MIN_LINK_QUALITY ||
961         walker->neigh_link_quality < MIN_LINK_QUALITY)
962       etx = 0.0;
963
964     else
965       etx = 1.0 / (walker->loss_link_quality * walker->neigh_link_quality);
966
967     olsr_printf(1, fstr, olsr_ip_to_string(&walker->neighbor_iface_addr),
968                 walker->L_link_quality, walker->loss_link_quality,
969                 walker->lost_packets, walker->total_packets,
970                 walker->neigh_link_quality, etx);
971   }
972 }
973
974 static void update_packet_loss_worker(struct link_entry *entry, int lost)
975 {
976   unsigned char mask = 1 << (entry->loss_index & 7);
977   int index = entry->loss_index >> 3;
978   double rel_lq, saved_lq;
979
980   if (lost == 0)
981     {
982       // packet not lost
983
984       if ((entry->loss_bitmap[index] & mask) != 0)
985         {
986           // but the packet that we replace was lost
987           // => decrement packet loss
988
989           entry->loss_bitmap[index] &= ~mask;
990           entry->lost_packets--;
991         }
992     }
993
994   else
995     {
996       // packet lost
997
998       if ((entry->loss_bitmap[index] & mask) == 0)
999         {
1000           // but the packet that we replace was not lost
1001           // => increment packet loss
1002
1003           entry->loss_bitmap[index] |= mask;
1004           entry->lost_packets++;
1005         }
1006     }
1007
1008   // move to the next packet
1009
1010   entry->loss_index++;
1011
1012   // wrap around at the end of the packet loss window
1013
1014   if (entry->loss_index >= entry->loss_window_size)
1015     entry->loss_index = 0;
1016
1017   // count the total number of handled packets up to the window size
1018
1019   if (entry->total_packets < entry->loss_window_size)
1020     entry->total_packets++;
1021
1022   // the current reference link quality
1023
1024   saved_lq = entry->saved_loss_link_quality;
1025
1026   if (saved_lq == 0.0)
1027     saved_lq = -1.0;
1028
1029   // calculate the new link quality
1030   //
1031   // start slowly: receive the first packet => link quality = 1 / n
1032   //               (n = window size)
1033
1034   entry->loss_link_quality =
1035     (float)(entry->total_packets - entry->lost_packets) /
1036     (float)(entry->loss_window_size);
1037
1038   // if the link quality has changed by more than 10 percent,
1039   // print the new link quality table
1040
1041   rel_lq = entry->loss_link_quality / saved_lq;
1042
1043   if (rel_lq > 1.1 || rel_lq < 0.9)
1044     {
1045       entry->saved_loss_link_quality = entry->loss_link_quality;
1046
1047       changes_neighborhood = OLSR_TRUE;
1048       changes_topology = OLSR_TRUE;
1049
1050       // create a new ANSN
1051
1052       // XXX - we should check whether we actually
1053       // announce this neighbour
1054
1055       changes = OLSR_TRUE;
1056     }
1057 }
1058
1059 void olsr_update_packet_loss_hello_int(struct link_entry *entry,
1060                                        double loss_hello_int)
1061 {
1062   // called for every LQ HELLO message - update the timeout
1063   // with the htime value from the message
1064
1065   entry->loss_hello_int = loss_hello_int;
1066 }
1067
1068 void olsr_update_packet_loss(union olsr_ip_addr *rem, union olsr_ip_addr *loc,
1069                              olsr_u16_t seqno)
1070 {
1071   struct link_entry *entry;
1072
1073   // called for every OLSR packet
1074
1075   entry = lookup_link_entry(rem, loc);
1076
1077   // it's the very first LQ HELLO message - we do not yet have a link
1078
1079   if (entry == NULL)
1080     return;
1081     
1082   // a) have we seen a packet before, i.e. is the sequence number valid?
1083
1084   // b) heuristically detect a restart (= sequence number reset)
1085   //    of our neighbor
1086
1087   if (entry->loss_seqno_valid != 0 && 
1088       (unsigned short)(seqno - entry->loss_seqno) < 100)
1089     {
1090       // loop through all lost packets
1091
1092       while (entry->loss_seqno != seqno)
1093         {
1094           // have we already considered all lost LQ HELLO messages?
1095
1096           if (entry->loss_missed_hellos == 0)
1097             update_packet_loss_worker(entry, 1);
1098
1099           // if not, then decrement the number of lost LQ HELLOs
1100
1101           else
1102             entry->loss_missed_hellos--;
1103
1104           entry->loss_seqno++;
1105         }
1106     }
1107
1108   // we have received a packet, otherwise this function would not
1109   // have been called
1110
1111   update_packet_loss_worker(entry, 0);
1112
1113   // (re-)initialize
1114
1115   entry->loss_missed_hellos = 0;
1116   entry->loss_seqno = seqno + 1;
1117
1118   // we now have a valid serial number for sure
1119
1120   entry->loss_seqno_valid = 1;
1121
1122   // timeout for the first lost packet is 1.5 x htime
1123
1124   olsr_get_timestamp((olsr_u32_t)(entry->loss_hello_int * 1500.0),
1125                      &entry->loss_timeout);
1126 }
1127
1128 static void olsr_time_out_packet_loss()
1129 {
1130   struct link_entry *walker;
1131
1132   // loop through all links
1133
1134   for (walker = link_set; walker != NULL; walker = walker->next)
1135     {
1136       // find a link that has not seen any packets for a very long
1137       // time (first time: 1.5 x htime, subsequently: 1.0 x htime)
1138
1139       if (!TIMED_OUT(&walker->loss_timeout))
1140         continue;
1141       
1142       // count the lost packet
1143
1144       update_packet_loss_worker(walker, 1);
1145
1146       // memorize that we've counted the packet, so that we do not
1147       // count it a second time later
1148
1149       walker->loss_missed_hellos++;
1150
1151       // next timeout in 1.0 x htime
1152
1153       olsr_get_timestamp((olsr_u32_t)(walker->loss_hello_int * 1000.0),
1154                          &walker->loss_timeout);
1155     }
1156 }
1157
1158 struct link_entry *olsr_neighbor_best_link(union olsr_ip_addr *main)
1159 {
1160   struct link_entry *walker;
1161   double best = 0.0;
1162   double curr;
1163   struct link_entry *res = NULL;
1164
1165   // loop through all links
1166
1167   for (walker = link_set; walker != NULL; walker = walker->next)
1168   {
1169     // check whether it's a link to the requested neighbor and
1170     // whether the link's quality is better than what we have
1171
1172     if(COMP_IP(main, &walker->neighbor->neighbor_main_addr))
1173     {
1174       curr = walker->loss_link_quality * walker->neigh_link_quality;
1175
1176       if (curr >= best)
1177       {
1178         best = curr;
1179         res = walker;
1180       }
1181     }
1182   }
1183
1184   return res;
1185 }
1186 #endif