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