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