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.21 2005/01/22 12:25:25 tlopatic Exp $
44 #include "neighbor_table.h"
46 #include "routing_table.h"
54 struct list_node node;
55 struct dijk_vertex *dest;
61 struct list_node node;
62 union olsr_ip_addr addr;
63 struct list edge_list;
65 struct dijk_vertex *prev;
69 // XXX - bad complexity
71 static void add_vertex(struct list *vertex_list, union olsr_ip_addr *addr,
74 struct list_node *node;
75 struct dijk_vertex *vert;
77 // see whether this destination is already in our list
79 node = list_get_head(vertex_list);
85 if (COMP_IP(&vert->addr, addr))
88 node = list_get_next(node);
91 // if it's not in our list, add it
95 vert = olsr_malloc(sizeof (struct dijk_vertex), "Dijkstra vertex");
97 vert->node.data = vert;
99 COPY_IP(&vert->addr, addr);
101 vert->path_etx = path_etx;
103 vert->done = OLSR_FALSE;
105 list_init(&vert->edge_list);
107 list_add_tail(vertex_list, &vert->node);
111 // XXX - bad complexity
113 static void add_edge(struct list *vertex_list, union olsr_ip_addr *src,
114 union olsr_ip_addr *dst, float etx)
116 struct list_node *node;
117 struct dijk_vertex *vert;
118 struct dijk_vertex *svert;
119 struct dijk_vertex *dvert;
120 struct dijk_edge *edge;
122 // source and destination lookup
124 node = list_get_head(vertex_list);
133 if (COMP_IP(&vert->addr, src))
141 else if (COMP_IP(&vert->addr, dst))
149 node = list_get_next(node);
152 // source or destination vertex does not exist
154 if (svert == NULL || dvert == NULL)
157 node = list_get_head(&svert->edge_list);
163 if (edge->dest == dvert)
166 node = list_get_next(node);
169 // edge already exists
174 edge = olsr_malloc(sizeof (struct dijk_vertex), "Dijkstra edge");
176 edge->node.data = edge;
181 list_add_tail(&svert->edge_list, &edge->node);
184 static void free_everything(struct list *vertex_list)
186 struct list_node *vnode, *enode;
187 struct dijk_vertex *vert;
188 struct dijk_edge *edge;
190 vnode = list_get_head(vertex_list);
192 // loop through all vertices
194 while (vnode != NULL)
198 enode = list_get_head(&vert->edge_list);
200 // loop through all edges of the current vertex
202 while (enode != NULL)
206 enode = list_get_next(enode);
210 vnode = list_get_next(vnode);
215 // XXX - bad complexity
217 static struct dijk_vertex *extract_best(struct list *vertex_list)
219 float best_etx = INFINITE_ETX + 1.0;
220 struct list_node *node;
221 struct dijk_vertex *vert;
222 struct dijk_vertex *res = NULL;
224 node = list_get_head(vertex_list);
226 // loop through all vertices
232 // see whether the current vertex is better than what we have
234 if (!vert->done && vert->path_etx < best_etx)
236 best_etx = vert->path_etx;
240 node = list_get_next(node);
243 // if we've found a vertex, remove it from the set
246 res->done = OLSR_TRUE;
251 static void relax(struct dijk_vertex *vert)
253 struct dijk_edge *edge;
255 struct list_node *node;
257 node = list_get_head(&vert->edge_list);
259 // loop through all edges of this vertex
265 // total quality of the path through this vertex to the
266 // destination of this edge
268 new_etx = vert->path_etx + edge->etx;
270 // if it's better than the current path quality of this
271 // edge's destination, then we've found a better path to
274 if (new_etx < edge->dest->path_etx)
276 edge->dest->path_etx = new_etx;
277 edge->dest->prev = vert;
280 node = list_get_next(node);
284 static char *etx_to_string(float etx)
286 static char buff[20];
288 if (etx == INFINITE_ETX)
291 sprintf(buff, "%.2f", etx);
295 void olsr_calculate_lq_routing_table(void)
297 struct list vertex_list;
299 struct tc_entry *tcsrc;
300 struct topo_dst *tcdst;
301 struct dijk_vertex *vert;
302 struct link_entry *link;
303 struct neighbor_entry *neigh;
304 struct list_node *node;
305 struct dijk_vertex *myself;
306 struct dijk_vertex *walker;
308 struct mid_address *mid_walker;
310 struct hna_entry *hna_gw;
312 struct rt_entry *gw_rt, *hna_rt, *head_rt;
314 // initialize the graph
316 list_init(&vertex_list);
318 // add ourselves to the vertex list
320 add_vertex(&vertex_list, &main_addr, 0.0);
322 // add our neighbours
324 for (i = 0; i < HASHSIZE; i++)
325 for (neigh = neighbortable[i].next; neigh != &neighbortable[i];
327 if (neigh->status == SYM)
328 add_vertex(&vertex_list, &neigh->neighbor_main_addr, INFINITE_ETX);
330 // add remaining vertices
332 for (i = 0; i < HASHSIZE; i++)
333 for (tcsrc = tc_table[i].next; tcsrc != &tc_table[i]; tcsrc = tcsrc->next)
337 add_vertex(&vertex_list, &tcsrc->T_last_addr, INFINITE_ETX);
339 // add destinations of this source
341 for (tcdst = tcsrc->destinations.next; tcdst != &tcsrc->destinations;
343 add_vertex(&vertex_list, &tcdst->T_dest_addr, INFINITE_ETX);
346 // add edges to and from our neighbours
348 for (i = 0; i < HASHSIZE; i++)
349 for (neigh = neighbortable[i].next; neigh != &neighbortable[i];
351 if (neigh->status == SYM)
353 link = olsr_neighbor_best_link(&neigh->neighbor_main_addr);
355 if (link->loss_link_quality >= MIN_LINK_QUALITY &&
356 link->neigh_link_quality >= MIN_LINK_QUALITY)
358 etx = 1.0 / (link->loss_link_quality * link->neigh_link_quality);
360 add_edge(&vertex_list, &main_addr, &neigh->neighbor_main_addr,
363 add_edge(&vertex_list, &neigh->neighbor_main_addr, &main_addr,
368 // add remaining edges
370 for (i = 0; i < HASHSIZE; i++)
371 for (tcsrc = tc_table[i].next; tcsrc != &tc_table[i]; tcsrc = tcsrc->next)
372 for (tcdst = tcsrc->destinations.next; tcdst != &tcsrc->destinations;
375 if (tcdst->link_quality >= MIN_LINK_QUALITY &&
376 tcdst->inverse_link_quality >= MIN_LINK_QUALITY)
378 etx = 1.0 / (tcdst->link_quality * tcdst->inverse_link_quality);
380 add_edge(&vertex_list, &tcsrc->T_last_addr, &tcdst->T_dest_addr,
383 add_edge(&vertex_list, &tcdst->T_dest_addr, &tcsrc->T_last_addr,
388 // run Dijkstra's algorithm
392 vert = extract_best(&vertex_list);
400 // save the old routing table
402 olsr_move_route_table(routingtable, old_routes);
404 node = list_get_head(&vertex_list);
406 // we're the first vertex in the list
410 olsr_printf(2, "\n--- %02d:%02d:%02d.%02d ------------------------------------------------- DIJKSTRA\n\n",
416 for (node = list_get_next(node); node != NULL; node = list_get_next(node))
422 // count hops to until the path ends or until we have reached a
425 for (walker = vert; walker != NULL && walker->prev != myself;
426 walker = walker->prev)
428 olsr_printf(2, "%s:%s <- ", olsr_ip_to_string(&walker->addr),
429 etx_to_string(walker->path_etx));
433 // if no path to a one-hop neighbour was found, ignore this node
437 olsr_printf(2, "%s:%s (one-hop)\n", olsr_ip_to_string(&walker->addr),
438 etx_to_string(walker->path_etx));
440 // node reachable => add to the set of unprocessed nodes
441 // for HNA processing
443 vert->done = OLSR_FALSE;
448 olsr_printf(2, "FAILED\n", olsr_ip_to_string(&vert->addr));
452 #if defined linux && 0
454 * on Linux we can add a new route for a destination before removing
455 * the old route, so frequent route updates are not a problem, as
456 * we never have a time window in which there isn't any route; hence
457 * we can use the more volatile ETX value instead of the hop count
460 hops = (int)vert->path_etx;
466 // add a route to the main address of the destination node
468 olsr_insert_routing_table(&vert->addr,
469 get_neighbor_nexthop(&walker->addr), hops);
471 // add routes to the remaining interfaces of the destination node
473 for (mid_walker = mid_lookup_aliases(&vert->addr); mid_walker != NULL;
474 mid_walker = mid_walker->next_alias)
475 olsr_insert_routing_table(&mid_walker->alias,
476 get_neighbor_nexthop(&walker->addr), hops);
479 // add HNA routes - the set of unprocessed network nodes contains
480 // all reachable network nodes
484 // extract the network node with the best ETX and remove it
485 // from the set of unprocessed network nodes
487 vert = extract_best(&vertex_list);
489 // no more nodes left
494 // find the node's HNAs
496 hna_gw = olsr_lookup_hna_gw(&vert->addr);
498 // node doesn't announce any HNAs
503 // loop through the node's HNAs
505 for (hna = hna_gw->networks.next; hna != &hna_gw->networks;
508 // we already have a route via a previous (better) node
510 if (olsr_lookup_routing_table(&hna->A_network_addr) != NULL)
513 // find route to the node
515 gw_rt = olsr_lookup_routing_table(&hna_gw->A_gateway_addr);
517 // should never happen as we only process reachable nodes
521 fprintf(stderr, "LQ HNA processing: Gateway without a route.");
525 // create route for the HNA
527 hna_rt = olsr_malloc(sizeof(struct rt_entry), "LQ HNA route entry");
529 // set HNA IP address and netmask
531 COPY_IP(&hna_rt->rt_dst, &hna->A_network_addr);
532 hna_rt->rt_mask = hna->A_netmask;
534 // copy remaining fields from the node's route
536 COPY_IP(&hna_rt->rt_router, &gw_rt->rt_router);
537 hna_rt->rt_metric = gw_rt->rt_metric;
538 hna_rt->rt_if = gw_rt->rt_if;
540 // we're not a host route
542 hna_rt->rt_flags = RTF_UP | RTF_GATEWAY;
544 // find the correct list
546 head_rt = &routingtable[olsr_hashing(&hna->A_network_addr)];
550 head_rt->next->prev = hna_rt;
551 hna_rt->next = head_rt->next;
553 head_rt->next = hna_rt;
554 hna_rt->prev = head_rt;
560 free_everything(&vertex_list);
562 // move the route changes into the kernel
564 olsr_update_kernel_routes();
566 // free the saved routing table
568 olsr_free_routing_table(old_routes);