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