9a9d58474f80a0440f5cdaceca38bff8889bd4bb
[oonf.git] / src / nhdp / mpr / neighbor-graph-routing.c
1
2 /*
3  * The olsr.org Optimized Link-State Routing daemon version 2 (olsrd2)
4  * Copyright (c) 2004-2015, 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 /**
43  * @file
44  */
45
46 #include <oonf/nhdp/nhdp/nhdp.h>
47 #include <oonf/nhdp/nhdp/nhdp_db.h>
48 #include <oonf/nhdp/nhdp/nhdp_domain.h>
49 #include <oonf/nhdp/nhdp/nhdp_interfaces.h>
50
51 #include <oonf/libcommon/autobuf.h>
52 #include <oonf/libcommon/avl.h>
53 #include <oonf/libcommon/avl_comp.h>
54 #include <oonf/oonf.h>
55 #include <oonf/libcommon/container_of.h>
56 #include <oonf/libconfig/cfg_schema.h>
57 #include <oonf/libcore/oonf_logging.h>
58 #include <oonf/subsystems/oonf_class.h>
59 #include <oonf/subsystems/oonf_rfc5444.h>
60
61 #include <oonf/nhdp/mpr/mpr.h>
62 #include <oonf/nhdp/mpr/mpr_internal.h>
63 #include <oonf/nhdp/mpr/neighbor-graph-routing.h>
64 #include <oonf/nhdp/mpr/neighbor-graph.h>
65
66 /* FIXME remove unneeded includes */
67
68 static bool _is_allowed_link_tuple(
69   const struct nhdp_domain *domain, struct nhdp_interface *current_interface, struct nhdp_link *lnk);
70 static uint32_t _calculate_d1_x_of_n2_addr(
71   const struct nhdp_domain *domain, struct neighbor_graph *graph, struct addr_node *addr);
72 static uint32_t _calculate_d_x_y(
73   const struct nhdp_domain *domain, struct neighbor_graph *, struct n1_node *x, struct addr_node *y);
74 static uint32_t _calculate_d2_x_y(const struct nhdp_domain *domain, struct n1_node *x, struct addr_node *y);
75 static uint32_t _get_willingness_n1(const struct nhdp_domain *domain, struct n1_node *node);
76
77 static uint32_t _calculate_d1_of_y(const struct nhdp_domain *domain, struct neighbor_graph *graph, struct addr_node *y);
78
79 static struct neighbor_graph_interface _rt_api_interface = {
80   .is_allowed_link_tuple = _is_allowed_link_tuple,
81   .calculate_d1_x_of_n2_addr = _calculate_d1_x_of_n2_addr,
82   .calculate_d_x_y = _calculate_d_x_y,
83   .calculate_d2_x_y = _calculate_d2_x_y,
84   .get_willingness_n1 = _get_willingness_n1,
85 };
86
87 /**
88  * Check if a given tuple is "reachable" according to section 18.4
89  * @param neigh NHDP neighbor
90  * @return true if reachable, false otherwise
91  */
92 static bool
93 _is_reachable_neighbor_tuple(const struct nhdp_domain *domain, struct nhdp_neighbor *neigh) {
94   struct nhdp_neighbor_domaindata *neighbordata;
95   neighbordata = nhdp_domain_get_neighbordata(domain, neigh);
96
97   return neighbordata->metric.in <= RFC7181_METRIC_MAX && neigh->symmetric > 0;
98 }
99
100 /**
101  * Check if a neighbor tuple is "allowed" according to section 18.4
102  * @param domain NHDP domain
103  * @param neigh NHDP neighbor
104  * @return true if allowed, false otherwise
105  */
106 static bool
107 _is_allowed_neighbor_tuple(const struct nhdp_domain *domain, struct nhdp_neighbor *neigh) {
108   struct nhdp_neighbor_domaindata *neighbordata;
109
110   neighbordata = nhdp_domain_get_neighbordata(domain, neigh);
111   return _is_reachable_neighbor_tuple(domain, neigh) && neighbordata->willingness > RFC7181_WILLINGNESS_NEVER;
112 }
113
114 static bool
115 _is_allowed_link_tuple(const struct nhdp_domain *domain,
116   struct nhdp_interface *current_interface __attribute__((unused)), struct nhdp_link *lnk) {
117   return _is_allowed_neighbor_tuple(domain, lnk->neigh);
118 }
119
120 static bool
121 _is_allowed_2hop_tuple(const struct nhdp_domain *domain, struct nhdp_l2hop *two_hop) {
122   struct nhdp_l2hop_domaindata *neighdata;
123   neighdata = nhdp_domain_get_l2hopdata(domain, two_hop);
124   return neighdata->metric.in <= RFC7181_METRIC_MAX;
125 }
126
127 /**
128  * Calculate d1(x) according to section 18.2 (draft 19)
129  * @param domain NHDP domain
130  * @param x node x
131  * @return metric distance
132  */
133 static uint32_t
134 _calculate_d1_x(const struct nhdp_domain *domain, struct n1_node *x) {
135   struct nhdp_neighbor_domaindata *neighdata;
136
137   neighdata = nhdp_domain_get_neighbordata(domain, x->neigh);
138   return neighdata->metric.in;
139 }
140
141 /**
142  * Calculate d2(x,y) according to section 18.2 (draft 19)
143  * @param domain NHDP domain
144  * @param x node x
145  * @param y node y
146  * @return metric distance
147  */
148 static uint32_t
149 _calculate_d2_x_y(const struct nhdp_domain *domain, struct n1_node *x, struct addr_node *y) {
150   struct nhdp_l2hop *l2hop;
151   struct nhdp_link *lnk;
152   struct nhdp_l2hop_domaindata *twohopdata;
153
154   /* find the corresponding 2-hop entry, if it exists */
155   list_for_each_element(&x->neigh->_links, lnk, _neigh_node) {
156     l2hop = avl_find_element(&lnk->_2hop, &y->addr, l2hop, _link_node);
157     if (l2hop) {
158       twohopdata = nhdp_domain_get_l2hopdata(domain, l2hop);
159       return twohopdata->metric.in;
160     }
161   }
162   return RFC7181_METRIC_INFINITE;
163 }
164
165 static uint32_t
166 _calculate_d_x_y(
167   const struct nhdp_domain *domain, struct neighbor_graph *graph, struct n1_node *x, struct addr_node *y) {
168   uint32_t cost, cost1, cost2, idx;
169 #ifdef OONF_LOG_DEBUG_INFO
170   struct netaddr_str nbuf1, nbuf2;
171 #endif
172
173   idx = x->table_offset + y->table_offset;
174   OONF_ASSERT(graph->d_x_y_cache, LOG_MPR, "graph cache should be initialized");
175
176   cost = graph->d_x_y_cache[idx];
177   if (!cost) {
178     cost1 = _calculate_d1_x(domain, x);
179     cost2 = _calculate_d2_x_y(domain, x, y);
180     if (cost1 > RFC7181_METRIC_MAX || cost2 > RFC7181_METRIC_MAX) {
181       cost = RFC7181_METRIC_INFINITE_PATH;
182     }
183     else {
184       cost = cost1 + cost2;
185     }
186     graph->d_x_y_cache[idx] = cost;
187     OONF_DEBUG(LOG_MPR, "d_x_y(%s,%s)=%u (%u,%u)", netaddr_to_string(&nbuf1, &x->addr),
188       netaddr_to_string(&nbuf2, &y->addr), cost, x->table_offset, y->table_offset);
189   }
190   else {
191     OONF_DEBUG(LOG_MPR, "d_x_y(%s,%s)=%u cached(%u,%u)", netaddr_to_string(&nbuf1, &x->addr),
192       netaddr_to_string(&nbuf2, &y->addr), cost, x->table_offset, y->table_offset);
193   }
194   return cost;
195 }
196
197 /**
198  * Calculate d1(y) according to section 18.2 (draft 19)
199  * @param domain NHDP domain
200  * @param graph neighbor graph instance
201  * @param y node y
202  * @return metric distance
203  */
204 static uint32_t
205 _calculate_d1_of_y(const struct nhdp_domain *domain, struct neighbor_graph *graph, struct addr_node *y) {
206   struct n1_node *node_n1;
207   struct nhdp_laddr *laddr;
208   struct nhdp_neighbor_domaindata *neighdata;
209
210   /* find the N1 neighbor corresponding to this address, if it exists */
211   avl_for_each_element(&graph->set_n1, node_n1, _avl_node) {
212     laddr = avl_find_element(&node_n1->neigh->_neigh_addresses, y, laddr, _neigh_node);
213     if (laddr != NULL) {
214       neighdata = nhdp_domain_get_neighbordata(domain, node_n1->neigh);
215       return neighdata->metric.in;
216     }
217   }
218   return RFC7181_METRIC_INFINITE;
219 }
220
221 /**
222  * Calculate d1(x) according to section 18.2 (draft 19)
223  * @param domain NHDP domain
224  * @param graph neighbor graph instance
225  * @param addr node address
226  * @return metric distance
227  */
228 static uint32_t
229 _calculate_d1_x_of_n2_addr(const struct nhdp_domain *domain, struct neighbor_graph *graph, struct addr_node *addr) {
230   uint32_t d1_x;
231
232   d1_x = _calculate_d1_of_y(domain, graph, addr);
233
234   return d1_x;
235 }
236
237 /**
238  * Calculate N1
239  * @param domain NHDP domain
240  * @param graph neighbor graph instance
241  */
242 static void
243 _calculate_n1(const struct nhdp_domain *domain, struct neighbor_graph *graph) {
244   struct nhdp_neighbor *neigh;
245
246 #ifdef OONF_LOG_DEBUG_INFO
247   struct netaddr_str buf1;
248 #endif
249
250   OONF_DEBUG(LOG_MPR, "Calculate N1 for routing MPRs");
251
252   list_for_each_element(nhdp_db_get_neigh_list(), neigh, _global_node) {
253     // Reset temporary selection state
254
255     neigh->selection_is_mpr = false;
256     if (_is_allowed_neighbor_tuple(domain, neigh)) {
257       OONF_DEBUG(LOG_MPR, "Add neighbor %s in: %u", netaddr_to_string(&buf1, &neigh->originator),
258         nhdp_domain_get_neighbordata(domain, neigh)->metric.in);
259       mpr_add_n1_node_to_set(&graph->set_n1, neigh, NULL, 0);
260     }
261   }
262 }
263
264 static void
265 _calculate_n2(const struct nhdp_domain *domain, struct neighbor_graph *graph) {
266   struct n1_node *n1_neigh;
267   struct nhdp_link *lnk;
268   struct nhdp_l2hop *twohop;
269
270 #ifdef OONF_LOG_DEBUG_INFO
271   struct nhdp_l2hop_domaindata *l2data;
272   struct nhdp_neighbor_domaindata *neighdata;
273   struct netaddr_str nbuf1, nbuf2;
274 #endif
275
276   OONF_DEBUG(LOG_MPR, "Calculate N2 for routing MPRs");
277
278   //    list_for_each_element(&nhdp_neigh_list, neigh, _global_node) {
279   //      list_for_each_element(&neigh->_links, link, _if_node) {
280   //        OONF_DEBUG(LOG_MPR, "Link status %u", link->neigh->symmetric);
281   //      }
282   //    }
283
284   /* iterate over all two-hop neighbor addresses of N1 members */
285   avl_for_each_element(&graph->set_n1, n1_neigh, _avl_node) {
286     list_for_each_element(&n1_neigh->neigh->_links, lnk, _neigh_node) {
287       avl_for_each_element(&lnk->_2hop, twohop, _link_node) {
288         // OONF_DEBUG(LOG_MPR, "Link status %u", lnk->neigh->symmetric);
289         if (_is_allowed_2hop_tuple(domain, twohop)) {
290 #ifdef OONF_LOG_DEBUG_INFO
291           neighdata = nhdp_domain_get_neighbordata(domain, n1_neigh->neigh);
292           l2data = nhdp_domain_get_l2hopdata(domain, twohop);
293           OONF_DEBUG(LOG_MPR, "Add twohop addr %s (over %s) in: %u out: %u (path-in: %u path-out: %u)",
294             netaddr_to_string(&nbuf1, &twohop->twohop_addr), netaddr_to_string(&nbuf2, &n1_neigh->addr),
295             l2data->metric.in, l2data->metric.out, l2data->metric.in + neighdata->metric.in,
296             l2data->metric.out + neighdata->metric.out);
297 #endif
298           mpr_add_addr_node_to_set(&graph->set_n2, twohop->twohop_addr, 0);
299         }
300       }
301     }
302   }
303 }
304
305 /**
306  * Returns the flooding/routing willingness of an N1 neighbor
307  * @param domain NHDP domain
308  * @param node neighbor node
309  * @return willingness
310  */
311 static uint32_t
312 _get_willingness_n1(const struct nhdp_domain *domain, struct n1_node *node) {
313   struct nhdp_neighbor_domaindata *neighdata;
314
315   neighdata = nhdp_domain_get_neighbordata(domain, node->neigh);
316   return neighdata->willingness;
317 }
318
319 static struct neighbor_graph_interface *
320 _get_neighbor_graph_interface_routing(void) {
321   return &_rt_api_interface;
322 }
323
324 void
325 mpr_calculate_neighbor_graph_routing(const struct nhdp_domain *domain, struct neighbor_graph *graph) {
326   struct neighbor_graph_interface *methods;
327
328   OONF_DEBUG(LOG_MPR, "Calculate neighbor graph for routing MPRs");
329
330   methods = _get_neighbor_graph_interface_routing();
331
332   mpr_init_neighbor_graph(graph, methods);
333   _calculate_n1(domain, graph);
334   _calculate_n2(domain, graph);
335 }