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

   1 /*
   2     graph.c -- graph algorithms
   3     Copyright (C) 2001-2011 Guus Sliepen <guus@tinc-vpn.org>,
   4                   2001-2005 Ivo Timmermans
   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 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.
  19 */
  20
  21 /* We need to generate two trees from the graph:
  22
  23    1. A minimum spanning tree for broadcasts,
  24    2. A single-source shortest path tree for unicasts.
  25
  26    Actually, the first one alone would suffice but would make unicast packets
  27    take longer routes than necessary.
  28
  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
  35    merge trees.
  36
  37    For the SSSP algorithm Dijkstra's seems to be a nice choice. Currently a
  38    simple breadth-first search is presented here.
  39
  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.
  43 */
  44
  45 #include "system.h"
  46
  47 #include "splay_tree.h"
  48 #include "config.h"
  49 #include "connection.h"
  50 #include "device.h"
  51 #include "edge.h"
  52 #include "logger.h"
  53 #include "netutl.h"
  54 #include "node.h"
  55 #include "process.h"
  56 #include "protocol.h"
  57 #include "subnet.h"
  58 #include "utils.h"
  59 #include "xalloc.h"
  60 #include "graph.h"
  61
  62 /* Implementation of Kruskal's algorithm.
  63    Running time: O(E)
  64    Please note that sorting on weight is already done by add_edge().
  65 */
  66
  67 void mst_kruskal(void) {
  68         splay_node_t *node, *next;
  69         edge_t *e;
  70         node_t *n;
  71         connection_t *c;
  72
  73         /* Clear MST status on connections */
  74
  75         for(node = connection_tree->head; node; node = node->next) {
  76                 c = node->data;
  77                 c->status.mst = false;
  78         }
  79
  80         ifdebug(SCARY_THINGS) logger(LOG_DEBUG, "Running Kruskal's algorithm:");
  81
  82         /* Clear visited status on nodes */
  83
  84         for(node = node_tree->head; node; node = node->next) {
  85                 n = node->data;
  86                 n->status.visited = false;
  87         }
  88
  89         /* Add safe edges */
  90
  91         for(node = edge_weight_tree->head; node; node = next) {
  92                 next = node->next;
  93                 e = node->data;
  94
  95                 if(!e->reverse || (e->from->status.visited && e->to->status.visited))
  96                         continue;
  97
  98                 e->from->status.visited = true;
  99                 e->to->status.visited = true;
 100
 101                 if(e->connection)
 102                         e->connection->status.mst = true;
 103
 104                 if(e->reverse->connection)
 105                         e->reverse->connection->status.mst = true;
 106
 107                 ifdebug(SCARY_THINGS) logger(LOG_DEBUG, " Adding edge %s - %s weight %d", e->from->name,
 108                                    e->to->name, e->weight);
 109         }
 110 }
 111
 112 /* Implementation of Dijkstra's algorithm.
 113    Running time: O(N^2)
 114 */
 115
 116 static void sssp_dijkstra(void) {
 117         splay_node_t *node, *to;
 118         edge_t *e;
 119         node_t *n, *m;
 120         list_t *todo_list;
 121         list_node_t *lnode, *nnode;
 122         bool indirect;
 123
 124         todo_list = list_alloc(NULL);
 125
 126         ifdebug(SCARY_THINGS) logger(LOG_DEBUG, "Running Dijkstra's algorithm:");
 127
 128         /* Clear visited status on nodes */
 129
 130         for(node = node_tree->head; node; node = node->next) {
 131                 n = node->data;
 132                 n->status.visited = false;
 133                 n->status.indirect = true;
 134                 n->distance = -1;
 135         }
 136
 137         /* Begin with myself */
 138
 139         myself->status.indirect = false;
 140         myself->nexthop = myself;
 141         myself->via = myself;
 142         myself->distance = 0;
 143         list_insert_head(todo_list, myself);
 144
 145         /* Loop while todo_list is filled */
 146
 147         while(todo_list->head) {
 148                 n = NULL;
 149                 nnode = NULL;
 150
 151                 /* Select node from todo_list with smallest distance */
 152
 153                 for(lnode = todo_list->head; lnode; lnode = lnode->next) {
 154                         m = lnode->data;
 155                         if(!n || m->status.indirect < n->status.indirect || m->distance < n->distance) {
 156                                 n = m;
 157                                 nnode = lnode;
 158                         }
 159                 }
 160
 161                 /* Mark this node as visited and remove it from the todo_list */
 162
 163                 n->status.visited = true;
 164                 list_unlink_node(todo_list, nnode);
 165
 166                 /* Update distance of neighbours and add them to the todo_list */
 167
 168                 for(to = n->edge_tree->head; to; to = to->next) {       /* "to" is the edge connected to "from" */
 169                         e = to->data;
 170
 171                         if(e->to->status.visited || !e->reverse)
 172                                 continue;
 173
 174                         /* Situation:
 175
 176                                    /
 177                                   /
 178                            ----->(n)---e-->(e->to)
 179                                   \
 180                                    \
 181
 182                            Where e is an edge, (n) and (e->to) are nodes.
 183                            n->address is set to the e->address of the edge left of n to n.
 184                            We are currently examining the edge e right of n from n:
 185
 186                            - If e->reverse->address != n->address, then e->to is probably
 187                              not reachable for the nodes left of n. We do as if the indirectdata
 188                              flag is set on edge e.
 189                            - If edge e provides for better reachability of e->to, update e->to.
 190                          */
 191
 192                         if(e->to->distance < 0)
 193                                 list_insert_tail(todo_list, e->to);
 194
 195                         indirect = n->status.indirect || e->options & OPTION_INDIRECT || ((n != myself) && sockaddrcmp(&n->address, &e->reverse->address));
 196
 197                         if(e->to->distance >= 0 && (!e->to->status.indirect || indirect) && e->to->distance <= n->distance + e->weight)
 198                                 continue;
 199
 200                         e->to->distance = n->distance + e->weight;
 201                         e->to->status.indirect = indirect;
 202                         e->to->nexthop = (n->nexthop == myself) ? e->to : n->nexthop;
 203                         e->to->via = indirect ? n->via : e->to;
 204                         e->to->options = e->options;
 205
 206                         if(sockaddrcmp(&e->to->address, &e->address)) {
 207                                 node = splay_unlink(node_udp_tree, e->to);
 208                                 sockaddrfree(&e->to->address);
 209                                 sockaddrcpy(&e->to->address, &e->address);
 210
 211                                 if(e->to->hostname)
 212                                         free(e->to->hostname);
 213
 214                                 e->to->hostname = sockaddr2hostname(&e->to->address);
 215
 216                                 if(node)
 217                                         splay_insert_node(node_udp_tree, node);
 218
 219                                 if(e->to->options & OPTION_PMTU_DISCOVERY) {
 220                                         e->to->mtuprobes = 0;
 221                                         e->to->minmtu = 0;
 222                                         e->to->maxmtu = MTU;
 223                                         if(e->to->status.validkey)
 224                                                 send_mtu_probe(e->to);
 225                                 }
 226                         }
 227
 228                         ifdebug(SCARY_THINGS) logger(LOG_DEBUG, " Updating edge %s - %s weight %d distance %d", e->from->name,
 229                                            e->to->name, e->weight, e->to->distance);
 230                 }
 231         }
 232
 233         list_free(todo_list);
 234 }
 235
 236 /* Implementation of a simple breadth-first search algorithm.
 237    Running time: O(E)
 238 */
 239
 240 void sssp_bfs(void) {
 241         splay_node_t *node, *to;
 242         edge_t *e;
 243         node_t *n;
 244         list_t *todo_list;
 245         list_node_t *from, *todonext;
 246         bool indirect;
 247
 248         todo_list = list_alloc(NULL);
 249
 250         /* Clear visited status on nodes */
 251
 252         for(node = node_tree->head; node; node = node->next) {
 253                 n = node->data;
 254                 n->status.visited = false;
 255                 n->status.indirect = true;
 256         }
 257
 258         /* Begin with myself */
 259
 260         myself->status.visited = true;
 261         myself->status.indirect = false;
 262         myself->nexthop = myself;
 263         myself->via = myself;
 264         list_insert_head(todo_list, myself);
 265
 266         /* Loop while todo_list is filled */
 267
 268         for(from = todo_list->head; from; from = todonext) {    /* "from" is the node from which we start */
 269                 n = from->data;
 270
 271                 for(to = n->edge_tree->head; to; to = to->next) {       /* "to" is the edge connected to "from" */
 272                         e = to->data;
 273
 274                         if(!e->reverse)
 275                                 continue;
 276
 277                         /* Situation:
 278
 279                                    /
 280                                   /
 281                            ----->(n)---e-->(e->to)
 282                                   \
 283                                    \
 284
 285                            Where e is an edge, (n) and (e->to) are nodes.
 286                            n->address is set to the e->address of the edge left of n to n.
 287                            We are currently examining the edge e right of n from n:
 288
 289                            - If edge e provides for better reachability of e->to, update
 290                              e->to and (re)add it to the todo_list to (re)examine the reachability
 291                              of nodes behind it.
 292                          */
 293
 294                         indirect = n->status.indirect || e->options & OPTION_INDIRECT;
 295
 296                         if(e->to->status.visited
 297                            && (!e->to->status.indirect || indirect))
 298                                 continue;
 299
 300                         e->to->status.visited = true;
 301                         e->to->status.indirect = indirect;
 302                         e->to->nexthop = (n->nexthop == myself) ? e->to : n->nexthop;
 303                         e->to->via = indirect ? n->via : e->to;
 304                         e->to->options = e->options;
 305
 306                         if(e->to->address.sa.sa_family == AF_UNSPEC && e->address.sa.sa_family != AF_UNKNOWN)
 307                                 update_node_udp(e->to, &e->address);
 308
 309                         list_insert_tail(todo_list, e->to);
 310                 }
 311
 312                 todonext = from->next;
 313                 list_delete_node(todo_list, from);
 314         }
 315
 316         list_free(todo_list);
 317 }
 318
 319 static void check_reachability(void) {
 320         splay_node_t *node, *next;
 321         node_t *n;
 322         char *name;
 323         char *address, *port;
 324         char *envp[7];
 325         int i;
 326
 327         /* Check reachability status. */
 328
 329         for(node = node_tree->head; node; node = next) {
 330                 next = node->next;
 331                 n = node->data;
 332
 333                 if(n->status.visited != n->status.reachable) {
 334                         n->status.reachable = !n->status.reachable;
 335
 336                         if(n->status.reachable) {
 337                                 ifdebug(TRAFFIC) logger(LOG_DEBUG, "Node %s (%s) became reachable",
 338                                            n->name, n->hostname);
 339                         } else {
 340                                 ifdebug(TRAFFIC) logger(LOG_DEBUG, "Node %s (%s) became unreachable",
 341                                            n->name, n->hostname);
 342                         }
 343
 344                         /* TODO: only clear status.validkey if node is unreachable? */
 345
 346                         n->status.validkey = false;
 347                         n->last_req_key = 0;
 348
 349                         n->maxmtu = MTU;
 350                         n->minmtu = 0;
 351                         n->mtuprobes = 0;
 352
 353                         if(timeout_initialized(&n->mtuevent))
 354                                 event_del(&n->mtuevent);
 355
 356                         xasprintf(&envp[0], "NETNAME=%s", netname ? : "");
 357                         xasprintf(&envp[1], "DEVICE=%s", device ? : "");
 358                         xasprintf(&envp[2], "INTERFACE=%s", iface ? : "");
 359                         xasprintf(&envp[3], "NODE=%s", n->name);
 360                         sockaddr2str(&n->address, &address, &port);
 361                         xasprintf(&envp[4], "REMOTEADDRESS=%s", address);
 362                         xasprintf(&envp[5], "REMOTEPORT=%s", port);
 363                         envp[6] = NULL;
 364
 365                         execute_script(n->status.reachable ? "host-up" : "host-down", envp);
 366
 367                         xasprintf(&name,
 368                                          n->status.reachable ? "hosts/%s-up" : "hosts/%s-down",
 369                                          n->name);
 370                         execute_script(name, envp);
 371
 372                         free(name);
 373                         free(address);
 374                         free(port);
 375
 376                         for(i = 0; i < 6; i++)
 377                                 free(envp[i]);
 378
 379                         subnet_update(n, NULL, n->status.reachable);
 380
 381                         if(!n->status.reachable)
 382                                 update_node_udp(n, NULL);
 383                         else if(n->connection)
 384                                 send_ans_key(n);
 385                 }
 386         }
 387 }
 388
 389 void graph(void) {
 390         subnet_cache_flush();
 391         sssp_dijkstra();
 392         check_reachability();
 393         mst_kruskal();
 394 }