Fix MPR calculation... at least make it possible to work in theory.
[olsrd.git] / src / lq_mpr.c
1
2
3 /*
4  * The olsr.org Optimized Link-State Routing daemon(olsrd)
5  * Copyright (c) 2004-2009, the olsr.org team - see HISTORY file
6  * All rights reserved.
7  *
8  * Redistribution and use in source and binary forms, with or without
9  * modification, are permitted provided that the following conditions
10  * are met:
11  *
12  * * Redistributions of source code must retain the above copyright
13  *   notice, this list of conditions and the following disclaimer.
14  * * Redistributions in binary form must reproduce the above copyright
15  *   notice, this list of conditions and the following disclaimer in
16  *   the documentation and/or other materials provided with the
17  *   distribution.
18  * * Neither the name of olsr.org, olsrd nor the names of its
19  *   contributors may be used to endorse or promote products derived
20  *   from this software without specific prior written permission.
21  *
22  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
23  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
24  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
25  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
26  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
27  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
28  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
29  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
30  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
31  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
32  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
33  * POSSIBILITY OF SUCH DAMAGE.
34  *
35  * Visit http://www.olsr.org for more information.
36  *
37  * If you find this software useful feel free to make a donation
38  * to the project. For more information see the website or contact
39  * the copyright holders.
40  *
41  */
42
43 #include "defs.h"
44 #include "neighbor_table.h"
45 #include "link_set.h"
46 #include "lq_mpr.h"
47 #include "olsr_timer.h"
48 #include "olsr_socket.h"
49 #include "lq_plugin.h"
50
51 static void olsr_calculate_lq_mpr2(void);
52
53 void
54 olsr_calculate_lq_mpr(void)
55 {
56   struct nbr_entry *neigh, *neigh_iterator;
57   struct link_entry *lnk, *lnk_iterator;
58   bool mpr_changes = false;
59
60   /* store old MPR state */
61   OLSR_FOR_ALL_NBR_ENTRIES(neigh, neigh_iterator) {
62     neigh->was_mpr = neigh->is_mpr;
63   }
64
65   /* calculate MPR set */
66   olsr_calculate_lq_mpr2();
67
68   /* look for MPR changes */
69   OLSR_FOR_ALL_NBR_ENTRIES(neigh, neigh_iterator) {
70     if (neigh->was_mpr != neigh->is_mpr) {
71       mpr_changes = true;
72       break;
73     }
74   }
75
76   if (!mpr_changes) {
77     /* no changes */
78     return;
79   }
80
81   /*
82    * we don't do MPRs on interface level...
83    * ugly hack: copy MPR set to link database
84    */
85   OLSR_FOR_ALL_LINK_ENTRIES(lnk, lnk_iterator) {
86     lnk->is_mpr = lnk->neighbor->is_mpr;
87   }
88
89   /* check if the link state changed */
90   if (mpr_changes && olsr_cnf->tc_redundancy > 0) {
91     signal_link_changes(true);
92   }
93 }
94
95 static void
96 olsr_calculate_lq_mpr2(void)
97 {
98   struct nbr_entry *neigh, *neigh_iterator;
99
100 /* use 0 to activate MPR calculation, use 1 to deactivate it */
101 #if 0
102   OLSR_FOR_ALL_NBR_ENTRIES(neigh, neigh_iterator) {
103     /* just use everyone as MPR */
104     neigh->is_mpr = true;
105   }
106 #else
107   struct nbr2_entry *nbr2, *nbr2_iterator;
108   struct nbr_con *walker, *walker_iterator;
109   struct link_entry *lnk;
110   int k;
111   olsr_linkcost best, best_1hop;
112   bool mpr_changes = false, found_better_path;
113
114   OLSR_FOR_ALL_NBR_ENTRIES(neigh, neigh_iterator) {
115     /* Clear current MPR status. */
116     neigh->is_mpr = false;
117
118     /* In this pass we are only interested in WILL_ALWAYS neighbors */
119     if (neigh->is_sym && neigh->willingness != WILL_ALWAYS) {
120       neigh->is_mpr = true;
121
122       if (neigh->is_mpr != neigh->was_mpr) {
123         mpr_changes = true;
124       }
125     }
126   }
127
128   /* loop through all 2-hop neighbors */
129   OLSR_FOR_ALL_NBR2_ENTRIES(nbr2, nbr2_iterator) {
130     best_1hop = ROUTE_COST_BROKEN;
131
132     /* check whether this 2-hop neighbors is also a neighbors */
133     neigh = olsr_lookup_nbr_entry(&nbr2->nbr2_addr, false);
134
135     if (neigh != NULL && neigh->is_sym) {
136       /*
137        * if the direct link is better than the best route via
138        * an MPR, then prefer the direct link and do not select
139        * an MPR for this 2-hop neighbors
140        */
141
142       /* determine the link quality of the direct link */
143       lnk = get_best_link_to_neighbor(neigh);
144       if (!lnk) {
145         /*
146          * this should not happen, a symmetric 1-hop neighbor
147          * should have a symmetric link
148          */
149         continue;
150       }
151
152       best_1hop = lnk->linkcost;
153     }
154
155     /* see if there is a better route via another 1-hop neighbor */
156     walker = NULL;
157     found_better_path = false;
158     OLSR_FOR_ALL_NBR2_CON_ENTRIES(nbr2, walker, walker_iterator) {
159       if (walker->path_linkcost < best_1hop) {
160         found_better_path = true;
161         break;
162       }
163     }
164
165     /* we've reached the end of the list, so we haven't found
166      * a better route via an MPR - so, skip MPR selection for
167      * this 1-hop neighbor */
168
169     if (!found_better_path) {
170       continue;
171     }
172
173     /*
174      * Now find the connecting 1-hop neighbors with the best total link qualities
175      */
176
177     /* mark all 1-hop neighbors as not used for MPR coverage */
178     OLSR_FOR_ALL_NBR2_CON_ENTRIES(nbr2, walker, walker_iterator) {
179       walker->nbr->skip = false;
180     }
181
182     for (k = 0; k < olsr_cnf->mpr_coverage; k++) {
183       /*
184        * look for the best 1-hop neighbor that we haven't yet selected
185        * that produce a better route than the direct one
186        */
187       neigh = NULL;
188       best = best_1hop;
189
190       OLSR_FOR_ALL_NBR2_CON_ENTRIES(nbr2, walker, walker_iterator) {
191         if (walker->nbr->is_sym && !walker->nbr->skip
192             && walker->second_hop_linkcost < LINK_COST_BROKEN
193             && walker->path_linkcost < best) {
194           neigh = walker->nbr;
195           best = walker->path_linkcost;
196         }
197       }
198
199       if (neigh == NULL) {
200         /* no more better 2-hop routes, stop looking */
201         break;
202       }
203
204       /*
205        * Found a 1-hop neighbor that we haven't previously selected.
206        */
207       neigh->is_mpr = true;
208
209       /* don't use this one for more MPR coverage */
210       neigh->skip = true;
211     }
212   }
213 #endif
214 }
215
216 /*
217  * Local Variables:
218  * c-basic-offset: 2
219  * indent-tabs-mode: nil
220  * End:
221  */