96fd41b0fe83c40664ca8ecb3aedfe5fd31697f4
[oonf.git] / src / nhdp / mpr / neighbor-graph-flooding.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-flooding.h>
64 #include <oonf/nhdp/mpr/neighbor-graph.h>
65
66 /* FIXME remove unneeded includes */
67
68 static uint32_t _calculate_d1_x(const struct nhdp_domain *domain, struct n1_node *x);
69 static uint32_t _calculate_d2_x_y(const struct nhdp_domain *domain, struct n1_node *x, struct addr_node *y);
70 static uint32_t _calculate_d_x_y(
71   const struct nhdp_domain *domain, struct neighbor_graph *graph, struct n1_node *x, struct addr_node *y);
72 #if 0
73 static uint32_t _calculate_d1_of_y(struct mpr_flooding_data *data, struct addr_node *y);
74 #endif
75 static uint32_t _calculate_d1_x_of_n2_addr(
76   const struct nhdp_domain *domain, struct neighbor_graph *graph, struct addr_node *addr);
77 static void _calculate_n1(const struct nhdp_domain *domain, struct mpr_flooding_data *data);
78 static void _calculate_n2(const struct nhdp_domain *domain, struct mpr_flooding_data *data);
79
80 static bool _is_allowed_link_tuple(
81   const struct nhdp_domain *domain, struct nhdp_interface *current_interface, struct nhdp_link *lnk);
82 static uint32_t _get_willingness_n1(const struct nhdp_domain *, struct n1_node *node);
83
84 static struct neighbor_graph_interface _api_interface = {
85   .is_allowed_link_tuple = _is_allowed_link_tuple,
86   .calculate_d1_x_of_n2_addr = _calculate_d1_x_of_n2_addr,
87   .calculate_d_x_y = _calculate_d_x_y,
88   .calculate_d2_x_y = _calculate_d2_x_y,
89   .get_willingness_n1 = _get_willingness_n1,
90 };
91
92 /**
93  * Check if a given tuple is "reachable" according to section 18.4
94  * @param domain NHDP domain
95  * @param current_interface NHDP interface
96  * @param lnk NHDP link
97  * @return true if reachable, false otherwise
98  */
99 static bool
100 _is_reachable_link_tuple(
101   const struct nhdp_domain *domain, struct nhdp_interface *current_interface, struct nhdp_link *lnk) {
102   struct nhdp_link_domaindata *linkdata;
103
104   linkdata = nhdp_domain_get_linkdata(domain, lnk);
105   return lnk->local_if == current_interface && linkdata->metric.out <= RFC7181_METRIC_MAX &&
106          lnk->status == NHDP_LINK_SYMMETRIC;
107 }
108
109 /**
110  * Check if a link tuple is "allowed" according to section 18.4
111  * @param domain NHDP domain
112  * @param current_interface NHDP interface
113  * @param lnk NHDP link
114  * @return true if link tuple is allowed, false otherwise
115  */
116 static bool
117 _is_allowed_link_tuple(
118   const struct nhdp_domain *domain, struct nhdp_interface *current_interface, struct nhdp_link *lnk) {
119   return _is_reachable_link_tuple(domain, current_interface, lnk) &&
120          lnk->flooding_willingness > RFC7181_WILLINGNESS_NEVER;
121 }
122
123 static bool
124 _is_allowed_2hop_tuple(
125   const struct nhdp_domain *domain, struct nhdp_interface *current_interface, struct nhdp_l2hop *two_hop) {
126   struct nhdp_l2hop_domaindata *twohopdata;
127
128   twohopdata = nhdp_domain_get_l2hopdata(domain, two_hop);
129   return two_hop->link->local_if == current_interface && twohopdata->metric.out <= RFC7181_METRIC_MAX;
130 }
131
132 static uint32_t
133 _calculate_d1_x(const struct nhdp_domain *domain, struct n1_node *x) {
134   struct nhdp_link_domaindata *linkdata;
135
136   linkdata = nhdp_domain_get_linkdata(domain, x->link);
137   return linkdata->metric.out;
138 }
139
140 static uint32_t
141 _calculate_d2_x_y(const struct nhdp_domain *domain, struct n1_node *x, struct addr_node *y) {
142   struct nhdp_l2hop *tmp_l2hop;
143   struct nhdp_l2hop_domaindata *twohopdata;
144
145   /* find the corresponding 2-hop entry, if it exists */
146   tmp_l2hop = avl_find_element(&x->link->_2hop, &y->addr, tmp_l2hop, _link_node);
147   if (tmp_l2hop) {
148     twohopdata = nhdp_domain_get_l2hopdata(domain, tmp_l2hop);
149     return twohopdata->metric.out;
150   }
151   return RFC7181_METRIC_INFINITE;
152 }
153
154 static uint32_t
155 _calculate_d_x_y(
156   const struct nhdp_domain *domain, struct neighbor_graph *graph, struct n1_node *x, struct addr_node *y) {
157   uint32_t cost, cost1, cost2, idx;
158 #ifdef OONF_LOG_DEBUG_INFO
159   struct netaddr_str nbuf1, nbuf2;
160 #endif
161
162   idx = x->table_offset + y->table_offset;
163   OONF_ASSERT(graph->d_x_y_cache, LOG_MPR, "graph cache should be initialized");
164
165   cost = graph->d_x_y_cache[idx];
166   if (!cost) {
167     cost1 = _calculate_d1_x(domain, x);
168     cost2 = _calculate_d2_x_y(domain, x, y);
169     if (cost1 > RFC7181_METRIC_MAX || cost2 > RFC7181_METRIC_MAX) {
170       cost = RFC7181_METRIC_INFINITE_PATH;
171     }
172     else {
173       cost = cost1 + cost2;
174     }
175     graph->d_x_y_cache[idx] = cost;
176     OONF_DEBUG(LOG_MPR, "d_x_y(%s,%s)=%u (%u,%u)", netaddr_to_string(&nbuf1, &x->addr),
177       netaddr_to_string(&nbuf2, &y->addr), cost, x->table_offset, y->table_offset);
178   }
179   else {
180     OONF_DEBUG(LOG_MPR, "d_x_y(%s,%s)=%u cached(%u,%u)", netaddr_to_string(&nbuf1, &x->addr),
181       netaddr_to_string(&nbuf2, &y->addr), cost, x->table_offset, y->table_offset);
182   }
183   return cost;
184 }
185
186 /**
187  * Calculate d1(x) according to section 18.2 (draft 19)
188  * @param domain NHDP domain
189  * @param graph neighbor graph instance
190  * @param addr node address
191  * @return distance of node
192  */
193 uint32_t
194 _calculate_d1_x_of_n2_addr(const struct nhdp_domain *domain, struct neighbor_graph *graph, struct addr_node *addr) {
195   struct n1_node *node_n1;
196   struct nhdp_naddr *naddr;
197   struct nhdp_link_domaindata *linkdata;
198
199   // FIXME Implementation correct?!?!
200
201   avl_for_each_element(&graph->set_n1, node_n1, _avl_node) {
202     /* check if the address provided corresponds to this node */
203     naddr = avl_find_element(&node_n1->neigh->_neigh_addresses, &addr->addr, naddr, _neigh_node);
204     if (naddr) {
205       linkdata = nhdp_domain_get_linkdata(domain, node_n1->link);
206       return linkdata->metric.out;
207     }
208   }
209
210   return RFC7181_METRIC_INFINITE;
211 }
212
213 /**
214  * Calculate N1
215  * @param domain NHDP domain
216  * @param data flooding data
217  */
218 static void
219 _calculate_n1(const struct nhdp_domain *domain, struct mpr_flooding_data *data) {
220   struct nhdp_link *lnk;
221
222   OONF_DEBUG(LOG_MPR, "Calculate N1 (flooding) for interface %s", nhdp_interface_get_name(data->current_interface));
223
224   list_for_each_element(nhdp_db_get_link_list(), lnk, _global_node) {
225     // Reset temporary selection state
226     lnk->neigh->selection_is_mpr = false;
227
228     if (_is_allowed_link_tuple(domain, data->current_interface, lnk)) {
229       mpr_add_n1_node_to_set(&data->neigh_graph.set_n1, lnk->neigh, lnk, 0);
230     }
231   }
232 }
233
234 /**
235  * Calculate N2
236  *
237  * For every neighbor in N1, N2 contains a unique entry for every neighbor
238  * 2-hop neighbor address. The same address may be reachable via multiple
239  * 1-hop neighbors, but is only represented once in N2.
240  *
241  * Note that N1 is generated per-interface, so we don't need to deal with
242  * multiple links to the same N1 member.
243  *
244  * @param domain NHDP domain
245  * @param data flooding data
246  */
247 static void
248 _calculate_n2(const struct nhdp_domain *domain, struct mpr_flooding_data *data) {
249   struct n1_node *n1_neigh;
250   struct nhdp_l2hop *twohop;
251
252   OONF_DEBUG(LOG_MPR, "Calculate N2 for flooding MPRs");
253
254   /* iterate over all two-hop neighbor addresses of N1 members */
255   avl_for_each_element(&data->neigh_graph.set_n1, n1_neigh, _avl_node) {
256     avl_for_each_element(&n1_neigh->link->_2hop, twohop, _link_node) {
257       if (_is_allowed_2hop_tuple(domain, data->current_interface, twohop)) {
258         mpr_add_addr_node_to_set(&data->neigh_graph.set_n2, twohop->twohop_addr, 0);
259       }
260     }
261   }
262 }
263
264 /**
265  * Returns the flooding/routing willingness of an N1 neighbor
266  * @param domain NHDP domain
267  * @param node NHDP node
268  * @return flooding willingness of NHDP node
269  */
270 static uint32_t
271 _get_willingness_n1(const struct nhdp_domain *domain __attribute__((unused)), struct n1_node *node) {
272   return node->link->flooding_willingness;
273 }
274
275 void
276 mpr_calculate_neighbor_graph_flooding(const struct nhdp_domain *domain, struct mpr_flooding_data *data) {
277   OONF_DEBUG(LOG_MPR, "Calculate neighbor graph for flooding MPRs");
278
279   mpr_init_neighbor_graph(&data->neigh_graph, &_api_interface);
280   _calculate_n1(domain, data);
281   _calculate_n2(domain, data);
282 }