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