/* * The olsr.org Optimized Link-State Routing daemon(olsrd) * Copyright (c) 2004, Andreas Tønnesen(andreto@olsr.org) * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * * * Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * * Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in * the documentation and/or other materials provided with the * distribution. * * Neither the name of olsr.org, olsrd nor the names of its * contributors may be used to endorse or promote products derived * from this software without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE * POSSIBILITY OF SUCH DAMAGE. * * Visit http://www.olsr.org for more information. * * If you find this software useful feel free to make a donation * to the project. For more information see the website or contact * the copyright holders. * * $Id: process_package.c,v 1.42 2007/09/13 15:31:59 bernd67 Exp $ */ #include "defs.h" #include "process_package.h" #include "lq_packet.h" #include "hysteresis.h" #include "two_hop_neighbor_table.h" #include "tc_set.h" #include "mpr_selector_set.h" #include "mid_set.h" #include "olsr.h" #include "parser.h" #include "duplicate_set.h" #include "rebuild_packet.h" #include "scheduler.h" #include "local_hna_set.h" /** *Initializing the parser functions we are using */ void olsr_init_package_process(void) { if (olsr_cnf->lq_level == 0) { olsr_parser_add_function(&olsr_process_received_hello, HELLO_MESSAGE, 1); olsr_parser_add_function(&olsr_process_received_tc, TC_MESSAGE, 1); } else { olsr_parser_add_function(&olsr_input_lq_hello, LQ_HELLO_MESSAGE, 1); olsr_parser_add_function(&olsr_input_lq_tc, LQ_TC_MESSAGE, 1); } olsr_parser_add_function(&olsr_process_received_mid, MID_MESSAGE, 1); olsr_parser_add_function(&olsr_process_received_hna, HNA_MESSAGE, 1); } void olsr_hello_tap(struct hello_message *message, struct interface *in_if, union olsr_ip_addr *from_addr) { struct neighbor_entry *neighbor; /* * Update link status */ struct link_entry *lnk = update_link_entry(&in_if->ip_addr, from_addr, message, in_if); if (olsr_cnf->lq_level > 0) { double saved_lq; double rel_lq; struct hello_neighbor *walker; // just in case our neighbor has changed its HELLO interval olsr_update_packet_loss_hello_int(lnk, message->htime); // find the input interface in the list of neighbor interfaces for (walker = message->neighbors; walker != NULL; walker = walker->next) if (COMP_IP(&walker->address, &in_if->ip_addr)) break; // the current reference link quality saved_lq = lnk->saved_neigh_link_quality; if (saved_lq == 0.0) saved_lq = -1.0; // memorize our neighbour's idea of the link quality, so that we // know the link quality in both directions if (walker != NULL) lnk->neigh_link_quality = walker->link_quality; else lnk->neigh_link_quality = 0.0; // if the link quality has changed by more than 10 percent, // print the new link quality table rel_lq = lnk->neigh_link_quality / saved_lq; if (rel_lq > 1.1 || rel_lq < 0.9) { lnk->saved_neigh_link_quality = lnk->neigh_link_quality; if (olsr_cnf->lq_dlimit > 0) { changes_neighborhood = OLSR_TRUE; changes_topology = OLSR_TRUE; } else OLSR_PRINTF(3, "Skipping Dijkstra (2)\n"); // create a new ANSN // XXX - we should check whether we actually // announce this neighbour signal_link_changes(OLSR_TRUE); } } neighbor = lnk->neighbor; /* * Hysteresis */ if(olsr_cnf->use_hysteresis) { /* Update HELLO timeout */ //printf("MESSAGE HTIME: %f\n", message->htime); olsr_update_hysteresis_hello(lnk, message->htime); } /* Check if we are chosen as MPR */ if(olsr_lookup_mpr_status(message, in_if)) /* source_addr is always the main addr of a node! */ olsr_update_mprs_set(&message->source_addr, message->vtime); /* Check willingness */ if(neighbor->willingness != message->willingness) { OLSR_PRINTF(1, "Willingness for %s changed from %d to %d - UPDATING\n", olsr_ip_to_string(&neighbor->neighbor_main_addr), neighbor->willingness, message->willingness); /* *If willingness changed - recalculate */ neighbor->willingness = message->willingness; changes_neighborhood = OLSR_TRUE; changes_topology = OLSR_TRUE; } /* Don't register neighbors of neighbors that announces WILL_NEVER */ if(neighbor->willingness != WILL_NEVER) olsr_process_message_neighbors(neighbor, message); /* Process changes immedeatly in case of MPR updates */ olsr_process_changes(); olsr_free_hello_packet(message); return; } /** *Processes a received HELLO message. * *@param m the incoming OLSR message *@return 0 on sucess */ void olsr_process_received_hello(union olsr_message *m, struct interface *in_if, union olsr_ip_addr *from_addr) { struct hello_message message; hello_chgestruct(&message, m); if(!olsr_validate_address(&message.source_addr)) { olsr_free_hello_packet(&message); return; } olsr_hello_tap(&message, in_if, from_addr); } void olsr_tc_tap(struct tc_message *message, struct interface *in_if, union olsr_ip_addr *from_addr, union olsr_message *m) { struct tc_mpr_addr *mpr; struct tc_entry *tc_last; if(!olsr_check_dup_table_proc(&message->originator, message->packet_seq_number)) { goto forward; } OLSR_PRINTF(3, "Processing TC from %s, seq 0x%04x\n", olsr_ip_to_string(&message->originator), message->ansn); /* * If the sender interface (NB: not originator) of this message * is not in the symmetric 1-hop neighborhood of this node, the * message MUST be discarded. */ if(check_neighbor_link(from_addr) != SYM_LINK) { OLSR_PRINTF(2, "Received TC from NON SYM neighbor %s\n", olsr_ip_to_string(from_addr)); olsr_free_tc_packet(message); return; } if(olsr_cnf->debug_level > 2) { mpr = message->multipoint_relay_selector_address; OLSR_PRINTF(3, "mpr_selector_list:["); while(mpr!=NULL) { OLSR_PRINTF(3, "%s:", olsr_ip_to_string(&mpr->address)); mpr=mpr->next; } OLSR_PRINTF(3, "]\n"); } tc_last = olsr_lookup_tc_entry(&message->originator); if(tc_last != NULL) { /* Update entry */ /* Delete destinations with lower ANSN */ if(olsr_tc_delete_mprs(tc_last, message)) changes_topology = OLSR_TRUE; /* Update destinations */ if(olsr_tc_update_mprs(tc_last, message)) changes_topology = OLSR_TRUE; } else { /*if message is empty then skip it */ if(message->multipoint_relay_selector_address != NULL) { /* New entry */ tc_last = olsr_add_tc_entry(&message->originator); /* Update destinations */ olsr_tc_update_mprs(tc_last, message); changes_topology = OLSR_TRUE; } else { OLSR_PRINTF(3, "Dropping empty TC from %s\n", olsr_ip_to_string(&message->originator)); } } /* Process changes */ //olsr_process_changes(); forward: olsr_forward_message(m, &message->originator, message->packet_seq_number, in_if, from_addr); olsr_free_tc_packet(message); return; } /** *Process a received TopologyControl message * * *@param m the incoming OLSR message *@return 0 on success */ void olsr_process_received_tc(union olsr_message *m, struct interface *in_if, union olsr_ip_addr *from_addr) { struct tc_message message; tc_chgestruct(&message, m, from_addr); if(!olsr_validate_address(&message.source_addr)) { olsr_free_tc_packet(&message); return; } olsr_tc_tap(&message, in_if, from_addr, m); } /** *Process a received(and parsed) MID message *For every address check if there is a topology node *registered with it and update its addresses. * *@param m the OLSR message received. *@return 1 on success */ void olsr_process_received_mid(union olsr_message *m, struct interface *in_if, union olsr_ip_addr *from_addr) { struct mid_alias *tmp_adr; struct mid_message message; mid_chgestruct(&message, m); if(!olsr_validate_address(&message.mid_origaddr)) { olsr_free_mid_packet(&message); return; } if(!olsr_check_dup_table_proc(&message.mid_origaddr, message.mid_seqno)) { goto forward; } #ifdef DEBUG OLSR_PRINTF(5, "Processing MID from %s...\n", olsr_ip_to_string(&message.mid_origaddr)); #endif tmp_adr = message.mid_addr; /* * If the sender interface (NB: not originator) of this message * is not in the symmetric 1-hop neighborhood of this node, the * message MUST be discarded. */ if(check_neighbor_link(from_addr) != SYM_LINK) { OLSR_PRINTF(2, "Received MID from NON SYM neighbor %s\n", olsr_ip_to_string(from_addr)); olsr_free_mid_packet(&message); return; } /* Update the timeout of the MID */ olsr_update_mid_table(&message.mid_origaddr, (float)message.vtime); while(tmp_adr) { if(!mid_lookup_main_addr(&tmp_adr->alias_addr)) { OLSR_PRINTF(1, "MID new: (%s, ", olsr_ip_to_string(&message.mid_origaddr)); OLSR_PRINTF(1, "%s)\n", olsr_ip_to_string(&tmp_adr->alias_addr)); insert_mid_alias(&message.mid_origaddr, &tmp_adr->alias_addr, (float)message.vtime); } tmp_adr = tmp_adr->next; } olsr_prune_aliases(&message.mid_origaddr, message.mid_addr); forward: olsr_forward_message(m, &message.mid_origaddr, message.mid_seqno, in_if, from_addr); olsr_free_mid_packet(&message); return; } /** *Process incoming HNA message. *Forwards the message if that is to be done. * *@param m the incoming OLSR message *the OLSR message. *@return 1 on success */ void olsr_process_received_hna(union olsr_message *m, struct interface *in_if, union olsr_ip_addr *from_addr) { struct hna_net_addr *hna_tmp; struct hna_message message; #ifdef DEBUG OLSR_PRINTF(5, "Processing HNA\n"); #endif hna_chgestruct(&message, m); if(!olsr_validate_address(&message.originator)) { olsr_free_hna_packet(&message); return; } if(!olsr_check_dup_table_proc(&message.originator, message.packet_seq_number)) { goto forward; } hna_tmp = message.hna_net; /* * If the sender interface (NB: not originator) of this message * is not in the symmetric 1-hop neighborhood of this node, the * message MUST be discarded. */ if(check_neighbor_link(from_addr) != SYM_LINK) { OLSR_PRINTF(2, "Received HNA from NON SYM neighbor %s\n", olsr_ip_to_string(from_addr)); olsr_free_hna_packet(&message); return; } while(hna_tmp) { /* Don't add an HNA entry that we are advertising ourselves. */ if (!find_local_hna4_entry(&hna_tmp->net, hna_tmp->netmask.v4) && !find_local_hna6_entry(&hna_tmp->net, hna_tmp->netmask.v6)) { olsr_update_hna_entry(&message.originator, &hna_tmp->net, &hna_tmp->netmask, (float)message.vtime); } hna_tmp = hna_tmp->next; } forward: olsr_forward_message(m, &message.originator, message.packet_seq_number, in_if, from_addr); olsr_free_hna_packet(&message); return; } /** *Processes an list of neighbors from an incoming HELLO message. *@param neighbor the neighbor who sent the message. *@param message the HELLO message *@return nada */ void olsr_process_message_neighbors(struct neighbor_entry *neighbor, struct hello_message *message) { struct hello_neighbor *message_neighbors; for(message_neighbors = message->neighbors; message_neighbors != NULL; message_neighbors = message_neighbors->next) { union olsr_ip_addr *neigh_addr; struct neighbor_2_entry *two_hop_neighbor; /* *check all interfaces *so that we don't add ourselves to the *2 hop list *IMPORTANT! */ if(if_ifwithaddr(&message_neighbors->address) != NULL) continue; /* Get the main address */ neigh_addr = mid_lookup_main_addr(&message_neighbors->address); if (neigh_addr != NULL) COPY_IP(&message_neighbors->address, neigh_addr); if(((message_neighbors->status == SYM_NEIGH) || (message_neighbors->status == MPR_NEIGH))) { struct neighbor_2_list_entry *two_hop_neighbor_yet = olsr_lookup_my_neighbors(neighbor, &message_neighbors->address); #ifdef DEBUG OLSR_PRINTF(7, "\tProcessing %s\n", olsr_ip_to_string(&message_neighbors->address)); #endif if (two_hop_neighbor_yet != NULL) { /* Updating the holding time for this neighbor */ two_hop_neighbor_yet->neighbor_2_timer = GET_TIMESTAMP(message->vtime*1000); two_hop_neighbor = two_hop_neighbor_yet->neighbor_2; // For link quality OLSR, reset the path link quality here. // The path link quality will be calculated in the second pass, below. // Keep the saved_path_link_quality for reference. if (olsr_cnf->lq_level > 0) { // loop through the one-hop neighbors that see this // 'two_hop_neighbor' struct neighbor_list_entry *walker; for (walker = two_hop_neighbor->neighbor_2_nblist.next; walker != &two_hop_neighbor->neighbor_2_nblist; walker = walker->next) { // have we found the one-hop neighbor that sent the // HELLO message that we're current processing? if (walker->neighbor == neighbor) { walker->path_link_quality = 0.0; } } } } else { two_hop_neighbor = olsr_lookup_two_hop_neighbor_table(&message_neighbors->address); if (two_hop_neighbor == NULL) { #ifdef DEBUG OLSR_PRINTF(5, "Adding 2 hop neighbor %s\n\n", olsr_ip_to_string(&message_neighbors->address)); #endif changes_neighborhood = OLSR_TRUE; changes_topology = OLSR_TRUE; two_hop_neighbor = olsr_malloc(sizeof(struct neighbor_2_entry), "Process HELLO"); two_hop_neighbor->neighbor_2_nblist.next = &two_hop_neighbor->neighbor_2_nblist; two_hop_neighbor->neighbor_2_nblist.prev = &two_hop_neighbor->neighbor_2_nblist; two_hop_neighbor->neighbor_2_pointer = 0; COPY_IP(&two_hop_neighbor->neighbor_2_addr, &message_neighbors->address); olsr_insert_two_hop_neighbor_table(two_hop_neighbor); olsr_linking_this_2_entries(neighbor, two_hop_neighbor, (float)message->vtime); } else { /* linking to this two_hop_neighbor entry */ changes_neighborhood = OLSR_TRUE; changes_topology = OLSR_TRUE; olsr_linking_this_2_entries(neighbor, two_hop_neighbor, (float)message->vtime); } } } } // Separate, second and third pass for link quality OLSR if (olsr_cnf->lq_level > 0) { struct link_entry *lnk = get_best_link_to_neighbor(&neighbor->neighbor_main_addr); if(!lnk) return; // Second pass for link quality OLSR: calculate the best 2-hop // path costs to all the 2-hop neighbors indicated in the // HELLO message. Since the same 2-hop neighbor may be listed // more than once in the same HELLO message (each at a possibly // different quality) we want to select only the best one, not just // the last one listed in the HELLO message. for(message_neighbors = message->neighbors; message_neighbors != NULL; message_neighbors = message_neighbors->next) { if(if_ifwithaddr(&message_neighbors->address) != NULL) continue; if(((message_neighbors->status == SYM_NEIGH) || (message_neighbors->status == MPR_NEIGH))) { struct neighbor_list_entry *walker; struct neighbor_2_entry *two_hop_neighbor; struct neighbor_2_list_entry *two_hop_neighbor_yet = olsr_lookup_my_neighbors(neighbor, &message_neighbors->address); if(!two_hop_neighbor_yet) continue; two_hop_neighbor = two_hop_neighbor_yet->neighbor_2; // loop through the one-hop neighbors that see this // 'two_hop_neighbor' for (walker = two_hop_neighbor->neighbor_2_nblist.next; walker != &two_hop_neighbor->neighbor_2_nblist; walker = walker->next) { // have we found the one-hop neighbor that sent the // HELLO message that we're current processing? if (walker->neighbor == neighbor) { double new_second_hop_link_quality, new_path_link_quality; // path link quality = link quality between us // and our one-hop neighbor x link quality between // our one-hop neighbor and the two-hop neighbor // let's compare this to ETX: // 1 / LQ1 + 1 / LQ2 < 1 / LQ3 + 1 / LQ4 <=> // LQ1 * LQ2 > LQ3 * LQ4 // so comparing path link quality values with ">" is // equivalent to comparing ETX values with "<" // the link quality between the 1-hop neighbour and the // 2-hop neighbour new_second_hop_link_quality = message_neighbors->link_quality * message_neighbors->neigh_link_quality; // the total quality for the route // "us --- 1-hop --- 2-hop" new_path_link_quality = new_second_hop_link_quality * lnk->loss_link_quality * lnk->neigh_link_quality; // Only copy the link quality if it is better than what we have // for this 2-hop neighbor if (new_path_link_quality > walker->path_link_quality) { walker->second_hop_link_quality = new_second_hop_link_quality; walker->path_link_quality = new_path_link_quality; } } } } } // Third pass for link quality OLSR: check if the 2-hop path qualities have // actually changed. If so, signal this through the 'changes_neighborhood' // and 'changes_topology' booleans. Keep a 'saved_path_link_quality' for // later reference. for(message_neighbors = message->neighbors; message_neighbors != NULL; message_neighbors = message_neighbors->next) { if(if_ifwithaddr(&message_neighbors->address) != NULL) continue; if(((message_neighbors->status == SYM_NEIGH) || (message_neighbors->status == MPR_NEIGH))) { struct neighbor_list_entry *walker; struct neighbor_2_entry *two_hop_neighbor; struct neighbor_2_list_entry *two_hop_neighbor_yet = olsr_lookup_my_neighbors(neighbor, &message_neighbors->address); if(!two_hop_neighbor_yet) continue; two_hop_neighbor = two_hop_neighbor_yet->neighbor_2; // loop through the one-hop neighbors that see this // 'two_hop_neighbor' for (walker = two_hop_neighbor->neighbor_2_nblist.next; walker != &two_hop_neighbor->neighbor_2_nblist; walker = walker->next) { // have we found the one-hop neighbor that sent the // HELLO message that we're current processing? if (walker->neighbor == neighbor) { double saved_lq, rel_lq; // saved previous total link quality saved_lq = walker->saved_path_link_quality; if (saved_lq == 0.0) saved_lq = -1.0; // if the link cost has changed by more than 10 // percent, signal rel_lq = walker->path_link_quality / saved_lq; if (rel_lq > 1.1 || rel_lq < 0.9) { walker->saved_path_link_quality = walker->path_link_quality; if (olsr_cnf->lq_dlimit > 0) { changes_neighborhood = OLSR_TRUE; changes_topology = OLSR_TRUE; } else OLSR_PRINTF(3, "Skipping Dijkstra (3)\n"); } } } } } } } /** *Links a one-hop neighbor with a 2-hop neighbor. * *@param neighbor the 1-hop neighbor *@param two_hop_neighbor the 2-hop neighbor *@return nada */ void olsr_linking_this_2_entries(struct neighbor_entry *neighbor,struct neighbor_2_entry *two_hop_neighbor, float vtime) { struct neighbor_list_entry *list_of_1_neighbors; struct neighbor_2_list_entry *list_of_2_neighbors; list_of_1_neighbors = olsr_malloc(sizeof(struct neighbor_list_entry), "Link entries 1"); list_of_2_neighbors = olsr_malloc(sizeof(struct neighbor_2_list_entry), "Link entries 2"); list_of_1_neighbors->neighbor = neighbor; list_of_1_neighbors->path_link_quality = 0.0; list_of_1_neighbors->saved_path_link_quality = 0.0; list_of_1_neighbors->second_hop_link_quality = 0.0; /* Queue */ two_hop_neighbor->neighbor_2_nblist.next->prev = list_of_1_neighbors; list_of_1_neighbors->next = two_hop_neighbor->neighbor_2_nblist.next; two_hop_neighbor->neighbor_2_nblist.next = list_of_1_neighbors; list_of_1_neighbors->prev = &two_hop_neighbor->neighbor_2_nblist; list_of_2_neighbors->neighbor_2 = two_hop_neighbor; list_of_2_neighbors->neighbor_2_timer = GET_TIMESTAMP(vtime*1000); /* Queue */ neighbor->neighbor_2_list.next->prev = list_of_2_neighbors; list_of_2_neighbors->next = neighbor->neighbor_2_list.next; neighbor->neighbor_2_list.next = list_of_2_neighbors; list_of_2_neighbors->prev = &neighbor->neighbor_2_list; /*increment the pointer counter*/ two_hop_neighbor->neighbor_2_pointer++; } /** *Check if a hello message states this node as a MPR. * *@param message the message to check *@param n_link the buffer to put the link status in *@param n_status the buffer to put the status in * *@return 1 if we are selected as MPR 0 if not */ int olsr_lookup_mpr_status(struct hello_message *message, struct interface *in_if) { struct hello_neighbor *neighbors; neighbors=message->neighbors; while(neighbors!=NULL) { //printf("(linkstatus)Checking %s ",olsr_ip_to_string(&neighbors->address)); //printf("against %s\n",olsr_ip_to_string(&main_addr)); if(olsr_cnf->ip_version == AF_INET) { /* IPv4 */ if(COMP_IP(&neighbors->address, &in_if->ip_addr)) { //printf("ok"); if((neighbors->link == SYM_LINK) && (neighbors->status == MPR_NEIGH)) return 1; return 0; } } else { /* IPv6 */ if(COMP_IP(&neighbors->address, &in_if->int6_addr.sin6_addr)) { //printf("ok"); if((neighbors->link == SYM_LINK) && (neighbors->status == MPR_NEIGH)) return 1; return 0; } } neighbors = neighbors->next; } /* Not found */ return 0; }