2 * The olsr.org Optimized Link-State Routing daemon(olsrd)
3 * Copyright (c) 2004, Thomas Lopatic (thomas@lopatic.de)
4 * IPv4 performance optimization (c) 2006, sven-ola(gmx.de)
5 * SPF implementation (c) 2007, Hannes Gredler (hannes@gredler.at)
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
12 * * Redistributions of source code must retain the above copyright
13 * notice, this list of conditions and the following disclaimer.
14 * * Redistributions in binary form must reproduce the above copyright
15 * notice, this list of conditions and the following disclaimer in
16 * the documentation and/or other materials provided with the
18 * * Neither the name of olsr.org, olsrd nor the names of its
19 * contributors may be used to endorse or promote products derived
20 * from this software without specific prior written permission.
22 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
23 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
24 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
25 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
26 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
27 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
28 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
29 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
30 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
31 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
32 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
33 * POSSIBILITY OF SUCH DAMAGE.
35 * Visit http://www.olsr.org for more information.
37 * If you find this software useful feel free to make a donation
38 * to the project. For more information see the website or contact
39 * the copyright holders.
41 * Implementation of Dijkstras algorithm. Initially all nodes
42 * are initialized to infinite cost. First we put ourselves
43 * on the heap of reachable nodes. Our heap implementation
44 * is based on an AVL tree which gives interesting performance
45 * characteristics for the frequent operations of minimum key
46 * extraction and re-keying. Next all neighbors of a node are
47 * explored and put on the heap if the cost of reaching them is
48 * better than reaching the current candidate node.
49 * The SPF calculation is terminated if there are no more nodes
57 #include "neighbor_table.h"
58 #include "two_hop_neighbor_table.h"
60 #include "routing_table.h"
63 #include "common/list.h"
64 #include "common/avl.h"
67 #include "lq_plugin.h"
69 struct timer_entry *spf_backoff_timer = NULL;
74 * compare two etx metrics.
75 * return 0 if there is an exact match and
76 * -1 / +1 depending on being smaller or bigger.
77 * note that this results in the most optimal code
78 * after compiler optimization.
81 avl_comp_etx (const void *etx1, const void *etx2)
83 if (*(const olsr_linkcost *)etx1 < *(const olsr_linkcost *)etx2) {
87 if (*(const olsr_linkcost *)etx1 > *(const olsr_linkcost *)etx2) {
95 * olsr_spf_add_cand_tree
97 * Key an existing vertex to a candidate tree.
100 olsr_spf_add_cand_tree (struct avl_tree *tree,
103 #if !defined(NODEBUG) && defined(DEBUG)
104 struct ipaddr_str buf;
105 struct lqtextbuffer lqbuffer;
107 tc->cand_tree_node.key = &tc->path_cost;
110 OLSR_PRINTF(2, "SPF: insert candidate %s, cost %s\n",
111 olsr_ip_to_string(&buf, &tc->addr),
112 get_linkcost_text(tc->path_cost, OLSR_FALSE, &lqbuffer));
115 avl_insert(tree, &tc->cand_tree_node, AVL_DUP);
119 * olsr_spf_del_cand_tree
121 * Unkey an existing vertex from a candidate tree.
124 olsr_spf_del_cand_tree (struct avl_tree *tree,
130 struct ipaddr_str buf;
131 struct lqtextbuffer lqbuffer;
133 OLSR_PRINTF(2, "SPF: delete candidate %s, cost %s\n",
134 olsr_ip_to_string(&buf, &tc->addr),
135 get_linkcost_text(tc->path_cost, OLSR_FALSE, &lqbuffer));
138 avl_delete(tree, &tc->cand_tree_node);
142 * olsr_spf_add_path_list
144 * Insert an SPF result at the end of the path list.
147 olsr_spf_add_path_list (struct list_node *head, int *path_count,
150 #if !defined(NODEBUG) && defined(DEBUG)
151 struct ipaddr_str pathbuf, nbuf;
152 struct lqtextbuffer lqbuffer;
156 OLSR_PRINTF(2, "SPF: append path %s, cost %s, via %s\n",
157 olsr_ip_to_string(&pathbuf, &tc->addr),
158 get_linkcost_text(tc->path_cost, OLSR_FALSE, &lqbuffer),
159 tc->next_hop ? olsr_ip_to_string(
160 &nbuf, &tc->next_hop->neighbor_iface_addr) : "-");
163 list_add_before(head, &tc->path_list_node);
164 *path_count = *path_count + 1;
168 * olsr_spf_extract_best
170 * return the node with the minimum pathcost.
172 static struct tc_entry *
173 olsr_spf_extract_best (struct avl_tree *tree)
175 struct avl_node *node = avl_walk_first(tree);
177 return (node ? cand_tree2tc(node) : NULL);
184 * Explore all edges of a node and add the node
185 * to the candidate tree if the if the aggregate
186 * path cost is better.
189 olsr_spf_relax (struct avl_tree *cand_tree, struct tc_entry *tc)
191 struct avl_node *edge_node;
192 olsr_linkcost new_cost;
196 struct ipaddr_str buf, nbuf;
197 struct lqtextbuffer lqbuffer;
199 OLSR_PRINTF(2, "SPF: exploring node %s, cost %s\n",
200 olsr_ip_to_string(&buf, &tc->addr),
201 get_linkcost_text(tc->path_cost, OLSR_FALSE, &lqbuffer));
205 * loop through all edges of this vertex.
207 for (edge_node = avl_walk_first(&tc->edge_tree);
209 edge_node = avl_walk_next(edge_node)) {
211 struct tc_entry *new_tc;
212 struct tc_edge_entry *tc_edge = edge_tree2tc_edge(edge_node);
215 * We are not interested in dead-end or dying edges.
217 if (!tc_edge->edge_inv ||
218 ((tc_edge->flags | tc_edge->edge_inv->flags) & OLSR_TC_EDGE_DOWN)) {
220 OLSR_PRINTF(2, "SPF: ignoring edge %s\n",
221 olsr_ip_to_string(&buf, &tc_edge->T_dest_addr));
222 if (!tc_edge->edge_inv) {
223 OLSR_PRINTF(2, "SPF: no inverse edge\n");
226 if (tc_edge->flags & OLSR_TC_EDGE_DOWN) {
227 OLSR_PRINTF(2, "SPF: edge down\n");
229 if (!tc_edge->edge_inv) {
230 OLSR_PRINTF(2, "SPF: no inverse edge\n");
231 } else if (tc_edge->edge_inv->flags & OLSR_TC_EDGE_DOWN){
232 OLSR_PRINTF(2, "SPF: inverse edge down\n");
239 * total quality of the path through this vertex
240 * to the destination of this edge
242 new_cost = tc->path_cost + tc_edge->cost;
245 OLSR_PRINTF(2, "SPF: exploring edge %s, cost %s\n",
246 olsr_ip_to_string(&buf, &tc_edge->T_dest_addr),
247 get_linkcost_text(new_cost, OLSR_TRUE, &lqbuffer));
251 * if it's better than the current path quality of this edge's
252 * destination node, then we've found a better path to this node.
254 new_tc = tc_edge->edge_inv->tc;
256 if (new_cost < new_tc->path_cost) {
258 /* if this node has been on the candidate tree delete it */
259 if (new_tc->path_cost < ROUTE_COST_BROKEN) {
260 olsr_spf_del_cand_tree(cand_tree, new_tc);
263 /* re-insert on candidate tree with the better metric */
264 new_tc->path_cost = new_cost;
265 olsr_spf_add_cand_tree(cand_tree, new_tc);
267 /* pull-up the next-hop and bump the hop count */
269 new_tc->next_hop = tc->next_hop;
271 new_tc->hops = tc->hops + 1;
274 OLSR_PRINTF(2, "SPF: better path to %s, cost %s, via %s, hops %u\n",
275 olsr_ip_to_string(&buf, &new_tc->addr),
276 get_linkcost_text(new_cost, OLSR_TRUE, &lqbuffer),
277 tc->next_hop ? olsr_ip_to_string(
278 &nbuf, &tc->next_hop->neighbor_iface_addr) : "<none>",
289 * Run the Dijkstra algorithm.
291 * A node gets added to the candidate tree when one of its edges has
292 * an overall better root path cost than the node itself.
293 * The node with the shortest metric gets moved from the candidate to
294 * the path list every pass.
295 * The SPF computation is completed when there are no more nodes
296 * on the candidate tree.
299 olsr_spf_run_full (struct avl_tree *cand_tree, struct list_node *path_list,
306 while ((tc = olsr_spf_extract_best(cand_tree))) {
308 olsr_spf_relax(cand_tree, tc);
311 * move the best path from the candidate tree
314 olsr_spf_del_cand_tree(cand_tree, tc);
315 olsr_spf_add_path_list(path_list, path_count, tc);
320 * Callback for the SPF backoff timer.
323 olsr_expire_spf_backoff(void *context __attribute__((unused)))
325 spf_backoff_timer = NULL;
329 olsr_calculate_routing_table (void *context __attribute__((unused)))
332 struct timeval t1, t2, t3, t4, t5, spf_init, spf_run, route, kernel, total;
334 struct avl_tree cand_tree;
335 struct avl_node *rtp_tree_node;
336 struct list_node path_list; /* head of the path_list */
339 struct tc_edge_entry *tc_edge;
340 struct neighbor_entry *neigh;
341 struct link_entry *link;
344 /* We are done if our backoff timer is running */
345 if (!spf_backoff_timer) {
347 olsr_start_timer(1000, 5, OLSR_TIMER_ONESHOT, &olsr_expire_spf_backoff,
354 gettimeofday(&t1, NULL);
358 * Prepare the candidate tree and result list.
360 avl_init(&cand_tree, avl_comp_etx);
361 list_head_init(&path_list);
362 olsr_bump_routingtree_version();
365 * Initialize vertices in the lsdb.
367 OLSR_FOR_ALL_TC_ENTRIES(tc) {
369 tc->path_cost = ROUTE_COST_BROKEN;
371 } OLSR_FOR_ALL_TC_ENTRIES_END(tc);
374 * zero ourselves and add us to the candidate tree.
376 olsr_change_myself_tc();
377 tc_myself->path_cost = ZERO_ROUTE_COST;
378 olsr_spf_add_cand_tree(&cand_tree, tc_myself);
381 * add edges to and from our neighbours.
383 OLSR_FOR_ALL_NBR_ENTRIES(neigh) {
385 if (neigh->status == SYM) {
387 tc_edge = olsr_lookup_tc_edge(tc_myself, &neigh->neighbor_main_addr);
388 link = get_best_link_to_neighbor(&neigh->neighbor_main_addr);
392 * If there is no best link to this neighbor
393 * and we had an edge before then flush the edge.
396 olsr_delete_tc_edge_entry(tc_edge);
401 /* find the interface for the link */
403 link->inter = if_ifwithname(link->if_name);
405 link->inter = if_ifwithaddr(&link->local_iface_addr);
409 * Set the next-hops of our neighbors.
412 tc_edge = olsr_add_tc_edge_entry(tc_myself, &neigh->neighbor_main_addr,
416 * Update LQ and timers, such that the edge does not get deleted.
418 olsr_copylq_link_entry_2_tc_edge_entry(tc_edge, link);
419 olsr_set_tc_edge_timer(tc_edge, link->vtime*1000);
420 olsr_calc_tc_edge_entry_etx(tc_edge);
422 if (tc_edge->edge_inv) {
423 tc_edge->edge_inv->tc->next_hop = link;
426 } OLSR_FOR_ALL_NBR_ENTRIES_END(neigh);
429 gettimeofday(&t2, NULL);
433 * Run the SPF calculation.
435 olsr_spf_run_full(&cand_tree, &path_list, &path_count);
437 OLSR_PRINTF(2, "\n--- %s ------------------------------------------------- DIJKSTRA\n\n",
438 olsr_wallclock_string());
441 gettimeofday(&t3, NULL);
445 * In the path list we have all the reachable nodes in our topology.
447 for (; !list_is_empty(&path_list); list_remove(path_list.next)) {
449 tc = pathlist2tc(path_list.next);
455 * Supress the error msg when our own tc_entry
456 * does not contain a next-hop.
458 if (tc != tc_myself) {
460 struct ipaddr_str buf;
462 OLSR_PRINTF(2, "SPF: %s no next-hop\n", olsr_ip_to_string(&buf, &tc->addr));
469 * Now walk all prefixes advertised by that node.
470 * Since the node is reachable, insert the prefix into the global RIB.
471 * If the prefix is already in the RIB, refresh the entry such
472 * that olsr_delete_outdated_routes() does not purge it off.
474 for (rtp_tree_node = avl_walk_first(&tc->prefix_tree);
476 rtp_tree_node = avl_walk_next(rtp_tree_node)) {
478 rtp = rtp_tree2rtp(rtp_tree_node);
483 * If there is a route entry, the prefix is already in the global RIB.
485 olsr_update_rt_path(rtp, tc, link);
490 * The prefix is reachable and not yet in the global RIB.
491 * Build a rt_entry for it.
493 olsr_insert_rt_path(rtp, tc, link);
498 /* Update the RIB based on the new SPF results */
500 olsr_update_rib_routes();
503 gettimeofday(&t4, NULL);
506 /* move the route changes into the kernel */
508 olsr_update_kernel_routes();
511 gettimeofday(&t5, NULL);
515 timersub(&t2, &t1, &spf_init);
516 timersub(&t3, &t2, &spf_run);
517 timersub(&t4, &t3, &route);
518 timersub(&t5, &t4, &kernel);
519 timersub(&t5, &t1, &total);
520 OLSR_PRINTF(1, "\n--- SPF-stats for %d nodes, %d routes (total/init/run/route/kern): "
521 "%d, %d, %d, %d, %d\n",
522 path_count, routingtree.count,
523 (int)total.tv_usec, (int)spf_init.tv_usec, (int)spf_run.tv_usec,
524 (int)route.tv_usec, (int)kernel.tv_usec);