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