tinc-vpn.org Git - tinc/blob - src/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.2.8 2002/03/12 13:42:23 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.
  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 <syslog.h>
  46 #include "config.h"
  47 #include <string.h>
  48 #if defined(HAVE_FREEBSD) || defined(HAVE_OPENBSD)
  49  #include <sys/param.h>
  50 #endif
  51 #include <netinet/in.h>
  52
  53 #include <avl_tree.h>
  54 #include <utils.h>
  55
  56 #include "netutl.h"
  57 #include "node.h"
  58 #include "edge.h"
  59 #include "connection.h"
  60
  61 #include "system.h"
  62
  63 /* Kruskal's minimum spanning tree algorithm.
  64    Running time: O(E)
  65    Edges are already sorted on weight.
  66 */
  67
  68 void mst_kruskal(void)
  69 {
  70   avl_node_t *node;
  71   edge_t *e;
  72   node_t *n;
  73   connection_t *c;
  74
  75   /* Clear MST status on connections */
  76
  77   for(node = connection_tree->head; node; node = node->next)
  78     {
  79       c = (connection_t *)node->data;
  80       c->status.mst = 0;
  81     }
  82
  83   /* Do we have something to do at all? */
  84
  85   if(!edge_weight_tree->head)
  86     return;
  87
  88   /* Clear visited status on nodes */
  89
  90   for(node = node_tree->head; node; node = node->next)
  91     {
  92       n = (node_t *)node->data;
  93       n->status.visited = 0;
  94     }
  95
  96   /* Starting point */
  97
  98   ((edge_t *)edge_weight_tree->head->data)->from.node->status.visited = 1;
  99
 100   /* Add safe edges */
 101
 102   for(node = edge_weight_tree->head; node; node = node->next)
 103     {
 104       e = (edge_t *)node->data;
 105
 106       if(e->from.node->status.visited && e->to.node->status.visited)
 107         continue;
 108
 109       e->from.node->status.visited = 1;
 110       e->to.node->status.visited = 1;
 111       if(e->connection)
 112         e->connection->status.mst = 1;
 113     }
 114 }
 115
 116 /* Implementation of a simple breadth-first search algorithm.
 117    Running time: O(E)
 118 */
 119
 120 void sssp_bfs(void)
 121 {
 122   avl_node_t *node, *from, *next, *to;
 123   edge_t *e;
 124   node_t *n;
 125   halfconnection_t to_hc, from_hc;
 126   avl_tree_t *todo_tree;
 127
 128   todo_tree = avl_alloc_tree(NULL, NULL);
 129
 130   /* Clear visited status on nodes */
 131
 132   for(node = node_tree->head; node; node = node->next)
 133     {
 134       n = (node_t *)node->data;
 135       n->status.visited = 0;
 136     }
 137
 138   /* Begin with myself */
 139
 140   myself->status.visited = 1;
 141   myself->nexthop = myself;
 142   myself->via = myself;
 143   node = avl_alloc_node();
 144   node->data = myself;
 145   avl_insert_top(todo_tree, node);
 146
 147   /* Loop while todo_tree is filled */
 148
 149   while(todo_tree->head)
 150     {
 151       for(from = todo_tree->head; from; from = next)             /* "from" is the node from which we start */
 152         {
 153           next = from->next;
 154           n = (node_t *)from->data;
 155
 156           for(to = n->edge_tree->head; to; to = to->next)        /* "to" is the edge connected to "from" */
 157             {
 158               e = (edge_t *)to->data;
 159
 160               if(e->from.node == n)                              /* "from_hc" is the halfconnection with .node == from */
 161                 to_hc = e->to, from_hc = e->from;
 162               else
 163                 to_hc = e->from, from_hc = e->to;
 164
 165               if(!to_hc.node->status.visited)
 166                 {
 167                   to_hc.node->status.visited = 1;
 168                   to_hc.node->nexthop = (n->nexthop == myself) ? to_hc.node : n->nexthop;
 169                   to_hc.node->via = (e->options & OPTION_INDIRECT || n->via != n) ? n->via : to_hc.node;
 170                   to_hc.node->options = e->options;
 171                   if(sockaddrcmp(&to_hc.node->address, &to_hc.udpaddress))
 172                   {
 173                     node = avl_unlink(node_udp_tree, to_hc.node);
 174                     to_hc.node->address = to_hc.udpaddress;
 175                     if(to_hc.node->hostname)
 176                       free(to_hc.node->hostname);
 177                     to_hc.node->hostname = sockaddr2hostname(&to_hc.udpaddress);
 178                     avl_insert_node(node_udp_tree, node);
 179                   }
 180                   node = avl_alloc_node();
 181                   node->data = to_hc.node;
 182                   avl_insert_before(todo_tree, from, node);
 183                 }
 184             }
 185
 186           avl_delete_node(todo_tree, from);
 187         }
 188     }
 189
 190   avl_free_tree(todo_tree);
 191
 192   /* Check reachability status. */
 193
 194   for(node = node_tree->head; node; node = next)
 195     {
 196       next = node->next;
 197       n = (node_t *)node->data;
 198
 199       if(n->status.visited)
 200       {
 201         if(!n->status.reachable)
 202         {
 203           if(debug_lvl >= DEBUG_TRAFFIC)
 204             syslog(LOG_DEBUG, _("Node %s (%s) became reachable"), n->name, n->hostname);
 205           n->status.reachable = 1;
 206         }
 207       }
 208       else
 209       {
 210         if(n->status.reachable)
 211         {
 212           if(debug_lvl >= DEBUG_TRAFFIC)
 213             syslog(LOG_DEBUG, _("Node %s (%s) became unreachable"), n->name, n->hostname);
 214           n->status.reachable = 0;
 215           n->status.validkey = 0;
 216           n->status.waitingforkey = 0;
 217           n->sent_seqno = 0;
 218         }
 219       }
 220     }
 221 }
 222
 223 void graph(void)
 224 {
 225   mst_kruskal();
 226   sssp_bfs();
 227 }