summaryrefslogtreecommitdiffstats
path: root/src/route.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/route.c')
-rw-r--r--src/route.c199
1 files changed, 199 insertions, 0 deletions
diff --git a/src/route.c b/src/route.c
new file mode 100644
index 0000000..91b4944
--- /dev/null
+++ b/src/route.c
@@ -0,0 +1,199 @@
+/*
+ Copyright (c) 2013, Matthias Schiffer <mschiffer@universe-factory.net>
+ All rights reserved.
+
+ Redistribution and use in source and binary forms, with or without
+ modification, are permitted provided that the following conditions are met:
+
+ 1. Redistributions of source code must retain the above copyright notice,
+ this list of conditions and the following disclaimer.
+ 2. Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+*/
+
+
+#include "babel.h"
+#include "neigh.h"
+
+#include <stdlib.h>
+
+
+gp_babel_route_t* gp_babel_route_new(gmrf_context_t *ctx) {
+ gp_babel_route_t *a = calloc(1, sizeof(gp_babel_route_t));
+
+ a->metric.metric = a->feasibility_distance.metric = a->last_metric = GP_BABEL_INFINITY;
+
+ a->next = ctx->routes;
+ ctx->routes = a;
+
+ return a;
+}
+
+gp_babel_route_t* gp_babel_route_find(gmrf_context_t *ctx, const gp_babel_node_id_t *node) {
+ gp_babel_route_t *route;
+ for (route = ctx->routes; route; route = route->next) {
+ if (gp_babel_node_id_equal(&route->node, node))
+ return route;
+ }
+
+ return NULL;
+}
+
+gp_babel_route_t* gp_babel_route_get(gmrf_context_t *ctx, const gp_babel_node_id_t *node) {
+ gp_babel_route_t *route = gp_babel_route_find(ctx, node);
+
+ if (!route) {
+ route = gp_babel_route_new(ctx);
+ route->node = *node;
+ }
+
+ return route;
+}
+
+void gp_babel_route_free(gmrf_context_t *ctx, gp_babel_route_t *route) {
+ free(route);
+}
+
+gp_babel_nexthop_t* gp_babel_route_nexthop_find(const gp_babel_route_t *route, gp_babel_neigh_t *neigh) {
+ gp_babel_nexthop_t *nexthop;
+ for (nexthop = route->nexthops; nexthop; nexthop = nexthop->next) {
+ if (nexthop->neigh == neigh)
+ return nexthop;
+ }
+
+ return NULL;
+}
+
+gp_babel_nexthop_t* gp_babel_route_nexthop_new(gp_babel_route_t *route, gp_babel_neigh_t *neigh) {
+ gp_babel_nexthop_t *nexthop = calloc(1, sizeof(gp_babel_nexthop_t));
+ nexthop->neigh = neigh;
+
+ nexthop->next = route->nexthops;
+ route->nexthops = nexthop;
+
+ gp_babel_neigh_ref(neigh);
+
+ return nexthop;
+}
+
+static void maintain_nexthops(gmrf_context_t *ctx, gp_babel_route_t *route) {
+ gp_babel_nexthop_t **cur, **next;
+ for (cur = &route->nexthops; *cur; cur = next) {
+ gp_babel_nexthop_t *nexthop = *cur;
+ next = &nexthop->next;
+
+ if (!nexthop->neigh) /* local */
+ continue;
+
+ if (!nexthop->neigh->iface) {
+ if (nexthop->metric_seqno.metric != GP_BABEL_INFINITY) {
+ nexthop->metric_seqno.metric = GP_BABEL_INFINITY;
+ nexthop->last_update = gmrf_now(ctx->gmrf);
+ nexthop->last_update += GP_BABEL_UPDATE_TIMEOUT(nexthop->interval)*10;
+ }
+
+ continue;
+ }
+
+ if (gmrf_now(ctx->gmrf) > nexthop->last_update+GP_BABEL_UPDATE_TIMEOUT(nexthop->interval)*10) {
+ if (nexthop->metric_seqno.metric == GP_BABEL_INFINITY) {
+ *cur = *next;
+ next = cur;
+
+ if (route->selected == nexthop)
+ route->selected = NULL;
+
+ gp_babel_neigh_unref(nexthop->neigh);
+
+ free(nexthop);
+ }
+ else {
+ nexthop->metric_seqno.metric = GP_BABEL_INFINITY;
+ nexthop->last_update += GP_BABEL_UPDATE_TIMEOUT(nexthop->interval)*10;
+ }
+ }
+ else if (gmrf_now(ctx->gmrf) > nexthop->last_update+GP_BABEL_UPDATE_REQUEST_TIMEOUT(nexthop->interval)*10 && route->selected == nexthop) {
+ if (!nexthop->requested_update) {
+ gmrf_logf(ctx->gmrf, LOG_INFO, "route about to expire, requesting update");
+ gp_babel_send_route_request(ctx, NULL, nexthop->neigh, &route->node);
+ nexthop->requested_update = true;
+ }
+ }
+ }
+}
+
+static gp_babel_nexthop_t* select_nexthop(gmrf_context_t *ctx, const gp_babel_route_t *route) {
+ uint16_t ret_metric = GP_BABEL_INFINITY;
+ gp_babel_nexthop_t *ret = NULL;
+
+ gp_babel_nexthop_t *nexthop;
+ for (nexthop = route->nexthops; nexthop; nexthop = nexthop->next) {
+ if (!nexthop->neigh) /* local */
+ return nexthop;
+
+ if (!gp_babel_is_feasible(route, nexthop->metric_seqno))
+ continue;
+
+ uint32_t metric = nexthop->metric_seqno.metric + gp_babel_neigh_get_cost(ctx, nexthop->neigh);
+
+ if (metric < ret_metric) {
+ ret = nexthop;
+ ret_metric = metric;
+ }
+ }
+
+ return ret;
+}
+
+gp_babel_metric_seqno_t get_metric(gmrf_context_t *ctx, const gp_babel_route_t *route) {
+ if (route->selected) {
+ uint32_t metric = route->selected->metric_seqno.metric + gp_babel_neigh_get_cost(ctx, route->selected->neigh);
+
+ if (metric < GP_BABEL_INFINITY)
+ return (gp_babel_metric_seqno_t){metric, route->selected->metric_seqno.seqno};
+ }
+
+ return (gp_babel_metric_seqno_t){GP_BABEL_INFINITY, 0};
+}
+
+void gp_babel_route_update(gmrf_context_t *ctx, gp_babel_route_t *route) {
+ maintain_nexthops(ctx, route);
+
+ route->selected = select_nexthop(ctx, route);
+ route->metric = get_metric(ctx, route);
+
+ if (!route->selected)
+ gp_babel_send_seqno_request_for(ctx, NULL, route);
+
+ /* triggered updates */
+ /*int diff = route->metric.metric - route->last_metric;
+
+ if (((route->last_metric == GP_BABEL_INFINITY) != (route->metric.metric == GP_BABEL_INFINITY))
+ || diff <= -1024 || diff >= 384) {
+ gmrf_logf(gmrf, LOG_INFO, "route metric has changed significantly, sending updates");
+ gp_babel_update_enqueue(&route->node, route->type, route->key, NULL, route->metric.metric == GP_BABEL_INFINITY);
+ } */
+}
+
+void gp_babel_route_update_nexthop(gmrf_context_t *ctx, gp_babel_route_t *route, gp_babel_nexthop_t *nexthop, gp_babel_metric_seqno_t ms, uint16_t interval) {
+ nexthop->metric_seqno = ms;
+ nexthop->interval = interval;
+ nexthop->requested_update = false;
+
+ if (ms.metric != GP_BABEL_INFINITY)
+ nexthop->last_update = gmrf_now(ctx->gmrf);
+
+ gp_babel_route_update(ctx, route);
+}