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