2 * OLSR ad-hoc routing table management protocol
3 * Copyright (C) 2003 Andreas Tønnesen (andreto@ifi.uio.no)
5 * This file is part of the olsr.org OLSR daemon.
7 * olsr.org is free software; you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation; either version 2 of the License, or
10 * (at your option) any later version.
12 * olsr.org is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
17 * You should have received a copy of the GNU General Public License
18 * along with olsr.org; if not, write to the Free Software
19 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
22 * $Id: process_package.c,v 1.20 2004/11/10 14:53:21 tlopatic Exp $
28 #include "process_package.h"
29 #include "hysteresis.h"
30 #include "two_hop_neighbor_table.h"
32 #include "mpr_selector_set.h"
36 #include "duplicate_set.h"
37 #include "rebuild_packet.h"
40 #include "linux/tunnel.h"
45 *Initializing the parser functions we are using
48 olsr_init_package_process()
50 #if defined USE_LINK_QUALITY
51 if (olsr_cnf->lq_level == 0)
54 olsr_parser_add_function(&olsr_process_received_hello, HELLO_MESSAGE, 1);
55 olsr_parser_add_function(&olsr_process_received_tc, TC_MESSAGE, 1);
56 #if defined USE_LINK_QUALITY
61 olsr_parser_add_function(&olsr_input_lq_hello, LQ_HELLO_MESSAGE, 1);
62 olsr_parser_add_function(&olsr_input_lq_tc, LQ_TC_MESSAGE, 1);
65 olsr_parser_add_function(&olsr_process_received_mid, MID_MESSAGE, 1);
66 olsr_parser_add_function(&olsr_process_received_hna, HNA_MESSAGE, 1);
70 olsr_hello_tap(struct hello_message *message, struct interface *in_if,
71 union olsr_ip_addr *from_addr)
73 struct link_entry *link;
74 struct neighbor_entry *neighbor;
75 #if defined USE_LINK_QUALITY
76 struct hello_neighbor *walker;
84 link = update_link_entry(&in_if->ip_addr, from_addr, message, in_if);
86 #if defined USE_LINK_QUALITY
87 if (olsr_cnf->lq_level > 0)
89 // just in case our neighbor has changed its HELLO interval
91 olsr_update_packet_loss_hello_int(link, message->htime);
93 // find the input interface in the list of neighbor interfaces
95 for (walker = message->neighbors; walker != NULL; walker = walker->next)
96 if (COMP_IP(&walker->address, &in_if->ip_addr))
99 // the current reference link quality
101 saved_lq = link->saved_neigh_link_quality;
106 // memorize our neighbour's idea of the link quality, so that we
107 // know the link quality in both directions
110 link->neigh_link_quality = walker->link_quality;
113 link->neigh_link_quality = 0.0;
115 // if the link quality has changed by more than 10 percent,
116 // print the new link quality table
118 rel_lq = link->neigh_link_quality / saved_lq;
120 if (rel_lq > 1.1 || rel_lq < 0.9)
122 link->saved_neigh_link_quality = link->neigh_link_quality;
124 changes_neighborhood = OLSR_TRUE;
125 changes_topology = OLSR_TRUE;
129 // XXX - we should check whether we actually
130 // announce this neighbour
137 neighbor = link->neighbor;
142 if(olsr_cnf->use_hysteresis)
144 /* Update HELLO timeout */
145 //printf("MESSAGE HTIME: %f\n", message->htime);
146 olsr_update_hysteresis_hello(link, message->htime);
149 /* Check if we are chosen as MPR */
150 if(olsr_lookup_mpr_status(message, in_if))
151 /* source_addr is always the main addr of a node! */
152 olsr_update_mprs_set(&message->source_addr, (float)message->vtime);
156 /* Check willingness */
157 if(neighbor->willingness != message->willingness)
159 olsr_printf(1, "Willingness for %s changed from %d to %d - UPDATING\n",
160 olsr_ip_to_string(&neighbor->neighbor_main_addr),
161 neighbor->willingness,
162 message->willingness);
164 *If willingness changed - recalculate
166 neighbor->willingness = message->willingness;
167 changes_neighborhood = OLSR_TRUE;
168 changes_topology = OLSR_TRUE;
172 /* Don't register neighbors of neighbors that announces WILL_NEVER */
173 if(neighbor->willingness != WILL_NEVER)
174 olsr_process_message_neighbors(neighbor, message);
176 /* Process changes immedeatly in case of MPR updates */
177 olsr_process_changes();
179 olsr_destroy_hello_message(message);
185 *Processes a received HELLO message.
187 *@param m the incoming OLSR message
192 olsr_process_received_hello(union olsr_message *m, struct interface *in_if, union olsr_ip_addr *from_addr)
194 struct hello_message message;
196 hello_chgestruct(&message, m);
198 olsr_hello_tap(&message, in_if, from_addr);
202 olsr_tc_tap(struct tc_message *message, struct interface *in_if,
203 union olsr_ip_addr *from_addr, union olsr_message *m)
205 struct tc_mpr_addr *mpr;
206 struct tc_entry *tc_last;
208 if(!olsr_check_dup_table_proc(&message->originator,
209 message->packet_seq_number))
214 olsr_printf(3, "Processing TC from %s\n",
215 olsr_ip_to_string(&message->originator));
218 * If the sender interface (NB: not originator) of this message
219 * is not in the symmetric 1-hop neighborhood of this node, the
220 * message MUST be discarded.
223 if(check_neighbor_link(from_addr) != SYM_LINK)
225 olsr_printf(2, "Received TC from NON SYM neighbor %s\n",
226 olsr_ip_to_string(from_addr));
227 olsr_destroy_tc_message(message);
231 if(olsr_cnf->debug_level > 2)
233 mpr = message->multipoint_relay_selector_address;
234 olsr_printf(3, "mpr_selector_list:[");
238 olsr_printf(3, "%s:", olsr_ip_to_string(&mpr->address));
242 olsr_printf(3, "]\n");
245 tc_last = olsr_lookup_tc_entry(&message->originator);
251 /* Delete destinations with lower ANSN */
252 if(olsr_tc_delete_mprs(tc_last, message))
253 changes_topology = OLSR_TRUE;
255 /* Update destinations */
256 if(olsr_tc_update_mprs(tc_last, message))
257 changes_topology = OLSR_TRUE;
259 /* Delete possible empty TC entry */
261 olsr_tc_delete_entry_if_empty(tc_last);
266 /*if message is empty then skip it */
267 if(message->multipoint_relay_selector_address != NULL)
270 tc_last = olsr_add_tc_entry(&message->originator);
272 /* Update destinations */
273 olsr_tc_update_mprs(tc_last, message);
275 changes_topology = OLSR_TRUE;
279 olsr_printf(3, "Dropping empty TC from %s\n",
280 olsr_ip_to_string(&message->originator));
284 /* Process changes */
285 //olsr_process_changes();
289 olsr_forward_message(m,
290 &message->originator,
291 message->packet_seq_number,
295 olsr_destroy_tc_message(message);
301 *Process a received TopologyControl message
304 *@param m the incoming OLSR message
305 *@return 0 on success
308 olsr_process_received_tc(union olsr_message *m, struct interface *in_if, union olsr_ip_addr *from_addr)
310 struct tc_message message;
312 tc_chgestruct(&message, m, from_addr);
314 olsr_tc_tap(&message, in_if, from_addr, m);
323 *Process a received(and parsed) MID message
324 *For every address check if there is a topology node
325 *registered with it and update its addresses.
327 *@param m the OLSR message received.
328 *@return 1 on success
332 olsr_process_received_mid(union olsr_message *m, struct interface *in_if, union olsr_ip_addr *from_addr)
334 struct mid_alias *tmp_adr;
335 struct mid_message message;
338 mid_chgestruct(&message, m);
341 if(COMP_IP(&message.mid_origaddr, &main_addr))
347 if(!olsr_check_dup_table_proc(&message.mid_origaddr,
353 olsr_printf(5, "Processing MID from %s...\n", olsr_ip_to_string(&message.mid_origaddr));
355 tmp_adr = message.mid_addr;
359 * If the sender interface (NB: not originator) of this message
360 * is not in the symmetric 1-hop neighborhood of this node, the
361 * message MUST be discarded.
364 if(check_neighbor_link(from_addr) != SYM_LINK)
366 olsr_printf(2, "Received MID from NON SYM neighbor %s\n", olsr_ip_to_string(from_addr));
367 olsr_destroy_mid_message(&message);
373 /* Update the timeout of the MID */
374 olsr_update_mid_table(&message.mid_origaddr, (float)message.vtime);
378 if(!mid_lookup_main_addr(&tmp_adr->alias_addr))
380 olsr_printf(1, "MID new: (%s, ", olsr_ip_to_string(&message.mid_origaddr));
381 olsr_printf(1, "%s)\n", olsr_ip_to_string(&tmp_adr->alias_addr));
382 insert_mid_alias(&message.mid_origaddr, &tmp_adr->alias_addr, (float)message.vtime);
386 tmp_adr = tmp_adr->next;
389 /*Update topology if neccesary*/
390 //olsr_process_changes();
394 olsr_forward_message(m,
395 &message.mid_origaddr,
399 olsr_destroy_mid_message(&message);
409 *Process incoming HNA message.
410 *Forwards the message if that is to be done.
412 *@param m the incoming OLSR message
414 *@return 1 on success
418 olsr_process_received_hna(union olsr_message *m, struct interface *in_if, union olsr_ip_addr *from_addr)
420 struct hna_net_addr *hna_tmp;
421 struct hna_message message;
423 //printf("Processing HNA\n");
425 hna_chgestruct(&message, m);
428 /* Process message */
430 if(COMP_IP(&message.originator, &main_addr))
436 if(!olsr_check_dup_table_proc(&message.originator,
437 message.packet_seq_number))
445 hna_tmp = message.hna_net;
450 * If the sender interface (NB: not originator) of this message
451 * is not in the symmetric 1-hop neighborhood of this node, the
452 * message MUST be discarded.
456 if(check_neighbor_link(from_addr) != SYM_LINK)
458 olsr_printf(2, "Received HNA from NON SYM neighbor %s\n", olsr_ip_to_string(from_addr));
459 olsr_destroy_hna_message(&message);
467 * Set up tunnel to Internet gateway
469 if((use_tunnel) && (olsr_cnf->ip_version == AF_INET) && (hna_tmp->net.v4 == 0))
471 if(inet_tnl_added || gw_tunnel)
473 hna_tmp = hna_tmp->next;
477 olsr_printf(1, "Internet gateway discovered! Setting up tunnel:\n");
479 /* Set up tunnel endpoint */
480 set_up_source_tnl(&main_addr, &message.originator, in_if->if_index);
485 olsr_update_hna_entry(&message.originator, &hna_tmp->net, &hna_tmp->netmask, (float)message.vtime);
488 hna_tmp = hna_tmp->next;
491 /*Update topology if neccesary*/
492 //olsr_process_changes();
495 olsr_forward_message(m,
497 message.packet_seq_number,
500 olsr_destroy_hna_message(&message);
512 *Processes an list of neighbors from an incoming HELLO message.
513 *@param neighbor the neighbor who sendt the message.
514 *@param message the HELLO message
518 olsr_process_message_neighbors(struct neighbor_entry *neighbor,
519 struct hello_message *message)
521 struct hello_neighbor *message_neighbors;
522 struct neighbor_2_list_entry *two_hop_neighbor_yet;
523 struct neighbor_2_entry *two_hop_neighbor;
524 union olsr_ip_addr *neigh_addr;
525 #if defined USE_LINK_QUALITY
526 struct neighbor_list_entry *walker;
527 struct link_entry *link;
530 for(message_neighbors = message->neighbors;
531 message_neighbors != NULL;
532 message_neighbors = message_neighbors->next)
535 *check all interfaces
536 *so that we don't add ourselves to the
540 if(if_ifwithaddr(&message_neighbors->address) != NULL)
543 /* Get the main address */
545 neigh_addr = mid_lookup_main_addr(&message_neighbors->address);
547 if (neigh_addr != NULL)
548 COPY_IP(&message_neighbors->address, neigh_addr);
550 if(((message_neighbors->status == SYM_NEIGH) ||
551 (message_neighbors->status == MPR_NEIGH)))
553 //printf("\tProcessing %s\n", olsr_ip_to_string(&message_neighbors->address));
554 //printf("\tMain addr: %s\n", olsr_ip_to_string(neigh_addr));
556 two_hop_neighbor_yet =
557 olsr_lookup_my_neighbors(neighbor,
558 &message_neighbors->address);
560 if (two_hop_neighbor_yet != NULL)
562 /* Updating the holding time for this neighbor */
563 olsr_get_timestamp((olsr_u32_t)message->vtime * 1000,
564 &two_hop_neighbor_yet->neighbor_2_timer);
566 two_hop_neighbor = two_hop_neighbor_yet->neighbor_2;
571 olsr_lookup_two_hop_neighbor_table(&message_neighbors->address);
572 if (two_hop_neighbor == NULL)
574 //printf("Adding 2 hop neighbor %s\n\n", olsr_ip_to_string(&message_neighbors->address));
576 changes_neighborhood = OLSR_TRUE;
577 changes_topology = OLSR_TRUE;
580 olsr_malloc(sizeof(struct neighbor_2_entry),
583 two_hop_neighbor->neighbor_2_nblist.next =
584 &two_hop_neighbor->neighbor_2_nblist;
586 two_hop_neighbor->neighbor_2_nblist.prev =
587 &two_hop_neighbor->neighbor_2_nblist;
589 two_hop_neighbor->neighbor_2_pointer = 0;
591 COPY_IP(&two_hop_neighbor->neighbor_2_addr,
592 &message_neighbors->address);
594 olsr_insert_two_hop_neighbor_table(two_hop_neighbor);
596 olsr_linking_this_2_entries(neighbor, two_hop_neighbor,
597 (float)message->vtime);
602 linking to this two_hop_neighbor entry
604 changes_neighborhood = OLSR_TRUE;
605 changes_topology = OLSR_TRUE;
607 olsr_linking_this_2_entries(neighbor, two_hop_neighbor,
608 (float)message->vtime);
611 #if defined USE_LINK_QUALITY
612 if (olsr_cnf->lq_level > 0)
614 link = olsr_neighbor_best_link(&neighbor->neighbor_main_addr);
616 // loop through the one-hop neighbors that see this
619 for (walker = two_hop_neighbor->neighbor_2_nblist.next;
620 walker != &two_hop_neighbor->neighbor_2_nblist;
621 walker = walker->next)
623 // have we found the one-hop neighbor that sent the
624 // HELLO message that we're current processing?
626 if (walker->neighbor == neighbor)
628 double saved_lq, rel_lq;
630 // saved previous total link quality
632 saved_lq = walker->saved_full_link_quality;
637 // total link quality = link quality between us
638 // and our one-hop neighbor x link quality between
639 // our one-hop neighbor and the two-hop neighbor
641 walker->full_link_quality =
642 link->neigh_link_quality *
643 message_neighbors->neigh_link_quality;
645 // if the link quality has changed by more than 10
648 rel_lq = walker->full_link_quality / saved_lq;
650 if (rel_lq > 1.1 || rel_lq < 0.9)
652 walker->saved_full_link_quality =
653 walker->full_link_quality;
655 changes_neighborhood = OLSR_TRUE;
656 changes_topology = OLSR_TRUE;
674 *Links a one-hop neighbor with a 2-hop neighbor.
676 *@param neighbor the 1-hop neighbor
677 *@param two_hop_neighbor the 2-hop neighbor
681 olsr_linking_this_2_entries(struct neighbor_entry *neighbor,struct neighbor_2_entry *two_hop_neighbor, float vtime)
683 struct neighbor_list_entry *list_of_1_neighbors;
684 struct neighbor_2_list_entry *list_of_2_neighbors;
686 list_of_1_neighbors = olsr_malloc(sizeof(struct neighbor_list_entry), "Link entries 1");
688 list_of_2_neighbors = olsr_malloc(sizeof(struct neighbor_2_list_entry), "Link entries 2");
690 list_of_1_neighbors->neighbor = neighbor;
692 #if defined USE_LINK_QUALITY
693 list_of_1_neighbors->full_link_quality = 0.0;
694 list_of_1_neighbors->saved_full_link_quality = 0.0;
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;
704 list_of_2_neighbors->neighbor_2 = two_hop_neighbor;
706 olsr_get_timestamp((olsr_u32_t) vtime*1000, &list_of_2_neighbors->neighbor_2_timer);
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;
714 /*increment the pointer counter*/
715 two_hop_neighbor->neighbor_2_pointer++;
724 *Check if a hello message states this node as a MPR.
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
730 *@return 1 if we are selected as MPR 0 if not
733 olsr_lookup_mpr_status(struct hello_message *message, struct interface *in_if)
736 struct hello_neighbor *neighbors;
738 neighbors=message->neighbors;
740 while(neighbors!=NULL)
742 //printf("(linkstatus)Checking %s ",olsr_ip_to_string(&neighbors->address));
743 //printf("against %s\n",olsr_ip_to_string(&main_addr));
746 if(olsr_cnf->ip_version == AF_INET)
749 if(COMP_IP(&neighbors->address, &in_if->ip_addr))
752 if((neighbors->link == SYM_LINK) && (neighbors->status == MPR_NEIGH))
761 if(COMP_IP(&neighbors->address, &in_if->int6_addr.sin6_addr))
764 if((neighbors->link == SYM_LINK) && (neighbors->status == MPR_NEIGH))
771 neighbors = neighbors->next;