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