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.
41 #include "process_package.h"
44 #include "lq_packet.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"
54 #include "scheduler.h"
59 static void process_message_neighbors(struct neighbor_entry *,
60 const struct hello_message *);
62 static void linking_this_2_entries(struct neighbor_entry *,
63 struct neighbor_2_entry *, float);
65 static olsr_bool lookup_mpr_status(const struct hello_message *,
66 const struct interface *);
70 *Processes an list of neighbors from an incoming HELLO message.
71 *@param neighbor the neighbor who sent the message.
72 *@param message the HELLO message
76 process_message_neighbors(struct neighbor_entry *neighbor, const struct hello_message *message)
78 struct hello_neighbor *message_neighbors;
80 for(message_neighbors = message->neighbors;
81 message_neighbors != NULL;
82 message_neighbors = message_neighbors->next)
84 #if !defined(NODEBUG) && defined(DEBUG)
85 struct ipaddr_str buf;
87 union olsr_ip_addr *neigh_addr;
88 struct neighbor_2_entry *two_hop_neighbor;
92 *so that we don't add ourselves to the
96 if(if_ifwithaddr(&message_neighbors->address) != NULL)
99 /* Get the main address */
100 neigh_addr = mid_lookup_main_addr(&message_neighbors->address);
102 if (neigh_addr != NULL) {
103 message_neighbors->address = *neigh_addr;
106 if(((message_neighbors->status == SYM_NEIGH) ||
107 (message_neighbors->status == MPR_NEIGH)))
109 struct neighbor_2_list_entry *two_hop_neighbor_yet =
110 olsr_lookup_my_neighbors(neighbor, &message_neighbors->address);
112 OLSR_PRINTF(7, "\tProcessing %s\n", olsr_ip_to_string(&buf, &message_neighbors->address));
114 if (two_hop_neighbor_yet != NULL)
116 /* Updating the holding time for this neighbor */
117 two_hop_neighbor_yet->neighbor_2_timer = GET_TIMESTAMP(message->vtime*1000);
118 two_hop_neighbor = two_hop_neighbor_yet->neighbor_2;
120 // For link quality OLSR, reset the path link quality here.
121 // The path link quality will be calculated in the second pass, below.
122 // Keep the saved_path_link_quality for reference.
124 if (olsr_cnf->lq_level > 0)
126 // loop through the one-hop neighbors that see this
127 // 'two_hop_neighbor'
129 struct neighbor_list_entry *walker;
131 for (walker = two_hop_neighbor->neighbor_2_nblist.next;
132 walker != &two_hop_neighbor->neighbor_2_nblist;
133 walker = walker->next)
135 // have we found the one-hop neighbor that sent the
136 // HELLO message that we're current processing?
138 if (walker->neighbor == neighbor)
140 walker->path_link_quality = 0.0;
148 olsr_lookup_two_hop_neighbor_table(&message_neighbors->address);
149 if (two_hop_neighbor == NULL)
153 "Adding 2 hop neighbor %s\n\n",
154 olsr_ip_to_string(&buf, &message_neighbors->address));
156 changes_neighborhood = OLSR_TRUE;
157 changes_topology = OLSR_TRUE;
160 olsr_malloc(sizeof(struct neighbor_2_entry), "Process HELLO");
162 two_hop_neighbor->neighbor_2_nblist.next =
163 &two_hop_neighbor->neighbor_2_nblist;
165 two_hop_neighbor->neighbor_2_nblist.prev =
166 &two_hop_neighbor->neighbor_2_nblist;
168 two_hop_neighbor->neighbor_2_pointer = 0;
170 two_hop_neighbor->neighbor_2_addr = message_neighbors->address;
172 olsr_insert_two_hop_neighbor_table(two_hop_neighbor);
174 linking_this_2_entries(neighbor, two_hop_neighbor, message->vtime);
179 linking to this two_hop_neighbor entry
181 changes_neighborhood = OLSR_TRUE;
182 changes_topology = OLSR_TRUE;
184 linking_this_2_entries(neighbor, two_hop_neighbor, message->vtime);
190 // Separate, second and third pass for link quality OLSR
192 if (olsr_cnf->lq_level > 0)
194 struct link_entry *lnk =
195 get_best_link_to_neighbor(&neighbor->neighbor_main_addr);
200 // Second pass for link quality OLSR: calculate the best 2-hop
201 // path costs to all the 2-hop neighbors indicated in the
202 // HELLO message. Since the same 2-hop neighbor may be listed
203 // more than once in the same HELLO message (each at a possibly
204 // different quality) we want to select only the best one, not just
205 // the last one listed in the HELLO message.
207 for(message_neighbors = message->neighbors;
208 message_neighbors != NULL;
209 message_neighbors = message_neighbors->next)
211 if(if_ifwithaddr(&message_neighbors->address) != NULL)
214 if(((message_neighbors->status == SYM_NEIGH) ||
215 (message_neighbors->status == MPR_NEIGH)))
217 struct neighbor_list_entry *walker;
218 struct neighbor_2_entry *two_hop_neighbor;
219 struct neighbor_2_list_entry *two_hop_neighbor_yet =
220 olsr_lookup_my_neighbors(neighbor, &message_neighbors->address);
222 if(!two_hop_neighbor_yet)
225 two_hop_neighbor = two_hop_neighbor_yet->neighbor_2;
227 // loop through the one-hop neighbors that see this
228 // 'two_hop_neighbor'
230 for (walker = two_hop_neighbor->neighbor_2_nblist.next;
231 walker != &two_hop_neighbor->neighbor_2_nblist;
232 walker = walker->next)
234 // have we found the one-hop neighbor that sent the
235 // HELLO message that we're current processing?
237 if (walker->neighbor == neighbor)
239 double new_second_hop_link_quality, new_path_link_quality;
241 // path link quality = link quality between us
242 // and our one-hop neighbor x link quality between
243 // our one-hop neighbor and the two-hop neighbor
245 // let's compare this to ETX:
247 // 1 / LQ1 + 1 / LQ2 < 1 / LQ3 + 1 / LQ4 <=>
248 // LQ1 * LQ2 > LQ3 * LQ4
250 // so comparing path link quality values with ">" is
251 // equivalent to comparing ETX values with "<"
253 // the link quality between the 1-hop neighbour and the
256 new_second_hop_link_quality =
257 message_neighbors->link_quality *
258 message_neighbors->neigh_link_quality;
260 // the total quality for the route
261 // "us --- 1-hop --- 2-hop"
263 new_path_link_quality =
264 new_second_hop_link_quality *
265 lnk->loss_link_quality * lnk->neigh_link_quality;
267 // Only copy the link quality if it is better than what we have
268 // for this 2-hop neighbor
269 if (new_path_link_quality > walker->path_link_quality)
271 walker->second_hop_link_quality = new_second_hop_link_quality;
272 walker->path_link_quality = new_path_link_quality;
279 // Third pass for link quality OLSR: check if the 2-hop path qualities have
280 // actually changed. If so, signal this through the 'changes_neighborhood'
281 // and 'changes_topology' booleans. Keep a 'saved_path_link_quality' for
283 for(message_neighbors = message->neighbors;
284 message_neighbors != NULL;
285 message_neighbors = message_neighbors->next)
287 if(if_ifwithaddr(&message_neighbors->address) != NULL)
290 if(((message_neighbors->status == SYM_NEIGH) ||
291 (message_neighbors->status == MPR_NEIGH)))
293 struct neighbor_list_entry *walker;
294 struct neighbor_2_entry *two_hop_neighbor;
295 struct neighbor_2_list_entry *two_hop_neighbor_yet =
296 olsr_lookup_my_neighbors(neighbor, &message_neighbors->address);
298 if(!two_hop_neighbor_yet)
301 two_hop_neighbor = two_hop_neighbor_yet->neighbor_2;
303 // loop through the one-hop neighbors that see this
304 // 'two_hop_neighbor'
306 for (walker = two_hop_neighbor->neighbor_2_nblist.next;
307 walker != &two_hop_neighbor->neighbor_2_nblist;
308 walker = walker->next)
310 // have we found the one-hop neighbor that sent the
311 // HELLO message that we're current processing?
313 if (walker->neighbor == neighbor)
315 double saved_lq, rel_lq;
317 // saved previous total link quality
319 saved_lq = walker->saved_path_link_quality;
324 // if the link cost has changed by more than 10
327 rel_lq = walker->path_link_quality / saved_lq;
329 if (rel_lq > 1.1 || rel_lq < 0.9)
331 walker->saved_path_link_quality =
332 walker->path_link_quality;
334 if (olsr_cnf->lq_dlimit > 0)
336 changes_neighborhood = OLSR_TRUE;
337 changes_topology = OLSR_TRUE;
341 OLSR_PRINTF(3, "Skipping Dijkstra (3)\n");
351 *Links a one-hop neighbor with a 2-hop neighbor.
353 *@param neighbor the 1-hop neighbor
354 *@param two_hop_neighbor the 2-hop neighbor
358 linking_this_2_entries(struct neighbor_entry *neighbor, struct neighbor_2_entry *two_hop_neighbor, float vtime)
360 struct neighbor_list_entry *list_of_1_neighbors = olsr_malloc(sizeof(struct neighbor_list_entry), "Link entries 1");
361 struct neighbor_2_list_entry *list_of_2_neighbors = olsr_malloc(sizeof(struct neighbor_2_list_entry), "Link entries 2");
363 list_of_1_neighbors->neighbor = neighbor;
365 list_of_1_neighbors->path_link_quality = 0.0;
366 list_of_1_neighbors->saved_path_link_quality = 0.0;
367 list_of_1_neighbors->second_hop_link_quality = 0.0;
370 two_hop_neighbor->neighbor_2_nblist.next->prev = list_of_1_neighbors;
371 list_of_1_neighbors->next = two_hop_neighbor->neighbor_2_nblist.next;
373 two_hop_neighbor->neighbor_2_nblist.next = list_of_1_neighbors;
374 list_of_1_neighbors->prev = &two_hop_neighbor->neighbor_2_nblist;
375 list_of_2_neighbors->neighbor_2 = two_hop_neighbor;
377 list_of_2_neighbors->neighbor_2_timer = GET_TIMESTAMP(vtime*1000);
380 neighbor->neighbor_2_list.next->prev = list_of_2_neighbors;
381 list_of_2_neighbors->next = neighbor->neighbor_2_list.next;
382 neighbor->neighbor_2_list.next = list_of_2_neighbors;
383 list_of_2_neighbors->prev = &neighbor->neighbor_2_list;
385 /*increment the pointer counter*/
386 two_hop_neighbor->neighbor_2_pointer++;
390 * Check if a hello message states this node as a MPR.
392 * @param message the message to check
393 * @param n_link the buffer to put the link status in
395 *@return 1 if we are selected as MPR 0 if not
398 lookup_mpr_status(const struct hello_message *message,
399 const struct interface *in_if)
401 struct hello_neighbor *neighbors;
403 for (neighbors = message->neighbors; neighbors; neighbors = neighbors->next) {
404 if (olsr_cnf->ip_version == AF_INET
405 ? ip4equal(&neighbors->address.v4, &in_if->ip_addr.v4)
406 : ip6equal(&neighbors->address.v6, &in_if->int6_addr.sin6_addr)) {
408 if (neighbors->link == SYM_LINK && neighbors->status == MPR_NEIGH) {
418 static int deserialize_hello(struct hello_message *hello, const void *ser) {
419 const unsigned char *limit;
423 const unsigned char *curr = ser;
424 pkt_get_u8(&curr, &type);
425 if (type != HELLO_MESSAGE && type != LQ_HELLO_MESSAGE) {
426 /* No need to do anything more */
429 pkt_get_double(&curr, &hello->vtime);
430 pkt_get_u16(&curr, &size);
431 pkt_get_ipaddress(&curr, &hello->source_addr);
433 pkt_get_u8(&curr, &hello->ttl);
434 pkt_get_u8(&curr, &hello->hop_count);
435 pkt_get_u16(&curr, &hello->packet_seq_number);
436 pkt_ignore_u16(&curr);
438 pkt_get_double(&curr, &hello->htime);
439 pkt_get_u8(&curr, &hello->willingness);
441 hello->neighbors = NULL;
442 limit = ((const unsigned char *)ser) + size;
443 while (curr < limit) {
444 const struct lq_hello_info_header *info_head = (const struct lq_hello_info_header *)curr;
445 const unsigned char *limit2 = curr + ntohs(info_head->size);
447 curr = (const unsigned char *)(info_head + 1);
448 while (curr < limit2) {
449 struct hello_neighbor *neigh = olsr_malloc(sizeof(struct hello_neighbor), "HELLO deserialization");
450 pkt_get_ipaddress(&curr, &neigh->address);
452 if (type == LQ_HELLO_MESSAGE) {
453 pkt_get_lq(&curr, &neigh->link_quality);
454 pkt_get_lq(&curr, &neigh->neigh_link_quality);
455 pkt_ignore_u16(&curr);
457 neigh->link = EXTRACT_LINK(info_head->link_code);
458 neigh->status = EXTRACT_STATUS(info_head->link_code);
460 neigh->next = hello->neighbors;
461 hello->neighbors = neigh;
467 void olsr_input_hello(union olsr_message *ser, struct interface *inif, union olsr_ip_addr *from) {
468 struct hello_message hello;
473 if (deserialize_hello(&hello, ser) != 0) {
476 olsr_hello_tap(&hello, inif, from);
480 *Initializing the parser functions we are using
483 olsr_init_package_process(void)
485 if (olsr_cnf->lq_level == 0)
487 olsr_parser_add_function(&olsr_input_hello, HELLO_MESSAGE, 1);
488 olsr_parser_add_function(&olsr_input_tc, TC_MESSAGE, 1);
492 olsr_parser_add_function(&olsr_input_hello, LQ_HELLO_MESSAGE, 1);
493 olsr_parser_add_function(&olsr_input_tc, LQ_TC_MESSAGE, 1);
496 olsr_parser_add_function(&olsr_process_received_mid, MID_MESSAGE, 1);
497 olsr_parser_add_function(&olsr_process_received_hna, HNA_MESSAGE, 1);
501 olsr_hello_tap(struct hello_message *message,
502 struct interface *in_if,
503 const union olsr_ip_addr *from_addr)
505 struct neighbor_entry *neighbor;
510 struct link_entry *lnk = update_link_entry(&in_if->ip_addr, from_addr, message, in_if);
512 if (olsr_cnf->lq_level > 0)
516 struct hello_neighbor *walker;
517 // just in case our neighbor has changed its HELLO interval
518 olsr_update_packet_loss_hello_int(lnk, message->htime);
520 // find the input interface in the list of neighbor interfaces
522 for (walker = message->neighbors; walker != NULL; walker = walker->next)
523 if (ipequal(&walker->address, &in_if->ip_addr))
526 // the current reference link quality
528 saved_lq = lnk->saved_neigh_link_quality;
533 // memorize our neighbour's idea of the link quality, so that we
534 // know the link quality in both directions
537 lnk->neigh_link_quality = walker->link_quality;
540 lnk->neigh_link_quality = 0.0;
542 // if the link quality has changed by more than 10 percent,
543 // print the new link quality table
545 rel_lq = lnk->neigh_link_quality / saved_lq;
547 if (rel_lq > 1.1 || rel_lq < 0.9)
549 lnk->saved_neigh_link_quality = lnk->neigh_link_quality;
551 if (olsr_cnf->lq_dlimit > 0)
553 changes_neighborhood = OLSR_TRUE;
554 changes_topology = OLSR_TRUE;
558 OLSR_PRINTF(3, "Skipping Dijkstra (2)\n");
562 // XXX - we should check whether we actually
563 // announce this neighbour
565 signal_link_changes(OLSR_TRUE);
569 neighbor = lnk->neighbor;
574 if(olsr_cnf->use_hysteresis)
576 /* Update HELLO timeout */
577 //printf("MESSAGE HTIME: %f\n", message->htime);
578 olsr_update_hysteresis_hello(lnk, message->htime);
581 /* Check if we are chosen as MPR */
582 if(lookup_mpr_status(message, in_if))
583 /* source_addr is always the main addr of a node! */
584 olsr_update_mprs_set(&message->source_addr, message->vtime);
588 /* Check willingness */
589 if(neighbor->willingness != message->willingness)
592 struct ipaddr_str buf;
594 OLSR_PRINTF(1, "Willingness for %s changed from %d to %d - UPDATING\n",
595 olsr_ip_to_string(&buf, &neighbor->neighbor_main_addr),
596 neighbor->willingness,
597 message->willingness);
599 *If willingness changed - recalculate
601 neighbor->willingness = message->willingness;
602 changes_neighborhood = OLSR_TRUE;
603 changes_topology = OLSR_TRUE;
607 /* Don't register neighbors of neighbors that announces WILL_NEVER */
608 if(neighbor->willingness != WILL_NEVER)
609 process_message_neighbors(neighbor, message);
611 /* Process changes immedeatly in case of MPR updates */
612 olsr_process_changes();
614 olsr_free_hello_packet(message);
620 *Process a received(and parsed) MID message
621 *For every address check if there is a topology node
622 *registered with it and update its addresses.
624 *@param m the OLSR message received.
625 *@return 1 on success
629 olsr_process_received_mid(union olsr_message *m,
630 struct interface *in_if,
631 union olsr_ip_addr *from_addr)
633 #if !defined(NODEBUG) && defined(DEBUG)
634 struct ipaddr_str buf;
636 struct mid_alias *tmp_adr;
637 struct mid_message message;
639 mid_chgestruct(&message, m);
641 if (!olsr_validate_address(&message.mid_origaddr)) {
642 olsr_free_mid_packet(&message);
646 if (olsr_check_dup_table_proc(&message.mid_origaddr,
647 message.mid_seqno)) {
650 OLSR_PRINTF(5, "Processing MID from %s...\n", olsr_ip_to_string(&buf, &message.mid_origaddr));
652 tmp_adr = message.mid_addr;
655 * If the sender interface (NB: not originator) of this message
656 * is not in the symmetric 1-hop neighborhood of this node, the
657 * message MUST be discarded.
660 if(check_neighbor_link(from_addr) != SYM_LINK) {
662 struct ipaddr_str buf;
664 OLSR_PRINTF(2, "Received MID from NON SYM neighbor %s\n", olsr_ip_to_string(&buf, from_addr));
665 olsr_free_mid_packet(&message);
669 /* Update the timeout of the MID */
670 olsr_update_mid_table(&message.mid_origaddr, (float)message.vtime);
673 if (!mid_lookup_main_addr(&tmp_adr->alias_addr)){
675 struct ipaddr_str buf;
677 OLSR_PRINTF(1, "MID new: (%s, ", olsr_ip_to_string(&buf, &message.mid_origaddr));
678 OLSR_PRINTF(1, "%s)\n", olsr_ip_to_string(&buf, &tmp_adr->alias_addr));
679 insert_mid_alias(&message.mid_origaddr, &tmp_adr->alias_addr, (float)message.vtime);
681 tmp_adr = tmp_adr->next;
684 olsr_prune_aliases(&message.mid_origaddr, message.mid_addr);
687 olsr_forward_message(m,
688 &message.mid_origaddr,
692 olsr_free_mid_packet(&message);
697 *Process incoming HNA message.
698 *Forwards the message if that is to be done.
700 *@param m the incoming OLSR message
702 *@return 1 on success
706 olsr_process_received_hna(union olsr_message *m,
707 struct interface *in_if,
708 union olsr_ip_addr *from_addr)
711 olsr_u8_t olsr_msgtype;
713 olsr_u16_t olsr_msgsize;
714 union olsr_ip_addr originator;
715 //olsr_u8_t ttl; unused
717 olsr_u16_t packet_seq_number;
720 const olsr_u8_t *curr, *curr_end;
723 OLSR_PRINTF(5, "Processing HNA\n");
726 /* Check if everyting is ok */
730 curr = (const olsr_u8_t *)m;
733 pkt_get_u8(&curr, &olsr_msgtype);
734 if (olsr_msgtype != HNA_MESSAGE) {
735 OLSR_PRINTF(0, "not a HNA message!\n");
739 pkt_get_double(&curr, &vtime);
742 pkt_get_u16(&curr, &olsr_msgsize);
743 hnasize = olsr_msgsize - (olsr_cnf->ip_version == AF_INET ? offsetof(struct olsrmsg, message) : offsetof(struct olsrmsg6, message));
745 OLSR_PRINTF(0, "message size %d too small (at least %lu)!\n", olsr_msgsize, (unsigned long)(olsr_cnf->ip_version == AF_INET ? offsetof(struct olsrmsg, message) : offsetof(struct olsrmsg6, message)));
748 if ((hnasize % (2 * olsr_cnf->ipsize)) != 0) {
749 OLSR_PRINTF(0, "Illegal message size %d!\n", olsr_msgsize);
752 curr_end = (const olsr_u8_t *)m + olsr_msgsize;
754 /* validate originator */
755 pkt_get_ipaddress(&curr, &originator);
756 //printf("HNA from %s\n\n", olsr_ip_to_string(&buf, &originator));
759 pkt_ignore_u8(&curr);
762 pkt_get_u8(&curr, &hop_count);
765 pkt_get_u16(&curr, &packet_seq_number);
767 if (olsr_check_dup_table_proc(&originator, packet_seq_number)) {
769 * If the sender interface (NB: not originator) of this message
770 * is not in the symmetric 1-hop neighborhood of this node, the
771 * message MUST be discarded.
773 if (check_neighbor_link(from_addr) != SYM_LINK) {
775 struct ipaddr_str buf;
777 OLSR_PRINTF(2, "Received HNA from NON SYM neighbor %s\n", olsr_ip_to_string(&buf, from_addr));
781 while (curr < curr_end) {
782 union olsr_ip_addr net;
784 struct ip_prefix_list *entry;
786 pkt_get_ipaddress(&curr, &net);
787 pkt_get_prefixlen(&curr, &prefixlen);
788 entry = ip_prefix_list_find(olsr_cnf->hna_entries, &net, prefixlen);
790 /* only update if it's not from us */
791 olsr_update_hna_entry(&originator, &net, prefixlen, vtime);
794 /* Don't add an HNA entry that we are advertising ourselves. */
795 if (!ip_prefix_list_find(olsr_cnf->hna_entries, &hna_tmp->net, hna_tmp->prefixlen)) {
796 olsr_update_hna_entry(&message.originator, &hna_tmp->net, hna_tmp->prefixlen, message.vtime);
801 olsr_forward_message(m,