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