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