summaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/announce.c112
-rw-r--r--src/babel.c56
-rw-r--r--src/babel.h4
-rw-r--r--src/neigh.c14
-rw-r--r--src/send.c6
-rw-r--r--src/tlv_types.c4
6 files changed, 178 insertions, 18 deletions
diff --git a/src/announce.c b/src/announce.c
index 1891341..1d17a02 100644
--- a/src/announce.c
+++ b/src/announce.c
@@ -33,7 +33,7 @@
gp_babel_announce_t* gp_babel_announce_new(gmrf_t *gmrf, gmrf_context_t *ctx) {
gp_babel_announce_t *a = calloc(1, sizeof(gp_babel_announce_t));
- a->metric.metric = a->feasibility_distance.metric = a->last_metric = 0xffff;
+ a->metric.metric = a->feasibility_distance.metric = a->last_metric = GP_BABEL_INFINITY;
a->next = ctx->announces;
ctx->announces = a;
@@ -91,3 +91,113 @@ gp_babel_nexthop_t* gp_babel_announce_nexthop_new(gp_babel_announce_t *announce,
return nexthop;
}
+
+static void maintain_nexthops(gmrf_t *gmrf, gp_babel_announce_t *announce) {
+ gp_babel_nexthop_t **cur, **next;
+ for (cur = &announce->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(gmrf);
+ nexthop->last_update += GP_BABEL_UPDATE_TIMEOUT(nexthop->interval)*10;
+ }
+
+ continue;
+ }
+
+ if (gmrf_now(gmrf) > nexthop->last_update+GP_BABEL_UPDATE_TIMEOUT(nexthop->interval)*10) {
+ if (nexthop->metric_seqno.metric == GP_BABEL_INFINITY) {
+ *cur = *next;
+ next = cur;
+
+ if (announce->selected == nexthop)
+ announce->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(gmrf) > nexthop->last_update+GP_BABEL_UPDATE_REQUEST_TIMEOUT(nexthop->interval)*10 && announce->selected == nexthop) {
+ if (!nexthop->requested_update) {
+ gmrf_logf(gmrf, LOG_INFO, "announce about to expire, requesting update");
+ // gp_babel_send_announce_request(nexthop->neigh->iface, nexthop->neigh, announce->node, announce->type, announce->key, false);
+ nexthop->requested_update = true;
+ }
+ }
+ }
+}
+
+static gp_babel_nexthop_t* select_nexthop(gmrf_t *gmrf, const gp_babel_announce_t *announce) {
+ uint16_t ret_metric = GP_BABEL_INFINITY;
+ gp_babel_nexthop_t *ret = NULL;
+
+ gp_babel_nexthop_t *nexthop;
+ for (nexthop = announce->nexthops; nexthop; nexthop = nexthop->next) {
+ if (!nexthop->neigh) /* local */
+ return nexthop;
+
+ if (!gp_babel_is_feasible(announce, nexthop->metric_seqno))
+ continue;
+
+ uint32_t metric = nexthop->metric_seqno.metric + gp_babel_neigh_get_cost(gmrf, nexthop->neigh);
+
+ if (metric < ret_metric) {
+ ret = nexthop;
+ ret_metric = metric;
+ }
+ }
+
+ return ret;
+}
+
+gp_babel_metric_seqno_t get_metric(gmrf_t *gmrf, const gp_babel_announce_t *announce) {
+ if (announce->selected) {
+ uint32_t metric = announce->selected->metric_seqno.metric + gp_babel_neigh_get_cost(gmrf, announce->selected->neigh);
+
+ if (metric < GP_BABEL_INFINITY)
+ return (gp_babel_metric_seqno_t){metric, announce->selected->metric_seqno.seqno};
+ }
+
+ return (gp_babel_metric_seqno_t){GP_BABEL_INFINITY, 0};
+}
+
+void gp_babel_announce_update(gmrf_t *gmrf, gp_babel_announce_t *announce) {
+ maintain_nexthops(gmrf, announce);
+
+ announce->selected = select_nexthop(gmrf, announce);
+ announce->metric = get_metric(gmrf, announce);
+
+ //if (!announce->selected)
+ // gp_babel_send_seqno_request_for(NULL, announce);
+
+ /* triggered updates */
+ /*int diff = announce->metric.metric - announce->last_metric;
+
+ if (((announce->last_metric == GP_BABEL_INFINITY) != (announce->metric.metric == GP_BABEL_INFINITY))
+ || diff <= -1024 || diff >= 384) {
+ gmrf_logf(gmrf, LOG_INFO, "announce metric has changed significantly, sending updates");
+ gp_babel_update_enqueue(&announce->node, announce->type, announce->key, NULL, announce->metric.metric == GP_BABEL_INFINITY);
+ } */
+}
+
+void gp_babel_announce_update_nexthop(gmrf_t *gmrf, gp_babel_announce_t *announce, 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(gmrf);
+
+ gp_babel_announce_update(gmrf, announce);
+}
diff --git a/src/babel.c b/src/babel.c
index 4177100..7e5e003 100644
--- a/src/babel.c
+++ b/src/babel.c
@@ -52,9 +52,7 @@ static void send_updates(gmrf_t *gmrf, gmrf_context_t *ctx, void *arg) {
}
}
-static void maintenance(gmrf_t *gmrf, gmrf_context_t *ctx, void *arg) {
- gmrf_schedule(gmrf, maintenance, NULL, GP_BABEL_MAINTENANCE_INTERVAL*10);
-
+static void maintain_neighbours(gmrf_t *gmrf, gmrf_context_t *ctx) {
gp_babel_iface_t *iface;
for (iface = ctx->interfaces; iface; iface = iface->next) {
gp_babel_neigh_t **cur, **next;
@@ -62,7 +60,7 @@ static void maintenance(gmrf_t *gmrf, gmrf_context_t *ctx, void *arg) {
gp_babel_neigh_t *neigh = *cur;
next = &neigh->next;
- if (gp_babel_neigh_get_rxcost(gmrf, neigh) == 0xffff && gp_babel_neigh_get_txcost(gmrf, neigh) == 0xffff && !neigh->ref) {
+ if (gp_babel_neigh_get_rxcost(gmrf, neigh) == GP_BABEL_INFINITY && gp_babel_neigh_get_txcost(gmrf, neigh) == GP_BABEL_INFINITY && !neigh->ref) {
*cur = *next;
next = cur;
free(neigh);
@@ -79,12 +77,58 @@ static void maintenance(gmrf_t *gmrf, gmrf_context_t *ctx, void *arg) {
}
}
+static void maintain_announces(gmrf_t *gmrf, gmrf_context_t *ctx) {
+ gp_babel_announce_t **cur, **next;
+ for (cur = &ctx->announces; *cur; cur = next) {
+ gp_babel_announce_t *announce = *cur;
+ next = &announce->next;
+
+ gp_babel_announce_update(gmrf, announce);
+
+ if (!announce->nexthops) {
+ *cur = *next;
+ next = cur;
+ gp_babel_announce_free(gmrf, ctx, announce);
+
+ continue;
+ }
+
+ gmrf_logf(gmrf, LOG_DEBUG, "node %04x%04x, type %04x, announce %04x (%u, seqno=%04x):",
+ ntohl(*(uint32_t*)announce->node.id), ntohl(*(uint32_t*)(announce->node.id+4)),
+ announce->type, announce->key, announce->metric.metric, announce->metric.seqno);
+
+ gp_babel_nexthop_t *nexthop;
+ for (nexthop = announce->nexthops; nexthop; nexthop = nexthop->next) {
+ gp_babel_neigh_t *neigh = nexthop->neigh;
+
+ if (!neigh) {
+ gmrf_logf(gmrf, LOG_DEBUG, " local");
+ continue;
+ }
+
+ gmrf_logf(gmrf, LOG_DEBUG, " nexthop: %02x:%02x:%02x:%02x:%02x:%02x:%02x:%02x[%s] (%u, seqno=%04x, cost=%u%s)",
+ neigh->addr.d[0], neigh->addr.d[1], neigh->addr.d[2], neigh->addr.d[3],
+ neigh->addr.d[4], neigh->addr.d[5], neigh->addr.d[6], neigh->addr.d[7],
+ neigh->iface ? gmrf_iface_get_name(gmrf, neigh->iface->gmrf_iface) : NULL,
+ nexthop->metric_seqno.metric, nexthop->metric_seqno.seqno, gp_babel_neigh_get_cost(gmrf, neigh),
+ (nexthop == announce->selected) ? ", selected" : "");
+ }
+ }
+}
+
+static void maintenance(gmrf_t *gmrf, gmrf_context_t *ctx, void *arg) {
+ gmrf_schedule(gmrf, maintenance, NULL, GP_BABEL_MAINTENANCE_INTERVAL*10);
+
+ maintain_neighbours(gmrf, ctx);
+ maintain_announces(gmrf, ctx);
+}
+
gmrf_context_t* gmrf_protocol_init(gmrf_t *gmrf) {
gmrf_logf(gmrf, LOG_INFO, "initalizing...");
gmrf_schedule(gmrf, send_hellos, NULL, GP_BABEL_HELLO_INTERVAL*10);
gmrf_schedule(gmrf, send_updates, NULL, GP_BABEL_UPDATE_INTERVAL*10);
- gmrf_schedule(gmrf, maintenance, NULL, GP_BABEL_MAINTENANCE_INTERVAL*10);
+ gmrf_schedule(gmrf, maintenance, NULL, 0);
gmrf_context_t *ctx = calloc(1, sizeof(gmrf_context_t));
gmrf_random_bytes(gmrf, &ctx->self, sizeof(gp_babel_node_id_t));
@@ -94,6 +138,8 @@ gmrf_context_t* gmrf_protocol_init(gmrf_t *gmrf) {
announce->type = 1;
announce->key = 1337;
+ announce->nexthops = announce->selected = calloc(1, sizeof(gp_babel_nexthop_t));
+
return ctx;
}
diff --git a/src/babel.h b/src/babel.h
index 3e9b3fd..52abfd5 100644
--- a/src/babel.h
+++ b/src/babel.h
@@ -41,6 +41,8 @@
#define GP_BABEL_HELLO_TIMEOUT(interval) (16*(interval))
#define GP_BABEL_IHU_TIMEOUT(interval) ((interval)*7/2)
+#define GP_BABEL_UPDATE_TIMEOUT(interval) ((interval)*7/2) /* 3.5 intervals */
+#define GP_BABEL_UPDATE_REQUEST_TIMEOUT(interval) ((interval)*13/4) /* 3.25 intervals */
#define GP_BABEL_MAINTENANCE_INTERVAL GP_BABEL_HELLO_INTERVAL
@@ -169,9 +171,11 @@ void gp_babel_send_update(gmrf_t *gmrf, gmrf_context_t *ctx, gp_babel_iface_t *i
gp_babel_announce_t* gp_babel_announce_new(gmrf_t *gmrf, gmrf_context_t *ctx);
gp_babel_announce_t* gp_babel_announce_find(gmrf_t *gmrf, gmrf_context_t *ctx, const gp_babel_node_id_t *node, uint16_t type, uint16_t key);
gp_babel_announce_t* gp_babel_announce_get(gmrf_t *gmrf, gmrf_context_t *ctx, const gp_babel_node_id_t *node, uint16_t type, uint16_t key);
+void gp_babel_announce_update(gmrf_t *gmrf, gp_babel_announce_t *announce);
void gp_babel_announce_free(gmrf_t *gmrf, gmrf_context_t *ctx, gp_babel_announce_t *announce);
gp_babel_nexthop_t* gp_babel_announce_nexthop_new(gp_babel_announce_t *announce, gp_babel_neigh_t *neigh);
gp_babel_nexthop_t* gp_babel_announce_nexthop_find(const gp_babel_announce_t *announce, gp_babel_neigh_t *neigh);
+void gp_babel_announce_update_nexthop(gmrf_t *gmrf, gp_babel_announce_t *announce, gp_babel_nexthop_t *nexthop, gp_babel_metric_seqno_t ms, uint16_t interval);
#endif /* _GMRF_PROTO_BABEL_BABEL_H_ */
diff --git a/src/neigh.c b/src/neigh.c
index bbef746..b89e284 100644
--- a/src/neigh.c
+++ b/src/neigh.c
@@ -40,7 +40,7 @@ gp_babel_neigh_t* gp_babel_neigh_get(gp_babel_iface_t *iface, const gmrf_addr_t
neigh->last_ihu = gmrf_time_unspec;
neigh->addr = *addr;
- neigh->txcost = 0xffff;
+ neigh->txcost = GP_BABEL_INFINITY;
}
return neigh;
@@ -66,25 +66,25 @@ void gp_babel_neigh_unref(gp_babel_neigh_t *neigh) {
uint16_t gp_babel_neigh_get_rxcost(gmrf_t *gmrf, const gp_babel_neigh_t *neigh) {
if (!neigh->hello_log || !neigh->hello_interval || !neigh->iface)
- return 0xffff;
+ return GP_BABEL_INFINITY;
int timediff = (gmrf_now(gmrf) - neigh->last_hello)/10;
int shift = (timediff - neigh->hello_interval/2)/neigh->hello_interval;
if (shift >= 16)
- return 0xffff;
+ return GP_BABEL_INFINITY;
int received = __builtin_popcount((neigh->hello_log << shift) & 0xffff);
if (received == 0)
- return 0xffff;
+ return GP_BABEL_INFINITY;
else
return (0x1000/received);
}
uint16_t gp_babel_neigh_get_txcost(gmrf_t *gmrf, const gp_babel_neigh_t *neigh) {
if ((gmrf_now(gmrf) - neigh->last_ihu)/10 > GP_BABEL_IHU_TIMEOUT(neigh->ihu_interval) || !neigh->iface)
- return 0xffff;
+ return GP_BABEL_INFINITY;
else
return neigh->txcost;
}
@@ -99,8 +99,8 @@ uint16_t gp_babel_neigh_get_cost(gmrf_t *gmrf, const gp_babel_neigh_t *neigh) {
uint32_t cost = (txcost * gp_babel_neigh_get_rxcost(gmrf, neigh)) >> 8;
- if (cost > 0xffff)
- return 0xffff;
+ if (cost > GP_BABEL_INFINITY)
+ return GP_BABEL_INFINITY;
else
return cost;
}
diff --git a/src/send.c b/src/send.c
index f566fee..b35d009 100644
--- a/src/send.c
+++ b/src/send.c
@@ -163,14 +163,14 @@ void gp_babel_send_update(gmrf_t *gmrf, gmrf_context_t *ctx, gp_babel_iface_t *i
gp_babel_packet_buf_t *buf = gp_babel_packet_alloca(GP_BABEL_PACKET_MAX);
if (announce) {
- add_update(buf, NULL, announce, with_data, iface || neigh);
+ add_update(buf, NULL, announce, with_data, neigh);
}
else {
gp_babel_node_id_t node_id = gp_babel_node_id_unspec;
gp_babel_announce_t *a;
for (a = ctx->announces; a; a = a->next) {
- if (!add_update(buf, &node_id, a, with_data, iface || neigh)) {
+ if (!add_update(buf, &node_id, a, with_data, neigh)) {
if (neigh)
send_neigh(gmrf, neigh, &buf->packet);
else
@@ -179,7 +179,7 @@ void gp_babel_send_update(gmrf_t *gmrf, gmrf_context_t *ctx, gp_babel_iface_t *i
node_id = gp_babel_node_id_unspec;
buf->packet.len = 0;
- if (!add_update(buf, &node_id, a, with_data, iface || neigh)) {
+ if (!add_update(buf, &node_id, a, with_data, neigh)) {
gmrf_logf(gmrf, LOG_ERR, "add_update failed");
return;
}
diff --git a/src/tlv_types.c b/src/tlv_types.c
index b860784..9b4c215 100644
--- a/src/tlv_types.c
+++ b/src/tlv_types.c
@@ -81,7 +81,7 @@ static void handle_tlv_hello(gmrf_t *gmrf, gmrf_context_t *ctx, const gp_babel_t
if (abs((int16_t)(seqno - seqexp)) > 16) {
gmrf_logf(gmrf, LOG_INFO, "neighbour was reset.");
neigh->hello_log = 0;
- neigh->txcost = 0xffff;
+ neigh->txcost = GP_BABEL_INFINITY;
}
else {
int16_t seqdiff = seqno - neigh->last_seqno;
@@ -212,7 +212,7 @@ static void handle_tlv_update(gmrf_t *gmrf, gmrf_context_t *ctx, const gp_babel_
gmrf_logf(gmrf, LOG_DEBUG, "the update was accepted.");
- //gp_babel_announce_update_nexthop(announce, nexthop, ms, ntohs(tlv_update->interval));
+ gp_babel_announce_update_nexthop(gmrf, announce, nexthop, ms, ntohs(tlv_update->interval));
}
static void handle_tlv(gmrf_t *gmrf, gmrf_context_t *ctx, gp_babel_tlv_type_t type, const void *data, size_t len, void *arg) {