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