Removed USE_LINK_QUALITY #ifdefs. The link quality code is now always
[olsrd.git] / src / process_package.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: process_package.c,v 1.24 2004/12/04 17:06:57 tlopatic Exp $
40  */
41
42
43 #include "defs.h"
44 #include "process_package.h"
45 #include "hysteresis.h"
46 #include "two_hop_neighbor_table.h"
47 #include "tc_set.h"
48 #include "mpr_selector_set.h"
49 #include "mid_set.h"
50 #include "olsr.h"
51 #include "parser.h"
52 #include "duplicate_set.h"
53 #include "rebuild_packet.h"
54
55
56 /**
57  *Initializing the parser functions we are using
58  */
59 void
60 olsr_init_package_process()
61 {
62   if (olsr_cnf->lq_level == 0)
63     {
64       olsr_parser_add_function(&olsr_process_received_hello, HELLO_MESSAGE, 1);
65       olsr_parser_add_function(&olsr_process_received_tc, TC_MESSAGE, 1);
66     }
67
68   else
69     {
70       olsr_parser_add_function(&olsr_input_lq_hello, LQ_HELLO_MESSAGE, 1);
71       olsr_parser_add_function(&olsr_input_lq_tc, LQ_TC_MESSAGE, 1);
72     }
73
74   olsr_parser_add_function(&olsr_process_received_mid, MID_MESSAGE, 1);
75   olsr_parser_add_function(&olsr_process_received_hna, HNA_MESSAGE, 1);
76 }
77
78 void
79 olsr_hello_tap(struct hello_message *message, struct interface *in_if,
80                union olsr_ip_addr *from_addr)
81 {
82   struct link_entry         *link;
83   struct neighbor_entry     *neighbor;
84   struct hello_neighbor *walker;
85   double saved_lq;
86   double rel_lq;
87
88   /*
89    * Update link status
90    */
91   link = update_link_entry(&in_if->ip_addr, from_addr, message, in_if);
92
93   if (olsr_cnf->lq_level > 0)
94     {
95       // just in case our neighbor has changed its HELLO interval
96
97       olsr_update_packet_loss_hello_int(link, message->htime);
98
99       // find the input interface in the list of neighbor interfaces
100
101       for (walker = message->neighbors; walker != NULL; walker = walker->next)
102         if (COMP_IP(&walker->address, &in_if->ip_addr))
103           break;
104
105       // the current reference link quality
106
107       saved_lq = link->saved_neigh_link_quality;
108
109       if (saved_lq == 0.0)
110         saved_lq = -1.0;
111
112       // memorize our neighbour's idea of the link quality, so that we
113       // know the link quality in both directions
114
115       if (walker != NULL)
116         link->neigh_link_quality = walker->link_quality;
117
118       else
119         link->neigh_link_quality = 0.0;
120
121       // if the link quality has changed by more than 10 percent,
122       // print the new link quality table
123
124       rel_lq = link->neigh_link_quality / saved_lq;
125
126       if (rel_lq > 1.1 || rel_lq < 0.9)
127         {
128           link->saved_neigh_link_quality = link->neigh_link_quality;
129
130           changes_neighborhood = OLSR_TRUE;
131           changes_topology = OLSR_TRUE;
132
133           // create a new ANSN
134
135           // XXX - we should check whether we actually
136           // announce this neighbour
137
138           changes = OLSR_TRUE;
139         }
140     }
141   
142   neighbor = link->neighbor;
143
144   /*
145    * Hysteresis
146    */
147   if(olsr_cnf->use_hysteresis)
148     {
149       /* Update HELLO timeout */
150       //printf("MESSAGE HTIME: %f\n", message->htime);
151       olsr_update_hysteresis_hello(link, message->htime);
152     }
153
154   /* Check if we are chosen as MPR */
155   if(olsr_lookup_mpr_status(message, in_if))
156     /* source_addr is always the main addr of a node! */
157     olsr_update_mprs_set(&message->source_addr, (float)message->vtime);
158
159
160
161   /* Check willingness */
162   if(neighbor->willingness != message->willingness)
163     {
164       olsr_printf(1, "Willingness for %s changed from %d to %d - UPDATING\n", 
165                   olsr_ip_to_string(&neighbor->neighbor_main_addr),
166                   neighbor->willingness,
167                   message->willingness);
168       /*
169        *If willingness changed - recalculate
170        */
171       neighbor->willingness = message->willingness;
172       changes_neighborhood = OLSR_TRUE;
173       changes_topology = OLSR_TRUE;
174     }
175
176
177   /* Don't register neighbors of neighbors that announces WILL_NEVER */
178   if(neighbor->willingness != WILL_NEVER)
179     olsr_process_message_neighbors(neighbor, message);
180
181   /* Process changes immedeatly in case of MPR updates */
182   olsr_process_changes();
183
184   olsr_destroy_hello_message(message);
185
186   return;
187 }
188
189 /**
190  *Processes a received HELLO message. 
191  *
192  *@param m the incoming OLSR message
193  *@return 0 on sucess
194  */
195
196 void
197 olsr_process_received_hello(union olsr_message *m, struct interface *in_if, union olsr_ip_addr *from_addr)
198 {
199   struct hello_message      message;
200
201   hello_chgestruct(&message, m);
202
203   olsr_hello_tap(&message, in_if, from_addr);
204 }
205
206 void
207 olsr_tc_tap(struct tc_message *message, struct interface *in_if,
208             union olsr_ip_addr *from_addr, union olsr_message *m)
209 {
210   struct tc_mpr_addr              *mpr;
211   struct tc_entry                 *tc_last;
212
213   if(!olsr_check_dup_table_proc(&message->originator, 
214                                 message->packet_seq_number))
215     {
216       goto forward;
217     }
218
219   olsr_printf(3, "Processing TC from %s\n",
220               olsr_ip_to_string(&message->originator));
221
222   /*
223    *      If the sender interface (NB: not originator) of this message
224    *      is not in the symmetric 1-hop neighborhood of this node, the
225    *      message MUST be discarded.
226    */
227
228   if(check_neighbor_link(from_addr) != SYM_LINK)
229     {
230       olsr_printf(2, "Received TC from NON SYM neighbor %s\n",
231                   olsr_ip_to_string(from_addr));
232       olsr_destroy_tc_message(message);
233       return;
234     }
235
236   if(olsr_cnf->debug_level > 2)
237     {
238       mpr = message->multipoint_relay_selector_address;
239       olsr_printf(3, "mpr_selector_list:[");
240
241       while(mpr!=NULL)
242         {
243           olsr_printf(3, "%s:", olsr_ip_to_string(&mpr->address));
244           mpr=mpr->next;
245         }
246
247       olsr_printf(3, "]\n");
248     }
249
250   tc_last = olsr_lookup_tc_entry(&message->originator);
251    
252   if(tc_last != NULL)
253     {
254       /* Update entry */
255
256       /* Delete destinations with lower ANSN */
257       if(olsr_tc_delete_mprs(tc_last, message))
258         changes_topology = OLSR_TRUE; 
259
260       /* Update destinations */
261       if(olsr_tc_update_mprs(tc_last, message))
262         changes_topology = OLSR_TRUE;
263
264       /* Delete possible empty TC entry */
265       if(changes_topology)
266         olsr_tc_delete_entry_if_empty(tc_last);
267     }
268
269   else
270     {
271       /*if message is empty then skip it */
272       if(message->multipoint_relay_selector_address != NULL)
273         {
274           /* New entry */
275           tc_last = olsr_add_tc_entry(&message->originator);      
276           
277           /* Update destinations */
278           olsr_tc_update_mprs(tc_last, message);
279           
280           changes_topology = OLSR_TRUE;
281         }
282       else
283         {
284           olsr_printf(3, "Dropping empty TC from %s\n",
285                       olsr_ip_to_string(&message->originator)); 
286         }
287     }
288
289   /* Process changes */
290   //olsr_process_changes();
291
292  forward:
293
294   olsr_forward_message(m, 
295                        &message->originator, 
296                        message->packet_seq_number, 
297                        in_if,
298                        from_addr);
299
300   olsr_destroy_tc_message(message);
301
302   return;
303 }
304
305 /**
306  *Process a received TopologyControl message
307  *
308  *
309  *@param m the incoming OLSR message
310  *@return 0 on success
311  */
312 void
313 olsr_process_received_tc(union olsr_message *m, struct interface *in_if, union olsr_ip_addr *from_addr)
314
315   struct tc_message               message;
316
317   tc_chgestruct(&message, m, from_addr);
318
319   olsr_tc_tap(&message, in_if, from_addr, m);
320 }
321
322
323
324
325
326
327 /**
328  *Process a received(and parsed) MID message
329  *For every address check if there is a topology node
330  *registered with it and update its addresses.
331  *
332  *@param m the OLSR message received.
333  *@return 1 on success
334  */
335
336 void
337 olsr_process_received_mid(union olsr_message *m, struct interface *in_if, union olsr_ip_addr *from_addr)
338 {
339   struct mid_alias *tmp_adr;
340   struct mid_message message;
341
342
343   mid_chgestruct(&message, m);
344
345   /*
346   if(COMP_IP(&message.mid_origaddr, &main_addr))
347     {
348       goto forward;  
349     }
350   */
351
352   if(!olsr_check_dup_table_proc(&message.mid_origaddr, 
353                                 message.mid_seqno))
354     {
355       goto forward;
356     }
357   
358   olsr_printf(5, "Processing MID from %s...\n", olsr_ip_to_string(&message.mid_origaddr));
359
360   tmp_adr = message.mid_addr;
361
362
363   /*
364    *      If the sender interface (NB: not originator) of this message
365    *      is not in the symmetric 1-hop neighborhood of this node, the
366    *      message MUST be discarded.
367    */
368
369   if(check_neighbor_link(from_addr) != SYM_LINK)
370     {
371       olsr_printf(2, "Received MID from NON SYM neighbor %s\n", olsr_ip_to_string(from_addr));
372       olsr_destroy_mid_message(&message);
373       return;
374     }
375
376
377
378   /* Update the timeout of the MID */
379   olsr_update_mid_table(&message.mid_origaddr, (float)message.vtime);
380
381   while(tmp_adr)
382     {
383       if(!mid_lookup_main_addr(&tmp_adr->alias_addr))
384         {
385           olsr_printf(1, "MID new: (%s, ", olsr_ip_to_string(&message.mid_origaddr));
386           olsr_printf(1, "%s)\n", olsr_ip_to_string(&tmp_adr->alias_addr));
387           insert_mid_alias(&message.mid_origaddr, &tmp_adr->alias_addr, (float)message.vtime);
388         }
389
390
391       tmp_adr = tmp_adr->next;
392     } 
393   
394   /*Update topology if neccesary*/
395   //olsr_process_changes();
396
397  forward:
398   
399   olsr_forward_message(m, 
400                        &message.mid_origaddr, 
401                        message.mid_seqno, 
402                        in_if,
403                        from_addr);
404   olsr_destroy_mid_message(&message);
405
406   return;
407 }
408
409
410
411
412
413 /**
414  *Process incoming HNA message.
415  *Forwards the message if that is to be done.
416  *
417  *@param m the incoming OLSR message
418  *the OLSR message.
419  *@return 1 on success
420  */
421
422 void
423 olsr_process_received_hna(union olsr_message *m, struct interface *in_if, union olsr_ip_addr *from_addr)
424 {
425   struct hna_net_addr  *hna_tmp;
426   struct  hna_message message;
427
428   //printf("Processing HNA\n");
429
430   hna_chgestruct(&message, m);
431   
432
433   /* Process message */   
434   /*
435   if(COMP_IP(&message.originator, &main_addr)) 
436     {
437       goto forward;
438     }
439   */
440
441   if(!olsr_check_dup_table_proc(&message.originator, 
442                                 message.packet_seq_number))
443     {
444       goto forward;
445     }
446
447
448
449
450   hna_tmp = message.hna_net;
451
452
453
454   /*
455    *      If the sender interface (NB: not originator) of this message
456    *      is not in the symmetric 1-hop neighborhood of this node, the
457    *      message MUST be discarded.
458    */
459
460
461   if(check_neighbor_link(from_addr) != SYM_LINK)
462     {
463       olsr_printf(2, "Received HNA from NON SYM neighbor %s\n", olsr_ip_to_string(from_addr));
464       olsr_destroy_hna_message(&message);
465       return;
466     }
467
468   while(hna_tmp)
469     {
470       olsr_update_hna_entry(&message.originator, &hna_tmp->net, &hna_tmp->netmask, (float)message.vtime); 
471       
472       hna_tmp = hna_tmp->next;
473     }
474   
475   /*Update topology if neccesary*/
476   //olsr_process_changes();
477
478  forward:
479   olsr_forward_message(m, 
480                        &message.originator, 
481                        message.packet_seq_number, 
482                        in_if,
483                        from_addr);
484   olsr_destroy_hna_message(&message);
485
486   return;
487 }
488
489
490
491
492
493
494
495 /**
496  *Processes an list of neighbors from an incoming HELLO message.
497  *@param neighbor the neighbor who sendt the message.
498  *@param message the HELLO message
499  *@return nada
500  */
501 void
502 olsr_process_message_neighbors(struct neighbor_entry *neighbor,
503                                struct hello_message *message)
504 {
505   struct hello_neighbor        *message_neighbors;
506   struct neighbor_2_list_entry *two_hop_neighbor_yet;
507   struct neighbor_2_entry      *two_hop_neighbor;
508   union olsr_ip_addr           *neigh_addr;
509   struct neighbor_list_entry *walker;
510   struct link_entry *link;
511
512   for(message_neighbors = message->neighbors;
513       message_neighbors != NULL;
514       message_neighbors = message_neighbors->next)
515     {
516       /*
517        *check all interfaces
518        *so that we don't add ourselves to the
519        *2 hop list
520        *IMPORTANT!
521        */
522       if(if_ifwithaddr(&message_neighbors->address) != NULL)
523         continue;
524
525       /* Get the main address */
526
527       neigh_addr = mid_lookup_main_addr(&message_neighbors->address);
528
529       if (neigh_addr != NULL)
530         COPY_IP(&message_neighbors->address, neigh_addr);
531       
532       if(((message_neighbors->status == SYM_NEIGH) ||
533           (message_neighbors->status == MPR_NEIGH)))
534         {
535           //printf("\tProcessing %s\n", olsr_ip_to_string(&message_neighbors->address));
536           //printf("\tMain addr: %s\n", olsr_ip_to_string(neigh_addr));
537           
538           two_hop_neighbor_yet =
539             olsr_lookup_my_neighbors(neighbor,
540                                      &message_neighbors->address);
541
542           if (two_hop_neighbor_yet != NULL)
543             {
544               /* Updating the holding time for this neighbor */
545               olsr_get_timestamp((olsr_u32_t)message->vtime * 1000,
546                                  &two_hop_neighbor_yet->neighbor_2_timer);
547
548               two_hop_neighbor = two_hop_neighbor_yet->neighbor_2;
549             }
550           else
551             {
552               two_hop_neighbor =
553                 olsr_lookup_two_hop_neighbor_table(&message_neighbors->address);
554               if (two_hop_neighbor == NULL)
555                 {
556                   //printf("Adding 2 hop neighbor %s\n\n", olsr_ip_to_string(&message_neighbors->address)); 
557
558                   changes_neighborhood = OLSR_TRUE;
559                   changes_topology = OLSR_TRUE;
560
561                   two_hop_neighbor =
562                     olsr_malloc(sizeof(struct neighbor_2_entry),
563                                 "Process HELLO");
564                   
565                   two_hop_neighbor->neighbor_2_nblist.next =
566                     &two_hop_neighbor->neighbor_2_nblist;
567
568                   two_hop_neighbor->neighbor_2_nblist.prev =
569                     &two_hop_neighbor->neighbor_2_nblist;
570
571                   two_hop_neighbor->neighbor_2_pointer = 0;
572                   
573                   COPY_IP(&two_hop_neighbor->neighbor_2_addr,
574                           &message_neighbors->address);
575
576                   olsr_insert_two_hop_neighbor_table(two_hop_neighbor);
577
578                   olsr_linking_this_2_entries(neighbor, two_hop_neighbor,
579                                               (float)message->vtime);
580                 }
581               else
582                 {
583                   /*
584                     linking to this two_hop_neighbor entry
585                   */    
586                   changes_neighborhood = OLSR_TRUE;
587                   changes_topology = OLSR_TRUE;
588                   
589                   olsr_linking_this_2_entries(neighbor, two_hop_neighbor,
590                                               (float)message->vtime); 
591                 }
592             }
593
594           if (olsr_cnf->lq_level > 0)
595             {
596               link = olsr_neighbor_best_link(&neighbor->neighbor_main_addr);
597
598               // loop through the one-hop neighbors that see this
599               // two hop neighbour
600
601               for (walker = two_hop_neighbor->neighbor_2_nblist.next;
602                    walker != &two_hop_neighbor->neighbor_2_nblist;
603                    walker = walker->next)
604                 {
605                   // have we found the one-hop neighbor that sent the
606                   // HELLO message that we're current processing?
607
608                   if (walker->neighbor == neighbor)
609                     {
610                       double saved_lq, rel_lq;
611
612                       // saved previous total link quality
613
614                       saved_lq = walker->saved_path_link_quality;
615
616                       if (saved_lq == 0.0)
617                         saved_lq = -1.0;
618
619                       // path link quality = link quality between us
620                       // and our one-hop neighbor x link quality between
621                       // our one-hop neighbor and the two-hop neighbor
622
623                       // let's compare this to ETX:
624
625                       // 1 / LQ1 + 1 / LQ2 < 1 / LQ3 + 1 / LQ4 <=>
626                       // LQ1 * LQ2 > LQ3 * LQ4
627
628                       // so comparing path link quality values with ">" is
629                       // equivalent to comparing ETX values with "<"
630
631                       walker->path_link_quality =
632                         link->loss_link_quality * link->neigh_link_quality *
633                         message_neighbors->link_quality *
634                         message_neighbors->neigh_link_quality;
635
636                       // if the link quality has changed by more than 10
637                       // percent, signal
638
639                       rel_lq = walker->path_link_quality / saved_lq;
640
641                       if (rel_lq > 1.1 || rel_lq < 0.9)
642                         {
643                           walker->saved_path_link_quality =
644                             walker->path_link_quality;
645
646                           changes_neighborhood = OLSR_TRUE;
647                           changes_topology = OLSR_TRUE;
648                         }
649                     }
650                 }
651             }
652         }
653     }
654 }
655
656
657
658
659
660
661
662
663 /**
664  *Links a one-hop neighbor with a 2-hop neighbor.
665  *
666  *@param neighbor the 1-hop neighbor
667  *@param two_hop_neighbor the 2-hop neighbor
668  *@return nada
669  */
670 void
671 olsr_linking_this_2_entries(struct neighbor_entry *neighbor,struct neighbor_2_entry *two_hop_neighbor, float vtime)
672 {
673   struct neighbor_list_entry    *list_of_1_neighbors;
674   struct neighbor_2_list_entry  *list_of_2_neighbors;
675
676   list_of_1_neighbors = olsr_malloc(sizeof(struct neighbor_list_entry), "Link entries 1");
677
678   list_of_2_neighbors = olsr_malloc(sizeof(struct neighbor_2_list_entry), "Link entries 2");
679
680   list_of_1_neighbors->neighbor = neighbor;
681
682   list_of_1_neighbors->path_link_quality = 0.0;
683   list_of_1_neighbors->saved_path_link_quality = 0.0;
684
685   /* Queue */
686   two_hop_neighbor->neighbor_2_nblist.next->prev = list_of_1_neighbors;
687   list_of_1_neighbors->next = two_hop_neighbor->neighbor_2_nblist.next;
688   two_hop_neighbor->neighbor_2_nblist.next = list_of_1_neighbors;
689   list_of_1_neighbors->prev = &two_hop_neighbor->neighbor_2_nblist;
690
691
692   list_of_2_neighbors->neighbor_2 = two_hop_neighbor;
693   
694   olsr_get_timestamp((olsr_u32_t) vtime*1000, &list_of_2_neighbors->neighbor_2_timer);
695
696   /* Queue */
697   neighbor->neighbor_2_list.next->prev = list_of_2_neighbors;
698   list_of_2_neighbors->next = neighbor->neighbor_2_list.next;
699   neighbor->neighbor_2_list.next = list_of_2_neighbors;
700   list_of_2_neighbors->prev = &neighbor->neighbor_2_list;
701   
702   /*increment the pointer counter*/
703   two_hop_neighbor->neighbor_2_pointer++;
704 }
705
706
707
708
709
710
711 /**
712  *Check if a hello message states this node as a MPR.
713  *
714  *@param message the message to check
715  *@param n_link the buffer to put the link status in
716  *@param n_status the buffer to put the status in
717  *
718  *@return 1 if we are selected as MPR 0 if not
719  */
720 int
721 olsr_lookup_mpr_status(struct hello_message *message, struct interface *in_if)
722 {
723   
724   struct hello_neighbor  *neighbors;
725
726   neighbors=message->neighbors;
727   
728   while(neighbors!=NULL)
729     {  
730       //printf("(linkstatus)Checking %s ",olsr_ip_to_string(&neighbors->address));
731       //printf("against %s\n",olsr_ip_to_string(&main_addr));
732
733
734     if(olsr_cnf->ip_version == AF_INET)
735       { 
736         /* IPv4 */  
737         if(COMP_IP(&neighbors->address, &in_if->ip_addr))
738           {
739             //printf("ok");
740             if((neighbors->link == SYM_LINK) && (neighbors->status == MPR_NEIGH))
741               return 1;
742             
743             return 0;
744           }
745       }
746     else
747       { 
748         /* IPv6 */  
749         if(COMP_IP(&neighbors->address, &in_if->int6_addr.sin6_addr))
750           {
751             //printf("ok");
752             if((neighbors->link == SYM_LINK) && (neighbors->status == MPR_NEIGH))
753               return 1;
754             
755             return 0;
756           }
757       }
758  
759       neighbors = neighbors->next; 
760     }
761
762   /* Not found */
763   return 0;
764 }