src/lq_mpr.c

   1
   2 /*
   3  * The olsr.org Optimized Link-State Routing daemon(olsrd)
   4  * Copyright (c) 2004-2009, the olsr.org team - see HISTORY file
   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 "defs.h"
  43 #include "neighbor_table.h"
  44 #include "link_set.h"
  45 #include "lq_mpr.h"
  46 #include "scheduler.h"
  47 #include "lq_plugin.h"
  48
  49 void
  50 olsr_calculate_lq_mpr(void)
  51 {
  52   struct nbr2_entry *nbr2;
  53   struct nbr_entry *neigh;
  54   struct nbr_con *walker;
  55   struct link_entry *lnk;
  56   struct list_iterator iterator, iterator2;
  57   int k;
  58   olsr_linkcost best, best_1hop;
  59   bool mpr_changes = false;
  60   bool found_better_path;
  61
  62   OLSR_FOR_ALL_NBR_ENTRIES(neigh, iterator) {
  63
  64     /* Memorize previous MPR status. */
  65     neigh->was_mpr = neigh->is_mpr;
  66
  67     /* Clear current MPR status. */
  68     neigh->is_mpr = false;
  69
  70     /* In this pass we are only interested in WILL_ALWAYS neighbours */
  71     if (!neigh->is_sym || neigh->willingness != WILL_ALWAYS) {
  72       continue;
  73     }
  74
  75     neigh->is_mpr = true;
  76
  77     if (neigh->is_mpr != neigh->was_mpr) {
  78       mpr_changes = true;
  79     }
  80
  81   }
  82
  83   /* loop through all 2-hop neighbours */
  84   OLSR_FOR_ALL_NBR2_ENTRIES(nbr2, iterator) {
  85
  86     best_1hop = LINK_COST_BROKEN;
  87
  88     /* check whether this 2-hop neighbour is also a neighbour */
  89     neigh = olsr_lookup_nbr_entry(&nbr2->nbr2_addr, false);
  90
  91     if (neigh != NULL && neigh->is_sym) {
  92       /*
  93        * if the direct link is better than the best route via
  94        * an MPR, then prefer the direct link and do not select
  95        * an MPR for this 2-hop neighbour
  96        */
  97
  98       /* determine the link quality of the direct link */
  99       lnk = get_best_link_to_neighbor_ip(&neigh->nbr_addr);
 100       if (!lnk) {
 101         continue;
 102       }
 103
 104       best_1hop = lnk->linkcost;
 105     }
 106       /* see wether we find a better route via an MPR */
 107       walker = NULL;
 108       found_better_path = false;
 109       OLSR_FOR_ALL_NBR2_CON_ENTRIES(nbr2, walker, iterator2) {
 110         if (walker->path_linkcost < best_1hop) {
 111           found_better_path = true;
 112           break;
 113         }
 114       }
 115
 116       /* we've reached the end of the list, so we haven't found
 117        * a better route via an MPR - so, skip MPR selection for
 118        * this 1-hop neighbor */
 119
 120       if (!found_better_path) {
 121         continue;
 122       }
 123
 124       /*
 125        * Now find the connecting 1-hop neighbours with the best total link qualities
 126        */
 127
 128       /* mark all 1-hop neighbours as not selected */
 129       OLSR_FOR_ALL_NBR2_CON_ENTRIES(nbr2, walker, iterator2) {
 130         walker->nbr->skip = false;
 131       }
 132
 133       for (k = 0; k < olsr_cnf->mpr_coverage; k++) {
 134
 135         /* look for the best 1-hop neighbour that we haven't yet selected */
 136         neigh = NULL;
 137         best = LINK_COST_BROKEN;
 138
 139         OLSR_FOR_ALL_NBR2_CON_ENTRIES(nbr2, walker, iterator2) {
 140           if (walker->nbr->is_sym && !walker->nbr->skip && walker->path_linkcost < best) {
 141             neigh = walker->nbr;
 142             best = walker->path_linkcost;
 143           }
 144         }
 145
 146         /*
 147          * Found a 1-hop neighbor that we haven't previously selected.
 148          * Use it as MPR only when the 2-hop path through it is better than
 149          * any existing 1-hop path.
 150          */
 151         if ((neigh != NULL) && (best < best_1hop)) {
 152           neigh->is_mpr = true;
 153           neigh->skip = true;
 154
 155           if (neigh->is_mpr != neigh->was_mpr) {
 156             mpr_changes = true;
 157           }
 158         } else {
 159
 160           /*
 161            * no neighbour found, hence the requested MPR coverage cannot * be satisfied => stop
 162            */
 163           break;
 164         }
 165       }
 166   }
 167
 168   /* ugly hack */
 169   OLSR_FOR_ALL_LINK_ENTRIES(lnk, iterator) {
 170     lnk->is_mpr = lnk->neighbor->is_mpr;
 171   }
 172
 173   if (mpr_changes && olsr_cnf->tc_redundancy > 0)
 174     signal_link_changes(true);
 175 }
 176
 177 /*
 178  * Local Variables:
 179  * c-basic-offset: 2
 180  * indent-tabs-mode: nil
 181  * End:
 182  */