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 * $Id: lq_route.c,v 1.64 2007/12/12 23:38:52 bernd67 Exp $
44 #define SPF_PROFILING 0
50 #include "neighbor_table.h"
51 #include "two_hop_neighbor_table.h"
53 #include "routing_table.h"
64 * compare two etx metrics.
65 * return 0 if there is an exact match and
66 * -1 / +1 depending on being smaller or bigger.
67 * note that this results in the most optimal code
68 * after compiler optimization.
71 avl_comp_etx (const void *etx1, const void *etx2)
73 if (*(const float *)etx1 < *(const float *)etx2) {
77 if (*(const float *)etx1 > *(const float *)etx2) {
85 * olsr_spf_add_cand_tree
87 * Key an existing vertex to a candidate tree.
90 olsr_spf_add_cand_tree (struct avl_tree *tree,
93 #if !defined(NODEBUG) && defined(DEBUG)
94 struct ipaddr_str buf;
96 tc->cand_tree_node.key = &tc->path_etx;
97 tc->cand_tree_node.data = tc;
100 OLSR_PRINTF(1, "SPF: insert candidate %s, cost %f\n",
101 olsr_ip_to_string(&buf, &tc->addr),
105 avl_insert(tree, &tc->cand_tree_node, AVL_DUP);
109 * olsr_spf_del_cand_tree
111 * Unkey an existing vertex from a candidate tree.
114 olsr_spf_del_cand_tree (struct avl_tree *tree,
120 struct ipaddr_str buf;
122 OLSR_PRINTF(1, "SPF: delete candidate %s, cost %f\n",
123 olsr_ip_to_string(&buf, &tc->addr),
127 avl_delete(tree, &tc->cand_tree_node);
131 * olsr_spf_add_path_list
133 * Insert an SPF result at the end of the path list.
136 olsr_spf_add_path_list (struct list_node *head, int *path_count,
139 #if !defined(NODEBUG) && defined(DEBUG)
140 struct ipaddr_str pathbuf, nbuf;
142 tc->path_list_node.data = tc;
145 OLSR_PRINTF(1, "SPF: append path %s, cost %f, via %s\n",
146 olsr_ip_to_string(&pathbuf, &tc->addr),
148 tc->next_hop ? olsr_ip_to_string(&nbuf, &tc->next_hop->neighbor_iface_addr) : "-");
151 list_add_before(head, &tc->path_list_node);
152 *path_count = *path_count + 1;
156 * olsr_spf_extract_best
158 * return the node with the minimum pathcost.
160 static struct tc_entry *
161 olsr_spf_extract_best (struct avl_tree *tree)
163 struct avl_node *node = avl_walk_first(tree);
165 return (node ? node->data : NULL);
169 const char *olsr_etx_to_string(float etx)
171 static char buff[20];
173 if (etx == INFINITE_ETX) {
176 snprintf(buff, sizeof(buff), "%.6f", etx);
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;
196 struct ipaddr_str buf, nbuf;
198 OLSR_PRINTF(1, "SPF: exploring node %s, cost %f\n",
199 olsr_ip_to_string(&buf, &tc->addr),
204 * loop through all edges of this vertex.
206 for (edge_node = avl_walk_first(&tc->edge_tree);
208 edge_node = avl_walk_next(edge_node)) {
210 struct tc_entry *new_tc;
211 struct tc_edge_entry *tc_edge = edge_node->data;
214 * We are not interested in dead-end or dying edges.
216 if (!tc_edge->edge_inv || (tc_edge->flags & OLSR_TC_EDGE_DOWN)) {
218 OLSR_PRINTF(1, "SPF: ignoring edge %s\n",
219 olsr_ip_to_string(&buf, &tc_edge->T_dest_addr));
220 if (tc_edge->flags & OLSR_TC_EDGE_DOWN) {
221 OLSR_PRINTF(1, "SPF: edge down\n");
223 if (!tc_edge->edge_inv) {
224 OLSR_PRINTF(1, "SPF: no inverse edge\n");
231 * total quality of the path through this vertex
232 * to the destination of this edge
234 new_etx = tc->path_etx + tc_edge->etx;
237 OLSR_PRINTF(1, "SPF: exploring edge %s, cost %s\n",
238 olsr_ip_to_string(&buf, &tc_edge->T_dest_addr),
239 olsr_etx_to_string(new_etx));
243 * if it's better than the current path quality of this edge's
244 * destination node, then we've found a better path to this node.
246 new_tc = tc_edge->edge_inv->tc;
248 if (new_etx < new_tc->path_etx) {
250 /* if this node has been on the candidate tree delete it */
251 if (new_tc->path_etx != INFINITE_ETX) {
252 olsr_spf_del_cand_tree(cand_tree, new_tc);
255 /* re-insert on candidate tree with the better metric */
256 new_tc->path_etx = new_etx;
257 olsr_spf_add_cand_tree(cand_tree, new_tc);
259 /* pull-up the next-hop and bump the hop count */
261 new_tc->next_hop = tc->next_hop;
263 new_tc->hops = tc->hops + 1;
266 OLSR_PRINTF(1, "SPF: better path to %s, cost %s -> %s, via %s, hops %u\n",
267 olsr_ip_to_string(&buf, &new_tc->addr),
268 olsr_etx_to_string(new_tc->path_etx),
269 olsr_etx_to_string(new_etx),
270 tc->next_hop ? olsr_ip_to_string(&nbuf, &tc->next_hop->neighbor_iface_addr) : "<none>",
281 * Run the Dijkstra algorithm.
283 * A node gets added to the candidate tree when one of its edges has
284 * an overall better root path cost than the node itself.
285 * The node with the shortest metric gets moved from the candidate to
286 * the path list every pass.
287 * The SPF computation is completed when there are no more nodes
288 * on the candidate tree.
291 olsr_spf_run_full (struct avl_tree *cand_tree, struct list_node *path_list,
298 while ((tc = olsr_spf_extract_best(cand_tree))) {
300 olsr_spf_relax(cand_tree, tc);
303 * move the best path from the candidate tree
306 olsr_spf_del_cand_tree(cand_tree, tc);
307 olsr_spf_add_path_list(path_list, path_count, tc);
312 olsr_calculate_routing_table (void)
314 #if !defined(NODEBUG) && defined(DEBUG)
315 struct ipaddr_str buf;
318 struct avl_tree cand_tree;
319 struct avl_node *rtp_tree_node;
320 struct list_node path_list; /* head of the path_list */
321 int i, path_count = 0;
324 struct tc_edge_entry *tc_edge;
325 struct neighbor_entry *neigh;
326 struct link_entry *link;
329 struct timeval t1, t2, t3, t4, t5, spf_init, spf_run, route, kernel, total;
331 gettimeofday(&t1, NULL);
335 * Prepare the candidate tree and result list.
337 avl_init(&cand_tree, avl_comp_etx);
338 list_head_init(&path_list);
339 olsr_bump_routingtree_version();
342 * Initialize vertices in the lsdb.
344 OLSR_FOR_ALL_TC_ENTRIES(tc) {
346 tc->path_etx = INFINITE_ETX;
348 } OLSR_FOR_ALL_TC_ENTRIES_END(tc);
351 * zero ourselves and add us to the candidate tree.
353 olsr_change_myself_tc();
354 tc_myself->path_etx = ZERO_ETX;
355 olsr_spf_add_cand_tree(&cand_tree, tc_myself);
358 * add edges to and from our neighbours.
360 for (i = 0; i < HASHSIZE; i++)
361 for (neigh = neighbortable[i].next; neigh != &neighbortable[i];
362 neigh = neigh->next) {
364 if (neigh->status == SYM) {
366 tc_edge = olsr_lookup_tc_edge(tc_myself, &neigh->neighbor_main_addr);
367 link = get_best_link_to_neighbor(&neigh->neighbor_main_addr);
371 * If there is no best link to this neighbor
372 * and we had an edge before then flush the edge.
375 olsr_delete_tc_edge_entry(tc_edge);
380 /* find the interface for the link */
382 link->inter = if_ifwithname(link->if_name);
384 link->inter = if_ifwithaddr(&link->local_iface_addr);
388 * Set the next-hops of our neighbors.
391 tc_edge = olsr_add_tc_edge_entry(tc_myself, &neigh->neighbor_main_addr,
393 link->loss_link_quality2,
394 link->neigh_link_quality2);
398 * Update LQ and timers, such that the edge does not get deleted.
400 tc_edge->link_quality = link->loss_link_quality2;
401 tc_edge->inverse_link_quality = link->neigh_link_quality2;
402 olsr_set_tc_edge_timer(tc_edge, link->vtime*1000);
403 olsr_calc_tc_edge_entry_etx(tc_edge);
405 if (tc_edge->edge_inv) {
406 tc_edge->edge_inv->tc->next_hop = link;
412 gettimeofday(&t2, NULL);
416 * Run the SPF calculation.
418 olsr_spf_run_full(&cand_tree, &path_list, &path_count);
420 OLSR_PRINTF(2, "\n--- %02d:%02d:%02d.%02d ------------------------------------------------- DIJKSTRA\n\n",
424 (int)now.tv_usec/10000);
427 gettimeofday(&t3, NULL);
431 * In the path list we have all the reachable nodes in our topology.
433 for (; !list_is_empty(&path_list); list_remove(path_list.next)) {
435 tc = path_list.next->data;
441 * Supress the error msg when our own tc_entry
442 * does not contain a next-hop.
444 if (tc != tc_myself) {
445 #if !defined(NODEBUG)
446 struct ipaddr_str buf;
448 OLSR_PRINTF(1, "SPF: %s no next-hop\n", olsr_ip_to_string(&buf, &tc->addr));
454 * Now walk all prefixes advertised by that node.
455 * Since the node is reachable, insert the prefix into the global RIB.
456 * If the prefix is already in the RIB, refresh the entry such
457 * that olsr_delete_outdated_routes() does not purge it off.
459 for (rtp_tree_node = avl_walk_first(&tc->prefix_tree);
461 rtp_tree_node = avl_walk_next(rtp_tree_node)) {
463 rtp = rtp_tree_node->data;
468 * If there is a route entry, the prefix is already in the global RIB.
470 olsr_update_rt_path(rtp, tc, link);
475 * The prefix is reachable and not yet in the global RIB.
476 * Build a rt_entry for it.
478 olsr_insert_rt_path(rtp, tc, link);
483 /* Update the RIB based on the new SPF results */
485 olsr_update_rib_routes();
488 gettimeofday(&t4, NULL);
491 /* move the route changes into the kernel */
493 olsr_update_kernel_routes();
496 gettimeofday(&t5, NULL);
500 timersub(&t2, &t1, &spf_init);
501 timersub(&t3, &t2, &spf_run);
502 timersub(&t4, &t3, &route);
503 timersub(&t5, &t4, &kernel);
504 timersub(&t5, &t1, &total);
505 OLSR_PRINTF(1, "\n--- SPF-stats for %d nodes, %d routes (total/init/run/route/kern): "
506 "%d, %d, %d, %d, %d\n",
507 path_count, routingtree.count,
508 (int)total.tv_usec, (int)spf_init.tv_usec, (int)spf_run.tv_usec,
509 (int)route.tv_usec, (int)kernel.tv_usec);