X-Git-Url: https://tinc-vpn.org/git/browse?a=blobdiff_plain;f=src%2Fgraph.c;h=9da552e743ccf36b4b8b2f834f4c0f6c2188e541;hb=7a71d48009e03ff1143a6e1084803f456a27c849;hp=d432023e496f4eb790804d545262a91ddfc07034;hpb=268c8545aaf83b7433f43402f5c77e39e20006ef;p=tinc diff --git a/src/graph.c b/src/graph.c index d432023e..9da552e7 100644 --- a/src/graph.c +++ b/src/graph.c @@ -110,108 +110,6 @@ static void mst_kruskal(void) { } } -/* Implementation of Dijkstra's algorithm. - Running time: O(N^2) -*/ - -static void sssp_dijkstra(void) { - splay_node_t *node, *to; - edge_t *e; - node_t *n, *m; - list_t *todo_list; - list_node_t *lnode, *nnode; - bool indirect; - - todo_list = list_alloc(NULL); - - logger(DEBUG_SCARY_THINGS, LOG_DEBUG, "Running Dijkstra's algorithm:"); - - /* Clear visited status on nodes */ - - for(node = node_tree->head; node; node = node->next) { - n = node->data; - n->status.visited = false; - n->status.indirect = true; - n->distance = -1; - } - - /* Begin with myself */ - - myself->status.indirect = false; - myself->nexthop = myself; - myself->via = myself; - myself->distance = 0; - list_insert_head(todo_list, myself); - - /* Loop while todo_list is filled */ - - while(todo_list->head) { - n = NULL; - nnode = NULL; - - /* Select node from todo_list with smallest distance */ - - for(lnode = todo_list->head; lnode; lnode = lnode->next) { - m = lnode->data; - if(!n || m->status.indirect < n->status.indirect || m->distance < n->distance) { - n = m; - nnode = lnode; - } - } - - /* Mark this node as visited and remove it from the todo_list */ - - n->status.visited = true; - list_unlink_node(todo_list, nnode); - - /* Update distance of neighbours and add them to the todo_list */ - - for(to = n->edge_tree->head; to; to = to->next) { /* "to" is the edge connected to "from" */ - e = to->data; - - if(e->to->status.visited || !e->reverse) - continue; - - /* Situation: - - / - / - ----->(n)---e-->(e->to) - \ - \ - - Where e is an edge, (n) and (e->to) are nodes. - n->address is set to the e->address of the edge left of n to n. - We are currently examining the edge e right of n from n: - - - If edge e provides for better reachability of e->to, update e->to. - */ - - if(e->to->distance < 0) - list_insert_tail(todo_list, e->to); - - indirect = n->status.indirect || e->options & OPTION_INDIRECT || ((n != myself) && sockaddrcmp(&n->address, &e->reverse->address)); - - if(e->to->distance >= 0 && (!e->to->status.indirect || indirect) && e->to->distance <= n->distance + e->weight) - continue; - - e->to->distance = n->distance + e->weight; - e->to->status.indirect = indirect; - e->to->nexthop = (n->nexthop == myself) ? e->to : n->nexthop; - e->to->via = indirect ? n->via : e->to; - e->to->options = e->options; - - if(e->to->address.sa.sa_family == AF_UNSPEC && e->address.sa.sa_family != AF_UNKNOWN) - update_node_udp(e->to, &e->address); - - logger(DEBUG_SCARY_THINGS, LOG_DEBUG, " Updating edge %s - %s weight %d distance %d", e->from->name, - e->to->name, e->weight, e->to->distance); - } - } - - list_free(todo_list); -} - /* Implementation of a simple breadth-first search algorithm. Running time: O(E) */ @@ -232,6 +130,7 @@ static void sssp_bfs(void) { n = node->data; n->status.visited = false; n->status.indirect = true; + n->distance = -1; } /* Begin with myself */ @@ -241,12 +140,15 @@ static void sssp_bfs(void) { myself->nexthop = myself; myself->prevedge = NULL; myself->via = myself; + myself->distance = 0; list_insert_head(todo_list, myself); /* Loop while todo_list is filled */ for(from = todo_list->head; from; from = todonext) { /* "from" is the node from which we start */ n = from->data; + if(n->distance < 0) + abort(); for(to = n->edge_tree->head; to; to = to->next) { /* "to" is the edge connected to "from" */ e = to->data; @@ -274,7 +176,8 @@ static void sssp_bfs(void) { indirect = n->status.indirect || e->options & OPTION_INDIRECT; if(e->to->status.visited - && (!e->to->status.indirect || indirect)) + && (!e->to->status.indirect || indirect) + && (e->to->distance != n->distance + 1 || e->weight >= e->to->prevedge->weight)) continue; e->to->status.visited = true; @@ -283,6 +186,7 @@ static void sssp_bfs(void) { e->to->prevedge = e; e->to->via = indirect ? n->via : e->to; e->to->options = e->options; + e->to->distance = n->distance + 1; if(e->to->address.sa.sa_family == AF_UNSPEC && e->address.sa.sa_family != AF_UNKNOWN) update_node_udp(e->to, &e->address); @@ -322,6 +226,9 @@ static void check_reachability(void) { n->name, n->hostname); } + if(experimental && OPTION_VERSION(n->options) >= 2) + n->status.sptps = true; + /* TODO: only clear status.validkey if node is unreachable? */ n->status.validkey = false; @@ -359,10 +266,16 @@ static void check_reachability(void) { subnet_update(n, NULL, n->status.reachable); - if(!n->status.reachable) + if(!n->status.reachable) { update_node_udp(n, NULL); - else if(n->connection) - send_ans_key(n); + } else if(n->connection) { + if(n->status.sptps) { + if(n->connection->outgoing) + send_req_key(n); + } else { + send_ans_key(n); + } + } } } }