Merge branch 'release-0.6.5'
[olsrd.git] / src / lq_mpr.c
1
2 /*
3  * The olsr.org Optimized Link-State Routing daemon(olsrd)
4  * Copyright (c) 2004, Thomas Lopatic (thomas@lopatic.de)
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 "two_hop_neighbor_table.h"
45 #include "link_set.h"
46 #include "lq_mpr.h"
47 #include "scheduler.h"
48 #include "lq_plugin.h"
49
50 void
51 olsr_calculate_lq_mpr(void)
52 {
53   struct neighbor_2_entry *neigh2;
54   struct neighbor_list_entry *walker;
55   int i, k;
56   struct neighbor_entry *neigh;
57   olsr_linkcost best, best_1hop;
58   bool mpr_changes = false;
59
60   OLSR_FOR_ALL_NBR_ENTRIES(neigh) {
61
62     /* Memorize previous MPR status. */
63
64     neigh->was_mpr = neigh->is_mpr;
65
66     /* Clear current MPR status. */
67
68     neigh->is_mpr = false;
69
70     /* In this pass we are only interested in WILL_ALWAYS neighbours */
71
72     if (neigh->status == NOT_SYM || neigh->willingness != WILL_ALWAYS) {
73       continue;
74     }
75
76     neigh->is_mpr = true;
77
78     if (neigh->is_mpr != neigh->was_mpr) {
79       mpr_changes = true;
80     }
81
82   }
83   OLSR_FOR_ALL_NBR_ENTRIES_END(neigh);
84
85   for (i = 0; i < HASHSIZE; i++) {
86     /* loop through all 2-hop neighbours */
87
88     for (neigh2 = two_hop_neighbortable[i].next; neigh2 != &two_hop_neighbortable[i]; neigh2 = neigh2->next) {
89       best_1hop = LINK_COST_BROKEN;
90
91       /* check whether this 2-hop neighbour is also a neighbour */
92
93       neigh = olsr_lookup_neighbor_table(&neigh2->neighbor_2_addr);
94
95       /* if it's a neighbour and also symmetric, then examine
96          the link quality */
97
98       if (neigh != NULL && neigh->status == SYM) {
99         /* if the direct link is better than the best route via
100          * an MPR, then prefer the direct link and do not select
101          * an MPR for this 2-hop neighbour */
102
103         /* determine the link quality of the direct link */
104
105         struct link_entry *lnk = get_best_link_to_neighbor(&neigh->neighbor_main_addr);
106
107         if (!lnk)
108           continue;
109
110         best_1hop = lnk->linkcost;
111
112         /* see wether we find a better route via an MPR */
113
114         for (walker = neigh2->neighbor_2_nblist.next; walker != &neigh2->neighbor_2_nblist; walker = walker->next)
115           if (walker->path_linkcost < best_1hop)
116             break;
117
118         /* we've reached the end of the list, so we haven't found
119          * a better route via an MPR - so, skip MPR selection for
120          * this 1-hop neighbor */
121
122         if (walker == &neigh2->neighbor_2_nblist)
123           continue;
124       }
125
126       /* find the connecting 1-hop neighbours with the
127        * best total link qualities */
128
129       /* mark all 1-hop neighbours as not selected */
130
131       for (walker = neigh2->neighbor_2_nblist.next; walker != &neigh2->neighbor_2_nblist; walker = walker->next)
132         walker->neighbor->skip = false;
133
134       for (k = 0; k < olsr_cnf->mpr_coverage; k++) {
135         /* look for the best 1-hop neighbour that we haven't
136          * yet selected */
137
138         neigh = NULL;
139         best = LINK_COST_BROKEN;
140
141         for (walker = neigh2->neighbor_2_nblist.next; walker != &neigh2->neighbor_2_nblist; walker = walker->next)
142           if (walker->neighbor->status == SYM && !walker->neighbor->skip && walker->path_linkcost < best) {
143             neigh = walker->neighbor;
144             best = walker->path_linkcost;
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         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
158         /* no neighbour found => the requested MPR coverage cannot
159          * be satisfied => stop */
160
161         else
162           break;
163       }
164     }
165   }
166
167   if (mpr_changes && olsr_cnf->tc_redundancy > 0)
168     signal_link_changes(true);
169 }
170
171 /*
172  * Local Variables:
173  * c-basic-offset: 2
174  * indent-tabs-mode: nil
175  * End:
176  */