- Implementation of Kruskal's minimum spanning tree algorithm.
## Produce this file with automake to get Makefile.in
-# $Id: Makefile.am,v 1.4.4.15 2001/10/28 08:41:19 guus Exp $
+# $Id: Makefile.am,v 1.4.4.16 2001/10/28 10:16:18 guus Exp $
sbin_PROGRAMS = tincd
-tincd_SOURCES = conf.c connection.c device.c meta.c net.c netutl.c node.c process.c \
- protocol.c route.c subnet.c tincd.c edge.c
+tincd_SOURCES = conf.c connection.c device.c edge.c graph.c meta.c net.c netutl.c node.c process.c \
+ protocol.c route.c subnet.c tincd.c
INCLUDES = @INCLUDES@ -I$(top_builddir) -I$(top_srcdir)/lib -I$(top_srcdir)/intl
-noinst_HEADERS = conf.h connection.h device.h meta.h net.h netutl.h node.h process.h \
- protocol.h route.h subnet.h edge.h
+noinst_HEADERS = conf.h connection.h device.h edge.h meta.h net.h netutl.h node.h process.h \
+ protocol.h route.h subnet.h
LIBS = @LIBS@ @INTLLIBS@
along with this program; if not, write to the Free Software
Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
- $Id: connection.h,v 1.1.2.18 2001/10/28 08:41:19 guus Exp $
+ $Id: connection.h,v 1.1.2.19 2001/10/28 10:16:18 guus Exp $
*/
#ifndef __TINC_CONNECTION_H__
int timeout:1; /* 1 if gotten timeout */
int encryptout:1; /* 1 if we can encrypt outgoing traffic */
int decryptin:1; /* 1 if we have to decrypt incoming traffic */
- int unused:18;
+ int mst:1; /* 1 if this connection is part of a minimum spanning tree */
+ int unused:17;
} connection_status_t;
typedef struct connection_t {
along with this program; if not, write to the Free Software
Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
- $Id: edge.c,v 1.1.2.1 2001/10/28 08:41:19 guus Exp $
+ $Id: edge.c,v 1.1.2.2 2001/10/28 10:16:18 guus Exp $
*/
#include "config.h"
#include "xalloc.h"
#include "system.h"
-avl_tree_t *edge_tree; /* Tree with all known vertices (replaces active_tree) */
+avl_tree_t *edge_tree; /* Tree with all known edges (replaces active_tree) */
+avl_tree_t *edge_weight_tree; /* Tree with all edges, sorted on weight */
int edge_compare(edge_t *a, edge_t *b)
{
*/
-void init_vertices(void)
+int edge_weight_compare(edge_t *a, edge_t *b)
+{
+ int result;
+ char *name_a1, *name_a2, *name_b1, *name_b2;
+
+
+ result = a->weight - b->weight;
+
+ if(result)
+ return result;
+
+ if(strcmp(a->from->name, a->to->name) < 0)
+ name_a1 = a->from->name, name_a2 = a->to->name;
+ else
+ name_a1 = a->to->name, name_a2 = a->from->name;
+
+ if(strcmp(b->from->name, b->to->name) < 0)
+ name_b1 = b->from->name, name_b2 = b->to->name;
+ else
+ name_b1 = b->to->name, name_b2 = b->from->name;
+
+ result = strcmp(name_a1, name_b1);
+
+ if(result)
+ return result;
+ else
+ return strcmp(name_a2, name_b2);
+}
+
+void init_edges(void)
{
cp
edge_tree = avl_alloc_tree((avl_compare_t)edge_compare, NULL);
+ edge_weight_tree = avl_alloc_tree((avl_compare_t)edge_weight_compare, NULL);
cp
}
-void exit_vertices(void)
+void exit_edges(void)
{
cp
avl_delete_tree(edge_tree);
edge_t *new_edge(void)
{
cp
- edge_t *v = (edge_t *)xmalloc_and_zero(sizeof(*v));
+ edge_t *e = (edge_t *)xmalloc_and_zero(sizeof(*e));
cp
- return v;
+ return e;
}
-void free_edge(edge_t *v)
+void free_edge(edge_t *e)
{
cp
- free(v);
+ free(e);
cp
}
-void edge_add(edge_t *v)
+void edge_add(edge_t *e)
{
cp
- avl_insert(edge_tree, v);
+ avl_insert(edge_tree, e);
+ avl_insert(edge_weight_tree, e);
cp
}
-void edge_del(edge_t *v)
+void edge_del(edge_t *e)
{
cp
- avl_delete(edge_tree, v);
+ avl_delete(edge_tree, e);
+ avl_delete(edge_weight_tree, e);
cp
}
return avl_search(edge_tree, &v);
}
-void dump_vertices(void)
+void dump_edges(void)
{
avl_node_t *node;
- edge_t *v;
+ edge_t *e;
cp
- syslog(LOG_DEBUG, _("Vertices:"));
+ syslog(LOG_DEBUG, _("Edges:"));
for(node = edge_tree->head; node; node = node->next)
{
- v = (edge_t *)node->data;
+ e = (edge_t *)node->data;
syslog(LOG_DEBUG, _(" %s - %s options %ld"),
- v->from->name, v->to->name, v->options);
+ e->from->name, e->to->name, e->options);
}
- syslog(LOG_DEBUG, _("End of vertices."));
+ syslog(LOG_DEBUG, _("End of edges."));
cp
}
along with this program; if not, write to the Free Software
Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
- $Id: edge.h,v 1.1.2.1 2001/10/28 08:41:19 guus Exp $
+ $Id: edge.h,v 1.1.2.2 2001/10/28 10:16:18 guus Exp $
*/
#ifndef __TINC_EDGE_H__
struct node_t *from;
struct node_t *to;
- long int options; /* options turned on for this connection */
- int metric; /* weight of this edge */
+ long int options; /* options turned on for this edge */
+ int weight; /* weight of this edge */
struct connection_t *connection; /* connection associated with this edge, if available */
} edge_t;
-extern avl_tree_t *edge_tree; /* Tree with all known vertices (replaces active_tree) */
+extern avl_tree_t *edge_tree; /* Tree with all known edges (replaces active_tree) */
+extern avl_tree_t *edge_weight_tree; /* Tree with all known edges sorted on weight */
-extern void init_vertices(void);
-extern void exit_vertices(void);
+extern void init_edges(void);
+extern void exit_edges(void);
extern edge_t *new_edge(void);
extern void free_edge(edge_t *);
extern void edge_add(edge_t *);
extern void edge_del(edge_t *);
extern edge_t *lookup_edge(struct node_t *, struct node_t *);
-extern void dump_vertices(void);
+extern void dump_edges(void);
#endif /* __TINC_EDGE_H__ */
--- /dev/null
+/*
+ graph.c -- graph algorithms
+ Copyright (C) 2001 Guus Sliepen <guus@sliepen.warande.net>,
+ 2001 Ivo Timmermans <itimmermans@bigfoot.com>
+
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 2 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+
+ $Id: graph.c,v 1.1.2.1 2001/10/28 10:16:18 guus Exp $
+*/
+
+/* We need to generate two trees from the graph:
+
+ 1. A minimum spanning tree for broadcasts,
+ 2. A single-source shortest path tree for unicasts.
+
+ Actually, the first one alone would suffice but would make unicast packets
+ take longer routes than necessary.
+
+ For the MST algorithm we can choose from Prim's or Kruskal's. I personally
+ favour Kruskal's, because we make an extra AVL tree of edges sorted on
+ weights (metric). That tree only has to be updated when an edge is added or
+ removed, and during the MST algorithm we just have go linearly through that
+ tree, adding safe edges until #edges = #nodes - 1.
+
+ For the SSSP algorithm Dijkstra's seems to be a nice choice.
+*/
+
+#include <syslog.h>
+#include "config.h"
+
+#include "node.h"
+#include "edge.h"
+#include "connection.h"
+
+#include "system.h"
+
+/* Implementation of Kruskal's algorithm.
+ Running time: O(V)
+ Please note that sorting on weight is already done by add_vertex().
+*/
+
+void kruskal(void)
+{
+ avl_node_t *node;
+ edge_t *e;
+ node_t *n;
+ connection_t *c;
+ int nodes;
+ int safe_edges = 0;
+
+ syslog(LOG_DEBUG, _("Running Kruskal's algorithm:"));
+
+ /* Clear MST status on nodes */
+
+ for(node = node_tree->head; node; node = node->next)
+ {
+ n = (node_t *)node->data;
+ n->status.mst = 0;
+ node++;
+ }
+
+ /* Clear MST status on connections */
+
+ for(node = connection_tree->head; node; node = node->next)
+ {
+ c = (edge_t *)node->data;
+ c->status.mst = 0;
+ }
+
+ /* Add safe edges */
+
+ for(node = edge_weight_tree->head; node; node = node->next)
+ {
+// Algorithm should work without this:
+// if(safe_edges = nodes - 1)
+// break;
+
+ e = (edge_t *)node->data;
+
+ if(e->from->status.mst && e->to->status.mst)
+ continue;
+
+ e->from->status.mst = 1;
+ e->to->status.mst = 1;
+ if(e->connection)
+ e->connection->status.mst = 1;
+
+ safe_edges++;
+
+ syslog(LOG_DEBUG, _("Adding safe edge %s - %s weight %d"), e->from->name, e->to->name, e->weight);
+ }
+
+ syslog(LOG_DEBUG, _("Done."));
+
+ if(safe_edges != nodes - 1)
+ {
+ syslog(LOG_ERR, _("Implementation of Kruskal's algorithm is screwed: %d nodes, found %d safe edges"), nodes, safe_edges);
+ }
+}
along with this program; if not, write to the Free Software
Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
- $Id: net.c,v 1.35.4.140 2001/10/28 08:41:19 guus Exp $
+ $Id: net.c,v 1.35.4.141 2001/10/28 10:16:18 guus Exp $
*/
#include "config.h"
init_connections();
init_subnets();
init_nodes();
- init_vertices();
+ init_edges();
if(get_config_int(lookup_config(config_tree, "PingTimeout"), &timeout))
{
along with this program; if not, write to the Free Software
Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
- $Id: node.h,v 1.1.2.5 2001/10/27 12:13:17 guus Exp $
+ $Id: node.h,v 1.1.2.6 2001/10/28 10:16:18 guus Exp $
*/
#ifndef __TINC_NODE_H__
int active:1; /* 1 if active.. */
int validkey:1; /* 1 if we currently have a valid key for him */
int waitingforkey:1; /* 1 if we already sent out a request */
- int unused:29;
+ int mst:1; /* 1 if this node has been visited by the MST algorithm */
+ int unused:28;
} node_status_t;
typedef struct node_t {
along with this program; if not, write to the Free Software
Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
- $Id: process.c,v 1.1.2.28 2001/10/27 15:19:13 guus Exp $
+ $Id: process.c,v 1.1.2.29 2001/10/28 10:16:18 guus Exp $
*/
#include "config.h"
{
dump_device_stats();
dump_nodes();
- dump_vertices();
+ dump_edges();
dump_subnets();
}
along with this program; if not, write to the Free Software
Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
- $Id: protocol.c,v 1.28.4.110 2001/10/28 08:41:19 guus Exp $
+ $Id: protocol.c,v 1.28.4.111 2001/10/28 10:16:18 guus Exp $
*/
#include "config.h"
c->edge->from = myself;
c->edge->to = n;
- c->edge->metric = 1;
+ c->edge->weight = 1;
c->edge->connection = c;
edge_add(c->edge);
return 0;
}
-/* Vertices */
+/* Edges */
-int send_add_edge(connection_t *c, edge_t *v)
+int send_add_edge(connection_t *c, edge_t *e)
{
cp
return send_request(c, "%d %s %s %lx", ADD_NODE,
- v->from->name, v->to->name, v->options);
+ e->from->name, e->to->name, e->options);
}
int add_edge_h(connection_t *c)
{
connection_t *other;
- edge_t *v;
+ edge_t *e;
node_t *from, *to;
char from_name[MAX_STRING_SIZE];
char to_name[MAX_STRING_SIZE];
/* Check if node already exists */
- v = lookup_edge(from, to);
+ e = lookup_edge(from, to);
- if(v)
+ if(e)
{
/* Check if it matches */
}
else
{
- v = new_edge();
- v->from = from;
- v->to = to;
- v->options = options;
- edge_add(v);
+ e = new_edge();
+ e->from = from;
+ e->to = to;
+ e->options = options;
+ edge_add(e);
}
/* Tell the rest about the new edge */
{
other = (connection_t *)node->data;
if(other->status.active && other != c)
- send_add_edge(other, v);
+ send_add_edge(other, e);
}
cp
return 0;
}
-int send_del_edge(connection_t *c, edge_t *v)
+int send_del_edge(connection_t *c, edge_t *e)
{
cp
return send_request(c, "%d %s %s %lx", DEL_EDGE,
- v->from->name, v->to->name, v->options);
+ e->from->name, e->to->name, e->options);
}
int del_edge_h(connection_t *c)
{
- edge_t *v;
+ edge_t *e;
char from_name[MAX_STRING_SIZE];
char to_name[MAX_STRING_SIZE];
node_t *from, *to;
/* Check if edge exists */
- v = lookup_edge(from, to);
+ e = lookup_edge(from, to);
- if(v)
+ if(e)
{
/* Check if it matches */
}
{
other = (connection_t *)node->data;
if(other->status.active && other != c)
- send_del_edge(other, v);
+ send_del_edge(other, e);
}
/* Delete the edge */
- edge_del(v);
+ edge_del(e);
cp
return 0;
}
projects / oweals / tinc.git / commitdiff