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)
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
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
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.
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.
34 * Visit http://www.olsr.org for more information.
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.
40 * $Id: lq_route.c,v 1.45 2007/03/29 00:05:50 tlopatic Exp $
46 #include "neighbor_table.h"
47 #include "two_hop_neighbor_table.h"
49 #include "routing_table.h"
58 struct avl_node tree_node;
59 struct list_node node;
60 struct dijk_vertex *dest;
66 struct avl_node tree_node;
67 struct list_node node;
68 union olsr_ip_addr addr;
69 struct avl_tree edge_tree;
70 struct list edge_list;
72 struct dijk_vertex *prev;
76 static int avl_comp_ipv6(void *ip1, void *ip2)
78 return memcmp(ip1, ip2, olsr_cnf->ipsize);
81 static int (*avl_comp)(void *, void *);
83 static void add_vertex(struct avl_tree *vertex_tree, union olsr_ip_addr *addr,
86 struct avl_node *node;
87 struct dijk_vertex *vert;
89 // see whether this destination is already in our list
91 node = avl_find(vertex_tree, addr);
93 // if it's not in our list, add it
97 vert = olsr_malloc(sizeof (struct dijk_vertex), "Dijkstra vertex");
99 vert->tree_node.data = vert;
100 vert->tree_node.key = &vert->addr;
102 COPY_IP(&vert->addr, addr);
104 vert->path_etx = path_etx;
106 vert->done = OLSR_FALSE;
108 avl_init(&vert->edge_tree, avl_comp);
109 list_init(&vert->edge_list);
111 avl_insert(vertex_tree, &vert->tree_node, 0);
115 static void add_edge(struct avl_tree *vertex_tree,
116 union olsr_ip_addr *src, union olsr_ip_addr *dst,
119 struct avl_node *node;
120 struct dijk_vertex *svert;
121 struct dijk_vertex *dvert;
122 struct dijk_edge *edge;
126 node = avl_find(vertex_tree, src);
128 // source vertex does not exist
135 // destination lookup
137 node = avl_find(vertex_tree, dst);
139 // destination vertex does not exist
146 // check for existing forward edge
148 if (avl_find(&svert->edge_tree, dst) == NULL)
152 edge = olsr_malloc(sizeof (struct dijk_vertex), "Dijkstra edge 1");
154 edge->tree_node.data = edge;
155 edge->tree_node.key = &dvert->addr;
157 edge->node.data = edge;
162 avl_insert(&svert->edge_tree, &edge->tree_node, 0);
163 list_add_tail(&svert->edge_list, &edge->node);
166 // check for existing inverse edge
168 if (avl_find(&dvert->edge_tree, src) == NULL)
172 edge = olsr_malloc(sizeof (struct dijk_vertex), "Dijkstra edge 2");
174 edge->tree_node.data = edge;
175 edge->tree_node.key = &svert->addr;
177 edge->node.data = edge;
182 avl_insert(&dvert->edge_tree, &edge->tree_node, 0);
183 list_add_tail(&dvert->edge_list, &edge->node);
187 static void create_vertex_list_rec(struct list *vertex_list,
188 struct avl_node *node,
189 int (*comp)(void *, void *))
191 struct dijk_vertex *vert = node->data;
193 if (node->left != NULL)
194 create_vertex_list_rec(vertex_list, node->left, comp);
196 // add the vertex to the list, if it's not us
198 if (inline_avl_comp_ipv4(&olsr_cnf->main_addr, node->key) != 0)
200 vert->node.data = vert;
201 list_add_tail(vertex_list, &vert->node);
205 if ((*comp)(&olsr_cnf->main_addr, node->key) != 0)
207 vert->node.data = vert;
208 list_add_tail(vertex_list, &vert->node);
212 if (node->right != NULL)
213 create_vertex_list_rec(vertex_list, node->right, comp);
216 static void create_vertex_list(struct avl_tree *vertex_tree,
217 struct list *vertex_list)
219 struct avl_node *node;
220 struct dijk_vertex *vert;
222 // make ourselves the first vertex in the list
224 node = avl_find(vertex_tree, &olsr_cnf->main_addr);
227 vert->node.data = vert;
228 list_add_tail(vertex_list, &vert->node);
230 // add the remaining vertices ordered by their main address
232 create_vertex_list_rec(vertex_list, vertex_tree->root, vertex_tree->comp);
235 static void free_everything(struct list *vertex_list)
237 struct list_node *vnode, *enode;
238 struct dijk_vertex *vert;
239 struct dijk_edge *edge;
241 vnode = list_get_head(vertex_list);
243 // loop through all vertices
245 while (vnode != NULL)
249 enode = list_get_head(&vert->edge_list);
251 // loop through all edges of the current vertex
253 while (enode != NULL)
257 enode = list_get_next(enode);
261 vnode = list_get_next(vnode);
266 // XXX - bad complexity
267 #define SVEN_OLA_OPTIMIZE
270 * The function extract_best() is most expensive (>50% CPU in profiling).
271 * It is called in two modes: while doing Dijkstra route calculation and
272 * while searching for a direct route/hna. The latter can be optimized
273 * because the stored verices do not change from call to call and it is
274 * more sufficient to have them sorted/popped from a list rather than
275 * searching the complete list by every call. Sven-Ola@gmx.de, 11/2006
277 * The SVEN_OLA_OPTIMIZE changes work in our berlin environment. However,
278 * they may introduce bugs, e.g. they are untested for IPv6. For this
279 * reason, the source still contains the ifdef SVEN_OLA_OPIMIZE.
282 #ifdef SVEN_OLA_OPTIMIZE
283 static struct dijk_vertex **etx_cache = 0;
284 static int etx_cache_count;
285 static int etx_cache_get;
287 static int etx_cache_compare(const void *a, const void *b)
289 // Oh jeah. I love this macro assembler :)
291 if ((*(struct dijk_vertex **)a)->path_etx > (*(struct dijk_vertex **)b)->path_etx) return 1;
292 if ((*(struct dijk_vertex **)a)->path_etx < (*(struct dijk_vertex **)b)->path_etx) return -1;
294 // This is for debugging only: etx==etx then compare pointers
295 // to make it possible to compare to the original search algo.
296 if (*(struct dijk_vertex **)a > *(struct dijk_vertex **)b) return 1;
297 if (*(struct dijk_vertex **)a < *(struct dijk_vertex **)b) return -1;
302 static struct dijk_vertex *extract_best_route(struct list *vertex_list)
304 struct list_node *node;
305 struct dijk_vertex *vert;
306 struct dijk_vertex *res = NULL;
308 if (NULL == etx_cache)
311 node = list_get_head(vertex_list);
315 if (!vert->done && vert->path_etx < INFINITE_ETX) count++;
316 node = list_get_next(node);
320 etx_cache = olsr_malloc(sizeof(etx_cache[0]) * count, "ETX Cache");
321 node = list_get_head(vertex_list);
327 if (!vert->done && vert->path_etx < INFINITE_ETX)
329 etx_cache[etx_cache_count] = vert;
332 node = list_get_next(node);
334 qsort(etx_cache, etx_cache_count, sizeof(etx_cache[0]), etx_cache_compare);
338 if (NULL != etx_cache && etx_cache_get < etx_cache_count)
340 res = etx_cache[etx_cache_get++];
343 // if we've found a vertex, remove it from the set
346 res->done = OLSR_TRUE;
350 #endif // SVEN_OLA_OPTIMIZE
352 static struct dijk_vertex *extract_best(struct list *vertex_list)
354 float best_etx = INFINITE_ETX + 1.0;
355 struct list_node *node;
356 struct dijk_vertex *vert;
357 struct dijk_vertex *res = NULL;
359 node = list_get_head(vertex_list);
361 // loop through all vertices
367 // see whether the current vertex is better than what we have
369 if (!vert->done && vert->path_etx < best_etx)
371 best_etx = vert->path_etx;
375 node = list_get_next(node);
378 // if we've found a vertex, remove it from the set
381 res->done = OLSR_TRUE;
386 static void relax(struct dijk_vertex *vert)
388 struct dijk_edge *edge;
390 struct list_node *node;
392 node = list_get_head(&vert->edge_list);
394 // loop through all edges of this vertex
400 // total quality of the path through this vertex to the
401 // destination of this edge
403 new_etx = vert->path_etx + edge->etx;
405 // if it's better than the current path quality of this
406 // edge's destination, then we've found a better path to
409 if (new_etx < edge->dest->path_etx)
411 edge->dest->path_etx = new_etx;
412 edge->dest->prev = vert;
415 node = list_get_next(node);
419 static char *etx_to_string(float etx)
421 static char buff[20];
423 if (etx == INFINITE_ETX)
426 snprintf(buff, 20, "%.2f", etx);
430 void olsr_calculate_lq_routing_table(void)
432 struct avl_tree vertex_tree;
433 struct list vertex_list;
435 struct tc_entry *tcsrc;
436 struct topo_dst *tcdst;
437 struct dijk_vertex *vert;
438 struct link_entry *link;
439 struct neighbor_entry *neigh;
440 struct list_node *node;
441 struct dijk_vertex *myself;
442 struct dijk_vertex *walker;
444 struct mid_address *mid_walker;
446 struct hna_entry *hna_gw;
448 struct rt_entry *gw_rt, *hna_rt, *head_rt;
449 struct neighbor_2_entry *neigh2;
451 struct neighbor_list_entry *neigh_walker;
453 struct interface *inter;
455 if (olsr_cnf->ipsize == 4)
458 avl_comp = avl_comp_ipv6;
460 // initialize the graph
462 avl_init(&vertex_tree, avl_comp);
463 list_init(&vertex_list);
465 // add ourselves to the vertex tree
467 add_vertex(&vertex_tree, &olsr_cnf->main_addr, 0.0);
469 // add our neighbours
471 for (i = 0; i < HASHSIZE; i++)
472 for (neigh = neighbortable[i].next; neigh != &neighbortable[i];
474 if (neigh->status == SYM)
475 add_vertex(&vertex_tree, &neigh->neighbor_main_addr, INFINITE_ETX);
477 // add our two-hop neighbours
479 for (i = 0; i < HASHSIZE; i++)
480 for (neigh2 = two_hop_neighbortable[i].next;
481 neigh2 != &two_hop_neighbortable[i];
482 neigh2 = neigh2->next)
483 add_vertex(&vertex_tree, &neigh2->neighbor_2_addr, INFINITE_ETX);
485 // add remaining vertices
487 for (i = 0; i < HASHSIZE; i++)
488 for (tcsrc = tc_table[i].next; tcsrc != &tc_table[i]; tcsrc = tcsrc->next)
492 add_vertex(&vertex_tree, &tcsrc->T_last_addr, INFINITE_ETX);
494 // add destinations of this source
496 for (tcdst = tcsrc->destinations.next; tcdst != &tcsrc->destinations;
498 add_vertex(&vertex_tree, &tcdst->T_dest_addr, INFINITE_ETX);
501 // add edges to and from our neighbours
503 for (i = 0; i < HASHSIZE; i++)
504 for (neigh = neighbortable[i].next; neigh != &neighbortable[i];
506 if (neigh->status == SYM)
508 link = get_best_link_to_neighbor(&neigh->neighbor_main_addr);
513 if (link->loss_link_quality2 >= MIN_LINK_QUALITY &&
514 link->neigh_link_quality2 >= MIN_LINK_QUALITY)
516 etx = 1.0 / (link->loss_link_quality2 * link->neigh_link_quality2);
518 add_edge(&vertex_tree, &neigh->neighbor_main_addr, &olsr_cnf->main_addr, etx);
522 // we now rely solely on TC messages for routes to our two-hop neighbours
526 // add edges between our neighbours and our two-hop neighbours
528 for (i = 0; i < HASHSIZE; i++)
529 for (neigh2 = two_hop_neighbortable[i].next;
530 neigh2 != &two_hop_neighbortable[i];
531 neigh2 = neigh2->next)
532 for (neigh_walker = neigh2->neighbor_2_nblist.next;
533 neigh_walker != &neigh2->neighbor_2_nblist;
534 neigh_walker = neigh_walker->next)
536 if (neigh_walker->second_hop_link_quality >=
537 MIN_LINK_QUALITY * MIN_LINK_QUALITY)
539 neigh = neigh_walker->neighbor;
541 etx = 1.0 / neigh_walker->second_hop_link_quality;
543 add_edge(&vertex_tree, &neigh2->neighbor_2_addr,
544 &neigh->neighbor_main_addr, etx);
550 // add remaining edges
552 for (i = 0; i < HASHSIZE; i++)
553 for (tcsrc = tc_table[i].next; tcsrc != &tc_table[i]; tcsrc = tcsrc->next)
554 for (tcdst = tcsrc->destinations.next; tcdst != &tcsrc->destinations;
557 if (tcdst->link_quality >= MIN_LINK_QUALITY &&
558 tcdst->inverse_link_quality >= MIN_LINK_QUALITY)
560 etx = 1.0 / (tcdst->link_quality * tcdst->inverse_link_quality);
562 add_edge(&vertex_tree, &tcdst->T_dest_addr, &tcsrc->T_last_addr,
567 // create a sorted vertex list from the vertex tree
569 create_vertex_list(&vertex_tree, &vertex_list);
571 // run Dijkstra's algorithm
575 vert = extract_best(&vertex_list);
583 // save the old routing table
585 olsr_move_route_table(routingtable, old_routes);
587 node = list_get_head(&vertex_list);
589 // we're the first vertex in the list
593 OLSR_PRINTF(2, "\n--- %02d:%02d:%02d.%02d ------------------------------------------------- DIJKSTRA\n\n",
597 (int)now.tv_usec/10000)
599 for (node = list_get_next(node); node != NULL; node = list_get_next(node))
605 // count hops to until the path ends or until we have reached a
608 for (walker = vert; walker != NULL && walker->prev != myself;
609 walker = walker->prev)
611 OLSR_PRINTF(2, "%s:%s <- ", olsr_ip_to_string(&walker->addr),
612 etx_to_string(walker->path_etx))
616 // if no path to a one-hop neighbour was found, ignore this node
620 OLSR_PRINTF(2, "%s:%s (one-hop)\n", olsr_ip_to_string(&walker->addr),
621 etx_to_string(walker->path_etx))
623 // node reachable => add to the set of unprocessed nodes
624 // for HNA processing
626 vert->done = OLSR_FALSE;
631 OLSR_PRINTF(2, "%s FAILED\n", olsr_ip_to_string(&vert->addr))
635 // find the best link to the one-hop neighbour
637 link = get_best_link_to_neighbor(&walker->addr);
639 // we may see NULL here, if the one-hop neighbour is not in the
640 // link and neighbour sets any longer, but we have derived an edge
641 // between us and the one-hop neighbour from the TC set
645 // find the interface for the found link
646 inter = link->if_name ? if_ifwithname(link->if_name) :
647 if_ifwithaddr(&link->local_iface_addr);
649 // we may see NULL here if the interface is down, but we have
650 // links that haven't timed out, yet
654 // XXX - fix me: structurally prevent duplicates, don't test via
655 // olsr_lookup_routing_table()
657 // route addition, case A - add a route to the main address of the
660 if (olsr_lookup_routing_table(&vert->addr) == NULL)
661 olsr_insert_routing_table(&vert->addr, &link->neighbor_iface_addr,
662 inter, hops, vert->path_etx);
664 // route addition, case B - add routes to the remaining interfaces
665 // of the destination node
667 for (mid_walker = mid_lookup_aliases(&vert->addr); mid_walker != NULL;
668 mid_walker = mid_walker->next_alias)
669 if (olsr_lookup_routing_table(&mid_walker->alias) == NULL)
670 olsr_insert_routing_table(&mid_walker->alias,
671 &link->neighbor_iface_addr, inter, hops,
674 // XXX - we used to use olsr_lookup_routing_table() only here, but
675 // this assumed that case A or case B had already happened for
676 // this destination; if case A or case B happened after case C
677 // for the same destination, we had duplicates, as cases A and
678 // B would not test whether case C had already happened
680 // route addition, case C - make sure that we have a route to the
681 // router - e.g. in case the router's not the main address and it's
682 // MID entry has timed out
684 if (olsr_lookup_routing_table(&link->neighbor_iface_addr) == NULL)
685 olsr_insert_routing_table(&link->neighbor_iface_addr,
686 &link->neighbor_iface_addr, inter, 1,
692 // save the old HNA routing table
694 olsr_move_route_table(hna_routes, old_hna);
696 // add HNA routes - the set of unprocessed network nodes contains
697 // all reachable network nodes
698 #ifdef SVEN_OLA_OPTIMIZE
699 if (NULL != etx_cache) {
707 // extract the network node with the best ETX and remove it
708 // from the set of unprocessed network nodes
710 #ifdef SVEN_OLA_OPTIMIZE
711 vert = extract_best_route(&vertex_list);
713 vert = extract_best(&vertex_list);
716 // no more nodes left
721 // find the node's HNAs
723 hna_gw = olsr_lookup_hna_gw(&vert->addr);
725 // node doesn't announce any HNAs
730 // find route to the node
732 gw_rt = olsr_lookup_routing_table(&hna_gw->A_gateway_addr);
734 // maybe we haven't found a link or an interface for the gateway above
735 // and hence haven't added a route - skip the HNA in this case
740 // loop through the node's HNAs
742 for (hna = hna_gw->networks.next; hna != &hna_gw->networks;
745 // we already have a route via a previous (better) node
747 if (olsr_lookup_hna_routing_table(&hna->A_network_addr) != NULL)
750 // create route for the HNA
752 hna_rt = olsr_malloc(sizeof(struct rt_entry), "LQ HNA route entry");
754 // set HNA IP address and netmask
756 COPY_IP(&hna_rt->rt_dst, &hna->A_network_addr);
757 hna_rt->rt_mask = hna->A_netmask;
759 // copy remaining fields from the node's route
761 COPY_IP(&hna_rt->rt_router, &gw_rt->rt_router);
762 hna_rt->rt_metric = gw_rt->rt_metric;
763 hna_rt->rt_etx = gw_rt->rt_etx;
764 hna_rt->rt_if = gw_rt->rt_if;
766 // we're not a host route
768 hna_rt->rt_flags = RTF_UP | RTF_GATEWAY;
770 // find the correct list
772 head_rt = &hna_routes[olsr_hashing(&hna->A_network_addr)];
776 head_rt->next->prev = hna_rt;
777 hna_rt->next = head_rt->next;
779 head_rt->next = hna_rt;
780 hna_rt->prev = head_rt;
786 free_everything(&vertex_list);
788 // move the route changes into the kernel
790 olsr_update_kernel_routes();
791 olsr_update_kernel_hna_routes();
793 // free the saved routing table
795 olsr_free_routing_table(old_routes);
796 olsr_free_routing_table(old_hna);