From 47bd032564a4812a607cbe9f5a44ef2b2f93278d Mon Sep 17 00:00:00 2001 From: Matthias Schiffer Date: Sun, 24 Mar 2013 03:45:16 +0100 Subject: Initial nexthop maintenance implementation Mostly taken from the FFD project, and quite incomplete. --- src/announce.c | 112 +++++++++++++++++++++++++++++++++++++++++++++++++++++++- src/babel.c | 56 +++++++++++++++++++++++++--- src/babel.h | 4 ++ src/neigh.c | 14 +++---- src/send.c | 6 +-- src/tlv_types.c | 4 +- 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) { -- cgit v1.2.3