3 * The olsr.org Optimized Link-State Routing daemon(olsrd)
4 * Copyright (c) 2004, Andreas Tonnesen(andreto@olsr.org)
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
11 * * Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * * Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in
15 * the documentation and/or other materials provided with the
17 * * Neither the name of olsr.org, olsrd nor the names of its
18 * contributors may be used to endorse or promote products derived
19 * from this software without specific prior written permission.
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
24 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
25 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
26 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
27 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
28 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
29 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
31 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
32 * POSSIBILITY OF SUCH DAMAGE.
34 * Visit http://www.olsr.org for more information.
36 * If you find this software useful feel free to make a donation
37 * to the project. For more information see the website or contact
38 * the copyright holders.
45 #include "two_hop_neighbor_table.h"
47 #include "neighbor_table.h"
48 #include "scheduler.h"
52 * Prototypes for internal functions
55 static uint16_t add_will_always_nodes(void);
57 static void olsr_optimize_mpr_set(void);
59 static void olsr_clear_mprs(void);
61 static void olsr_clear_two_hop_processed(void);
63 static struct neighbor_entry *olsr_find_maximum_covered(int);
65 static uint16_t olsr_calculate_two_hop_neighbors(void);
67 static int olsr_check_mpr_changes(void);
69 static int olsr_chosen_mpr(struct neighbor_entry *, uint16_t *);
71 static struct neighbor_2_list_entry *olsr_find_2_hop_neighbors_with_1_link(int);
74 * Prototypes for internal functions
78 *Find all 2 hop neighbors with 1 link
79 *connecting them to us trough neighbors
80 *with a given willingness.
82 *@param willingness the willigness of the neighbors
84 *@return a linked list of allocated neighbor_2_list_entry structures
86 static struct neighbor_2_list_entry *
87 olsr_find_2_hop_neighbors_with_1_link(int willingness)
91 struct neighbor_2_list_entry *two_hop_list_tmp = NULL;
92 struct neighbor_2_list_entry *two_hop_list = NULL;
93 struct neighbor_entry *dup_neighbor;
94 struct neighbor_2_entry *two_hop_neighbor = NULL;
96 for (idx = 0; idx < HASHSIZE; idx++) {
98 for (two_hop_neighbor = two_hop_neighbortable[idx].next; two_hop_neighbor != &two_hop_neighbortable[idx];
99 two_hop_neighbor = two_hop_neighbor->next) {
101 //two_hop_neighbor->neighbor_2_state=0;
102 //two_hop_neighbor->mpr_covered_count = 0;
104 dup_neighbor = olsr_lookup_neighbor_table(&two_hop_neighbor->neighbor_2_addr);
106 if ((dup_neighbor != NULL) && (dup_neighbor->status != NOT_SYM)) {
108 //OLSR_PRINTF(1, "(1)Skipping 2h neighbor %s - already 1hop\n", olsr_ip_to_string(&buf, &two_hop_neighbor->neighbor_2_addr));
113 if (two_hop_neighbor->neighbor_2_pointer == 1) {
114 if ((two_hop_neighbor->neighbor_2_nblist.next->neighbor->willingness == willingness)
115 && (two_hop_neighbor->neighbor_2_nblist.next->neighbor->status == SYM)) {
116 two_hop_list_tmp = olsr_malloc(sizeof(struct neighbor_2_list_entry), "MPR two hop list");
118 //OLSR_PRINTF(1, "ONE LINK ADDING %s\n", olsr_ip_to_string(&buf, &two_hop_neighbor->neighbor_2_addr));
120 /* Only queue one way here */
121 two_hop_list_tmp->neighbor_2 = two_hop_neighbor;
123 two_hop_list_tmp->next = two_hop_list;
125 two_hop_list = two_hop_list_tmp;
133 return (two_hop_list_tmp);
137 *This function processes the chosen MPRs and updates the counters
138 *used in calculations
141 olsr_chosen_mpr(struct neighbor_entry *one_hop_neighbor, uint16_t * two_hop_covered_count)
143 struct neighbor_list_entry *the_one_hop_list;
144 struct neighbor_2_list_entry *second_hop_entries;
145 struct neighbor_entry *dup_neighbor;
147 struct ipaddr_str buf;
148 count = *two_hop_covered_count;
150 OLSR_PRINTF(1, "Setting %s as MPR\n", olsr_ip_to_string(&buf, &one_hop_neighbor->neighbor_main_addr));
152 //printf("PRE COUNT: %d\n\n", count);
154 one_hop_neighbor->is_mpr = true; //NBS_MPR;
156 for (second_hop_entries = one_hop_neighbor->neighbor_2_list.next; second_hop_entries != &one_hop_neighbor->neighbor_2_list;
157 second_hop_entries = second_hop_entries->next) {
158 dup_neighbor = olsr_lookup_neighbor_table(&second_hop_entries->neighbor_2->neighbor_2_addr);
160 if ((dup_neighbor != NULL) && (dup_neighbor->status == SYM)) {
161 //OLSR_PRINTF(7, "(2)Skipping 2h neighbor %s - already 1hop\n", olsr_ip_to_string(&buf, &second_hop_entries->neighbor_2->neighbor_2_addr));
164 // if(!second_hop_entries->neighbor_2->neighbor_2_state)
165 //if(second_hop_entries->neighbor_2->mpr_covered_count < olsr_cnf->mpr_coverage)
168 Now the neighbor is covered by this mpr
170 second_hop_entries->neighbor_2->mpr_covered_count++;
171 the_one_hop_list = second_hop_entries->neighbor_2->neighbor_2_nblist.next;
173 //OLSR_PRINTF(1, "[%s](%x) has coverage %d\n", olsr_ip_to_string(&buf, &second_hop_entries->neighbor_2->neighbor_2_addr), second_hop_entries->neighbor_2, second_hop_entries->neighbor_2->mpr_covered_count);
175 if (second_hop_entries->neighbor_2->mpr_covered_count >= olsr_cnf->mpr_coverage)
178 while (the_one_hop_list != &second_hop_entries->neighbor_2->neighbor_2_nblist) {
180 if ((the_one_hop_list->neighbor->status == SYM)) {
181 if (second_hop_entries->neighbor_2->mpr_covered_count >= olsr_cnf->mpr_coverage) {
182 the_one_hop_list->neighbor->neighbor_2_nocov--;
185 the_one_hop_list = the_one_hop_list->next;
191 //printf("POST COUNT %d\n\n", count);
193 *two_hop_covered_count = count;
199 *Find the neighbor that covers the most 2 hop neighbors
200 *with a given willingness
202 *@param willingness the willingness of the neighbor
204 *@return a pointer to the neighbor_entry struct
206 static struct neighbor_entry *
207 olsr_find_maximum_covered(int willingness)
210 struct neighbor_entry *a_neighbor;
211 struct neighbor_entry *mpr_candidate = NULL;
215 OLSR_FOR_ALL_NBR_ENTRIES(a_neighbor) {
218 printf("[%s] nocov: %d mpr: %d will: %d max: %d\n\n", olsr_ip_to_string(&buf, &a_neighbor->neighbor_main_addr),
219 a_neighbor->neighbor_2_nocov, a_neighbor->is_mpr, a_neighbor->willingness, maximum);
222 if ((!a_neighbor->is_mpr) && (a_neighbor->willingness == willingness) && (maximum < a_neighbor->neighbor_2_nocov)) {
224 maximum = a_neighbor->neighbor_2_nocov;
225 mpr_candidate = a_neighbor;
228 OLSR_FOR_ALL_NBR_ENTRIES_END(a_neighbor);
230 return mpr_candidate;
234 *Remove all MPR registrations
237 olsr_clear_mprs(void)
239 struct neighbor_entry *a_neighbor;
240 struct neighbor_2_list_entry *two_hop_list;
242 OLSR_FOR_ALL_NBR_ENTRIES(a_neighbor) {
244 /* Clear MPR selection. */
245 if (a_neighbor->is_mpr) {
246 a_neighbor->was_mpr = true;
247 a_neighbor->is_mpr = false;
250 /* Clear two hop neighbors coverage count/ */
251 for (two_hop_list = a_neighbor->neighbor_2_list.next; two_hop_list != &a_neighbor->neighbor_2_list;
252 two_hop_list = two_hop_list->next) {
253 two_hop_list->neighbor_2->mpr_covered_count = 0;
257 OLSR_FOR_ALL_NBR_ENTRIES_END(a_neighbor);
261 *Check for changes in the MPR set
263 *@return 1 if changes occured 0 if not
266 olsr_check_mpr_changes(void)
268 struct neighbor_entry *a_neighbor;
273 OLSR_FOR_ALL_NBR_ENTRIES(a_neighbor) {
275 if (a_neighbor->was_mpr) {
276 a_neighbor->was_mpr = false;
278 if (!a_neighbor->is_mpr) {
283 OLSR_FOR_ALL_NBR_ENTRIES_END(a_neighbor);
289 *Clears out proccess registration
290 *on two hop neighbors
293 olsr_clear_two_hop_processed(void)
297 for (idx = 0; idx < HASHSIZE; idx++) {
298 struct neighbor_2_entry *neighbor_2;
299 for (neighbor_2 = two_hop_neighbortable[idx].next; neighbor_2 != &two_hop_neighbortable[idx]; neighbor_2 = neighbor_2->next) {
301 neighbor_2->processed = 0;
308 *This function calculates the number of two hop neighbors
311 olsr_calculate_two_hop_neighbors(void)
313 struct neighbor_entry *a_neighbor, *dup_neighbor;
314 struct neighbor_2_list_entry *twohop_neighbors;
316 uint16_t n_count = 0;
319 /* Clear 2 hop neighs */
320 olsr_clear_two_hop_processed();
322 OLSR_FOR_ALL_NBR_ENTRIES(a_neighbor) {
324 if (a_neighbor->status == NOT_SYM) {
325 a_neighbor->neighbor_2_nocov = count;
329 for (twohop_neighbors = a_neighbor->neighbor_2_list.next; twohop_neighbors != &a_neighbor->neighbor_2_list;
330 twohop_neighbors = twohop_neighbors->next) {
332 dup_neighbor = olsr_lookup_neighbor_table(&twohop_neighbors->neighbor_2->neighbor_2_addr);
334 if ((dup_neighbor == NULL) || (dup_neighbor->status != SYM)) {
336 if (!twohop_neighbors->neighbor_2->processed) {
338 twohop_neighbors->neighbor_2->processed = 1;
342 a_neighbor->neighbor_2_nocov = n_count;
344 /* Add the two hop count */
348 OLSR_FOR_ALL_NBR_ENTRIES_END(a_neighbor);
350 OLSR_PRINTF(3, "Two hop neighbors: %d\n", sum);
355 * Adds all nodes with willingness set to WILL_ALWAYS
358 add_will_always_nodes(void)
360 struct neighbor_entry *a_neighbor;
364 printf("\nAdding WILL ALWAYS nodes....\n");
367 OLSR_FOR_ALL_NBR_ENTRIES(a_neighbor) {
368 struct ipaddr_str buf;
369 if ((a_neighbor->status == NOT_SYM) || (a_neighbor->willingness != WILL_ALWAYS)) {
372 olsr_chosen_mpr(a_neighbor, &count);
374 OLSR_PRINTF(3, "Adding WILL_ALWAYS: %s\n", olsr_ip_to_string(&buf, &a_neighbor->neighbor_main_addr));
377 OLSR_FOR_ALL_NBR_ENTRIES_END(a_neighbor);
380 OLSR_PRINTF(1, "Count: %d\n", count);
386 *This function calculates the mpr neighbors
390 olsr_calculate_mpr(void)
392 uint16_t two_hop_covered_count;
393 uint16_t two_hop_count;
396 OLSR_PRINTF(3, "\n**RECALCULATING MPR**\n\n");
399 two_hop_count = olsr_calculate_two_hop_neighbors();
400 two_hop_covered_count = add_will_always_nodes();
403 *Calculate MPRs based on WILLINGNESS
406 for (i = WILL_ALWAYS - 1; i > WILL_NEVER; i--) {
407 struct neighbor_entry *mprs;
408 struct neighbor_2_list_entry *two_hop_list = olsr_find_2_hop_neighbors_with_1_link(i);
410 while (two_hop_list != NULL) {
411 struct neighbor_2_list_entry *tmp;
412 //printf("CHOSEN FROM 1 LINK\n");
413 if (!two_hop_list->neighbor_2->neighbor_2_nblist.next->neighbor->is_mpr)
414 olsr_chosen_mpr(two_hop_list->neighbor_2->neighbor_2_nblist.next->neighbor, &two_hop_covered_count);
416 two_hop_list = two_hop_list->next;;
420 if (two_hop_covered_count >= two_hop_count) {
424 //printf("two hop covered count: %d\n", two_hop_covered_count);
426 while ((mprs = olsr_find_maximum_covered(i)) != NULL) {
427 //printf("CHOSEN FROM MAXCOV\n");
428 olsr_chosen_mpr(mprs, &two_hop_covered_count);
430 if (two_hop_covered_count >= two_hop_count) {
439 increment the mpr sequence number
441 //neighbortable.neighbor_mpr_seq++;
443 /* Optimize selection */
444 olsr_optimize_mpr_set();
446 if (olsr_check_mpr_changes()) {
447 OLSR_PRINTF(3, "CHANGES IN MPR SET\n");
448 if (olsr_cnf->tc_redundancy > 0)
449 signal_link_changes(true);
455 *Optimize MPR set by removing all entries
456 *where all 2 hop neighbors actually is
457 *covered by enough MPRs already
458 *Described in RFC3626 section 8.3.1
464 olsr_optimize_mpr_set(void)
466 struct neighbor_entry *a_neighbor, *dup_neighbor;
467 struct neighbor_2_list_entry *two_hop_list;
471 printf("\n**MPR OPTIMIZING**\n\n");
474 for (i = WILL_NEVER + 1; i < WILL_ALWAYS; i++) {
476 OLSR_FOR_ALL_NBR_ENTRIES(a_neighbor) {
478 if (a_neighbor->willingness != i) {
482 if (a_neighbor->is_mpr) {
485 for (two_hop_list = a_neighbor->neighbor_2_list.next; two_hop_list != &a_neighbor->neighbor_2_list;
486 two_hop_list = two_hop_list->next) {
488 dup_neighbor = olsr_lookup_neighbor_table(&two_hop_list->neighbor_2->neighbor_2_addr);
490 if ((dup_neighbor != NULL) && (dup_neighbor->status != NOT_SYM)) {
493 //printf("\t[%s] coverage %d\n", olsr_ip_to_string(&buf, &two_hop_list->neighbor_2->neighbor_2_addr), two_hop_list->neighbor_2->mpr_covered_count);
494 /* Do not remove if we find a entry which need this MPR */
495 if (two_hop_list->neighbor_2->mpr_covered_count <= olsr_cnf->mpr_coverage) {
501 struct ipaddr_str buf;
502 OLSR_PRINTF(3, "MPR OPTIMIZE: removiong mpr %s\n\n", olsr_ip_to_string(&buf, &a_neighbor->neighbor_main_addr));
503 a_neighbor->is_mpr = false;
506 } OLSR_FOR_ALL_NBR_ENTRIES_END(a_neighbor);
512 olsr_print_mpr_set(void)
514 /* The whole function makes no sense without it. */
515 struct neighbor_entry *a_neighbor;
517 OLSR_PRINTF(1, "MPR SET: ");
519 OLSR_FOR_ALL_NBR_ENTRIES(a_neighbor) {
522 * Remove MPR settings
524 if (a_neighbor->is_mpr) {
525 struct ipaddr_str buf;
526 OLSR_PRINTF(1, "[%s] ", olsr_ip_to_string(&buf, &a_neighbor->neighbor_main_addr));
528 } OLSR_FOR_ALL_NBR_ENTRIES_END(a_neighbor);
530 OLSR_PRINTF(1, "\n");
537 * indent-tabs-mode: nil