The seqno request retransmission handling was tracking the destination that a forwarded request was being sent to and always retransmitting to that same destination. This is unnecessary because we only need to retransmit requests we originate ourselves, not those we forward on behalf of others; in fact retransmitting on behalf of others can lead to exponential multiplication of requests, which would be bad. So rework the seqno request tracking so that instead of storing the destination of a request, we just track whether it was a request that we forwarded on behalf of another node, or if it was a request we originated ourselves. Forwarded requests are not retransmitted, they are only used for duplicate suppression, and for triggering an update when satisfied. If we end up originating a request that we previously forwarded, we "upgrade" the old request and restart the retransmit counter. One complication with this is that requests sent in response to unfeasible updates (section 3.8.2.2 of the RFC) have to be sent as unicast to a particular peer. However, we don't really need to retransmit those as there's no starvation when sending such a request; so we just change such requests to be one-off unicast requests that are not subject to retransmission or duplicate suppression. This is the same behaviour as babeld has for such requests. Signed-off-by: Toke Høiland-Jørgensen <toke@toke.dk> --- v5: - Set an explicit duplicate suppression time for forwarded requests instead of repurposing the multi-expiry logic for forwarded requests v4: - Keep the last parameter of babel_add_seqno_request() as the request target and resolve it in the caller - Drop check for 0-valued hop count - Add a comment explaining why we expire forwarded requests but don't retransmit them v3: - Rework the dupliate suppression logic to avoid suppressing resends v2: - Get rid of the neighbour pointer in the request state tracking - Change the resend behaviour to only resend requests we originated ourselves. proto/babel/babel.c | 152 ++++++++++++++++++++++++++++---------------- proto/babel/babel.h | 6 +- 2 files changed, 101 insertions(+), 57 deletions(-) diff --git a/proto/babel/babel.c b/proto/babel/babel.c index ecfd2763d737..e8476ff5f72f 100644 --- a/proto/babel/babel.c +++ b/proto/babel/babel.c @@ -53,7 +53,7 @@ static void babel_expire_requests(struct babel_proto *p, struct babel_entry *e); static void babel_select_route(struct babel_proto *p, struct babel_entry *e, struct babel_route *mod); static inline void babel_announce_retraction(struct babel_proto *p, struct babel_entry *e); static void babel_send_route_request(struct babel_proto *p, struct babel_entry *e, struct babel_neighbor *n); -static void babel_send_seqno_request(struct babel_proto *p, struct babel_entry *e, struct babel_seqno_request *sr); +static void babel_send_seqno_request(struct babel_proto *p, struct babel_entry *e, struct babel_seqno_request *sr, struct babel_neighbor *tgt); static void babel_update_cost(struct babel_neighbor *n); static inline void babel_kick_timer(struct babel_proto *p); static inline void babel_iface_kick_timer(struct babel_iface *ifa); @@ -288,9 +288,6 @@ babel_expire_routes(struct babel_proto *p) babel_expire_routes_(p, &p->ip6_rtable); } -static inline int seqno_request_valid(struct babel_seqno_request *sr) -{ return !sr->nbr || sr->nbr->ifa; } - /* * Add seqno request to the table of pending requests (RFC 6216 3.2.6) and send * it to network. Do nothing if it is already in the table. @@ -299,50 +296,82 @@ static inline int seqno_request_valid(struct babel_seqno_request *sr) static void babel_add_seqno_request(struct babel_proto *p, struct babel_entry *e, u64 router_id, u16 seqno, u8 hop_count, - struct babel_neighbor *nbr) + struct babel_neighbor *tgt) { struct babel_seqno_request *sr; + btime now_ = current_time(); WALK_LIST(sr, e->requests) if (sr->router_id == router_id) { - /* Found matching or newer */ - if (ge_mod64k(sr->seqno, seqno) && seqno_request_valid(sr)) + /* + * To suppress duplicates, check if we already have a newer (higher seqno) + * outstanding request. If we do, suppress this request if the outstanding + * request is one we originated ourselves. If the outstanding request is + * forwarded, suppress only if this request is also one we're forwarding + * *and* we're within the duplicate suppression time of that request (see + * below). + */ + if (ge_mod64k(sr->seqno, seqno) && + (!sr->forwarded || (tgt && now_ < sr->dup_suppress_time))) return; - /* Found older */ rem_node(NODE sr); - if (sr->nbr) - rem_node(&sr->nbr_node); + /* Allow upgrading from forwarded to non-forwarded */ + if (!tgt) + sr->forwarded = 0; goto found; } /* No entries found */ sr = sl_allocz(p->seqno_slab); + sr->forwarded = !!tgt; found: sr->router_id = router_id; sr->seqno = seqno; - sr->hop_count = hop_count; + sr->hop_count = hop_count ?: BABEL_INITIAL_HOP_COUNT; sr->count = 0; - sr->expires = current_time() + BABEL_SEQNO_REQUEST_EXPIRY; - if (sr->nbr = nbr) - add_tail(&nbr->requests, &sr->nbr_node); + if (sr->forwarded) + { + /* + * We want to keep the entry around for a reasonable period of time so it + * can be used to trigger an update (through babel_satisfy_seqno_request()). + * However, duplicate suppression should only trigger for a short period of + * time so it suppresses duplicates from multiple sources, but not + * retransmissions from the same source. Hence we keep two timers. + */ + sr->expires = now_ + BABEL_SEQNO_FORWARD_EXPIRY; + sr->dup_suppress_time = now_ + BABEL_SEQNO_DUP_SUPPRESS_TIME; + } + else + { + sr->expires = now_ + BABEL_SEQNO_REQUEST_EXPIRY; + } add_tail(&e->requests, NODE sr); + babel_send_seqno_request(p, e, sr, tgt); +} - babel_send_seqno_request(p, e, sr); +static void +babel_generate_seqno_request(struct babel_proto *p, struct babel_entry *e, + u64 router_id, u16 seqno, struct babel_neighbor *tgt) +{ + struct babel_seqno_request req = { + .router_id = router_id, + .seqno = seqno, + .hop_count = BABEL_INITIAL_HOP_COUNT, + }; + + babel_send_seqno_request(p, e, &req, tgt); } static void babel_remove_seqno_request(struct babel_proto *p UNUSED, struct babel_seqno_request *sr) { - if (sr->nbr) - rem_node(&sr->nbr_node); - rem_node(NODE sr); sl_free(sr); } @@ -372,21 +401,14 @@ babel_expire_requests(struct babel_proto *p, struct babel_entry *e) WALK_LIST_DELSAFE(sr, srx, e->requests) { - /* Remove seqno requests sent to dead neighbors */ - if (!seqno_request_valid(sr)) - { - babel_remove_seqno_request(p, sr); - continue; - } - /* Handle expired requests - resend or remove */ if (sr->expires && sr->expires <= now_) { - if (sr->count < BABEL_SEQNO_REQUEST_RETRY) + if (!sr->forwarded && sr->count < BABEL_SEQNO_REQUEST_RETRY) { sr->count++; sr->expires += (BABEL_SEQNO_REQUEST_EXPIRY << sr->count); - babel_send_seqno_request(p, e, sr); + babel_send_seqno_request(p, e, sr, NULL); } else { @@ -431,7 +453,6 @@ babel_get_neighbor(struct babel_iface *ifa, ip_addr addr) nbr->cost = BABEL_INFINITY; nbr->init_expiry = current_time() + BABEL_INITIAL_NEIGHBOR_TIMEOUT; init_list(&nbr->routes); - init_list(&nbr->requests); add_tail(&ifa->neigh_list, NODE nbr); return nbr; @@ -452,10 +473,6 @@ babel_flush_neighbor(struct babel_proto *p, struct babel_neighbor *nbr) babel_flush_route(p, r); } - struct babel_seqno_request *sr; - WALK_LIST_FIRST2(sr, nbr_node, nbr->requests) - babel_remove_seqno_request(p, sr); - nbr->ifa = NULL; rem_node(NODE nbr); mb_free(nbr); @@ -903,22 +920,23 @@ babel_send_wildcard_request(struct babel_iface *ifa) } static void -babel_send_seqno_request(struct babel_proto *p, struct babel_entry *e, struct babel_seqno_request *sr) +babel_send_seqno_request(struct babel_proto *p, struct babel_entry *e, + struct babel_seqno_request *sr, struct babel_neighbor *tgt) { union babel_msg msg = {}; msg.type = BABEL_TLV_SEQNO_REQUEST; - msg.seqno_request.hop_count = sr->hop_count ?: BABEL_INITIAL_HOP_COUNT; + msg.seqno_request.hop_count = sr->hop_count; msg.seqno_request.seqno = sr->seqno; msg.seqno_request.router_id = sr->router_id; net_copy(&msg.seqno_request.net, e->n.addr); - if (sr->nbr) + if (tgt) { TRACE(D_PACKETS, "Sending seqno request for %N router-id %lR seqno %d to %I on %s", - e->n.addr, sr->router_id, sr->seqno, sr->nbr->addr, sr->nbr->ifa->ifname); + e->n.addr, sr->router_id, sr->seqno, tgt->addr, tgt->ifa->ifname); - babel_send_unicast(&msg, sr->nbr->ifa, sr->nbr->addr); + babel_send_unicast(&msg, tgt->ifa, tgt->addr); } else { @@ -1285,10 +1303,13 @@ babel_handle_update(union babel_msg *m, struct babel_iface *ifa) metric = babel_compute_metric(nbr, msg->metric); best = e->selected; - /* RFC section 3.8.2.2 - Dealing with unfeasible updates */ + /* + * RFC section 3.8.2.2 - Dealing with unfeasible updates. Generate a one-off + * (not retransmitted) unicast seqno request to the originator of this update + */ if (!feasible && (metric != BABEL_INFINITY) && (!best || (r == best) || (metric < best->metric))) - babel_add_seqno_request(p, e, s->router_id, s->seqno + 1, 0, nbr); + babel_generate_seqno_request(p, e, s->router_id, s->seqno + 1, nbr); /* Special case - ignore unfeasible update to best route */ if (r == best && !feasible && (msg->router_id == r->router_id)) @@ -1353,6 +1374,32 @@ babel_handle_route_request(union babel_msg *m, struct babel_iface *ifa) } } +static struct babel_neighbor * +babel_find_seqno_request_tgt(struct babel_entry *e, struct babel_neighbor *skip) +{ + struct babel_route *r, *best_feasible = NULL, *best_any = NULL; + + WALK_LIST(r, e->routes) + { + if (r->neigh == skip) + continue; + + if (r->feasible && (!best_feasible || r->metric < best_feasible->metric)) + best_feasible = r; + + if (!best_any || r->metric < best_any->metric) + best_any = r; + } + + if (best_feasible) + return best_feasible->neigh; + + if (best_any) + return best_any->neigh; + + return NULL; +} + void babel_handle_seqno_request(union babel_msg *m, struct babel_iface *ifa) { @@ -1389,26 +1436,21 @@ babel_handle_seqno_request(union babel_msg *m, struct babel_iface *ifa) { /* Not ours; forward if TTL allows it */ - /* Find best admissible route */ - struct babel_route *r, *best1 = NULL, *best2 = NULL; - WALK_LIST(r, e->routes) - if ((r->router_id == msg->router_id) && !ipa_equal(r->neigh->addr, msg->sender)) - { - /* Find best feasible route */ - if ((!best1 || r->metric < best1->metric) && r->feasible) - best1 = r; + struct babel_neighbor *nbr, *tgt; - /* Find best not necessary feasible route */ - if (!best2 || r->metric < best2->metric) - best2 = r; - } + nbr = babel_find_neighbor(ifa, msg->sender); + if (!nbr) + return; - /* If no route is found, do nothing */ - r = best1 ?: best2; - if (!r) + tgt = babel_find_seqno_request_tgt(e, nbr); + if (!tgt) + { + TRACE(D_PACKETS, "Couldn't find a neighbour to forward seqno request for %N router-id %lR seqno %d to", + e->n.addr, msg->router_id, msg->seqno); return; + } - babel_add_seqno_request(p, e, msg->router_id, msg->seqno, msg->hop_count-1, r->neigh); + babel_add_seqno_request(p, e, msg->router_id, msg->seqno, msg->hop_count-1, tgt); } } diff --git a/proto/babel/babel.h b/proto/babel/babel.h index 8b6da3c8ce91..b6e56ecb30a6 100644 --- a/proto/babel/babel.h +++ b/proto/babel/babel.h @@ -48,6 +48,8 @@ #define BABEL_ROUTE_REFRESH_FACTOR(X) ((btime)(X)*5/2) /* 2.5 */ #define BABEL_SEQNO_REQUEST_RETRY 4 #define BABEL_SEQNO_REQUEST_EXPIRY (2 S_) +#define BABEL_SEQNO_FORWARD_EXPIRY (10 S_) +#define BABEL_SEQNO_DUP_SUPPRESS_TIME (1 S_) #define BABEL_GARBAGE_INTERVAL (300 S_) #define BABEL_RXCOST_WIRED 96 #define BABEL_RXCOST_WIRELESS 256 @@ -240,7 +242,6 @@ struct babel_neighbor { btime init_expiry; list routes; /* Routes this neighbour has sent us (struct babel_route) */ - list requests; /* Seqno requests bound to this neighbor */ }; struct babel_source { @@ -276,7 +277,8 @@ struct babel_seqno_request { u8 hop_count; u8 count; btime expires; - struct babel_neighbor *nbr; + btime dup_suppress_time; + u8 forwarded; }; struct babel_entry { -- 2.39.0