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
53 #define SPF_PROFILING 0
59 #include "neighbor_table.h"
60 #include "two_hop_neighbor_table.h"
62 #include "routing_table.h"
73 * compare two etx metrics.
74 * return 0 if there is an exact match and
75 * -1 / +1 depending on being smaller or bigger.
76 * note that this results in the most optimal code
77 * after compiler optimization.
80 avl_comp_etx (const void *etx1, const void *etx2)
82 if (*(const float *)etx1 < *(const float *)etx2) {
86 if (*(const float *)etx1 > *(const float *)etx2) {
94 * olsr_spf_add_cand_tree
96 * Key an existing vertex to a candidate tree.
99 olsr_spf_add_cand_tree (struct avl_tree *tree,
102 #if !defined(NODEBUG) && defined(DEBUG)
103 struct ipaddr_str buf;
105 tc->cand_tree_node.key = &tc->path_etx;
106 tc->cand_tree_node.data = tc;
109 OLSR_PRINTF(1, "SPF: insert candidate %s, cost %f\n",
110 olsr_ip_to_string(&buf, &tc->addr),
114 avl_insert(tree, &tc->cand_tree_node, AVL_DUP);
118 * olsr_spf_del_cand_tree
120 * Unkey an existing vertex from a candidate tree.
123 olsr_spf_del_cand_tree (struct avl_tree *tree,
129 struct ipaddr_str buf;
131 OLSR_PRINTF(1, "SPF: delete candidate %s, cost %f\n",
132 olsr_ip_to_string(&buf, &tc->addr),
136 avl_delete(tree, &tc->cand_tree_node);
140 * olsr_spf_add_path_list
142 * Insert an SPF result at the end of the path list.
145 olsr_spf_add_path_list (struct list_node *head, int *path_count,
148 #if !defined(NODEBUG) && defined(DEBUG)
149 struct ipaddr_str pathbuf, nbuf;
151 tc->path_list_node.data = tc;
154 OLSR_PRINTF(1, "SPF: append path %s, cost %f, via %s\n",
155 olsr_ip_to_string(&pathbuf, &tc->addr),
157 tc->next_hop ? olsr_ip_to_string(&nbuf, &tc->next_hop->neighbor_iface_addr) : "-");
160 list_add_before(head, &tc->path_list_node);
161 *path_count = *path_count + 1;
165 * olsr_spf_extract_best
167 * return the node with the minimum pathcost.
169 static struct tc_entry *
170 olsr_spf_extract_best (struct avl_tree *tree)
172 struct avl_node *node = avl_walk_first(tree);
174 return (node ? node->data : NULL);
178 const char *olsr_etx_to_string(float etx)
180 static char buff[20];
182 if (etx == INFINITE_ETX) {
185 snprintf(buff, sizeof(buff), "%.6f", etx);
193 * Explore all edges of a node and add the node
194 * to the candidate tree if the if the aggregate
195 * path cost is better.
198 olsr_spf_relax (struct avl_tree *cand_tree, struct tc_entry *tc)
200 struct avl_node *edge_node;
205 struct ipaddr_str buf, nbuf;
207 OLSR_PRINTF(1, "SPF: exploring node %s, cost %f\n",
208 olsr_ip_to_string(&buf, &tc->addr),
213 * loop through all edges of this vertex.
215 for (edge_node = avl_walk_first(&tc->edge_tree);
217 edge_node = avl_walk_next(edge_node)) {
219 struct tc_entry *new_tc;
220 struct tc_edge_entry *tc_edge = edge_node->data;
223 * We are not interested in dead-end or dying edges.
225 if (!tc_edge->edge_inv || (tc_edge->flags & OLSR_TC_EDGE_DOWN)) {
227 OLSR_PRINTF(1, "SPF: ignoring edge %s\n",
228 olsr_ip_to_string(&buf, &tc_edge->T_dest_addr));
229 if (tc_edge->flags & OLSR_TC_EDGE_DOWN) {
230 OLSR_PRINTF(1, "SPF: edge down\n");
232 if (!tc_edge->edge_inv) {
233 OLSR_PRINTF(1, "SPF: no inverse edge\n");
240 * total quality of the path through this vertex
241 * to the destination of this edge
243 new_etx = tc->path_etx + tc_edge->etx;
246 OLSR_PRINTF(1, "SPF: exploring edge %s, cost %s\n",
247 olsr_ip_to_string(&buf, &tc_edge->T_dest_addr),
248 olsr_etx_to_string(new_etx));
252 * if it's better than the current path quality of this edge's
253 * destination node, then we've found a better path to this node.
255 new_tc = tc_edge->edge_inv->tc;
257 if (new_etx < new_tc->path_etx) {
259 /* if this node has been on the candidate tree delete it */
260 if (new_tc->path_etx != INFINITE_ETX) {
261 olsr_spf_del_cand_tree(cand_tree, new_tc);
264 /* re-insert on candidate tree with the better metric */
265 new_tc->path_etx = new_etx;
266 olsr_spf_add_cand_tree(cand_tree, new_tc);
268 /* pull-up the next-hop and bump the hop count */
270 new_tc->next_hop = tc->next_hop;
272 new_tc->hops = tc->hops + 1;
275 OLSR_PRINTF(1, "SPF: better path to %s, cost %s -> %s, via %s, hops %u\n",
276 olsr_ip_to_string(&buf, &new_tc->addr),
277 olsr_etx_to_string(new_tc->path_etx),
278 olsr_etx_to_string(new_etx),
279 tc->next_hop ? olsr_ip_to_string(&nbuf, &tc->next_hop->neighbor_iface_addr) : "<none>",
290 * Run the Dijkstra algorithm.
292 * A node gets added to the candidate tree when one of its edges has
293 * an overall better root path cost than the node itself.
294 * The node with the shortest metric gets moved from the candidate to
295 * the path list every pass.
296 * The SPF computation is completed when there are no more nodes
297 * on the candidate tree.
300 olsr_spf_run_full (struct avl_tree *cand_tree, struct list_node *path_list,
307 while ((tc = olsr_spf_extract_best(cand_tree))) {
309 olsr_spf_relax(cand_tree, tc);
312 * move the best path from the candidate tree
315 olsr_spf_del_cand_tree(cand_tree, tc);
316 olsr_spf_add_path_list(path_list, path_count, tc);
321 olsr_calculate_routing_table (void)
323 struct avl_tree cand_tree;
324 struct avl_node *rtp_tree_node;
325 struct list_node path_list; /* head of the path_list */
326 int i, path_count = 0;
329 struct tc_edge_entry *tc_edge;
330 struct neighbor_entry *neigh;
331 struct link_entry *link;
334 struct timeval t1, t2, t3, t4, t5, spf_init, spf_run, route, kernel, total;
336 gettimeofday(&t1, NULL);
340 * Prepare the candidate tree and result list.
342 avl_init(&cand_tree, avl_comp_etx);
343 list_head_init(&path_list);
344 olsr_bump_routingtree_version();
347 * Initialize vertices in the lsdb.
349 OLSR_FOR_ALL_TC_ENTRIES(tc) {
351 tc->path_etx = INFINITE_ETX;
353 } OLSR_FOR_ALL_TC_ENTRIES_END(tc);
356 * zero ourselves and add us to the candidate tree.
358 olsr_change_myself_tc();
359 tc_myself->path_etx = ZERO_ETX;
360 olsr_spf_add_cand_tree(&cand_tree, tc_myself);
363 * add edges to and from our neighbours.
365 for (i = 0; i < HASHSIZE; i++)
366 for (neigh = neighbortable[i].next; neigh != &neighbortable[i];
367 neigh = neigh->next) {
369 if (neigh->status == SYM) {
371 tc_edge = olsr_lookup_tc_edge(tc_myself, &neigh->neighbor_main_addr);
372 link = get_best_link_to_neighbor(&neigh->neighbor_main_addr);
376 * If there is no best link to this neighbor
377 * and we had an edge before then flush the edge.
380 olsr_delete_tc_edge_entry(tc_edge);
385 /* find the interface for the link */
387 link->inter = if_ifwithname(link->if_name);
389 link->inter = if_ifwithaddr(&link->local_iface_addr);
393 * Set the next-hops of our neighbors.
396 tc_edge = olsr_add_tc_edge_entry(tc_myself, &neigh->neighbor_main_addr,
398 link->loss_link_quality2,
399 link->neigh_link_quality2);
403 * Update LQ and timers, such that the edge does not get deleted.
405 tc_edge->link_quality = link->loss_link_quality2;
406 tc_edge->inverse_link_quality = link->neigh_link_quality2;
407 olsr_set_tc_edge_timer(tc_edge, link->vtime*1000);
408 olsr_calc_tc_edge_entry_etx(tc_edge);
410 if (tc_edge->edge_inv) {
411 tc_edge->edge_inv->tc->next_hop = link;
417 gettimeofday(&t2, NULL);
421 * Run the SPF calculation.
423 olsr_spf_run_full(&cand_tree, &path_list, &path_count);
425 OLSR_PRINTF(2, "\n--- %02d:%02d:%02d.%02d ------------------------------------------------- DIJKSTRA\n\n",
429 (int)now.tv_usec/10000);
432 gettimeofday(&t3, NULL);
436 * In the path list we have all the reachable nodes in our topology.
438 for (; !list_is_empty(&path_list); list_remove(path_list.next)) {
440 tc = path_list.next->data;
446 * Supress the error msg when our own tc_entry
447 * does not contain a next-hop.
449 if (tc != tc_myself) {
451 struct ipaddr_str buf;
453 OLSR_PRINTF(1, "SPF: %s no next-hop\n", olsr_ip_to_string(&buf, &tc->addr));
460 * Now walk all prefixes advertised by that node.
461 * Since the node is reachable, insert the prefix into the global RIB.
462 * If the prefix is already in the RIB, refresh the entry such
463 * that olsr_delete_outdated_routes() does not purge it off.
465 for (rtp_tree_node = avl_walk_first(&tc->prefix_tree);
467 rtp_tree_node = avl_walk_next(rtp_tree_node)) {
469 rtp = rtp_tree_node->data;
474 * If there is a route entry, the prefix is already in the global RIB.
476 olsr_update_rt_path(rtp, tc, link);
481 * The prefix is reachable and not yet in the global RIB.
482 * Build a rt_entry for it.
484 olsr_insert_rt_path(rtp, tc, link);
489 /* Update the RIB based on the new SPF results */
491 olsr_update_rib_routes();
494 gettimeofday(&t4, NULL);
497 /* move the route changes into the kernel */
499 olsr_update_kernel_routes();
502 gettimeofday(&t5, NULL);
506 timersub(&t2, &t1, &spf_init);
507 timersub(&t3, &t2, &spf_run);
508 timersub(&t4, &t3, &route);
509 timersub(&t5, &t4, &kernel);
510 timersub(&t5, &t1, &total);
511 OLSR_PRINTF(1, "\n--- SPF-stats for %d nodes, %d routes (total/init/run/route/kern): "
512 "%d, %d, %d, %d, %d\n",
513 path_count, routingtree.count,
514 (int)total.tv_usec, (int)spf_init.tv_usec, (int)spf_run.tv_usec,
515 (int)route.tv_usec, (int)kernel.tv_usec);