2 * The olsr.org Optimized Link-State Routing daemon(olsrd)
3 * Copyright (c) 2004, Thomas Lopatic (thomas@lopatic.de)
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
10 * * Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 * * Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in
14 * the documentation and/or other materials provided with the
16 * * Neither the name of olsr.org, olsrd nor the names of its
17 * contributors may be used to endorse or promote products derived
18 * from this software without specific prior written permission.
20 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
21 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
22 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
23 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
24 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
25 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
26 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
27 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
28 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
29 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
30 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
31 * POSSIBILITY OF SUCH DAMAGE.
33 * Visit http://www.olsr.org for more information.
35 * If you find this software useful feel free to make a donation
36 * to the project. For more information see the website or contact
37 * the copyright holders.
39 * $Id: lq_route.c,v 1.27 2005/02/17 02:06:22 tlopatic Exp $
44 #include "neighbor_table.h"
45 #include "two_hop_neighbor_table.h"
47 #include "routing_table.h"
56 struct avl_node tree_node;
57 struct list_node node;
58 struct dijk_vertex *dest;
64 struct avl_node tree_node;
65 struct list_node node;
66 union olsr_ip_addr addr;
67 struct avl_tree edge_tree;
68 struct list edge_list;
70 struct dijk_vertex *prev;
74 static int avl_comp_ipv6(void *ip1, void *ip2)
76 return memcmp(ip1, ip2, ipsize);
79 static int avl_comp_ipv4(void *ip1, void *ip2)
81 if (*(unsigned int *)ip1 < *(unsigned int *)ip2)
84 if (*(unsigned int *)ip1 == *(unsigned int *)ip2)
90 static int (*avl_comp)(void *, void *);
92 static void add_vertex(struct avl_tree *vertex_tree, struct list *vertex_list,
93 union olsr_ip_addr *addr, float path_etx)
95 struct avl_node *node;
96 struct dijk_vertex *vert;
98 // see whether this destination is already in our list
100 node = avl_find(vertex_tree, addr);
102 // if it's not in our list, add it
106 vert = olsr_malloc(sizeof (struct dijk_vertex), "Dijkstra vertex");
108 vert->tree_node.data = vert;
109 vert->tree_node.key = &vert->addr;
111 vert->node.data = vert;
113 COPY_IP(&vert->addr, addr);
115 vert->path_etx = path_etx;
117 vert->done = OLSR_FALSE;
119 avl_init(&vert->edge_tree, avl_comp);
120 list_init(&vert->edge_list);
122 avl_insert(vertex_tree, &vert->tree_node);
123 list_add_tail(vertex_list, &vert->node);
127 static void add_edge(struct avl_tree *vertex_tree, struct list *vertex_list,
128 union olsr_ip_addr *src, union olsr_ip_addr *dst,
131 struct avl_node *node;
132 struct dijk_vertex *svert;
133 struct dijk_vertex *dvert;
134 struct dijk_edge *edge;
138 node = avl_find(vertex_tree, src);
140 // source vertex does not exist
147 // destination lookup
149 node = avl_find(vertex_tree, dst);
151 // destination vertex does not exist
158 // check for existing forward edge
160 if (avl_find(&svert->edge_tree, dst) == NULL)
164 edge = olsr_malloc(sizeof (struct dijk_vertex), "Dijkstra edge 1");
166 edge->tree_node.data = edge;
167 edge->tree_node.key = &dvert->addr;
169 edge->node.data = edge;
174 avl_insert(&svert->edge_tree, &edge->tree_node);
175 list_add_tail(&svert->edge_list, &edge->node);
178 // check for existing inverse edge
180 if (avl_find(&dvert->edge_tree, src) == NULL)
184 edge = olsr_malloc(sizeof (struct dijk_vertex), "Dijkstra edge 2");
186 edge->tree_node.data = edge;
187 edge->tree_node.key = &svert->addr;
189 edge->node.data = edge;
194 avl_insert(&dvert->edge_tree, &edge->tree_node);
195 list_add_tail(&dvert->edge_list, &edge->node);
199 static void free_everything(struct list *vertex_list)
201 struct list_node *vnode, *enode;
202 struct dijk_vertex *vert;
203 struct dijk_edge *edge;
205 vnode = list_get_head(vertex_list);
207 // loop through all vertices
209 while (vnode != NULL)
213 enode = list_get_head(&vert->edge_list);
215 // loop through all edges of the current vertex
217 while (enode != NULL)
221 enode = list_get_next(enode);
225 vnode = list_get_next(vnode);
230 // XXX - bad complexity
232 static struct dijk_vertex *extract_best(struct list *vertex_list)
234 float best_etx = INFINITE_ETX + 1.0;
235 struct list_node *node;
236 struct dijk_vertex *vert;
237 struct dijk_vertex *res = NULL;
239 node = list_get_head(vertex_list);
241 // loop through all vertices
247 // see whether the current vertex is better than what we have
249 if (!vert->done && vert->path_etx < best_etx)
251 best_etx = vert->path_etx;
255 node = list_get_next(node);
258 // if we've found a vertex, remove it from the set
261 res->done = OLSR_TRUE;
266 static void relax(struct dijk_vertex *vert)
268 struct dijk_edge *edge;
270 struct list_node *node;
272 node = list_get_head(&vert->edge_list);
274 // loop through all edges of this vertex
280 // total quality of the path through this vertex to the
281 // destination of this edge
283 new_etx = vert->path_etx + edge->etx;
285 // if it's better than the current path quality of this
286 // edge's destination, then we've found a better path to
289 if (new_etx < edge->dest->path_etx)
291 edge->dest->path_etx = new_etx;
292 edge->dest->prev = vert;
295 node = list_get_next(node);
299 static char *etx_to_string(float etx)
301 static char buff[20];
303 if (etx == INFINITE_ETX)
306 sprintf(buff, "%.2f", etx);
310 void olsr_calculate_lq_routing_table(void)
312 struct avl_tree vertex_tree;
313 struct list vertex_list;
315 struct tc_entry *tcsrc;
316 struct topo_dst *tcdst;
317 struct dijk_vertex *vert;
318 struct link_entry *link;
319 struct neighbor_entry *neigh;
320 struct list_node *node;
321 struct dijk_vertex *myself;
322 struct dijk_vertex *walker;
324 struct mid_address *mid_walker;
326 struct hna_entry *hna_gw;
328 struct rt_entry *gw_rt, *hna_rt, *head_rt;
329 struct neighbor_2_entry *neigh2;
330 struct neighbor_list_entry *neigh_walker;
331 struct interface *inter;
334 avl_comp = avl_comp_ipv4;
337 avl_comp = avl_comp_ipv6;
339 // initialize the graph
341 avl_init(&vertex_tree, avl_comp);
342 list_init(&vertex_list);
344 // add ourselves to the vertex list
346 add_vertex(&vertex_tree, &vertex_list, &main_addr, 0.0);
348 // add our neighbours
350 for (i = 0; i < HASHSIZE; i++)
351 for (neigh = neighbortable[i].next; neigh != &neighbortable[i];
353 if (neigh->status == SYM)
354 add_vertex(&vertex_tree, &vertex_list, &neigh->neighbor_main_addr,
357 // add our two-hop neighbours
359 for (i = 0; i < HASHSIZE; i++)
360 for (neigh2 = two_hop_neighbortable[i].next;
361 neigh2 != &two_hop_neighbortable[i];
362 neigh2 = neigh2->next)
363 add_vertex(&vertex_tree, &vertex_list, &neigh2->neighbor_2_addr,
366 // add remaining vertices
368 for (i = 0; i < HASHSIZE; i++)
369 for (tcsrc = tc_table[i].next; tcsrc != &tc_table[i]; tcsrc = tcsrc->next)
373 add_vertex(&vertex_tree, &vertex_list, &tcsrc->T_last_addr,
376 // add destinations of this source
378 for (tcdst = tcsrc->destinations.next; tcdst != &tcsrc->destinations;
380 add_vertex(&vertex_tree, &vertex_list, &tcdst->T_dest_addr,
384 // add edges to and from our neighbours
386 for (i = 0; i < HASHSIZE; i++)
387 for (neigh = neighbortable[i].next; neigh != &neighbortable[i];
389 if (neigh->status == SYM)
391 link = get_best_link_to_neighbor(&neigh->neighbor_main_addr);
393 if (link->loss_link_quality >= MIN_LINK_QUALITY &&
394 link->neigh_link_quality >= MIN_LINK_QUALITY)
396 etx = 1.0 / (link->loss_link_quality * link->neigh_link_quality);
398 add_edge(&vertex_tree, &vertex_list, &neigh->neighbor_main_addr,
403 // add edges between our neighbours and our two-hop neighbours
405 for (i = 0; i < HASHSIZE; i++)
406 for (neigh2 = two_hop_neighbortable[i].next;
407 neigh2 != &two_hop_neighbortable[i];
408 neigh2 = neigh2->next)
409 for (neigh_walker = neigh2->neighbor_2_nblist.next;
410 neigh_walker != &neigh2->neighbor_2_nblist;
411 neigh_walker = neigh_walker->next)
413 if (neigh_walker->second_hop_link_quality >=
414 MIN_LINK_QUALITY * MIN_LINK_QUALITY)
416 neigh = neigh_walker->neighbor;
418 etx = 1.0 / neigh_walker->second_hop_link_quality;
420 add_edge(&vertex_tree, &vertex_list, &neigh2->neighbor_2_addr,
421 &neigh->neighbor_main_addr, etx);
425 // add remaining edges
427 for (i = 0; i < HASHSIZE; i++)
428 for (tcsrc = tc_table[i].next; tcsrc != &tc_table[i]; tcsrc = tcsrc->next)
429 for (tcdst = tcsrc->destinations.next; tcdst != &tcsrc->destinations;
432 if (tcdst->link_quality >= MIN_LINK_QUALITY &&
433 tcdst->inverse_link_quality >= MIN_LINK_QUALITY)
435 etx = 1.0 / (tcdst->link_quality * tcdst->inverse_link_quality);
437 add_edge(&vertex_tree, &vertex_list, &tcdst->T_dest_addr,
438 &tcsrc->T_last_addr, etx);
442 // run Dijkstra's algorithm
446 vert = extract_best(&vertex_list);
454 // save the old routing table
456 olsr_move_route_table(routingtable, old_routes);
458 node = list_get_head(&vertex_list);
460 // we're the first vertex in the list
464 olsr_printf(2, "\n--- %02d:%02d:%02d.%02d ------------------------------------------------- DIJKSTRA\n\n",
470 for (node = list_get_next(node); node != NULL; node = list_get_next(node))
476 // count hops to until the path ends or until we have reached a
479 for (walker = vert; walker != NULL && walker->prev != myself;
480 walker = walker->prev)
482 olsr_printf(2, "%s:%s <- ", olsr_ip_to_string(&walker->addr),
483 etx_to_string(walker->path_etx));
487 // if no path to a one-hop neighbour was found, ignore this node
491 olsr_printf(2, "%s:%s (one-hop)\n", olsr_ip_to_string(&walker->addr),
492 etx_to_string(walker->path_etx));
494 // node reachable => add to the set of unprocessed nodes
495 // for HNA processing
497 vert->done = OLSR_FALSE;
502 olsr_printf(2, "FAILED\n", olsr_ip_to_string(&vert->addr));
506 // find the best link to the one-hop neighbour
508 link = get_best_link_to_neighbor(&walker->addr);
510 // we may see NULL here, if the one-hop neighbour is not in the
511 // link and neighbour sets any longer, but we have derived an edge
512 // between us and the one-hop neighbour from the TC set
516 // find the interface for the found link
518 inter = if_ifwithaddr(&link->local_iface_addr);
520 // we may see NULL here if the interface is down, but we have
521 // links that haven't timed out, yet
525 // add a route to the main address of the destination node, if
526 // we haven't already added it above
528 olsr_insert_routing_table(&vert->addr, &link->neighbor_iface_addr,
531 // add routes to the remaining interfaces of the destination node,
532 // if we haven't already added it above
534 for (mid_walker = mid_lookup_aliases(&vert->addr); mid_walker != NULL;
535 mid_walker = mid_walker->next_alias)
536 olsr_insert_routing_table(&mid_walker->alias,
537 &link->neighbor_iface_addr, inter, hops);
542 // add HNA routes - the set of unprocessed network nodes contains
543 // all reachable network nodes
547 // extract the network node with the best ETX and remove it
548 // from the set of unprocessed network nodes
550 vert = extract_best(&vertex_list);
552 // no more nodes left
557 // find the node's HNAs
559 hna_gw = olsr_lookup_hna_gw(&vert->addr);
561 // node doesn't announce any HNAs
566 // find route to the node
568 gw_rt = olsr_lookup_routing_table(&hna_gw->A_gateway_addr);
570 // maybe we haven't found a link or an interface for the gateway above
571 // and hence haven't added a route - skip the HNA in this case
576 // loop through the node's HNAs
578 for (hna = hna_gw->networks.next; hna != &hna_gw->networks;
581 // we already have a route via a previous (better) node
583 if (olsr_lookup_routing_table(&hna->A_network_addr) != NULL)
586 // create route for the HNA
588 hna_rt = olsr_malloc(sizeof(struct rt_entry), "LQ HNA route entry");
590 // set HNA IP address and netmask
592 COPY_IP(&hna_rt->rt_dst, &hna->A_network_addr);
593 hna_rt->rt_mask = hna->A_netmask;
595 // copy remaining fields from the node's route
597 COPY_IP(&hna_rt->rt_router, &gw_rt->rt_router);
598 hna_rt->rt_metric = gw_rt->rt_metric;
599 hna_rt->rt_if = gw_rt->rt_if;
601 // we're not a host route
603 hna_rt->rt_flags = RTF_UP | RTF_GATEWAY;
605 // find the correct list
607 head_rt = &routingtable[olsr_hashing(&hna->A_network_addr)];
611 head_rt->next->prev = hna_rt;
612 hna_rt->next = head_rt->next;
614 head_rt->next = hna_rt;
615 hna_rt->prev = head_rt;
621 free_everything(&vertex_list);
623 // move the route changes into the kernel
625 olsr_update_kernel_routes();
627 // free the saved routing table
629 olsr_free_routing_table(old_routes);