src/mpr.c

   1
   2 /*
   3  * The olsr.org Optimized Link-State Routing daemon(olsrd)
   4  * Copyright (c) 2004, Andreas Tonnesen(andreto@olsr.org)
   5  * All rights reserved.
   6  *
   7  * Redistribution and use in source and binary forms, with or without
   8  * modification, are permitted provided that the following conditions
   9  * are met:
  10  *
  11  * * Redistributions of source code must retain the above copyright
  12  *   notice, this list of conditions and the following disclaimer.
  13  * * Redistributions in binary form must reproduce the above copyright
  14  *   notice, this list of conditions and the following disclaimer in
  15  *   the documentation and/or other materials provided with the
  16  *   distribution.
  17  * * Neither the name of olsr.org, olsrd nor the names of its
  18  *   contributors may be used to endorse or promote products derived
  19  *   from this software without specific prior written permission.
  20  *
  21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  22  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  23  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  24  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
  25  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  26  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
  27  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  28  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  29  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  30  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
  31  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  32  * POSSIBILITY OF SUCH DAMAGE.
  33  *
  34  * Visit http://www.olsr.org for more information.
  35  *
  36  * If you find this software useful feel free to make a donation
  37  * to the project. For more information see the website or contact
  38  * the copyright holders.
  39  *
  40  */
  41
  42 #include "ipcalc.h"
  43 #include "defs.h"
  44 #include "mpr.h"
  45 #include "two_hop_neighbor_table.h"
  46 #include "olsr.h"
  47 #include "neighbor_table.h"
  48 #include "scheduler.h"
  49 #include "net_olsr.h"
  50
  51 /* Begin:
  52  * Prototypes for internal functions
  53  */
  54
  55 static uint16_t add_will_always_nodes(void);
  56
  57 static void olsr_optimize_mpr_set(void);
  58
  59 static void olsr_clear_mprs(void);
  60
  61 static void olsr_clear_two_hop_processed(void);
  62
  63 static struct neighbor_entry *olsr_find_maximum_covered(int);
  64
  65 static uint16_t olsr_calculate_two_hop_neighbors(void);
  66
  67 static int olsr_check_mpr_changes(void);
  68
  69 static int olsr_chosen_mpr(struct neighbor_entry *, uint16_t *);
  70
  71 static struct neighbor_2_list_entry *olsr_find_2_hop_neighbors_with_1_link(int);
  72
  73 /* End:
  74  * Prototypes for internal functions
  75  */
  76
  77 /**
  78  *Find all 2 hop neighbors with 1 link
  79  *connecting them to us trough neighbors
  80  *with a given willingness.
  81  *
  82  *@param willingness the willigness of the neighbors
  83  *
  84  *@return a linked list of allocated neighbor_2_list_entry structures
  85  */
  86 static struct neighbor_2_list_entry *
  87 olsr_find_2_hop_neighbors_with_1_link(int willingness)
  88 {
  89
  90   uint8_t idx;
  91   struct neighbor_2_list_entry *two_hop_list_tmp = NULL;
  92   struct neighbor_2_list_entry *two_hop_list = NULL;
  93   struct neighbor_entry *dup_neighbor;
  94   struct neighbor_2_entry *two_hop_neighbor = NULL;
  95
  96   for (idx = 0; idx < HASHSIZE; idx++) {
  97
  98     for (two_hop_neighbor = two_hop_neighbortable[idx].next; two_hop_neighbor != &two_hop_neighbortable[idx];
  99          two_hop_neighbor = two_hop_neighbor->next) {
 100
 101       //two_hop_neighbor->neighbor_2_state=0;
 102       //two_hop_neighbor->mpr_covered_count = 0;
 103
 104       dup_neighbor = olsr_lookup_neighbor_table(&two_hop_neighbor->neighbor_2_addr);
 105
 106       if ((dup_neighbor != NULL) && (dup_neighbor->status != NOT_SYM)) {
 107
 108         //OLSR_PRINTF(1, "(1)Skipping 2h neighbor %s - already 1hop\n", olsr_ip_to_string(&buf, &two_hop_neighbor->neighbor_2_addr));
 109
 110         continue;
 111       }
 112
 113       if (two_hop_neighbor->neighbor_2_pointer == 1) {
 114         if ((two_hop_neighbor->neighbor_2_nblist.next->neighbor->willingness == willingness)
 115             && (two_hop_neighbor->neighbor_2_nblist.next->neighbor->status == SYM)) {
 116           two_hop_list_tmp = olsr_malloc(sizeof(struct neighbor_2_list_entry), "MPR two hop list");
 117
 118           //OLSR_PRINTF(1, "ONE LINK ADDING %s\n", olsr_ip_to_string(&buf, &two_hop_neighbor->neighbor_2_addr));
 119
 120           /* Only queue one way here */
 121           two_hop_list_tmp->neighbor_2 = two_hop_neighbor;
 122
 123           two_hop_list_tmp->next = two_hop_list;
 124
 125           two_hop_list = two_hop_list_tmp;
 126         }
 127       }
 128
 129     }
 130
 131   }
 132
 133   return (two_hop_list_tmp);
 134 }
 135
 136 /**
 137  *This function processes the chosen MPRs and updates the counters
 138  *used in calculations
 139  */
 140 static int
 141 olsr_chosen_mpr(struct neighbor_entry *one_hop_neighbor, uint16_t * two_hop_covered_count)
 142 {
 143   struct neighbor_list_entry *the_one_hop_list;
 144   struct neighbor_2_list_entry *second_hop_entries;
 145   struct neighbor_entry *dup_neighbor;
 146   uint16_t count;
 147   struct ipaddr_str buf;
 148   count = *two_hop_covered_count;
 149
 150   OLSR_PRINTF(1, "Setting %s as MPR\n", olsr_ip_to_string(&buf, &one_hop_neighbor->neighbor_main_addr));
 151
 152   //printf("PRE COUNT: %d\n\n", count);
 153
 154   one_hop_neighbor->is_mpr = true;      //NBS_MPR;
 155
 156   for (second_hop_entries = one_hop_neighbor->neighbor_2_list.next; second_hop_entries != &one_hop_neighbor->neighbor_2_list;
 157        second_hop_entries = second_hop_entries->next) {
 158     dup_neighbor = olsr_lookup_neighbor_table(&second_hop_entries->neighbor_2->neighbor_2_addr);
 159
 160     if ((dup_neighbor != NULL) && (dup_neighbor->status == SYM)) {
 161       //OLSR_PRINTF(7, "(2)Skipping 2h neighbor %s - already 1hop\n", olsr_ip_to_string(&buf, &second_hop_entries->neighbor_2->neighbor_2_addr));
 162       continue;
 163     }
 164     //      if(!second_hop_entries->neighbor_2->neighbor_2_state)
 165     //if(second_hop_entries->neighbor_2->mpr_covered_count < olsr_cnf->mpr_coverage)
 166     //{
 167     /*
 168        Now the neighbor is covered by this mpr
 169      */
 170     second_hop_entries->neighbor_2->mpr_covered_count++;
 171     the_one_hop_list = second_hop_entries->neighbor_2->neighbor_2_nblist.next;
 172
 173     //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);
 174
 175     if (second_hop_entries->neighbor_2->mpr_covered_count >= olsr_cnf->mpr_coverage)
 176       count++;
 177
 178     while (the_one_hop_list != &second_hop_entries->neighbor_2->neighbor_2_nblist) {
 179
 180       if ((the_one_hop_list->neighbor->status == SYM)) {
 181         if (second_hop_entries->neighbor_2->mpr_covered_count >= olsr_cnf->mpr_coverage) {
 182           the_one_hop_list->neighbor->neighbor_2_nocov--;
 183         }
 184       }
 185       the_one_hop_list = the_one_hop_list->next;
 186     }
 187
 188     //}
 189   }
 190
 191   //printf("POST COUNT %d\n\n", count);
 192
 193   *two_hop_covered_count = count;
 194   return count;
 195
 196 }
 197
 198 /**
 199  *Find the neighbor that covers the most 2 hop neighbors
 200  *with a given willingness
 201  *
 202  *@param willingness the willingness of the neighbor
 203  *
 204  *@return a pointer to the neighbor_entry struct
 205  */
 206 static struct neighbor_entry *
 207 olsr_find_maximum_covered(int willingness)
 208 {
 209   uint16_t maximum;
 210   struct neighbor_entry *a_neighbor;
 211   struct neighbor_entry *mpr_candidate = NULL;
 212
 213   maximum = 0;
 214
 215   OLSR_FOR_ALL_NBR_ENTRIES(a_neighbor) {
 216
 217 #if 0
 218     printf("[%s] nocov: %d mpr: %d will: %d max: %d\n\n", olsr_ip_to_string(&buf, &a_neighbor->neighbor_main_addr),
 219            a_neighbor->neighbor_2_nocov, a_neighbor->is_mpr, a_neighbor->willingness, maximum);
 220 #endif /* 0 */
 221
 222     if ((!a_neighbor->is_mpr) && (a_neighbor->willingness == willingness) && (maximum < a_neighbor->neighbor_2_nocov)) {
 223
 224       maximum = a_neighbor->neighbor_2_nocov;
 225       mpr_candidate = a_neighbor;
 226     }
 227   }
 228   OLSR_FOR_ALL_NBR_ENTRIES_END(a_neighbor);
 229
 230   return mpr_candidate;
 231 }
 232
 233 /**
 234  *Remove all MPR registrations
 235  */
 236 static void
 237 olsr_clear_mprs(void)
 238 {
 239   struct neighbor_entry *a_neighbor;
 240   struct neighbor_2_list_entry *two_hop_list;
 241
 242   OLSR_FOR_ALL_NBR_ENTRIES(a_neighbor) {
 243
 244     /* Clear MPR selection. */
 245     if (a_neighbor->is_mpr) {
 246       a_neighbor->was_mpr = true;
 247       a_neighbor->is_mpr = false;
 248     }
 249
 250     /* Clear two hop neighbors coverage count/ */
 251     for (two_hop_list = a_neighbor->neighbor_2_list.next; two_hop_list != &a_neighbor->neighbor_2_list;
 252          two_hop_list = two_hop_list->next) {
 253       two_hop_list->neighbor_2->mpr_covered_count = 0;
 254     }
 255
 256   }
 257   OLSR_FOR_ALL_NBR_ENTRIES_END(a_neighbor);
 258 }
 259
 260 /**
 261  *Check for changes in the MPR set
 262  *
 263  *@return 1 if changes occured 0 if not
 264  */
 265 static int
 266 olsr_check_mpr_changes(void)
 267 {
 268   struct neighbor_entry *a_neighbor;
 269   int retval;
 270
 271   retval = 0;
 272
 273   OLSR_FOR_ALL_NBR_ENTRIES(a_neighbor) {
 274
 275     if (a_neighbor->was_mpr) {
 276       a_neighbor->was_mpr = false;
 277
 278       if (!a_neighbor->is_mpr) {
 279         retval = 1;
 280       }
 281     }
 282   }
 283   OLSR_FOR_ALL_NBR_ENTRIES_END(a_neighbor);
 284
 285   return retval;
 286 }
 287
 288 /**
 289  *Clears out proccess registration
 290  *on two hop neighbors
 291  */
 292 static void
 293 olsr_clear_two_hop_processed(void)
 294 {
 295   int idx;
 296
 297   for (idx = 0; idx < HASHSIZE; idx++) {
 298     struct neighbor_2_entry *neighbor_2;
 299     for (neighbor_2 = two_hop_neighbortable[idx].next; neighbor_2 != &two_hop_neighbortable[idx]; neighbor_2 = neighbor_2->next) {
 300       /* Clear */
 301       neighbor_2->processed = 0;
 302     }
 303   }
 304
 305 }
 306
 307 /**
 308  *This function calculates the number of two hop neighbors
 309  */
 310 static uint16_t
 311 olsr_calculate_two_hop_neighbors(void)
 312 {
 313   struct neighbor_entry *a_neighbor, *dup_neighbor;
 314   struct neighbor_2_list_entry *twohop_neighbors;
 315   uint16_t count = 0;
 316   uint16_t n_count = 0;
 317   uint16_t sum = 0;
 318
 319   /* Clear 2 hop neighs */
 320   olsr_clear_two_hop_processed();
 321
 322   OLSR_FOR_ALL_NBR_ENTRIES(a_neighbor) {
 323
 324     if (a_neighbor->status == NOT_SYM) {
 325       a_neighbor->neighbor_2_nocov = count;
 326       continue;
 327     }
 328
 329     for (twohop_neighbors = a_neighbor->neighbor_2_list.next; twohop_neighbors != &a_neighbor->neighbor_2_list;
 330          twohop_neighbors = twohop_neighbors->next) {
 331
 332       dup_neighbor = olsr_lookup_neighbor_table(&twohop_neighbors->neighbor_2->neighbor_2_addr);
 333
 334       if ((dup_neighbor == NULL) || (dup_neighbor->status != SYM)) {
 335         n_count++;
 336         if (!twohop_neighbors->neighbor_2->processed) {
 337           count++;
 338           twohop_neighbors->neighbor_2->processed = 1;
 339         }
 340       }
 341     }
 342     a_neighbor->neighbor_2_nocov = n_count;
 343
 344     /* Add the two hop count */
 345     sum += count;
 346
 347   }
 348   OLSR_FOR_ALL_NBR_ENTRIES_END(a_neighbor);
 349
 350   OLSR_PRINTF(3, "Two hop neighbors: %d\n", sum);
 351   return sum;
 352 }
 353
 354 /**
 355  * Adds all nodes with willingness set to WILL_ALWAYS
 356  */
 357 static uint16_t
 358 add_will_always_nodes(void)
 359 {
 360   struct neighbor_entry *a_neighbor;
 361   uint16_t count = 0;
 362
 363 #if 0
 364   printf("\nAdding WILL ALWAYS nodes....\n");
 365 #endif /* 0 */
 366
 367   OLSR_FOR_ALL_NBR_ENTRIES(a_neighbor) {
 368     struct ipaddr_str buf;
 369     if ((a_neighbor->status == NOT_SYM) || (a_neighbor->willingness != WILL_ALWAYS)) {
 370       continue;
 371     }
 372     olsr_chosen_mpr(a_neighbor, &count);
 373
 374     OLSR_PRINTF(3, "Adding WILL_ALWAYS: %s\n", olsr_ip_to_string(&buf, &a_neighbor->neighbor_main_addr));
 375
 376   }
 377   OLSR_FOR_ALL_NBR_ENTRIES_END(a_neighbor);
 378
 379 #if 0
 380   OLSR_PRINTF(1, "Count: %d\n", count);
 381 #endif /* 0 */
 382   return count;
 383 }
 384
 385 /**
 386  *This function calculates the mpr neighbors
 387  *@return nada
 388  */
 389 void
 390 olsr_calculate_mpr(void)
 391 {
 392   uint16_t two_hop_covered_count;
 393   uint16_t two_hop_count;
 394   int i;
 395
 396   OLSR_PRINTF(3, "\n**RECALCULATING MPR**\n\n");
 397
 398   olsr_clear_mprs();
 399   two_hop_count = olsr_calculate_two_hop_neighbors();
 400   two_hop_covered_count = add_will_always_nodes();
 401
 402   /*
 403    *Calculate MPRs based on WILLINGNESS
 404    */
 405
 406   for (i = WILL_ALWAYS - 1; i > WILL_NEVER; i--) {
 407     struct neighbor_entry *mprs;
 408     struct neighbor_2_list_entry *two_hop_list = olsr_find_2_hop_neighbors_with_1_link(i);
 409
 410     while (two_hop_list != NULL) {
 411       struct neighbor_2_list_entry *tmp;
 412       //printf("CHOSEN FROM 1 LINK\n");
 413       if (!two_hop_list->neighbor_2->neighbor_2_nblist.next->neighbor->is_mpr)
 414         olsr_chosen_mpr(two_hop_list->neighbor_2->neighbor_2_nblist.next->neighbor, &two_hop_covered_count);
 415       tmp = two_hop_list;
 416       two_hop_list = two_hop_list->next;;
 417       free(tmp);
 418     }
 419
 420     if (two_hop_covered_count >= two_hop_count) {
 421       i = WILL_NEVER;
 422       break;
 423     }
 424     //printf("two hop covered count: %d\n", two_hop_covered_count);
 425
 426     while ((mprs = olsr_find_maximum_covered(i)) != NULL) {
 427       //printf("CHOSEN FROM MAXCOV\n");
 428       olsr_chosen_mpr(mprs, &two_hop_covered_count);
 429
 430       if (two_hop_covered_count >= two_hop_count) {
 431         i = WILL_NEVER;
 432         break;
 433       }
 434
 435     }
 436   }
 437
 438   /*
 439      increment the mpr sequence number
 440    */
 441   //neighbortable.neighbor_mpr_seq++;
 442
 443   /* Optimize selection */
 444   olsr_optimize_mpr_set();
 445
 446   if (olsr_check_mpr_changes()) {
 447     OLSR_PRINTF(3, "CHANGES IN MPR SET\n");
 448     if (olsr_cnf->tc_redundancy > 0)
 449       signal_link_changes(true);
 450   }
 451
 452 }
 453
 454 /**
 455  *Optimize MPR set by removing all entries
 456  *where all 2 hop neighbors actually is
 457  *covered by enough MPRs already
 458  *Described in RFC3626 section 8.3.1
 459  *point 5
 460  *
 461  *@return nada
 462  */
 463 static void
 464 olsr_optimize_mpr_set(void)
 465 {
 466   struct neighbor_entry *a_neighbor, *dup_neighbor;
 467   struct neighbor_2_list_entry *two_hop_list;
 468   int i, removeit;
 469
 470 #if 0
 471   printf("\n**MPR OPTIMIZING**\n\n");
 472 #endif /* 0 */
 473
 474   for (i = WILL_NEVER + 1; i < WILL_ALWAYS; i++) {
 475
 476     OLSR_FOR_ALL_NBR_ENTRIES(a_neighbor) {
 477
 478       if (a_neighbor->willingness != i) {
 479         continue;
 480       }
 481
 482       if (a_neighbor->is_mpr) {
 483         removeit = 1;
 484
 485         for (two_hop_list = a_neighbor->neighbor_2_list.next; two_hop_list != &a_neighbor->neighbor_2_list;
 486              two_hop_list = two_hop_list->next) {
 487
 488           dup_neighbor = olsr_lookup_neighbor_table(&two_hop_list->neighbor_2->neighbor_2_addr);
 489
 490           if ((dup_neighbor != NULL) && (dup_neighbor->status != NOT_SYM)) {
 491             continue;
 492           }
 493           //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);
 494           /* Do not remove if we find a entry which need this MPR */
 495           if (two_hop_list->neighbor_2->mpr_covered_count <= olsr_cnf->mpr_coverage) {
 496             removeit = 0;
 497           }
 498         }
 499
 500         if (removeit) {
 501           struct ipaddr_str buf;
 502           OLSR_PRINTF(3, "MPR OPTIMIZE: removiong mpr %s\n\n", olsr_ip_to_string(&buf, &a_neighbor->neighbor_main_addr));
 503           a_neighbor->is_mpr = false;
 504         }
 505       }
 506     } OLSR_FOR_ALL_NBR_ENTRIES_END(a_neighbor);
 507   }
 508 }
 509
 510 #ifndef NODEBUG
 511 void
 512 olsr_print_mpr_set(void)
 513 {
 514   /* The whole function makes no sense without it. */
 515   struct neighbor_entry *a_neighbor;
 516
 517   OLSR_PRINTF(1, "MPR SET: ");
 518
 519   OLSR_FOR_ALL_NBR_ENTRIES(a_neighbor) {
 520
 521     /*
 522      * Remove MPR settings
 523      */
 524     if (a_neighbor->is_mpr) {
 525       struct ipaddr_str buf;
 526       OLSR_PRINTF(1, "[%s] ", olsr_ip_to_string(&buf, &a_neighbor->neighbor_main_addr));
 527     }
 528   } OLSR_FOR_ALL_NBR_ENTRIES_END(a_neighbor);
 529
 530   OLSR_PRINTF(1, "\n");
 531 }
 532 #endif /* NODEBUG */
 533
 534 /*
 535  * Local Variables:
 536  * c-basic-offset: 2
 537  * indent-tabs-mode: nil
 538  * End:
 539  */