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 edges.
217 if (!tc_edge->edge_inv) {
219 OLSR_PRINTF(2, "SPF: ignoring edge %s\n",
220 olsr_ip_to_string(&buf, &tc_edge->T_dest_addr));
221 if (!tc_edge->edge_inv) {
222 OLSR_PRINTF(2, "SPF: no inverse edge\n");
229 * total quality of the path through this vertex
230 * to the destination of this edge
232 new_cost = tc->path_cost + tc_edge->cost;
235 OLSR_PRINTF(2, "SPF: exploring edge %s, cost %s\n",
236 olsr_ip_to_string(&buf, &tc_edge->T_dest_addr),
237 get_linkcost_text(new_cost, OLSR_TRUE, &lqbuffer));
241 * if it's better than the current path quality of this edge's
242 * destination node, then we've found a better path to this node.
244 new_tc = tc_edge->edge_inv->tc;
246 if (new_cost < new_tc->path_cost) {
248 /* if this node has been on the candidate tree delete it */
249 if (new_tc->path_cost < ROUTE_COST_BROKEN) {
250 olsr_spf_del_cand_tree(cand_tree, new_tc);
253 /* re-insert on candidate tree with the better metric */
254 new_tc->path_cost = new_cost;
255 olsr_spf_add_cand_tree(cand_tree, new_tc);
257 /* pull-up the next-hop and bump the hop count */
259 new_tc->next_hop = tc->next_hop;
261 new_tc->hops = tc->hops + 1;
264 OLSR_PRINTF(2, "SPF: better path to %s, cost %s, via %s, hops %u\n",
265 olsr_ip_to_string(&buf, &new_tc->addr),
266 get_linkcost_text(new_cost, OLSR_TRUE, &lqbuffer),
267 tc->next_hop ? olsr_ip_to_string(
268 &nbuf, &tc->next_hop->neighbor_iface_addr) : "<none>",
279 * Run the Dijkstra algorithm.
281 * A node gets added to the candidate tree when one of its edges has
282 * an overall better root path cost than the node itself.
283 * The node with the shortest metric gets moved from the candidate to
284 * the path list every pass.
285 * The SPF computation is completed when there are no more nodes
286 * on the candidate tree.
289 olsr_spf_run_full (struct avl_tree *cand_tree, struct list_node *path_list,
296 while ((tc = olsr_spf_extract_best(cand_tree))) {
298 olsr_spf_relax(cand_tree, tc);
301 * move the best path from the candidate tree
304 olsr_spf_del_cand_tree(cand_tree, tc);
305 olsr_spf_add_path_list(path_list, path_count, tc);
310 * Callback for the SPF backoff timer.
313 olsr_expire_spf_backoff(void *context __attribute__((unused)))
315 spf_backoff_timer = NULL;
319 olsr_calculate_routing_table (void)
322 struct timeval t1, t2, t3, t4, t5, spf_init, spf_run, route, kernel, total;
324 struct avl_tree cand_tree;
325 struct avl_node *rtp_tree_node;
326 struct list_node path_list; /* head of the path_list */
329 struct tc_edge_entry *tc_edge;
330 struct neighbor_entry *neigh;
331 struct link_entry *link;
334 /* We are done if our backoff timer is running */
335 if (!spf_backoff_timer) {
337 olsr_start_timer(1000, 5, OLSR_TIMER_ONESHOT, &olsr_expire_spf_backoff,
344 gettimeofday(&t1, NULL);
348 * Prepare the candidate tree and result list.
350 avl_init(&cand_tree, avl_comp_etx);
351 list_head_init(&path_list);
352 olsr_bump_routingtree_version();
355 * Initialize vertices in the lsdb.
357 OLSR_FOR_ALL_TC_ENTRIES(tc) {
359 tc->path_cost = ROUTE_COST_BROKEN;
361 } OLSR_FOR_ALL_TC_ENTRIES_END(tc);
364 * zero ourselves and add us to the candidate tree.
366 olsr_change_myself_tc();
367 tc_myself->path_cost = ZERO_ROUTE_COST;
368 olsr_spf_add_cand_tree(&cand_tree, tc_myself);
371 * add edges to and from our neighbours.
373 OLSR_FOR_ALL_NBR_ENTRIES(neigh) {
375 if (neigh->status == SYM) {
377 tc_edge = olsr_lookup_tc_edge(tc_myself, &neigh->neighbor_main_addr);
378 link = get_best_link_to_neighbor(&neigh->neighbor_main_addr);
382 * If there is no best link to this neighbor
383 * and we had an edge before then flush the edge.
386 olsr_delete_tc_edge_entry(tc_edge);
391 /* find the interface for the link */
393 link->inter = if_ifwithname(link->if_name);
395 link->inter = if_ifwithaddr(&link->local_iface_addr);
399 * Set the next-hops of our neighbors.
402 tc_edge = olsr_add_tc_edge_entry(tc_myself, &neigh->neighbor_main_addr,
407 * Update LQ and timers, such that the edge does not get deleted.
409 olsr_copylq_link_entry_2_tc_edge_entry(tc_edge, link);
410 olsr_calc_tc_edge_entry_etx(tc_edge);
412 if (tc_edge->edge_inv) {
413 tc_edge->edge_inv->tc->next_hop = link;
416 } OLSR_FOR_ALL_NBR_ENTRIES_END(neigh);
419 gettimeofday(&t2, NULL);
423 * Run the SPF calculation.
425 olsr_spf_run_full(&cand_tree, &path_list, &path_count);
427 OLSR_PRINTF(2, "\n--- %s ------------------------------------------------- DIJKSTRA\n\n",
428 olsr_wallclock_string());
431 gettimeofday(&t3, NULL);
435 * In the path list we have all the reachable nodes in our topology.
437 for (; !list_is_empty(&path_list); list_remove(path_list.next)) {
439 tc = pathlist2tc(path_list.next);
445 * Supress the error msg when our own tc_entry
446 * does not contain a next-hop.
448 if (tc != tc_myself) {
450 struct ipaddr_str buf;
452 OLSR_PRINTF(2, "SPF: %s no next-hop\n", olsr_ip_to_string(&buf, &tc->addr));
459 * Now walk all prefixes advertised by that node.
460 * Since the node is reachable, insert the prefix into the global RIB.
461 * If the prefix is already in the RIB, refresh the entry such
462 * that olsr_delete_outdated_routes() does not purge it off.
464 for (rtp_tree_node = avl_walk_first(&tc->prefix_tree);
466 rtp_tree_node = avl_walk_next(rtp_tree_node)) {
468 rtp = rtp_prefix_tree2rtp(rtp_tree_node);
473 * If there is a route entry, the prefix is already in the global RIB.
475 olsr_update_rt_path(rtp, tc, link);
480 * The prefix is reachable and not yet in the global RIB.
481 * Build a rt_entry for it.
483 olsr_insert_rt_path(rtp, tc, link);
488 /* Update the RIB based on the new SPF results */
490 olsr_update_rib_routes();
493 gettimeofday(&t4, NULL);
496 /* move the route changes into the kernel */
498 olsr_update_kernel_routes();
501 gettimeofday(&t5, NULL);
505 timersub(&t2, &t1, &spf_init);
506 timersub(&t3, &t2, &spf_run);
507 timersub(&t4, &t3, &route);
508 timersub(&t5, &t4, &kernel);
509 timersub(&t5, &t1, &total);
510 OLSR_PRINTF(1, "\n--- SPF-stats for %d nodes, %d routes (total/init/run/route/kern): "
511 "%d, %d, %d, %d, %d\n",
512 path_count, routingtree.count,
513 (int)total.tv_usec, (int)spf_init.tv_usec, (int)spf_run.tv_usec,
514 (int)route.tv_usec, (int)kernel.tv_usec);