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