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