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