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