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

   1 /*
   2     graph.c -- graph algorithms
   3     Copyright (C) 2001-2003 Guus Sliepen <guus@sliepen.eu.org>,
   4                   2001-2003 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.24 2003/07/12 17:41:45 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 <string.h>
  51 #ifdef HAVE_SYS_PARAM_H
  52 #include <sys/param.h>
  53 #endif
  54 #include <netinet/in.h>
  55
  56 #include <avl_tree.h>
  57 #include <utils.h>
  58
  59 #include "netutl.h"
  60 #include "node.h"
  61 #include "edge.h"
  62 #include "connection.h"
  63 #include "process.h"
  64 #include "device.h"
  65 #include "logger.h"
  66
  67 #include "system.h"
  68
  69 /* Implementation of Kruskal's algorithm.
  70    Running time: O(EN)
  71    Please note that sorting on weight is already done by add_edge().
  72 */
  73
  74 void mst_kruskal(void)
  75 {
  76         avl_node_t *node, *next;
  77         edge_t *e;
  78         node_t *n;
  79         connection_t *c;
  80         int nodes = 0;
  81         int safe_edges = 0;
  82         int skipped;
  83
  84         cp();
  85
  86         /* Clear MST status on connections */
  87
  88         for(node = connection_tree->head; node; node = node->next) {
  89                 c = (connection_t *) node->data;
  90                 c->status.mst = 0;
  91         }
  92
  93         /* Do we have something to do at all? */
  94
  95         if(!edge_weight_tree->head)
  96                 return;
  97
  98         ifdebug(SCARY_THINGS) logger(LOG_DEBUG, "Running Kruskal's algorithm:");
  99
 100         /* Clear visited status on nodes */
 101
 102         for(node = node_tree->head; node; node = node->next) {
 103                 n = (node_t *) node->data;
 104                 n->status.visited = 0;
 105                 nodes++;
 106         }
 107
 108         /* Starting point */
 109
 110         ((edge_t *) edge_weight_tree->head->data)->from->status.visited = 1;
 111
 112         /* Add safe edges */
 113
 114         for(skipped = 0, node = edge_weight_tree->head; node; node = next) {
 115                 next = node->next;
 116                 e = (edge_t *) node->data;
 117
 118                 if(!e->reverse || e->from->status.visited == e->to->status.visited) {
 119                         skipped = 1;
 120                         continue;
 121                 }
 122
 123                 e->from->status.visited = 1;
 124                 e->to->status.visited = 1;
 125
 126                 if(e->connection)
 127                         e->connection->status.mst = 1;
 128
 129                 if(e->reverse->connection)
 130                         e->reverse->connection->status.mst = 1;
 131
 132                 safe_edges++;
 133
 134                 ifdebug(SCARY_THINGS) logger(LOG_DEBUG, " Adding edge %s - %s weight %d", e->from->name,
 135                                    e->to->name, e->weight);
 136
 137                 if(skipped) {
 138                         skipped = 0;
 139                         next = edge_weight_tree->head;
 140                         continue;
 141                 }
 142         }
 143
 144         ifdebug(SCARY_THINGS) logger(LOG_DEBUG, "Done, counted %d nodes and %d safe edges.", nodes,
 145                            safe_edges);
 146 }
 147
 148 /* Implementation of a simple breadth-first search algorithm.
 149    Running time: O(E)
 150 */
 151
 152 void sssp_bfs(void)
 153 {
 154         avl_node_t *node, *from, *next, *to;
 155         edge_t *e;
 156         node_t *n;
 157         avl_tree_t *todo_tree;
 158         int indirect;
 159         char *name;
 160         char *address, *port;
 161         char *envp[7];
 162         int i;
 163
 164         cp();
 165
 166         todo_tree = avl_alloc_tree(NULL, NULL);
 167
 168         /* Clear visited status on nodes */
 169
 170         for(node = node_tree->head; node; node = node->next) {
 171                 n = (node_t *) node->data;
 172                 n->status.visited = 0;
 173                 n->status.indirect = 1;
 174         }
 175
 176         /* Begin with myself */
 177
 178         myself->status.visited = 1;
 179         myself->status.indirect = 0;
 180         myself->nexthop = myself;
 181         myself->via = myself;
 182         node = avl_alloc_node();
 183         node->data = myself;
 184         avl_insert_top(todo_tree, node);
 185
 186         /* Loop while todo_tree is filled */
 187
 188         while(todo_tree->head) {
 189                 for(from = todo_tree->head; from; from = next) {        /* "from" is the node from which we start */
 190                         next = from->next;
 191                         n = (node_t *) from->data;
 192
 193                         for(to = n->edge_tree->head; to; to = to->next) {       /* "to" is the edge connected to "from" */
 194                                 e = (edge_t *) to->data;
 195
 196                                 if(!e->reverse)
 197                                         continue;
 198
 199                                 /* Situation:
 200
 201                                     /
 202                                    /
 203                                    ------(n)-----(e->to)
 204                                    \
 205                                     \
 206
 207                                    n->address is set to the e->address of the edge left of n to n.
 208                                    We are currently examining the edge e right of n from n:
 209
 210                                    - If e->reverse->address != n->address, then e->to is probably
 211                                      not reachable for the nodes left of n. We do as if the indirectdata
 212                                      flag is set on edge e.
 213                                    - If edge e provides for better reachability of e->to, update
 214                                      e->to and (re)add it to the todo_tree to (re)examine the reachability
 215                                      of nodes behind it.
 216                                  */
 217
 218                                 indirect = n->status.indirect || e->options & OPTION_INDIRECT
 219                                         || ((n != myself) && sockaddrcmp(&n->address, &e->reverse->address));
 220
 221                                 if(e->to->status.visited
 222                                    && (!e->to->status.indirect || indirect))
 223                                         continue;
 224
 225                                 e->to->status.visited = 1;
 226                                 e->to->status.indirect = indirect;
 227                                 e->to->nexthop = (n->nexthop == myself) ? e->to : n->nexthop;
 228                                 e->to->via = indirect ? n->via : e->to;
 229                                 e->to->options = e->options;
 230
 231                                 if(sockaddrcmp(&e->to->address, &e->address)) {
 232                                         node = avl_unlink(node_udp_tree, e->to);
 233                                         e->to->address = e->address;
 234
 235                                         if(e->to->hostname)
 236                                                 free(e->to->hostname);
 237
 238                                         e->to->hostname = sockaddr2hostname(&e->to->address);
 239                                         avl_insert_node(node_udp_tree, node);
 240                                 }
 241
 242                                 node = avl_alloc_node();
 243                                 node->data = e->to;
 244                                 avl_insert_before(todo_tree, from, node);
 245                         }
 246
 247                         avl_delete_node(todo_tree, from);
 248                 }
 249         }
 250
 251         avl_free_tree(todo_tree);
 252
 253         /* Check reachability status. */
 254
 255         for(node = node_tree->head; node; node = next) {
 256                 next = node->next;
 257                 n = (node_t *) node->data;
 258
 259                 if(n->status.visited != n->status.reachable) {
 260                         n->status.reachable = !n->status.reachable;
 261
 262                         if(n->status.reachable) {
 263                                 ifdebug(TRAFFIC) logger(LOG_DEBUG, _("Node %s (%s) became reachable"),
 264                                            n->name, n->hostname);
 265                         } else {
 266                                 ifdebug(TRAFFIC) logger(LOG_DEBUG, _("Node %s (%s) became unreachable"),
 267                                            n->name, n->hostname);
 268                         }
 269
 270                         n->status.validkey = 0;
 271                         n->status.waitingforkey = 0;
 272
 273                         asprintf(&envp[0], "NETNAME=%s", netname ? : "");
 274                         asprintf(&envp[1], "DEVICE=%s", device ? : "");
 275                         asprintf(&envp[2], "INTERFACE=%s", interface ? : "");
 276                         asprintf(&envp[3], "NODE=%s", n->name);
 277                         sockaddr2str(&n->address, &address, &port);
 278                         asprintf(&envp[4], "REMOTEADDRESS=%s", address);
 279                         asprintf(&envp[5], "REMOTEPORT=%s", port);
 280                         envp[6] = NULL;
 281
 282                         asprintf(&name,
 283                                          n->status.reachable ? "hosts/%s-up" : "hosts/%s-down",
 284                                          n->name);
 285                         execute_script(name, envp);
 286
 287                         free(name);
 288                         free(address);
 289                         free(port);
 290
 291                         for(i = 0; i < 7; i++)
 292                                 free(envp[i]);
 293                 }
 294         }
 295 }
 296
 297 void graph(void)
 298 {
 299         mst_kruskal();
 300         sssp_bfs();
 301 }