www.tinc-vpn.org Git - tinc/blob - src/graph.c

   1 /*
   2     graph.c -- graph algorithms
   3     Copyright (C) 2001-2002 Guus Sliepen <guus@sliepen.eu.org>,
   4                   2001-2002 Ivo Timmermans <ivo@o2w.nl>
   5
   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.
  10
  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.
  15
  16     You should have received a copy of the GNU General Public License
  17     along with this program; if not, write to the Free Software
  18     Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  19
  20     $Id: graph.c,v 1.1.2.19 2002/09/09 21:24:34 guus Exp $
  21 */
  22
  23 /* We need to generate two trees from the graph:
  24
  25    1. A minimum spanning tree for broadcasts,
  26    2. A single-source shortest path tree for unicasts.
  27
  28    Actually, the first one alone would suffice but would make unicast packets
  29    take longer routes than necessary.
  30
  31    For the MST algorithm we can choose from Prim's or Kruskal's. I personally
  32    favour Kruskal's, because we make an extra AVL tree of edges sorted on
  33    weights (metric). That tree only has to be updated when an edge is added or
  34    removed, and during the MST algorithm we just have go linearly through that
  35    tree, adding safe edges until #edges = #nodes - 1. The implementation here
  36    however is not so fast, because I tried to avoid having to make a forest and
  37    merge trees.
  38
  39    For the SSSP algorithm Dijkstra's seems to be a nice choice. Currently a
  40    simple breadth-first search is presented here.
  41
  42    The SSSP algorithm will also be used to determine whether nodes are directly,
  43    indirectly or not reachable from the source. It will also set the correct
  44    destination address and port of a node if possible.
  45 */
  46
  47 #include "config.h"
  48
  49 #include <stdio.h>
  50 #include <syslog.h>
  51 #include "config.h"
  52 #include <string.h>
  53 #ifdef HAVE_SYS_PARAM_H
  54 #include <sys/param.h>
  55 #endif
  56 #include <netinet/in.h>
  57
  58 #include <avl_tree.h>
  59 #include <utils.h>
  60
  61 #include "netutl.h"
  62 #include "node.h"
  63 #include "edge.h"
  64 #include "connection.h"
  65 #include "process.h"
  66 #include "device.h"
  67
  68 #include "system.h"
  69
  70 /* Implementation of Kruskal's algorithm.
  71    Running time: O(EN)
  72    Please note that sorting on weight is already done by add_edge().
  73 */
  74
  75 void mst_kruskal(void)
  76 {
  77         avl_node_t *node, *next;
  78         edge_t *e;
  79         node_t *n;
  80         connection_t *c;
  81         int nodes = 0;
  82         int safe_edges = 0;
  83         int skipped;
  84
  85         cp();
  86
  87         /* Clear MST status on connections */
  88
  89         for(node = connection_tree->head; node; node = node->next) {
  90                 c = (connection_t *) node->data;
  91                 c->status.mst = 0;
  92         }
  93
  94         /* Do we have something to do at all? */
  95
  96         if(!edge_weight_tree->head)
  97                 return;
  98
  99         if(debug_lvl >= DEBUG_SCARY_THINGS)
 100                 syslog(LOG_DEBUG, "Running Kruskal's algorithm:");
 101
 102         /* Clear visited status on nodes */
 103
 104         for(node = node_tree->head; node; node = node->next) {
 105                 n = (node_t *) node->data;
 106                 n->status.visited = 0;
 107                 nodes++;
 108         }
 109
 110         /* Starting point */
 111
 112         ((edge_t *) edge_weight_tree->head->data)->from->status.visited = 1;
 113
 114         /* Add safe edges */
 115
 116         for(skipped = 0, node = edge_weight_tree->head; node; node = next) {
 117                 next = node->next;
 118                 e = (edge_t *) node->data;
 119
 120                 if(!e->reverse || e->from->status.visited == e->to->status.visited) {
 121                         skipped = 1;
 122                         continue;
 123                 }
 124
 125                 e->from->status.visited = 1;
 126                 e->to->status.visited = 1;
 127
 128                 if(e->connection)
 129                         e->connection->status.mst = 1;
 130
 131                 if(e->reverse->connection)
 132                         e->reverse->connection->status.mst = 1;
 133
 134                 safe_edges++;
 135
 136                 if(debug_lvl >= DEBUG_SCARY_THINGS)
 137                         syslog(LOG_DEBUG, " Adding edge %s - %s weight %d", e->from->name,
 138                                    e->to->name, e->weight);
 139
 140                 if(skipped) {
 141                         skipped = 0;
 142                         next = edge_weight_tree->head;
 143                         continue;
 144                 }
 145         }
 146
 147         if(debug_lvl >= DEBUG_SCARY_THINGS)
 148                 syslog(LOG_DEBUG, "Done, counted %d nodes and %d safe edges.", nodes,
 149                            safe_edges);
 150 }
 151
 152 /* Implementation of a simple breadth-first search algorithm.
 153    Running time: O(E)
 154 */
 155
 156 void sssp_bfs(void)
 157 {
 158         avl_node_t *node, *from, *next, *to;
 159         edge_t *e;
 160         node_t *n;
 161         avl_tree_t *todo_tree;
 162         int indirect;
 163         char *name;
 164         char *address, *port;
 165         char *envp[7];
 166         int i;
 167
 168         cp();
 169
 170         todo_tree = avl_alloc_tree(NULL, NULL);
 171
 172         /* Clear visited status on nodes */
 173
 174         for(node = node_tree->head; node; node = node->next) {
 175                 n = (node_t *) node->data;
 176                 n->status.visited = 0;
 177                 n->status.indirect = 1;
 178         }
 179
 180         /* Begin with myself */
 181
 182         myself->status.visited = 1;
 183         myself->status.indirect = 0;
 184         myself->nexthop = myself;
 185         myself->via = myself;
 186         node = avl_alloc_node();
 187         node->data = myself;
 188         avl_insert_top(todo_tree, node);
 189
 190         /* Loop while todo_tree is filled */
 191
 192         while(todo_tree->head) {
 193                 for(from = todo_tree->head; from; from = next) {        /* "from" is the node from which we start */
 194                         next = from->next;
 195                         n = (node_t *) from->data;
 196
 197                         for(to = n->edge_tree->head; to; to = to->next) {       /* "to" is the edge connected to "from" */
 198                                 e = (edge_t *) to->data;
 199
 200                                 if(!e->reverse)
 201                                         continue;
 202
 203                                 /* Situation:
 204
 205                                    /
 206                                    /
 207                                    ------(n)-----(e->to)
 208                                    \
 209                                    \
 210
 211                                    n->address is set to the e->address of the edge left of n to n.
 212                                    We are currently examining the edge e right of n from n:
 213
 214                                    - If e->reverse->address != n->address, then e->to is probably
 215                                    not reachable for the nodes left of n. We do as if the indirectdata
 216                                    flag is set on edge e.
 217                                    - If edge e provides for better reachability of e->to, update
 218                                    e->to and (re)add it to the todo_tree to (re)examine the reachability
 219                                    of nodes behind it.
 220                                  */
 221
 222                                 indirect = n->status.indirect || e->options & OPTION_INDIRECT
 223                                         || ((n != myself)
 224                                                 && sockaddrcmp(&n->address, &e->reverse->address));
 225
 226                                 if(e->to->status.visited
 227                                    && (!e->to->status.indirect || indirect))
 228                                         continue;
 229
 230                                 e->to->status.visited = 1;
 231                                 e->to->status.indirect = indirect;
 232                                 e->to->nexthop = (n->nexthop == myself) ? e->to : n->nexthop;
 233                                 e->to->via = indirect ? n->via : e->to;
 234                                 e->to->options = e->options;
 235
 236                                 if(sockaddrcmp(&e->to->address, &e->address)) {
 237                                         node = avl_unlink(node_udp_tree, e->to);
 238                                         e->to->address = e->address;
 239
 240                                         if(e->to->hostname)
 241                                                 free(e->to->hostname);
 242
 243                                         e->to->hostname = sockaddr2hostname(&e->to->address);
 244                                         avl_insert_node(node_udp_tree, node);
 245                                 }
 246
 247                                 node = avl_alloc_node();
 248                                 node->data = e->to;
 249                                 avl_insert_before(todo_tree, from, node);
 250                         }
 251
 252                         avl_delete_node(todo_tree, from);
 253                 }
 254         }
 255
 256         avl_free_tree(todo_tree);
 257
 258         /* Check reachability status. */
 259
 260         for(node = node_tree->head; node; node = next) {
 261                 next = node->next;
 262                 n = (node_t *) node->data;
 263
 264                 if(n->status.visited != n->status.reachable) {
 265                         n->status.reachable = !n->status.reachable;
 266
 267                         if(debug_lvl >= DEBUG_TRAFFIC)
 268                                 if(n->status.reachable)
 269                                         syslog(LOG_DEBUG, _("Node %s (%s) became reachable"),
 270                                                    n->name, n->hostname);
 271                                 else
 272                                         syslog(LOG_DEBUG, _("Node %s (%s) became unreachable"),
 273                                                    n->name, n->hostname);
 274
 275                         n->status.validkey = 0;
 276                         n->status.waitingforkey = 0;
 277
 278                         asprintf(&envp[0], "NETNAME=%s", netname ? : "");
 279                         asprintf(&envp[1], "DEVICE=%s", device ? : "");
 280                         asprintf(&envp[2], "INTERFACE=%s", interface ? : "");
 281                         asprintf(&envp[3], "NODE=%s", n->name);
 282                         sockaddr2str(&n->address, &address, &port);
 283                         asprintf(&envp[4], "REMOTEADDRESS=%s", address);
 284                         asprintf(&envp[5], "REMOTEPORT=%s", port);
 285                         envp[6] = NULL;
 286
 287                         asprintf(&name,
 288                                          n->status.reachable ? "hosts/%s-up" : "hosts/%s-down",
 289                                          n->name);
 290                         execute_script(name, envp);
 291
 292                         free(name);
 293                         free(address);
 294                         free(port);
 295
 296                         for(i = 0; i < 7; i++)
 297                                 free(envp[i]);
 298                 }
 299         }
 300 }
 301
 302 void graph(void)
 303 {
 304         mst_kruskal();
 305         sssp_bfs();
 306 }