remove CVS ID markers
[olsrd.git] / src / mpr.c
1 /*
2  * The olsr.org Optimized Link-State Routing daemon(olsrd)
3  * Copyright (c) 2004, Andreas T√łnnesen(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 /* Begin:
51  * Prototypes for internal functions 
52  */
53
54 static olsr_u16_t
55 add_will_always_nodes(void);
56
57 static void
58 olsr_optimize_mpr_set(void);
59
60 static void
61 olsr_clear_mprs(void);
62
63 static void
64 olsr_clear_two_hop_processed(void);
65
66 static struct neighbor_entry *
67 olsr_find_maximum_covered(int);
68
69 static olsr_u16_t
70 olsr_calculate_two_hop_neighbors(void);
71
72 static int
73 olsr_check_mpr_changes(void);
74
75 static int
76 olsr_chosen_mpr(struct neighbor_entry *, olsr_u16_t *);
77
78 static struct neighbor_2_list_entry *
79 olsr_find_2_hop_neighbors_with_1_link(int);
80
81
82 /* End:
83  * Prototypes for internal functions 
84  */
85
86
87
88 /**
89  *Find all 2 hop neighbors with 1 link
90  *connecting them to us trough neighbors
91  *with a given willingness.
92  *
93  *@param willingness the willigness of the neighbors
94  *
95  *@return a linked list of allocated neighbor_2_list_entry structures
96  */
97 static struct neighbor_2_list_entry *
98 olsr_find_2_hop_neighbors_with_1_link(int willingness)
99 {
100   
101  
102   olsr_u8_t                    index;
103   struct neighbor_2_list_entry *two_hop_list_tmp = NULL;
104   struct neighbor_2_list_entry *two_hop_list = NULL;
105   struct neighbor_entry        *dup_neighbor;
106   struct neighbor_2_entry      *two_hop_neighbor = NULL;
107
108
109   for(index=0;index<HASHSIZE;index++)
110     {
111
112       for(two_hop_neighbor = two_hop_neighbortable[index].next;
113           two_hop_neighbor != &two_hop_neighbortable[index];
114           two_hop_neighbor = two_hop_neighbor->next)
115         {
116           
117           //two_hop_neighbor->neighbor_2_state=0;
118           //two_hop_neighbor->mpr_covered_count = 0;
119           
120           dup_neighbor = olsr_lookup_neighbor_table(&two_hop_neighbor->neighbor_2_addr);
121           
122           if((dup_neighbor != NULL) && (dup_neighbor->status != NOT_SYM))
123             {
124               
125               //OLSR_PRINTF(1, "(1)Skipping 2h neighbor %s - already 1hop\n", olsr_ip_to_string(&buf, &two_hop_neighbor->neighbor_2_addr));
126
127               continue;
128             }
129           
130           if(two_hop_neighbor->neighbor_2_pointer == 1)
131             {
132               if((two_hop_neighbor->neighbor_2_nblist.next->neighbor->willingness == willingness) &&
133                  (two_hop_neighbor->neighbor_2_nblist.next->neighbor->status == SYM))
134                 {
135                   two_hop_list_tmp = olsr_malloc(sizeof(struct neighbor_2_list_entry), "MPR two hop list");
136
137                   //OLSR_PRINTF(1, "ONE LINK ADDING %s\n", olsr_ip_to_string(&buf, &two_hop_neighbor->neighbor_2_addr));
138
139                   /* Only queue one way here */           
140                   two_hop_list_tmp->neighbor_2 = two_hop_neighbor;
141                   
142                   two_hop_list_tmp->next = two_hop_list;
143                   
144                   two_hop_list= two_hop_list_tmp;
145                 }
146             }
147           
148         }
149       
150     }
151   
152   return(two_hop_list_tmp);
153 }
154   
155
156
157
158
159
160 /**
161  *This function processes the chosen MPRs and updates the counters
162  *used in calculations
163  */
164 static int
165 olsr_chosen_mpr(struct neighbor_entry *one_hop_neighbor, olsr_u16_t *two_hop_covered_count)
166 {
167   struct neighbor_list_entry   *the_one_hop_list;
168   struct neighbor_2_list_entry *second_hop_entries; 
169   struct neighbor_entry        *dup_neighbor;
170   olsr_u16_t                   count;
171 #ifndef NODEBUG
172   struct ipaddr_str            buf;
173 #endif  
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   olsr_u8_t                   index;
245   struct neighbor_entry       *a_neighbor;
246   struct neighbor_entry       *mpr_candidate=NULL;
247    
248   maximum = 0;
249   
250   for (index=0;index<HASHSIZE;index++)
251     {
252       for(a_neighbor = neighbortable[index].next;
253           a_neighbor != &neighbortable[index];
254           a_neighbor = a_neighbor->next)
255         {
256           /*      
257           printf("[%s] nocov: %d mpr: %d will: %d max: %d\n\n", 
258                  olsr_ip_to_string(&buf, &a_neighbor->neighbor_main_addr), 
259                  a_neighbor->neighbor_2_nocov,
260                  a_neighbor->is_mpr,
261                  a_neighbor->willingness,
262                  maximum);
263           */
264           if((!a_neighbor->is_mpr) &&
265              (a_neighbor->willingness == willingness) && 
266              (maximum < a_neighbor->neighbor_2_nocov))
267             {
268               //printf("ADDING\n");
269               maximum = a_neighbor->neighbor_2_nocov;
270               mpr_candidate = a_neighbor;
271             }
272         }
273     }
274   return mpr_candidate;
275 }
276
277
278 /**
279  *Remove all MPR registrations
280  */
281 static void
282 olsr_clear_mprs(void)
283 {
284   olsr_u32_t index;
285   
286   for (index=0;index<HASHSIZE;index++)
287     {
288       struct neighbor_entry   *a_neighbor;
289       for(a_neighbor = neighbortable[index].next;
290           a_neighbor != &neighbortable[index];
291           a_neighbor = a_neighbor->next)
292         {
293           struct neighbor_2_list_entry *two_hop_list;
294           /* Clear MPR selection */
295           if(a_neighbor->is_mpr)
296             {
297               a_neighbor->was_mpr = OLSR_TRUE;
298               a_neighbor->is_mpr = OLSR_FALSE;
299             }
300
301           /* Clear two hop neighbors coverage count */
302           for(two_hop_list = a_neighbor->neighbor_2_list.next;
303               two_hop_list != &a_neighbor->neighbor_2_list;
304               two_hop_list = two_hop_list->next)
305             {
306               two_hop_list->neighbor_2->mpr_covered_count = 0;
307             }
308         }
309     }
310 }
311
312
313 /**
314  *Check for changes in the MPR set
315  *
316  *@return 1 if changes occured 0 if not
317  */
318 static int
319 olsr_check_mpr_changes(void)
320 {
321   olsr_u32_t index;
322   int retval;
323
324   retval = 0;
325   
326   for (index=0;index<HASHSIZE;index++)
327     {
328       struct neighbor_entry *a_neighbor;
329       for(a_neighbor = neighbortable[index].next;
330           a_neighbor != &neighbortable[index];
331           a_neighbor = a_neighbor->next)
332         {
333           if(a_neighbor->was_mpr)
334             {
335               a_neighbor->was_mpr = OLSR_FALSE;
336               if(!a_neighbor->is_mpr)
337                 retval = 1;
338             }
339         }
340     }
341
342   return retval;
343 }
344
345
346 /**
347  *Clears out proccess registration
348  *on two hop neighbors
349  */
350 static void
351 olsr_clear_two_hop_processed(void)
352 {
353   int index;
354   
355   for(index=0;index<HASHSIZE;index++)
356     {
357       struct neighbor_2_entry  *neighbor_2;
358       for(neighbor_2 = two_hop_neighbortable[index].next;
359           neighbor_2 != &two_hop_neighbortable[index];
360           neighbor_2 = neighbor_2->next)
361         {
362           /* Clear */
363           neighbor_2->processed = 0;
364         }
365     }
366
367 }
368
369
370 /**
371  *This function calculates the number of two hop neighbors
372  */
373 static olsr_u16_t
374 olsr_calculate_two_hop_neighbors(void)
375 {
376   olsr_u8_t                    index;
377   olsr_u16_t                   sum = 0;
378   
379   /* Clear 2 hop neighs */
380   olsr_clear_two_hop_processed();
381
382   for(index=0;index<HASHSIZE;index++)
383     {
384       struct neighbor_entry *a_neighbor;
385       for(a_neighbor = neighbortable[index].next; a_neighbor != &neighbortable[index]; a_neighbor = a_neighbor->next)
386         { 
387           struct neighbor_2_list_entry *twohop_neighbors;
388           olsr_u16_t                   count = 0;
389           olsr_u16_t                   n_count = 0;
390           if(a_neighbor->status == NOT_SYM)
391             {       
392               a_neighbor->neighbor_2_nocov = count;
393               continue;
394             }
395
396           for(twohop_neighbors = a_neighbor->neighbor_2_list.next;
397               twohop_neighbors != &a_neighbor->neighbor_2_list;
398               twohop_neighbors = twohop_neighbors->next)
399             {
400               //printf("\tChecking %s....", olsr_ip_to_string(&buf, &twohop_neighbors->neighbor_2->neighbor_2_addr));
401               struct neighbor_entry *dup_neighbor = olsr_lookup_neighbor_table(&twohop_neighbors->neighbor_2->neighbor_2_addr);
402               
403               if((dup_neighbor == NULL) || (dup_neighbor->status != SYM))
404                 {
405                   n_count++;
406                   if(!twohop_neighbors->neighbor_2->processed)
407                     {
408                       count++;
409                       twohop_neighbors->neighbor_2->processed = 1;
410                     }
411                 }
412             }
413           a_neighbor->neighbor_2_nocov = n_count;
414           
415           /* Add the two hop count */
416           sum += count;
417         }
418     }
419   
420   OLSR_PRINTF(3, "Two hop neighbors: %d\n", sum);
421   return sum;
422 }
423
424
425
426
427 /**
428  * Adds all nodes with willingness set to WILL_ALWAYS
429  */
430 static olsr_u16_t
431 add_will_always_nodes(void)
432 {
433   olsr_u16_t                   count = 0;
434   olsr_u8_t                    idx;
435
436   //printf("\nAdding WILL ALWAYS nodes....\n");
437
438   for(idx=0;idx<HASHSIZE;idx++)
439     {
440       struct neighbor_entry        *a_neighbor;
441       for(a_neighbor = neighbortable[idx].next;
442           a_neighbor != &neighbortable[idx];
443           a_neighbor = a_neighbor->next)
444         { 
445 #ifndef NODEBUG
446           struct ipaddr_str buf;
447 #endif
448           if((a_neighbor->status == NOT_SYM) || (a_neighbor->willingness != WILL_ALWAYS)) {
449             continue;
450           }
451           olsr_chosen_mpr(a_neighbor, &count); 
452
453           OLSR_PRINTF(3, "Adding WILL_ALWAYS: %s\n", olsr_ip_to_string(&buf, &a_neighbor->neighbor_main_addr));
454
455         }
456     }
457   
458   //OLSR_PRINTF(1, "Count: %d\n", count);
459   return count;
460 }
461
462 /**
463  *This function calculates the mpr neighbors
464  *@return nada
465  */
466 void
467 olsr_calculate_mpr(void)     
468 {  
469   olsr_u16_t two_hop_covered_count;
470   olsr_u16_t two_hop_count;
471   int i;
472
473   OLSR_PRINTF(3, "\n**RECALCULATING MPR**\n\n");
474
475   olsr_clear_mprs();
476   two_hop_count = olsr_calculate_two_hop_neighbors();
477   two_hop_covered_count = add_will_always_nodes();
478
479   /*
480    *Calculate MPRs based on WILLINGNESS
481    */
482
483   for(i = WILL_ALWAYS - 1; i > WILL_NEVER; i--)
484     {
485       struct neighbor_entry        *mprs; 
486       struct neighbor_2_list_entry *two_hop_list = olsr_find_2_hop_neighbors_with_1_link(i);
487
488       while(two_hop_list != NULL)
489         {
490           struct neighbor_2_list_entry *tmp;
491           //printf("CHOSEN FROM 1 LINK\n");
492           if(!two_hop_list->neighbor_2->neighbor_2_nblist.next->neighbor->is_mpr)
493             olsr_chosen_mpr(two_hop_list->neighbor_2->neighbor_2_nblist.next->neighbor, &two_hop_covered_count); 
494           tmp = two_hop_list;
495           two_hop_list = two_hop_list->next;;
496           free(tmp);
497         }
498       
499       if(two_hop_covered_count >= two_hop_count)
500         {
501           i = WILL_NEVER;
502           break;
503         }
504
505       //printf("two hop covered count: %d\n", two_hop_covered_count);
506    
507       while((mprs = olsr_find_maximum_covered(i)) != NULL)
508         {
509           //printf("CHOSEN FROM MAXCOV\n");
510           olsr_chosen_mpr(mprs,&two_hop_covered_count);
511
512           if(two_hop_covered_count >= two_hop_count)
513             {
514               i = WILL_NEVER;
515               break;
516             }
517
518         }
519     }
520   
521   /*
522     increment the mpr sequence number
523   */
524   //neighbortable.neighbor_mpr_seq++;
525
526   /* Optimize selection */
527   olsr_optimize_mpr_set();
528
529   if(olsr_check_mpr_changes())
530     {
531       OLSR_PRINTF(3, "CHANGES IN MPR SET\n");
532       if(olsr_cnf->tc_redundancy > 0)
533         signal_link_changes(OLSR_TRUE);
534     }
535
536 }
537
538 /**
539  *Optimize MPR set by removing all entries
540  *where all 2 hop neighbors actually is
541  *covered by enough MPRs already
542  *Described in RFC3626 section 8.3.1
543  *point 5
544  *
545  *@return nada
546  */
547 static void
548 olsr_optimize_mpr_set(void)
549 {
550   int i, remove;
551
552   //printf("\n**MPR OPTIMIZING**\n\n");
553
554   for(i = WILL_NEVER + 1; i < WILL_ALWAYS; i++)
555     {
556       int idx;
557       for(idx=0;idx<HASHSIZE;idx++)
558         {
559           struct neighbor_entry *a_neighbor;
560           for(a_neighbor = neighbortable[idx].next;
561               a_neighbor != &neighbortable[idx];
562               a_neighbor = a_neighbor->next)
563             {
564               
565               if(a_neighbor->willingness != i)
566                 continue;
567               
568               if(a_neighbor->is_mpr)
569                 {
570                   struct neighbor_2_list_entry *two_hop_list;
571                   //printf("\tChecking %s\n", olsr_ip_to_string(&buf, &a_neighbor->neighbor_main_addr));
572                   remove = 1;
573
574                   for(two_hop_list = a_neighbor->neighbor_2_list.next;
575                       two_hop_list != &a_neighbor->neighbor_2_list;
576                       two_hop_list = two_hop_list->next)
577                     {
578                       
579                       const struct neighbor_entry * const dup_neighbor = olsr_lookup_neighbor_table(&two_hop_list->neighbor_2->neighbor_2_addr);
580                       
581                       if((dup_neighbor != NULL) && (dup_neighbor->status != NOT_SYM))
582                         continue;
583                       
584                       //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);
585                       /* Do not remove if we find a entry which need this MPR */
586                       if(two_hop_list->neighbor_2->mpr_covered_count <= olsr_cnf->mpr_coverage)
587                         remove = 0;
588                       
589                     }
590                   if(remove)
591                     {
592 #ifndef NODEBUG
593                       struct ipaddr_str buf;
594 #endif
595                       OLSR_PRINTF(3, "MPR OPTIMIZE: removiong mpr %s\n\n", olsr_ip_to_string(&buf, &a_neighbor->neighbor_main_addr));
596                       a_neighbor->is_mpr = OLSR_FALSE;
597                     }
598                 }
599             }
600         }
601     }
602 }
603
604 void
605 olsr_print_mpr_set(void)
606 {
607 #ifndef NODEBUG
608   /* The whole function makes no sense without it. */
609   int idx;
610
611   OLSR_PRINTF(1, "MPR SET: ");
612
613   for(idx = 0; idx < HASHSIZE; idx++) {
614     struct neighbor_entry *a_neighbor;
615     for(a_neighbor = neighbortable[idx].next; a_neighbor != &neighbortable[idx]; a_neighbor = a_neighbor->next) { 
616       /* 
617        * Remove MPR settings
618        */
619       if(a_neighbor->is_mpr) {
620         struct ipaddr_str buf;
621         OLSR_PRINTF(1, "[%s] ", olsr_ip_to_string(&buf, &a_neighbor->neighbor_main_addr));
622       }
623     }
624   }
625   OLSR_PRINTF(1, "\n");
626 #endif
627 }