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