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