2 graph.c -- graph algorithms
3 Copyright (C) 2001-2014 Guus Sliepen <guus@tinc-vpn.org>,
4 2001-2005 Ivo Timmermans
6 This program is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2 of the License, or
9 (at your option) any later version.
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License along
17 with this program; if not, write to the Free Software Foundation, Inc.,
18 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
21 /* We need to generate two trees from the graph:
23 1. A minimum spanning tree for broadcasts,
24 2. A single-source shortest path tree for unicasts.
26 Actually, the first one alone would suffice but would make unicast packets
27 take longer routes than necessary.
29 For the MST algorithm we can choose from Prim's or Kruskal's. I personally
30 favour Kruskal's, because we make an extra AVL tree of edges sorted on
31 weights (metric). That tree only has to be updated when an edge is added or
32 removed, and during the MST algorithm we just have go linearly through that
33 tree, adding safe edges until #edges = #nodes - 1. The implementation here
34 however is not so fast, because I tried to avoid having to make a forest and
37 For the SSSP algorithm Dijkstra's seems to be a nice choice. Currently a
38 simple breadth-first search is presented here.
40 The SSSP algorithm will also be used to determine whether nodes are directly,
41 indirectly or not reachable from the source. It will also set the correct
42 destination address and port of a node if possible.
49 #include "connection.h"
62 static bool graph_changed = true;
64 /* Implementation of Kruskal's algorithm.
66 Please note that sorting on weight is already done by add_edge().
69 static void mst_kruskal(void) {
70 avl_node_t *node, *next;
78 /* Clear MST status on connections */
80 for(node = connection_tree->head; node; node = node->next) {
82 c->status.mst = false;
85 /* Do we have something to do at all? */
87 if(!edge_weight_tree->head) {
91 ifdebug(SCARY_THINGS) logger(LOG_DEBUG, "Running Kruskal's algorithm:");
93 /* Clear visited status on nodes */
95 for(node = node_tree->head; node; node = node->next) {
97 n->status.visited = false;
103 for(node = edge_weight_tree->head; node; node = node->next) {
106 if(e->from->status.reachable) {
107 e->from->status.visited = true;
114 for(skipped = false, node = edge_weight_tree->head; node; node = next) {
118 if(!e->reverse || e->from->status.visited == e->to->status.visited) {
123 e->from->status.visited = true;
124 e->to->status.visited = true;
127 e->connection->status.mst = true;
130 if(e->reverse->connection) {
131 e->reverse->connection->status.mst = true;
136 ifdebug(SCARY_THINGS) logger(LOG_DEBUG, " Adding edge %s - %s weight %d", e->from->name,
137 e->to->name, e->weight);
141 next = edge_weight_tree->head;
146 ifdebug(SCARY_THINGS) logger(LOG_DEBUG, "Done, counted %d nodes and %d safe edges.", nodes,
150 /* Implementation of a simple breadth-first search algorithm.
154 static void sssp_bfs(void) {
155 avl_node_t *node, *next, *to;
159 list_node_t *from, *todonext;
162 char *address, *port;
163 char *envp[8] = {NULL};
166 todo_list = list_alloc(NULL);
168 /* Clear visited status on nodes */
170 for(node = node_tree->head; node; node = node->next) {
172 n->status.visited = false;
173 n->status.indirect = true;
176 /* Begin with myself */
178 myself->status.visited = true;
179 myself->status.indirect = false;
180 myself->nexthop = myself;
181 myself->prevedge = NULL;
182 myself->via = myself;
183 list_insert_head(todo_list, myself);
185 /* Loop while todo_list is filled */
187 for(from = todo_list->head; from; from = todonext) { /* "from" is the node from which we start */
190 for(to = n->edge_tree->head; to; to = to->next) { /* "to" is the edge connected to "from" */
201 ----->(n)---e-->(e->to)
205 Where e is an edge, (n) and (e->to) are nodes.
206 n->address is set to the e->address of the edge left of n to n.
207 We are currently examining the edge e right of n from n:
209 - If edge e provides for better reachability of e->to, update
210 e->to and (re)add it to the todo_list to (re)examine the reachability
214 indirect = n->status.indirect || e->options & OPTION_INDIRECT;
216 if(e->to->status.visited
217 && (!e->to->status.indirect || indirect)) {
221 // Only update nexthop the first time we visit this node.
223 if(!e->to->status.visited) {
224 e->to->nexthop = (n->nexthop == myself) ? e->to : n->nexthop;
227 e->to->status.visited = true;
228 e->to->status.indirect = indirect;
230 e->to->via = indirect ? n->via : e->to;
231 e->to->options = e->options;
233 if(e->to->address.sa.sa_family == AF_UNSPEC && e->address.sa.sa_family != AF_UNKNOWN) {
234 update_node_udp(e->to, &e->address);
237 list_insert_tail(todo_list, e->to);
240 todonext = from->next;
241 list_delete_node(todo_list, from);
244 list_free(todo_list);
246 /* Check reachability status. */
248 for(node = node_tree->head; node; node = next) {
252 if(n->status.visited != n->status.reachable) {
253 n->status.reachable = !n->status.reachable;
255 if(n->status.reachable) {
256 ifdebug(TRAFFIC) logger(LOG_DEBUG, "Node %s (%s) became reachable",
257 n->name, n->hostname);
259 ifdebug(TRAFFIC) logger(LOG_DEBUG, "Node %s (%s) became unreachable",
260 n->name, n->hostname);
263 /* TODO: only clear status.validkey if node is unreachable? */
265 n->status.validkey = false;
273 event_del(n->mtuevent);
277 xasprintf(&envp[0], "NETNAME=%s", netname ? netname : "");
278 xasprintf(&envp[1], "DEVICE=%s", device ? device : "");
279 xasprintf(&envp[2], "INTERFACE=%s", iface ? iface : "");
280 xasprintf(&envp[3], "NODE=%s", n->name);
281 sockaddr2str(&n->address, &address, &port);
282 xasprintf(&envp[4], "REMOTEADDRESS=%s", address);
283 xasprintf(&envp[5], "REMOTEPORT=%s", port);
284 xasprintf(&envp[6], "NAME=%s", myself->name);
286 execute_script(n->status.reachable ? "host-up" : "host-down", envp);
289 n->status.reachable ? "hosts/%s-up" : "hosts/%s-down",
291 execute_script(name, envp);
297 for(i = 0; i < 7; i++) {
301 subnet_update(n, NULL, n->status.reachable);
303 if(!n->status.reachable) {
304 update_node_udp(n, NULL);
305 memset(&n->status, 0, sizeof(n->status));
307 } else if(n->connection) {
315 subnet_cache_flush();
318 graph_changed = true;
323 /* Dump nodes and edges to a graphviz file.
325 The file can be converted to an image with
326 dot -Tpng graph_filename -o image_filename.png -Gconcentrate=true
329 void dump_graph(void) {
333 char *filename = NULL, *tmpname = NULL;
334 FILE *file, *pipe = NULL;
336 if(!graph_changed || !get_config_string(lookup_config(config_tree, "GraphDumpFile"), &filename)) {
340 graph_changed = false;
342 ifdebug(PROTOCOL) logger(LOG_NOTICE, "Dumping graph");
344 if(filename[0] == '|') {
345 file = pipe = popen(filename + 1, "w");
347 xasprintf(&tmpname, "%s.new", filename);
348 file = fopen(tmpname, "w");
352 logger(LOG_ERR, "Unable to open graph dump file %s: %s", filename, strerror(errno));
358 fprintf(file, "digraph {\n");
360 /* dump all nodes first */
361 for(node = node_tree->head; node; node = node->next) {
363 fprintf(file, " \"%s\" [label = \"%s\"];\n", n->name, n->name);
366 /* now dump all edges */
367 for(node = edge_weight_tree->head; node; node = node->next) {
369 fprintf(file, " \"%s\" -> \"%s\";\n", e->from->name, e->to->name);
372 fprintf(file, "}\n");
382 if(rename(tmpname, filename)) {
383 logger(LOG_ERR, "Could not rename %s to %s: %s\n", tmpname, filename, strerror(errno));