plugin: dot_draw: readme: make it clear, that it only opens an IPv4-socket, so a...
[olsrd.git] / src / mpr.c
1
2 /*
3  * The olsr.org Optimized Link-State Routing daemon(olsrd)
4  * Copyright (c) 2004, Andreas Tonnesen(andreto@olsr.org)
5  * All rights reserved.
6  *
7  * Redistribution and use in source and binary forms, with or without
8  * modification, are permitted provided that the following conditions
9  * are met:
10  *
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
16  *   distribution.
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.
20  *
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.
33  *
34  * Visit http://www.olsr.org for more information.
35  *
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.
39  *
40  */
41
42 #include "ipcalc.h"
43 #include "defs.h"
44 #include "mpr.h"
45 #include "two_hop_neighbor_table.h"
46 #include "olsr.h"
47 #include "neighbor_table.h"
48 #include "scheduler.h"
49 #include "net_olsr.h"
50
51 /* Begin:
52  * Prototypes for internal functions
53  */
54
55 static uint16_t add_will_always_nodes(void);
56
57 static void olsr_optimize_mpr_set(void);
58
59 static void olsr_clear_mprs(void);
60
61 static void olsr_clear_two_hop_processed(void);
62
63 static struct neighbor_entry *olsr_find_maximum_covered(int);
64
65 static uint16_t olsr_calculate_two_hop_neighbors(void);
66
67 static int olsr_check_mpr_changes(void);
68
69 static int olsr_chosen_mpr(struct neighbor_entry *, uint16_t *);
70
71 static struct neighbor_2_list_entry *olsr_find_2_hop_neighbors_with_1_link(int);
72
73 /* End:
74  * Prototypes for internal functions
75  */
76
77 /**
78  *Find all 2 hop neighbors with 1 link
79  *connecting them to us trough neighbors
80  *with a given willingness.
81  *
82  *@param willingness the willigness of the neighbors
83  *
84  *@return a linked list of allocated neighbor_2_list_entry structures
85  */
86 static struct neighbor_2_list_entry *
87 olsr_find_2_hop_neighbors_with_1_link(int willingness)
88 {
89
90   uint8_t idx;
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;
95
96   for (idx = 0; idx < HASHSIZE; idx++) {
97
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) {
100
101       //two_hop_neighbor->neighbor_2_state=0;
102       //two_hop_neighbor->mpr_covered_count = 0;
103
104       dup_neighbor = olsr_lookup_neighbor_table(&two_hop_neighbor->neighbor_2_addr);
105
106       if ((dup_neighbor != NULL) && (dup_neighbor->status != NOT_SYM)) {
107
108         //OLSR_PRINTF(1, "(1)Skipping 2h neighbor %s - already 1hop\n", olsr_ip_to_string(&buf, &two_hop_neighbor->neighbor_2_addr));
109
110         continue;
111       }
112
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");
117
118           //OLSR_PRINTF(1, "ONE LINK ADDING %s\n", olsr_ip_to_string(&buf, &two_hop_neighbor->neighbor_2_addr));
119
120           /* Only queue one way here */
121           two_hop_list_tmp->neighbor_2 = two_hop_neighbor;
122
123           two_hop_list_tmp->next = two_hop_list;
124
125           two_hop_list = two_hop_list_tmp;
126         }
127       }
128
129     }
130
131   }
132
133   return (two_hop_list_tmp);
134 }
135
136 /**
137  *This function processes the chosen MPRs and updates the counters
138  *used in calculations
139  */
140 static int
141 olsr_chosen_mpr(struct neighbor_entry *one_hop_neighbor, uint16_t * two_hop_covered_count)
142 {
143   struct neighbor_list_entry *the_one_hop_list;
144   struct neighbor_2_list_entry *second_hop_entries;
145   struct neighbor_entry *dup_neighbor;
146   uint16_t count;
147   struct ipaddr_str buf;
148   count = *two_hop_covered_count;
149
150   OLSR_PRINTF(1, "Setting %s as MPR\n", olsr_ip_to_string(&buf, &one_hop_neighbor->neighbor_main_addr));
151
152   //printf("PRE COUNT: %d\n\n", count);
153
154   one_hop_neighbor->is_mpr = true;      //NBS_MPR;
155
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);
159
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));
162       continue;
163     }
164     //      if(!second_hop_entries->neighbor_2->neighbor_2_state)
165     //if(second_hop_entries->neighbor_2->mpr_covered_count < olsr_cnf->mpr_coverage)
166     //{
167     /*
168        Now the neighbor is covered by this mpr
169      */
170     second_hop_entries->neighbor_2->mpr_covered_count++;
171     the_one_hop_list = second_hop_entries->neighbor_2->neighbor_2_nblist.next;
172
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);
174
175     if (second_hop_entries->neighbor_2->mpr_covered_count >= olsr_cnf->mpr_coverage)
176       count++;
177
178     while (the_one_hop_list != &second_hop_entries->neighbor_2->neighbor_2_nblist) {
179
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--;
183         }
184       }
185       the_one_hop_list = the_one_hop_list->next;
186     }
187
188     //}
189   }
190
191   //printf("POST COUNT %d\n\n", count);
192
193   *two_hop_covered_count = count;
194   return count;
195
196 }
197
198 /**
199  *Find the neighbor that covers the most 2 hop neighbors
200  *with a given willingness
201  *
202  *@param willingness the willingness of the neighbor
203  *
204  *@return a pointer to the neighbor_entry struct
205  */
206 static struct neighbor_entry *
207 olsr_find_maximum_covered(int willingness)
208 {
209   uint16_t maximum;
210   struct neighbor_entry *a_neighbor;
211   struct neighbor_entry *mpr_candidate = NULL;
212
213   maximum = 0;
214
215   OLSR_FOR_ALL_NBR_ENTRIES(a_neighbor) {
216
217 #if 0
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);
220 #endif /* 0 */
221
222     if ((!a_neighbor->is_mpr) && (a_neighbor->willingness == willingness) && (maximum < a_neighbor->neighbor_2_nocov)) {
223
224       maximum = a_neighbor->neighbor_2_nocov;
225       mpr_candidate = a_neighbor;
226     }
227   }
228   OLSR_FOR_ALL_NBR_ENTRIES_END(a_neighbor);
229
230   return mpr_candidate;
231 }
232
233 /**
234  *Remove all MPR registrations
235  */
236 static void
237 olsr_clear_mprs(void)
238 {
239   struct neighbor_entry *a_neighbor;
240   struct neighbor_2_list_entry *two_hop_list;
241
242   OLSR_FOR_ALL_NBR_ENTRIES(a_neighbor) {
243
244     /* Clear MPR selection. */
245     if (a_neighbor->is_mpr) {
246       a_neighbor->was_mpr = true;
247       a_neighbor->is_mpr = false;
248     }
249
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;
254     }
255
256   }
257   OLSR_FOR_ALL_NBR_ENTRIES_END(a_neighbor);
258 }
259
260 /**
261  *Check for changes in the MPR set
262  *
263  *@return 1 if changes occured 0 if not
264  */
265 static int
266 olsr_check_mpr_changes(void)
267 {
268   struct neighbor_entry *a_neighbor;
269   int retval;
270
271   retval = 0;
272
273   OLSR_FOR_ALL_NBR_ENTRIES(a_neighbor) {
274
275     if (a_neighbor->was_mpr) {
276       a_neighbor->was_mpr = false;
277
278       if (!a_neighbor->is_mpr) {
279         retval = 1;
280       }
281     }
282   }
283   OLSR_FOR_ALL_NBR_ENTRIES_END(a_neighbor);
284
285   return retval;
286 }
287
288 /**
289  *Clears out proccess registration
290  *on two hop neighbors
291  */
292 static void
293 olsr_clear_two_hop_processed(void)
294 {
295   int idx;
296
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) {
300       /* Clear */
301       neighbor_2->processed = 0;
302     }
303   }
304
305 }
306
307 /**
308  *This function calculates the number of two hop neighbors
309  */
310 static uint16_t
311 olsr_calculate_two_hop_neighbors(void)
312 {
313   struct neighbor_entry *a_neighbor, *dup_neighbor;
314   struct neighbor_2_list_entry *twohop_neighbors;
315   uint16_t count = 0;
316   uint16_t n_count = 0;
317   uint16_t sum = 0;
318
319   /* Clear 2 hop neighs */
320   olsr_clear_two_hop_processed();
321
322   OLSR_FOR_ALL_NBR_ENTRIES(a_neighbor) {
323
324     if (a_neighbor->status == NOT_SYM) {
325       a_neighbor->neighbor_2_nocov = count;
326       continue;
327     }
328
329     for (twohop_neighbors = a_neighbor->neighbor_2_list.next; twohop_neighbors != &a_neighbor->neighbor_2_list;
330          twohop_neighbors = twohop_neighbors->next) {
331
332       dup_neighbor = olsr_lookup_neighbor_table(&twohop_neighbors->neighbor_2->neighbor_2_addr);
333
334       if ((dup_neighbor == NULL) || (dup_neighbor->status != SYM)) {
335         n_count++;
336         if (!twohop_neighbors->neighbor_2->processed) {
337           count++;
338           twohop_neighbors->neighbor_2->processed = 1;
339         }
340       }
341     }
342     a_neighbor->neighbor_2_nocov = n_count;
343
344     /* Add the two hop count */
345     sum += count;
346
347   }
348   OLSR_FOR_ALL_NBR_ENTRIES_END(a_neighbor);
349
350   OLSR_PRINTF(3, "Two hop neighbors: %d\n", sum);
351   return sum;
352 }
353
354 /**
355  * Adds all nodes with willingness set to WILL_ALWAYS
356  */
357 static uint16_t
358 add_will_always_nodes(void)
359 {
360   struct neighbor_entry *a_neighbor;
361   uint16_t count = 0;
362
363 #if 0
364   printf("\nAdding WILL ALWAYS nodes....\n");
365 #endif /* 0 */
366
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)) {
370       continue;
371     }
372     olsr_chosen_mpr(a_neighbor, &count);
373
374     OLSR_PRINTF(3, "Adding WILL_ALWAYS: %s\n", olsr_ip_to_string(&buf, &a_neighbor->neighbor_main_addr));
375
376   }
377   OLSR_FOR_ALL_NBR_ENTRIES_END(a_neighbor);
378
379 #if 0
380   OLSR_PRINTF(1, "Count: %d\n", count);
381 #endif /* 0 */
382   return count;
383 }
384
385 /**
386  *This function calculates the mpr neighbors
387  *@return nada
388  */
389 void
390 olsr_calculate_mpr(void)
391 {
392   uint16_t two_hop_covered_count;
393   uint16_t two_hop_count;
394   int i;
395
396   OLSR_PRINTF(3, "\n**RECALCULATING MPR**\n\n");
397
398   olsr_clear_mprs();
399   two_hop_count = olsr_calculate_two_hop_neighbors();
400   two_hop_covered_count = add_will_always_nodes();
401
402   /*
403    *Calculate MPRs based on WILLINGNESS
404    */
405
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);
409
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);
415       tmp = two_hop_list;
416       two_hop_list = two_hop_list->next;;
417       free(tmp);
418     }
419
420     if (two_hop_covered_count >= two_hop_count) {
421       i = WILL_NEVER;
422       break;
423     }
424     //printf("two hop covered count: %d\n", two_hop_covered_count);
425
426     while ((mprs = olsr_find_maximum_covered(i)) != NULL) {
427       //printf("CHOSEN FROM MAXCOV\n");
428       olsr_chosen_mpr(mprs, &two_hop_covered_count);
429
430       if (two_hop_covered_count >= two_hop_count) {
431         i = WILL_NEVER;
432         break;
433       }
434
435     }
436   }
437
438   /*
439      increment the mpr sequence number
440    */
441   //neighbortable.neighbor_mpr_seq++;
442
443   /* Optimize selection */
444   olsr_optimize_mpr_set();
445
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);
450   }
451
452 }
453
454 /**
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
459  *point 5
460  *
461  *@return nada
462  */
463 static void
464 olsr_optimize_mpr_set(void)
465 {
466   struct neighbor_entry *a_neighbor, *dup_neighbor;
467   struct neighbor_2_list_entry *two_hop_list;
468   int i, removeit;
469
470 #if 0
471   printf("\n**MPR OPTIMIZING**\n\n");
472 #endif /* 0 */
473
474   for (i = WILL_NEVER + 1; i < WILL_ALWAYS; i++) {
475
476     OLSR_FOR_ALL_NBR_ENTRIES(a_neighbor) {
477
478       if (a_neighbor->willingness != i) {
479         continue;
480       }
481
482       if (a_neighbor->is_mpr) {
483         removeit = 1;
484
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) {
487
488           dup_neighbor = olsr_lookup_neighbor_table(&two_hop_list->neighbor_2->neighbor_2_addr);
489
490           if ((dup_neighbor != NULL) && (dup_neighbor->status != NOT_SYM)) {
491             continue;
492           }
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) {
496             removeit = 0;
497           }
498         }
499
500         if (removeit) {
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;
504         }
505       }
506     } OLSR_FOR_ALL_NBR_ENTRIES_END(a_neighbor);
507   }
508 }
509
510 #ifndef NODEBUG
511 void
512 olsr_print_mpr_set(void)
513 {
514   /* The whole function makes no sense without it. */
515   struct neighbor_entry *a_neighbor;
516
517   OLSR_PRINTF(1, "MPR SET: ");
518
519   OLSR_FOR_ALL_NBR_ENTRIES(a_neighbor) {
520
521     /*
522      * Remove MPR settings
523      */
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));
527     }
528   } OLSR_FOR_ALL_NBR_ENTRIES_END(a_neighbor);
529
530   OLSR_PRINTF(1, "\n");
531 }
532 #endif /* NODEBUG */
533
534 /*
535  * Local Variables:
536  * c-basic-offset: 2
537  * indent-tabs-mode: nil
538  * End:
539  */