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