From: Guus Sliepen Date: Sun, 28 Oct 2001 22:42:49 +0000 (+0000) Subject: - More changes needed for Kruskal's algorithm X-Git-Tag: release-1.0pre5~42 X-Git-Url: https://www.tinc-vpn.org/git/browse?p=tinc;a=commitdiff_plain;h=b6298e2c082035b8238ea08673ced15d0fb7b89a - More changes needed for Kruskal's algorithm - Implemented a breadth-first search algorithm as a cheap substitution for a single-source shortest path algorithm. --- diff --git a/src/connection.c b/src/connection.c index 8fb96112..1bad1182 100644 --- a/src/connection.c +++ b/src/connection.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: connection.c,v 1.1.2.22 2001/10/28 08:41:19 guus Exp $ + $Id: connection.c,v 1.1.2.23 2001/10/28 22:42:49 guus Exp $ */ #include "config.h" @@ -25,6 +25,7 @@ #include #include #include +#include #include #include @@ -65,6 +66,11 @@ connection_t *new_connection(void) connection_t *c; cp c = (connection_t *)xmalloc_and_zero(sizeof(connection_t)); + + if(!c) + return NULL; + + gettimeofday(&c->start, NULL); cp return c; } diff --git a/src/connection.h b/src/connection.h index 9f2bf275..5307147a 100644 --- a/src/connection.h +++ b/src/connection.h @@ -17,12 +17,14 @@ 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.19 2001/10/28 10:16:18 guus Exp $ + $Id: connection.h,v 1.1.2.20 2001/10/28 22:42:49 guus Exp $ */ #ifndef __TINC_CONNECTION_H__ #define __TINC_CONNECTION_H__ +#include + #include #include @@ -71,6 +73,8 @@ typedef struct connection_t { int socket; /* socket used for this connection */ long int options; /* options for this connection */ struct connection_status_t status; /* status info */ + int estimated_weight; /* estimation for the weight of the edge for this connection */ + struct timeval start; /* time this connection was started, used for above estimation */ struct node_t *node; /* node associated with the other end */ struct edge_t *edge; /* edge associated with this connection */ diff --git a/src/edge.c b/src/edge.c index aee1be0f..92abbb3c 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.2 2001/10/28 10:16:18 guus Exp $ + $Id: edge.c,v 1.1.2.3 2001/10/28 22:42:49 guus Exp $ */ #include "config.h" @@ -65,17 +65,11 @@ int edge_compare(edge_t *a, edge_t *b) */ -int edge_weight_compare(edge_t *a, edge_t *b) +int edge_name_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 @@ -94,6 +88,18 @@ int edge_weight_compare(edge_t *a, edge_t *b) return strcmp(name_a2, name_b2); } +int edge_weight_compare(edge_t *a, edge_t *b) +{ + int result; + + result = a->weight - b->weight; + + if(result) + return result; + else + return edge_name_compare(a, b); +} + void init_edges(void) { cp @@ -102,6 +108,20 @@ cp cp } +avl_tree_t *new_edge_tree(void) +{ +cp + edge_tree = avl_alloc_tree((avl_compare_t)edge_name_compare, NULL); +cp +} + +void free_edge_tree(avl_tree_t *edge_tree) +{ +cp + avl_delete_tree(edge_tree); +cp +} + void exit_edges(void) { cp @@ -113,8 +133,9 @@ cp edge_t *new_edge(void) { + edge_t *e; cp - edge_t *e = (edge_t *)xmalloc_and_zero(sizeof(*e)); + e = (edge_t *)xmalloc_and_zero(sizeof(*e)); cp return e; } @@ -131,6 +152,8 @@ void edge_add(edge_t *e) cp avl_insert(edge_tree, e); avl_insert(edge_weight_tree, e); + avl_insert(e->from->edge_tree, e); + avl_insert(e->to->edge_tree, e); cp } @@ -139,6 +162,8 @@ void edge_del(edge_t *e) cp avl_delete(edge_tree, e); avl_delete(edge_weight_tree, e); + avl_delete(e->from->edge_tree, e); + avl_delete(e->to->edge_tree, e); cp } diff --git a/src/edge.h b/src/edge.h index 3bd475e6..4fff3878 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.2 2001/10/28 10:16:18 guus Exp $ + $Id: edge.h,v 1.1.2.3 2001/10/28 22:42:49 guus Exp $ */ #ifndef __TINC_EDGE_H__ @@ -55,6 +55,8 @@ extern void init_edges(void); extern void exit_edges(void); extern edge_t *new_edge(void); extern void free_edge(edge_t *); +extern avl_tree_t *new_edge_tree(void); +extern void free_edge_tree(avl_tree_t *); extern void edge_add(edge_t *); extern void edge_del(edge_t *); extern edge_t *lookup_edge(struct node_t *, struct node_t *); diff --git a/src/graph.c b/src/graph.c index 50695e4a..c7ca8af1 100644 --- a/src/graph.c +++ b/src/graph.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: graph.c,v 1.1.2.1 2001/10/28 10:16:18 guus Exp $ + $Id: graph.c,v 1.1.2.2 2001/10/28 22:42:49 guus Exp $ */ /* We need to generate two trees from the graph: @@ -34,12 +34,15 @@ 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. + For the SSSP algorithm Dijkstra's seems to be a nice choice. Currently a + simple breadth-first search is presented here. */ #include #include "config.h" +#include + #include "node.h" #include "edge.h" #include "connection.h" @@ -47,35 +50,35 @@ #include "system.h" /* Implementation of Kruskal's algorithm. - Running time: O(V) - Please note that sorting on weight is already done by add_vertex(). + Running time: O(E) + Please note that sorting on weight is already done by add_edge(). */ -void kruskal(void) +void mst_kruskal(void) { avl_node_t *node; edge_t *e; node_t *n; connection_t *c; - int nodes; + int nodes = 0; int safe_edges = 0; syslog(LOG_DEBUG, _("Running Kruskal's algorithm:")); - /* Clear MST status on nodes */ + /* Clear visited status on nodes */ for(node = node_tree->head; node; node = node->next) { n = (node_t *)node->data; - n->status.mst = 0; - node++; + n->status.visited = 0; + nodes++; } /* Clear MST status on connections */ for(node = connection_tree->head; node; node = node->next) { - c = (edge_t *)node->data; + c = (connection_t *)node->data; c->status.mst = 0; } @@ -89,11 +92,11 @@ void kruskal(void) e = (edge_t *)node->data; - if(e->from->status.mst && e->to->status.mst) + if(e->from->status.visited && e->to->status.visited) continue; - e->from->status.mst = 1; - e->to->status.mst = 1; + e->from->status.visited = 1; + e->to->status.visited = 1; if(e->connection) e->connection->status.mst = 1; @@ -109,3 +112,79 @@ void kruskal(void) syslog(LOG_ERR, _("Implementation of Kruskal's algorithm is screwed: %d nodes, found %d safe edges"), nodes, safe_edges); } } + +/* Implementation of a simple breadth-first search algorithm. + Running time: O(E) +*/ + +void sssp_bfs(void) +{ + avl_node_t *node, *from, *next, *to; + edge_t *e; + node_t *n, *check; + int nodes = 0; + int visited = 0; + avl_tree_t *todo_tree; + + syslog(LOG_DEBUG, _("Running BFS algorithm:")); + + todo_tree = avl_alloc_tree(NULL, NULL); + + /* Clear visited status on nodes */ + + for(node = node_tree->head; node; node = node->next) + { + n = (node_t *)node->data; + n->status.visited = 0; + nodes++; + } + + /* Begin with myself */ + + myself->status.visited = 1; + myself->nexthop = myself; + myself->via = myself; + node = avl_alloc_node(); + node->data = myself; + avl_insert_top(todo_tree, node); + visited++; + + /* Loop while todo_tree is filled */ + + while(todo_tree->head) + { + for(from = todo_tree->head; from; from = next) + { + next = from->next; + n = (node_t *)from->data; + + for(to = n->edge_tree->head; to; to = to->next) + { + e = (edge_t *)to->data; + + if(e->from == n) + check = e->to; + else + check = e->from; + + if(!check->status.visited) + { + check->status.visited = 1; + check->nexthop = (n->nexthop == myself)?n:n->nexthop; + check->via = check; /* FIXME: only if !(e->options & INDIRECT), otherwise use n->via */ + avl_insert_before(todo_tree, todo_tree->head, to); + visited++; + } + } + + avl_delete_node(todo_tree, from); + } + } + + syslog(LOG_DEBUG, _("Done.")); + + if(visited != nodes) + { + syslog(LOG_ERR, _("Implementation of BFS algorithm is screwed: %d nodes, visited %d"), nodes, visited); + } +} diff --git a/src/node.c b/src/node.c index 3776d184..f50d365f 100644 --- a/src/node.c +++ b/src/node.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: node.c,v 1.1.2.3 2001/10/27 13:13:35 guus Exp $ + $Id: node.c,v 1.1.2.4 2001/10/28 22:42:49 guus Exp $ */ #include "config.h" @@ -73,7 +73,8 @@ node_t *new_node(void) { node_t *n = (node_t *)xmalloc_and_zero(sizeof(*n)); cp - n->subnet_tree = avl_alloc_tree((avl_compare_t)subnet_compare, NULL); + n->subnet_tree = new_subnet_tree(); + n->edge_tree = new_edge_tree(); n->queue = list_alloc((list_action_t)free); cp return n; @@ -90,6 +91,10 @@ cp free(n->hostname); if(n->key) free(n->key); + if(n->subnet_tree) + free_subnet_tree(n->subnet_tree); + if(n->edge_tree) + free_edge_tree(n->edge_tree); free(n); cp } diff --git a/src/node.h b/src/node.h index b7c77e63..cc81b3b4 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.6 2001/10/28 10:16:18 guus Exp $ + $Id: node.h,v 1.1.2.7 2001/10/28 22:42:49 guus Exp $ */ #ifndef __TINC_NODE_H__ @@ -32,7 +32,7 @@ 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 mst:1; /* 1 if this node has been visited by the MST algorithm */ + int visited:1; /* 1 if this node has been visited by one of the graph algorithms */ int unused:28; } node_status_t; @@ -50,13 +50,15 @@ typedef struct node_t { char *key; /* Cipher key and iv */ int keylength; /* Cipher key and iv length*/ - list_t *queue; /* Queue for packets awaiting to be encrypted */ + list_t *queue; /* Queue for packets awaiting to be encrypted */ struct node_t *nexthop; /* nearest node from us to him */ struct node_t *via; /* next hop for UDP packets */ avl_tree_t *subnet_tree; /* Pointer to a tree of subnets belonging to this node */ + avl_tree_t *edge_tree; /* Edges with this node as one of the endpoints */ + struct connection_t *connection; /* Connection associated with this node (if a direct connection exists) */ } node_t; diff --git a/src/protocol.c b/src/protocol.c index 2771405c..63b10b1e 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.111 2001/10/28 10:16:18 guus Exp $ + $Id: protocol.c,v 1.28.4.112 2001/10/28 22:42:49 guus Exp $ */ #include "config.h" @@ -526,18 +526,26 @@ int send_ack(connection_t *c) { /* ACK message contains rest of the information the other end needs to create node_t and edge_t structures. */ + + struct timeval now; + + /* Estimate weight */ + + gettimeofday(&now, NULL); + c->estimated_weight = (now.tv_sec - c->start.tv_sec) * 1000 + (now.tv_usec - c->start.tv_usec) / 1000; cp - return send_request(c, "%d %d", ACK, myself->port); + return send_request(c, "%d %hd %d", ACK, myself->port, c->estimated_weight); } int ack_h(connection_t *c) { port_t port; + int weight; node_t *n; subnet_t *s; avl_node_t *node, *node2; cp - if(sscanf(c->buffer, "%*d %hd", &port) != 1) + if(sscanf(c->buffer, "%*d %hd %d", &port, &weight) != 2) { syslog(LOG_ERR, _("Got bad %s from %s (%s)"), "ACK", c->name, c->hostname); return -1; @@ -600,7 +608,7 @@ cp c->edge->from = myself; c->edge->to = n; - c->edge->weight = 1; + c->edge->weight = (weight + c->estimated_weight) / 2; c->edge->connection = c; edge_add(c->edge); diff --git a/src/subnet.c b/src/subnet.c index fff384ff..99d97bcd 100644 --- a/src/subnet.c +++ b/src/subnet.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: subnet.c,v 1.1.2.26 2001/10/27 13:13:35 guus Exp $ + $Id: subnet.c,v 1.1.2.27 2001/10/28 22:42:49 guus Exp $ */ #include "config.h" @@ -40,13 +40,6 @@ avl_tree_t *subnet_tree; -void init_subnets(void) -{ -cp - subnet_tree = avl_alloc_tree((avl_compare_t)subnet_compare, (avl_action_t)free_subnet); -cp -} - /* Subnet comparison */ int subnet_compare_mac(subnet_t *a, subnet_t *b) @@ -121,6 +114,36 @@ cp } } +/* Initialising trees */ + +void init_subnets(void) +{ +cp + subnet_tree = avl_alloc_tree((avl_compare_t)subnet_compare, (avl_action_t)free_subnet); +cp +} + +void exit_subnets(void) +{ +cp + avl_delete_tree(subnet_tree); +cp +} + +avl_tree_t *new_subnet_tree(void) +{ +cp + return avl_alloc_tree((avl_compare_t)subnet_compare, NULL); +cp +} + +void free_subnet_tree(avl_tree_t *subnet_tree) +{ +cp + avl_delete_tree(subnet_tree); +cp +} + /* Allocating and freeing space for subnets */ subnet_t *new_subnet(void) diff --git a/src/subnet.h b/src/subnet.h index 50cfefd7..d1dd9651 100644 --- a/src/subnet.h +++ b/src/subnet.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: subnet.h,v 1.1.2.12 2001/10/27 13:13:35 guus Exp $ + $Id: subnet.h,v 1.1.2.13 2001/10/28 22:42:49 guus Exp $ */ #ifndef __TINC_SUBNET_H__ @@ -72,11 +72,13 @@ typedef struct subnet_t { extern subnet_t *new_subnet(void); extern void free_subnet(subnet_t *); extern void init_subnets(void); +extern void exit_subnets(void); +extern avl_tree_t *new_subnet_tree(void); +extern void free_subnet_tree(avl_tree_t *); extern void subnet_add(struct node_t *, subnet_t *); extern void subnet_del(struct node_t *, subnet_t *); extern char *net2str(subnet_t *); extern subnet_t *str2net(char *); -extern int subnet_compare(subnet_t *, subnet_t *); extern subnet_t *lookup_subnet(struct node_t *, subnet_t *); extern subnet_t *lookup_subnet_mac(mac_t *); extern subnet_t *lookup_subnet_ipv4(ipv4_t *);