2 * The olsr.org Optimized Link-State Routing daemon(olsrd)
3 * Copyright (c) 2004, Andreas Tønnesen(andreto@olsr.org)
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
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
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.
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.
33 * Visit http://www.olsr.org for more information.
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.
39 * $Id: process_package.c,v 1.24 2004/12/04 17:06:57 tlopatic Exp $
44 #include "process_package.h"
45 #include "hysteresis.h"
46 #include "two_hop_neighbor_table.h"
48 #include "mpr_selector_set.h"
52 #include "duplicate_set.h"
53 #include "rebuild_packet.h"
57 *Initializing the parser functions we are using
60 olsr_init_package_process()
62 if (olsr_cnf->lq_level == 0)
64 olsr_parser_add_function(&olsr_process_received_hello, HELLO_MESSAGE, 1);
65 olsr_parser_add_function(&olsr_process_received_tc, TC_MESSAGE, 1);
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);
74 olsr_parser_add_function(&olsr_process_received_mid, MID_MESSAGE, 1);
75 olsr_parser_add_function(&olsr_process_received_hna, HNA_MESSAGE, 1);
79 olsr_hello_tap(struct hello_message *message, struct interface *in_if,
80 union olsr_ip_addr *from_addr)
82 struct link_entry *link;
83 struct neighbor_entry *neighbor;
84 struct hello_neighbor *walker;
91 link = update_link_entry(&in_if->ip_addr, from_addr, message, in_if);
93 if (olsr_cnf->lq_level > 0)
95 // just in case our neighbor has changed its HELLO interval
97 olsr_update_packet_loss_hello_int(link, message->htime);
99 // find the input interface in the list of neighbor interfaces
101 for (walker = message->neighbors; walker != NULL; walker = walker->next)
102 if (COMP_IP(&walker->address, &in_if->ip_addr))
105 // the current reference link quality
107 saved_lq = link->saved_neigh_link_quality;
112 // memorize our neighbour's idea of the link quality, so that we
113 // know the link quality in both directions
116 link->neigh_link_quality = walker->link_quality;
119 link->neigh_link_quality = 0.0;
121 // if the link quality has changed by more than 10 percent,
122 // print the new link quality table
124 rel_lq = link->neigh_link_quality / saved_lq;
126 if (rel_lq > 1.1 || rel_lq < 0.9)
128 link->saved_neigh_link_quality = link->neigh_link_quality;
130 changes_neighborhood = OLSR_TRUE;
131 changes_topology = OLSR_TRUE;
135 // XXX - we should check whether we actually
136 // announce this neighbour
142 neighbor = link->neighbor;
147 if(olsr_cnf->use_hysteresis)
149 /* Update HELLO timeout */
150 //printf("MESSAGE HTIME: %f\n", message->htime);
151 olsr_update_hysteresis_hello(link, message->htime);
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);
161 /* Check willingness */
162 if(neighbor->willingness != message->willingness)
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);
169 *If willingness changed - recalculate
171 neighbor->willingness = message->willingness;
172 changes_neighborhood = OLSR_TRUE;
173 changes_topology = OLSR_TRUE;
177 /* Don't register neighbors of neighbors that announces WILL_NEVER */
178 if(neighbor->willingness != WILL_NEVER)
179 olsr_process_message_neighbors(neighbor, message);
181 /* Process changes immedeatly in case of MPR updates */
182 olsr_process_changes();
184 olsr_destroy_hello_message(message);
190 *Processes a received HELLO message.
192 *@param m the incoming OLSR message
197 olsr_process_received_hello(union olsr_message *m, struct interface *in_if, union olsr_ip_addr *from_addr)
199 struct hello_message message;
201 hello_chgestruct(&message, m);
203 olsr_hello_tap(&message, in_if, from_addr);
207 olsr_tc_tap(struct tc_message *message, struct interface *in_if,
208 union olsr_ip_addr *from_addr, union olsr_message *m)
210 struct tc_mpr_addr *mpr;
211 struct tc_entry *tc_last;
213 if(!olsr_check_dup_table_proc(&message->originator,
214 message->packet_seq_number))
219 olsr_printf(3, "Processing TC from %s\n",
220 olsr_ip_to_string(&message->originator));
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.
228 if(check_neighbor_link(from_addr) != SYM_LINK)
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);
236 if(olsr_cnf->debug_level > 2)
238 mpr = message->multipoint_relay_selector_address;
239 olsr_printf(3, "mpr_selector_list:[");
243 olsr_printf(3, "%s:", olsr_ip_to_string(&mpr->address));
247 olsr_printf(3, "]\n");
250 tc_last = olsr_lookup_tc_entry(&message->originator);
256 /* Delete destinations with lower ANSN */
257 if(olsr_tc_delete_mprs(tc_last, message))
258 changes_topology = OLSR_TRUE;
260 /* Update destinations */
261 if(olsr_tc_update_mprs(tc_last, message))
262 changes_topology = OLSR_TRUE;
264 /* Delete possible empty TC entry */
266 olsr_tc_delete_entry_if_empty(tc_last);
271 /*if message is empty then skip it */
272 if(message->multipoint_relay_selector_address != NULL)
275 tc_last = olsr_add_tc_entry(&message->originator);
277 /* Update destinations */
278 olsr_tc_update_mprs(tc_last, message);
280 changes_topology = OLSR_TRUE;
284 olsr_printf(3, "Dropping empty TC from %s\n",
285 olsr_ip_to_string(&message->originator));
289 /* Process changes */
290 //olsr_process_changes();
294 olsr_forward_message(m,
295 &message->originator,
296 message->packet_seq_number,
300 olsr_destroy_tc_message(message);
306 *Process a received TopologyControl message
309 *@param m the incoming OLSR message
310 *@return 0 on success
313 olsr_process_received_tc(union olsr_message *m, struct interface *in_if, union olsr_ip_addr *from_addr)
315 struct tc_message message;
317 tc_chgestruct(&message, m, from_addr);
319 olsr_tc_tap(&message, in_if, from_addr, m);
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.
332 *@param m the OLSR message received.
333 *@return 1 on success
337 olsr_process_received_mid(union olsr_message *m, struct interface *in_if, union olsr_ip_addr *from_addr)
339 struct mid_alias *tmp_adr;
340 struct mid_message message;
343 mid_chgestruct(&message, m);
346 if(COMP_IP(&message.mid_origaddr, &main_addr))
352 if(!olsr_check_dup_table_proc(&message.mid_origaddr,
358 olsr_printf(5, "Processing MID from %s...\n", olsr_ip_to_string(&message.mid_origaddr));
360 tmp_adr = message.mid_addr;
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.
369 if(check_neighbor_link(from_addr) != SYM_LINK)
371 olsr_printf(2, "Received MID from NON SYM neighbor %s\n", olsr_ip_to_string(from_addr));
372 olsr_destroy_mid_message(&message);
378 /* Update the timeout of the MID */
379 olsr_update_mid_table(&message.mid_origaddr, (float)message.vtime);
383 if(!mid_lookup_main_addr(&tmp_adr->alias_addr))
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);
391 tmp_adr = tmp_adr->next;
394 /*Update topology if neccesary*/
395 //olsr_process_changes();
399 olsr_forward_message(m,
400 &message.mid_origaddr,
404 olsr_destroy_mid_message(&message);
414 *Process incoming HNA message.
415 *Forwards the message if that is to be done.
417 *@param m the incoming OLSR message
419 *@return 1 on success
423 olsr_process_received_hna(union olsr_message *m, struct interface *in_if, union olsr_ip_addr *from_addr)
425 struct hna_net_addr *hna_tmp;
426 struct hna_message message;
428 //printf("Processing HNA\n");
430 hna_chgestruct(&message, m);
433 /* Process message */
435 if(COMP_IP(&message.originator, &main_addr))
441 if(!olsr_check_dup_table_proc(&message.originator,
442 message.packet_seq_number))
450 hna_tmp = message.hna_net;
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.
461 if(check_neighbor_link(from_addr) != SYM_LINK)
463 olsr_printf(2, "Received HNA from NON SYM neighbor %s\n", olsr_ip_to_string(from_addr));
464 olsr_destroy_hna_message(&message);
470 olsr_update_hna_entry(&message.originator, &hna_tmp->net, &hna_tmp->netmask, (float)message.vtime);
472 hna_tmp = hna_tmp->next;
475 /*Update topology if neccesary*/
476 //olsr_process_changes();
479 olsr_forward_message(m,
481 message.packet_seq_number,
484 olsr_destroy_hna_message(&message);
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
502 olsr_process_message_neighbors(struct neighbor_entry *neighbor,
503 struct hello_message *message)
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;
512 for(message_neighbors = message->neighbors;
513 message_neighbors != NULL;
514 message_neighbors = message_neighbors->next)
517 *check all interfaces
518 *so that we don't add ourselves to the
522 if(if_ifwithaddr(&message_neighbors->address) != NULL)
525 /* Get the main address */
527 neigh_addr = mid_lookup_main_addr(&message_neighbors->address);
529 if (neigh_addr != NULL)
530 COPY_IP(&message_neighbors->address, neigh_addr);
532 if(((message_neighbors->status == SYM_NEIGH) ||
533 (message_neighbors->status == MPR_NEIGH)))
535 //printf("\tProcessing %s\n", olsr_ip_to_string(&message_neighbors->address));
536 //printf("\tMain addr: %s\n", olsr_ip_to_string(neigh_addr));
538 two_hop_neighbor_yet =
539 olsr_lookup_my_neighbors(neighbor,
540 &message_neighbors->address);
542 if (two_hop_neighbor_yet != NULL)
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);
548 two_hop_neighbor = two_hop_neighbor_yet->neighbor_2;
553 olsr_lookup_two_hop_neighbor_table(&message_neighbors->address);
554 if (two_hop_neighbor == NULL)
556 //printf("Adding 2 hop neighbor %s\n\n", olsr_ip_to_string(&message_neighbors->address));
558 changes_neighborhood = OLSR_TRUE;
559 changes_topology = OLSR_TRUE;
562 olsr_malloc(sizeof(struct neighbor_2_entry),
565 two_hop_neighbor->neighbor_2_nblist.next =
566 &two_hop_neighbor->neighbor_2_nblist;
568 two_hop_neighbor->neighbor_2_nblist.prev =
569 &two_hop_neighbor->neighbor_2_nblist;
571 two_hop_neighbor->neighbor_2_pointer = 0;
573 COPY_IP(&two_hop_neighbor->neighbor_2_addr,
574 &message_neighbors->address);
576 olsr_insert_two_hop_neighbor_table(two_hop_neighbor);
578 olsr_linking_this_2_entries(neighbor, two_hop_neighbor,
579 (float)message->vtime);
584 linking to this two_hop_neighbor entry
586 changes_neighborhood = OLSR_TRUE;
587 changes_topology = OLSR_TRUE;
589 olsr_linking_this_2_entries(neighbor, two_hop_neighbor,
590 (float)message->vtime);
594 if (olsr_cnf->lq_level > 0)
596 link = olsr_neighbor_best_link(&neighbor->neighbor_main_addr);
598 // loop through the one-hop neighbors that see this
601 for (walker = two_hop_neighbor->neighbor_2_nblist.next;
602 walker != &two_hop_neighbor->neighbor_2_nblist;
603 walker = walker->next)
605 // have we found the one-hop neighbor that sent the
606 // HELLO message that we're current processing?
608 if (walker->neighbor == neighbor)
610 double saved_lq, rel_lq;
612 // saved previous total link quality
614 saved_lq = walker->saved_path_link_quality;
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
623 // let's compare this to ETX:
625 // 1 / LQ1 + 1 / LQ2 < 1 / LQ3 + 1 / LQ4 <=>
626 // LQ1 * LQ2 > LQ3 * LQ4
628 // so comparing path link quality values with ">" is
629 // equivalent to comparing ETX values with "<"
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;
636 // if the link quality has changed by more than 10
639 rel_lq = walker->path_link_quality / saved_lq;
641 if (rel_lq > 1.1 || rel_lq < 0.9)
643 walker->saved_path_link_quality =
644 walker->path_link_quality;
646 changes_neighborhood = OLSR_TRUE;
647 changes_topology = OLSR_TRUE;
664 *Links a one-hop neighbor with a 2-hop neighbor.
666 *@param neighbor the 1-hop neighbor
667 *@param two_hop_neighbor the 2-hop neighbor
671 olsr_linking_this_2_entries(struct neighbor_entry *neighbor,struct neighbor_2_entry *two_hop_neighbor, float vtime)
673 struct neighbor_list_entry *list_of_1_neighbors;
674 struct neighbor_2_list_entry *list_of_2_neighbors;
676 list_of_1_neighbors = olsr_malloc(sizeof(struct neighbor_list_entry), "Link entries 1");
678 list_of_2_neighbors = olsr_malloc(sizeof(struct neighbor_2_list_entry), "Link entries 2");
680 list_of_1_neighbors->neighbor = neighbor;
682 list_of_1_neighbors->path_link_quality = 0.0;
683 list_of_1_neighbors->saved_path_link_quality = 0.0;
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;
692 list_of_2_neighbors->neighbor_2 = two_hop_neighbor;
694 olsr_get_timestamp((olsr_u32_t) vtime*1000, &list_of_2_neighbors->neighbor_2_timer);
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;
702 /*increment the pointer counter*/
703 two_hop_neighbor->neighbor_2_pointer++;
712 *Check if a hello message states this node as a MPR.
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
718 *@return 1 if we are selected as MPR 0 if not
721 olsr_lookup_mpr_status(struct hello_message *message, struct interface *in_if)
724 struct hello_neighbor *neighbors;
726 neighbors=message->neighbors;
728 while(neighbors!=NULL)
730 //printf("(linkstatus)Checking %s ",olsr_ip_to_string(&neighbors->address));
731 //printf("against %s\n",olsr_ip_to_string(&main_addr));
734 if(olsr_cnf->ip_version == AF_INET)
737 if(COMP_IP(&neighbors->address, &in_if->ip_addr))
740 if((neighbors->link == SYM_LINK) && (neighbors->status == MPR_NEIGH))
749 if(COMP_IP(&neighbors->address, &in_if->int6_addr.sin6_addr))
752 if((neighbors->link == SYM_LINK) && (neighbors->status == MPR_NEIGH))
759 neighbors = neighbors->next;