From 66067cc9c1347fb2de35660d531fdd4be8aede6a Mon Sep 17 00:00:00 2001 From: Guus Sliepen Date: Sun, 28 Oct 2001 10:16:18 +0000 Subject: [PATCH] - More s/vertex/edge/g - Implementation of Kruskal's minimum spanning tree algorithm. --- src/Makefile.am | 10 ++--- src/connection.h | 5 ++- src/edge.c | 69 +++++++++++++++++++++-------- src/edge.h | 15 ++++--- src/graph.c | 111 +++++++++++++++++++++++++++++++++++++++++++++++ src/net.c | 4 +- src/node.h | 5 ++- src/process.c | 4 +- src/protocol.c | 42 +++++++++--------- 9 files changed, 206 insertions(+), 59 deletions(-) create mode 100644 src/graph.c diff --git a/src/Makefile.am b/src/Makefile.am index 9a181093..c74433d4 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -1,15 +1,15 @@ ## 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@ diff --git a/src/connection.h b/src/connection.h index 40548042..9f2bf275 100644 --- a/src/connection.h +++ b/src/connection.h @@ -17,7 +17,7 @@ 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__ @@ -56,7 +56,8 @@ typedef struct connection_status_t { 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 { diff --git a/src/edge.c b/src/edge.c index 24c67c36..aee1be0f 100644 --- a/src/edge.c +++ b/src/edge.c @@ -17,7 +17,7 @@ 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" @@ -39,7 +39,8 @@ #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) { @@ -64,14 +65,44 @@ 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); @@ -83,29 +114,31 @@ cp 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 } @@ -127,20 +160,20 @@ 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 } diff --git a/src/edge.h b/src/edge.h index c2212cc7..3bd475e6 100644 --- a/src/edge.h +++ b/src/edge.h @@ -17,7 +17,7 @@ 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__ @@ -42,21 +42,22 @@ typedef struct edge_t { 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__ */ diff --git a/src/graph.c b/src/graph.c new file mode 100644 index 00000000..50695e4a --- /dev/null +++ b/src/graph.c @@ -0,0 +1,111 @@ +/* + graph.c -- graph algorithms + Copyright (C) 2001 Guus Sliepen , + 2001 Ivo Timmermans + + 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 +#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); + } +} diff --git a/src/net.c b/src/net.c index 35d9563c..0e7dcc9d 100644 --- a/src/net.c +++ b/src/net.c @@ -17,7 +17,7 @@ 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" @@ -776,7 +776,7 @@ cp init_connections(); init_subnets(); init_nodes(); - init_vertices(); + init_edges(); if(get_config_int(lookup_config(config_tree, "PingTimeout"), &timeout)) { diff --git a/src/node.h b/src/node.h index 9f2a35a7..b7c77e63 100644 --- a/src/node.h +++ b/src/node.h @@ -17,7 +17,7 @@ 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__ @@ -32,7 +32,8 @@ typedef struct node_status_t { 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 { diff --git a/src/process.c b/src/process.c index 86153b5a..525836b8 100644 --- a/src/process.c +++ b/src/process.c @@ -17,7 +17,7 @@ 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" @@ -380,7 +380,7 @@ sigusr2_handler(int a, siginfo_t *info, void *b) { dump_device_stats(); dump_nodes(); - dump_vertices(); + dump_edges(); dump_subnets(); } diff --git a/src/protocol.c b/src/protocol.c index d1bb524f..2771405c 100644 --- a/src/protocol.c +++ b/src/protocol.c @@ -17,7 +17,7 @@ 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" @@ -600,7 +600,7 @@ cp c->edge->from = myself; c->edge->to = n; - c->edge->metric = 1; + c->edge->weight = 1; c->edge->connection = c; edge_add(c->edge); @@ -934,19 +934,19 @@ cp 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]; @@ -993,19 +993,19 @@ cp /* 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 */ @@ -1014,23 +1014,23 @@ cp { 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; @@ -1079,9 +1079,9 @@ cp /* Check if edge exists */ - v = lookup_edge(from, to); + e = lookup_edge(from, to); - if(v) + if(e) { /* Check if it matches */ } @@ -1097,12 +1097,12 @@ cp { 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; } -- 2.20.1