Port all olsrd 0.6.0 OS specific files and adapt them to the new interface.
[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;
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  */