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

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