- Bird-users - Mailing Lists

[PATCH v4] babel: Rework seqno request handling
by Toke Høiland-Jørgensen 20 Dec '22

20 Dec '22

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(a)toke.dk> --- 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 | 153 ++++++++++++++++++++++++++++---------------- proto/babel/babel.h | 3 +- 2 files changed, 100 insertions(+), 56 deletions(-) diff --git a/proto/babel/babel.c b/proto/babel/babel.c index ecfd2763d737..fda7865fb99b 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,73 @@ 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; 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, supress only if this request is also one we're forwarding + * *and* we're within the first expiry period of that request. The latter + * is to ensure we don't suppress retransmissions of the request from the + * same source. + */ + if (ge_mod64k(sr->seqno, seqno) && + (!sr->forwarded || (tgt && !sr->count))) 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); + /* + * Set the initial expiry time of forwarded requests to half the usual expiry + * time to be reasonably sure we expire it before it is resent by the source. + */ + sr->expires = current_time() + (sr->forwarded ? + (BABEL_SEQNO_REQUEST_EXPIRY/2) : + 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,13 +392,6 @@ 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_) { @@ -386,7 +399,19 @@ babel_expire_requests(struct babel_proto *p, struct babel_entry *e) { sr->count++; sr->expires += (BABEL_SEQNO_REQUEST_EXPIRY << sr->count); - babel_send_seqno_request(p, e, sr); + + /* + * Forwarded requests will be resent by their originator. However, we + * don't want to immediately remove the forwarded request objects, + * because they are also used to trigger updates (see + * babel_satisfy_seqno_request()). For this reason we cycle forwarded + * requests through the same number of expiry rounds as those we + * retransmit; there's a check in babel_add_seqno_request() which uses + * sr->count to determine if the request is within the first expiry + * period. + */ + if (!sr->forwarded) + babel_send_seqno_request(p, e, sr, NULL); } else { @@ -431,7 +456,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 +476,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 +923,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 +1306,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 +1377,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 +1439,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..3e6673e574fe 100644 --- a/proto/babel/babel.h +++ b/proto/babel/babel.h @@ -240,7 +240,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 +275,7 @@ struct babel_seqno_request { u8 hop_count; u8 count; btime expires; - struct babel_neighbor *nbr; + u8 forwarded; }; struct babel_entry { -- 2.39.0

1 0

[PATCH] babel: Rework seqno request handling to track sender, not destination
by Toke Høiland-Jørgensen 18 Dec '22

18 Dec '22

The seqno request retransmission handling was tracking the destination that a forwarded request was being sent to and always retransmitting to that same sender. Instead, we should really be tracking the originator of the request (i.e., the neighbour on behalf of which we're forwarding the request), and always selecting the best candidate to send the request to whenever we do a retransmission. Tying the seqno request entry to the destination had the problem that when that destination neighbour entry was removed, we'd remove the entire request, and thus no longer retransmit it. Tying the entry to the neighbour on whose behalf we are forwarding the entry instead means that we can just clear out the neighbour from the request entry when we're removing it, as long as we keep a separate flag specifying that it's a unicast request. One complication that arises from this change is that seqno requests sent in response to unfeasible updates (section 3.8.2.2 of the RFC) have to be sent as unicast, but not necessarily to the "best" candidate according to the selection logic. Rather than complicate the request tracking, we just change the requests sent in response to an unfeasible update to be one-off unicast messages without any retransmission tracking. This should be OK, as we'll send another request the next time we receive the unfeasible update anyway. Also make sure to discard incoming requests with a hop count of zero (as they are forbidden by the RFC). Signed-off-by: Toke Høiland-Jørgensen <toke(a)toke.dk> --- Ondrej originally noticed this issue back in May[0], I only just got around to fixing it now. We can't remove the neighbour tracking entirely, as we need it to make sure we don't send a unicasted request back to the neighbour it came from. [0] https://bird.network.cz/pipermail/bird-users/2022-May/016140.html proto/babel/babel.c | 172 ++++++++++++++++++++++++++++++-------------- proto/babel/babel.h | 3 +- 2 files changed, 122 insertions(+), 53 deletions(-) diff --git a/proto/babel/babel.c b/proto/babel/babel.c index ecfd2763d737..0cc59ce26d8f 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,21 +296,25 @@ 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 *fwd_from) { struct babel_seqno_request *sr; + /* + * To suppress duplicates, check if we already have a newer (higher seqno) + * outstanding request; if this one is newer, replace the old one. Consider + * unicast and multicast requests separately. + */ WALK_LIST(sr, e->requests) - if (sr->router_id == router_id) + if (sr->router_id == router_id && sr->unicast == !!fwd_from) { - /* Found matching or newer */ - if (ge_mod64k(sr->seqno, seqno) && seqno_request_valid(sr)) + if (ge_mod64k(sr->seqno, seqno)) return; /* Found older */ rem_node(NODE sr); - if (sr->nbr) + if (sr->from) rem_node(&sr->nbr_node); goto found; @@ -325,22 +326,48 @@ babel_add_seqno_request(struct babel_proto *p, struct babel_entry *e, 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); + sr->from = fwd_from; + if (sr->from) { + add_tail(&fwd_from->requests, &sr->nbr_node); + sr->unicast = 1; + } add_tail(&e->requests, NODE sr); - babel_send_seqno_request(p, e, sr); + babel_send_seqno_request(p, e, sr, NULL); +} + +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 *sr, req = { + .router_id = router_id, + .seqno = seqno, + .hop_count = BABEL_INITIAL_HOP_COUNT, + .unicast = 1, + }; + + WALK_LIST(sr, e->requests) + /* + * We only suppress targeted seqno requests if we already have an + * outstanding *multicast* request for the same prefix (as other outstanding + * requests may not be sent to the same target) + */ + if (sr->router_id == router_id && ge_mod64k(sr->seqno, seqno) && !sr->from) + return; + + 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) + if (sr->from) rem_node(&sr->nbr_node); rem_node(NODE sr); @@ -351,17 +378,17 @@ static int babel_satisfy_seqno_request(struct babel_proto *p, struct babel_entry *e, u64 router_id, u16 seqno) { - struct babel_seqno_request *sr; + struct babel_seqno_request *sr, *srx; + int ret = 0; - WALK_LIST(sr, e->requests) + WALK_LIST_DELSAFE(sr, srx, e->requests) if ((sr->router_id == router_id) && ge_mod64k(seqno, sr->seqno)) { - /* Found the request, remove it */ babel_remove_seqno_request(p, sr); - return 1; + ret = 1; } - return 0; + return ret; } static void @@ -372,13 +399,6 @@ 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_) { @@ -386,7 +406,7 @@ babel_expire_requests(struct babel_proto *p, struct babel_entry *e) { 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 { @@ -454,7 +474,16 @@ babel_flush_neighbor(struct babel_proto *p, struct babel_neighbor *nbr) struct babel_seqno_request *sr; WALK_LIST_FIRST2(sr, nbr_node, nbr->requests) - babel_remove_seqno_request(p, sr); + { + /* + * There may be other neighbours who sent the same request but were + * suppressed as duplicates, so keep the request alive but remove the + * neighbour entry (which is only used to make sure the request is not + * sent back where it came from). + */ + rem_node(&sr->nbr_node); + sr->from = NULL; + } nbr->ifa = NULL; rem_node(NODE nbr); @@ -902,23 +931,66 @@ babel_send_wildcard_request(struct babel_iface *ifa) babel_enqueue(&msg, 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; +} + 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 || sr->unicast) { + if (!tgt) + { + /* + * If we don't have a target to send to, but we're forwarding this request + * on behalf of another node, select a new target from the routing table + */ + + tgt = babel_find_seqno_request_tgt(e, sr->from); + 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, sr->router_id, sr->seqno); + return; + } + } + 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 +1357,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)) @@ -1361,6 +1436,12 @@ babel_handle_seqno_request(union babel_msg *m, struct babel_iface *ifa) /* RFC 6126 3.8.1.2 */ + if (!msg->hop_count) { + TRACE(D_PACKETS, "Discarding seqno request for %N router-id %lR with hop count 0 from %I", + &msg->net, msg->router_id, msg->sender); + return; + } + TRACE(D_PACKETS, "Handling seqno request for %N router-id %lR seqno %d hop count %d", &msg->net, msg->router_id, msg->seqno, msg->hop_count); @@ -1389,26 +1470,13 @@ 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; - - /* Find best not necessary feasible route */ - if (!best2 || r->metric < best2->metric) - best2 = r; - } + struct babel_neighbor *nbr; - /* If no route is found, do nothing */ - r = best1 ?: best2; - if (!r) + nbr = babel_find_neighbor(ifa, msg->sender); + if (!nbr) 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, nbr); } } diff --git a/proto/babel/babel.h b/proto/babel/babel.h index 8b6da3c8ce91..a87a11ff3620 100644 --- a/proto/babel/babel.h +++ b/proto/babel/babel.h @@ -276,7 +276,8 @@ struct babel_seqno_request { u8 hop_count; u8 count; btime expires; - struct babel_neighbor *nbr; + struct babel_neighbor *from; + u8 unicast; }; struct babel_entry { -- 2.38.1

3 8

[PATCH v2] babel: Rework seqno request handling to track sender, not destination
by Toke Høiland-Jørgensen 17 Dec '22

17 Dec '22

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 (but still expired by the same rules as a retransmitted request). 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. We also weren't discarding requests with a hop count of zero, so let's add such a check (they are forbidden by the RFC). Signed-off-by: Toke Høiland-Jørgensen <toke(a)toke.dk> --- v2 of the patch (after discussion with Juliusz) gets rid of the neighbour pointer in the request state tracking entirely, and changes the resend behaviour so we only resend requests we originated ourselves. proto/babel/babel.c | 142 +++++++++++++++++++++++++++----------------- proto/babel/babel.h | 3 +- 2 files changed, 88 insertions(+), 57 deletions(-) diff --git a/proto/babel/babel.c b/proto/babel/babel.c index ecfd2763d737..e620261d6be9 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,8 +288,31 @@ 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; } +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; +} /* * Add seqno request to the table of pending requests (RFC 6216 3.2.6) and send @@ -299,23 +322,36 @@ 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 *fwd_from) { + struct babel_neighbor *tgt = NULL; struct babel_seqno_request *sr; + if (fwd_from) + { + tgt = babel_find_seqno_request_tgt(e, fwd_from); + 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, router_id, seqno); + return; + } + } + + /* + * To suppress duplicates, check if we already have a newer (higher seqno) + * outstanding request; if this one is newer, replace the old one. Also allow + * upgrading a previously forwarded request to one we originate. + */ 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)) + if (ge_mod64k(sr->seqno, seqno) && (!sr->forwarded || fwd_from)) return; - /* Found older */ + /* Found older, or upgrading a forwarded request */ rem_node(NODE sr); - if (sr->nbr) - rem_node(&sr->nbr_node); - goto found; } @@ -325,24 +361,31 @@ babel_add_seqno_request(struct babel_proto *p, struct babel_entry *e, 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); + sr->forwarded = !!fwd_from; add_tail(&e->requests, NODE sr); + babel_send_seqno_request(p, e, sr, tgt); +} + +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, sr); + 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,13 +415,6 @@ 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_) { @@ -386,7 +422,10 @@ babel_expire_requests(struct babel_proto *p, struct babel_entry *e) { sr->count++; sr->expires += (BABEL_SEQNO_REQUEST_EXPIRY << sr->count); - babel_send_seqno_request(p, e, sr); + + /* Forwarded requests will be resent by their originator */ + if (!sr->forwarded) + babel_send_seqno_request(p, e, sr, NULL); } else { @@ -431,7 +470,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 +490,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 +937,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 +1320,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)) @@ -1361,6 +1399,13 @@ babel_handle_seqno_request(union babel_msg *m, struct babel_iface *ifa) /* RFC 6126 3.8.1.2 */ + if (!msg->hop_count) + { + TRACE(D_PACKETS, "Discarding seqno request for %N router-id %lR with hop count 0 from %I", + &msg->net, msg->router_id, msg->sender); + return; + } + TRACE(D_PACKETS, "Handling seqno request for %N router-id %lR seqno %d hop count %d", &msg->net, msg->router_id, msg->seqno, msg->hop_count); @@ -1389,26 +1434,13 @@ 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; - - /* Find best not necessary feasible route */ - if (!best2 || r->metric < best2->metric) - best2 = r; - } + struct babel_neighbor *nbr; - /* If no route is found, do nothing */ - r = best1 ?: best2; - if (!r) + nbr = babel_find_neighbor(ifa, msg->sender); + if (!nbr) 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, nbr); } } diff --git a/proto/babel/babel.h b/proto/babel/babel.h index 8b6da3c8ce91..3e6673e574fe 100644 --- a/proto/babel/babel.h +++ b/proto/babel/babel.h @@ -240,7 +240,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 +275,7 @@ struct babel_seqno_request { u8 hop_count; u8 count; btime expires; - struct babel_neighbor *nbr; + u8 forwarded; }; struct babel_entry { -- 2.38.1

1 1

[PATCH] Netlink on FreeBSD support
by Alexander V. Chernikov 17 Dec '22

17 Dec '22

Dear bird developers, Netlink support was added to FreeBSD recently [1]. It’s not as “full-featured” as its Linux counterpart yet, however the added subset is enough to make a routing daemon work. Specifically, it supports multiple tables, multipath, nexthops and nexthops groups. No MPLS support yet. It aims to be compatible (whenever possible) to minimise the netlink users adoption efforts. The first FreeBSD releases to have netlink support will be 14.0 and 13.2. Both are planned to be released in ~Q1 2023. The attached change adds 'bsd-netlink’ sysconf target, allowing to build both netlink & rtsock versions on FreeBSD. Example output: bird> show status BIRD 2.0.10-124-g8e63db05 Router ID is 10.0.0.4 Hostname is devel2.ipfw.ru Current server time is 2022-12-01 13:40:08.960 Last reboot on 2022-12-01 13:35:39.293 Last reconfiguration on 2022-12-01 13:37:20.593 Daemon is up and running bird> show interfaces vtnet0 up (index=1) MultiAccess Broadcast Multicast AdminUp LinkUp MTU=1500 10.0.0.4/24 (Preferred, scope site) fe80::5054:ff:fe14:e319/64 (Preferred, scope link) 2a01:4f9:3a:fa00:5054:ff:fe14:e319/64 (Preferred, scope univ) lo0 up (index=2) MultiAccess Multicast AdminUp LinkUp Loopback Ignored MTU=16384 127.0.0.1/8 (Preferred, scope host) ::1/128 (Preferred, scope host) fe80::1/64 (Preferred, scope link) vtnet0.2 up (index=3) MultiAccess Broadcast Multicast AdminUp LinkUp MTU=1500 fe80::5054:ff:fe14:e319/64 (Preferred, scope link) bird> show route protocol ospf2 Table master4: 7.7.7.0/24 unicast [ospf2 13:39:41.717] * E2 (150/10/10000) [10.0.0.157] via 10.0.0.2 on vtnet0 10.0.0.0/24 unicast [ospf2 13:37:26.734] I (150/10) [10.0.0.4] dev vtnet0 bird> show route protocol static2 Table master4: 10.1.0.0/24 unicast [static2 13:46:16.543] * (200) via 10.0.0.6 on vtnet0 weight 4 via 10.0.0.5 on vtnet0 weight 3 [1] https://github.com/freebsd/freebsd-src/commit/7e5bf68495cc0a8c9793a338a8a02…

4 13

Unexpected RIP route output with Bird 2.0.11 vs Bird 2.0.10
by Nigel Kukard 14 Dec '22

14 Dec '22

Hi guys, During testing of Bird 2.0.11 I noticed something a bit odd in terms of the output for RIP routes, is the below "RIP.02" and "<type 16>" expected? 0001 BIRD 2.0.11 ready. 1007-Table t_kernel4: 192.168.21.0/24 unicast [rip4 2022-12-14 15:03:21] * (120/3) via 192.168.0.2 on eth0 1008- Type: RIP univ 1012- RIP.metric: 3 RIP.tag: 0000 RIP.02: *<type 16>* 1007-192.168.11.0/24 unicast [kernel4 2022-12-14 15:03:17] * (10) via 192.168.10.2 on eth1 1008- Type: inherit univ 1012- Kernel.source: 3 Kernel.metric: 0 0000 Kind Regards Nigel

3 4

Bug on route reflection with BIRD (no originator ID on withdrawals)
by Vasileios Kotronis 14 Dec '22

14 Dec '22

Hello there, I am facing an issue with a route reflection setup on BIRD. I have the following setup: external router --(eBGP)-- monitor | (iBGP) | reflector | (iBGP) | client The reflector reflects routes from the monitor (monitoring the external router via BGP) to the client. However, I notice that the originator ID (used for loop detection in a RR setup) is input by the BIRD RR only in announcements, and not in withdrawals. This means that if the same withdrawal (from the monitor) propagates within the RR cluster there is no way to disambiguate this from another withdrawal. According to RFC4456 ( https://www.rfc-editor.org/rfc/rfc4456) ORIGINATOR_ID ORIGINATOR_ID is a new optional, non-transitive BGP attribute of Type code 9. This attribute is 4 bytes long and it will be created by an RR in reflecting a route. This attribute will carry the BGP Identifier of the originator of the route in the local AS. A BGP speaker SHOULD NOT create an ORIGINATOR_ID attribute if one already exists. A router that recognizes the ORIGINATOR_ID attribute SHOULD ignore a route received with its BGP Identifier as the ORIGINATOR_ID. Also: If a route carries the ORIGINATOR_ID attribute, then in Step f) the ORIGINATOR_ID SHOULD be treated as the BGP Identifier of the BGP speaker that has advertised the route. So, since RFC4456 is fully supported in BIRD, shouldn't this be present both in route announcements and withdrawals? This is my simple BIRD configuration (I am running version 2.0.10): log syslog all; router id 192.168.55.4; protocol device { } template bgp rr_clients { local 192.168.55.4 as 50414; neighbor as 50414; rr client; rr cluster id 1.0.0.1; ipv4 { import all; export all; }; ipv6 { import all; export all; }; } protocol bgp monitor from rr_clients { neighbor 192.168.55.3; } protocol bgp client1 from rr_clients { neighbor 192.168.55.2; } Thanks in advance! Best regards, Vasileios -- Vasileios Kotronis CTO & Co-founder www.codebgp.com Monitor • Detect • Protect

2 3

OSPFv3 doesn't announce loopback IPv6 network
by Bernhard Ehlers 12 Dec '22

12 Dec '22

I want to use OSPF with BIRD v2.0.10 on Linux. That works well, except that the IPv6 network of the lo interface isn't announced on OSPFv3. The IPv6 networks of the ethernet interfaces are announced as well as the IPv4 networks of all interfaces (ethernet and lo). The only missing is the IPv6 network of lo. Here the OSPF config, really basic: protocol ospf v2 { ipv4 { import all; export all; }; area 0 { interface "eth*" { }; interface "lo" { stub; }; }; } protocol ospf v3 { ipv6 { import all; export all; }; area 0 { interface "eth*" { }; interface "lo" { stub; }; }; } Without any active OSPF neighbor the routes show all interface networks except that of interface lo: # birdc show route BIRD 2.0.10 ready. Table master4: 10.1.1.0/24 unicast [ospf1 17:03:20.860] * I (150/10) [3.3.3.3] dev eth0 10.1.2.0/24 unicast [ospf1 17:03:20.860] * I (150/10) [3.3.3.3] dev eth1 3.3.3.3/32 unicast [ospf1 17:03:20.860] * I (150/0) [3.3.3.3] dev lo Table master6: 2001:1::/64 unicast [ospf2 17:03:25.861] * I (150/10) [3.3.3.3] dev eth0 2001:2::/64 unicast [ospf2 17:03:25.861] * I (150/10) [3.3.3.3] dev eth1 Here the configuration of interface lo: # ip addr show dev lo 1: lo: <LOOPBACK,UP,LOWER_UP> mtu 65536 qdisc noqueue state UNKNOWN group default qlen 1000 link/loopback 00:00:00:00:00:00 brd 00:00:00:00:00:00 inet 127.0.0.1/8 scope host lo valid_lft forever preferred_lft forever inet 3.3.3.3/32 scope global lo:1 valid_lft forever preferred_lft forever inet6 2001::3/128 scope global valid_lft forever preferred_lft forever inet6 ::1/128 scope host valid_lft forever preferred_lft forever What am I missing?

5 7

BIRD version 2.0.11
by Ondrej Filip 11 Dec '22

11 Dec '22

Dear users, We just released third stable version of BIRD this year. Many thanks to my great colleagues and namely Santiago. Here is a list of the main improvements: Version 2.0.11 (2022-11-12) o BGP roles (RFC 9234) o BGP: Keepalive time scaling o BGP: New 'min hold time' and 'min keepalive time' options o BGP: New 'next hop prefer global' option o Filter: For loops and direct recursion o Filter: Mixed declarations of local variables o Filter: Improved static type checks o Filter: Literal [] for empty set o Linux: Netlink KRT improvements o BSD: Experimental support for Netlink API o Memory management improvements o Many bugfixes Notes: In contrast to prior versions, configured keepalive time in BGP now scales with negotiated hold time to maintain proportion between the keepalive time and the hold time. The Linux KRT was updated to use the recent API for IPv6 ECMP routes instead of the legacy one. Consequently, the Linux versions older than 4.11 are no longer supported, at least for IPv6 ECMP routes. Also, routing table scanning now runs separately for each table to avoid congestion. There is a minor change in recursive next hop processing. Previously, recursive next hop must be resolved through a non-recursive route, now it must be resolved through a prefix where both the best route and all routes with the same preference (as the best route) are non-recursive. The old behavior might lead in some corner cases to an infinite loop of recursive next hop resolution due to a priority inversion. There is a minor change in the 'configure undo' command, it is no longer available after failed reconfiguration, as the old configuration is already released. Enjoy! Ondrej

1 0

Calling Bird2 from Python script fails
by Stavros Konstantaras 11 Dec '22

11 Dec '22

Hi all, I am trying to automate Bird2 configuration with Python3 and I faced this strange issue: * If I generate a part of the config which is included in the main config file and then I call “birdc configure” via os.system() function, the new configuration is ignored. * If I generate a full config and I call “birdc configure” via os.system() function, I get the strange error “bird2_control.conf:1:1 No protocol is specified in the config file” Which is strange because the first line of my config is a big comment that can be ignored. * If myself execute ““birdc configure” without touching/changing anything in the config, it is accepted and executed immediately without issues !!! Things I tried so far to overcome the issue: * I used subprocess.run() but didn’t have any luck * Tried to use a 2s sleep between writing the new config and reloading bird2, didn’t work * I used python2 instead of python3 but still didn’t have any luck * I executed “birdc configure” via a BASH script, still didn’t work * User and file permissions checked, now problem. Anyone has experienced this weird problem before and has a suggestion to overcome it? It seems to be a birdc issue and doesn’t like to be called from scripts. FYI, I use Bird 2.0.10 on CentOS 7 and Python 3.6.8 Kind Regards Stavros

6 7

Re: bgp keepalive & hold timers
by Serge G 10 Dec '22

10 Dec '22

Hi, Not sure if it's still relevant, but I just wanted to propose another approach. Instead of comparing configured keepalive with the hold timer received from a peer, it might be more straightforward to add another knob, e.g. "minimum-hold-timer". (as on Juniper https://www.juniper.net/documentation/us/en/software/junos/bgp/topics/ref/s…; Nokia also has similar knob) Reason for this is that (the following is just my opinion) 'keepalive' only configures an interval for keepalive messages. And if we start using the value of keepalive timer to enforce some restrictions on peer's hold timer, this may be confusing. In other words, "minimum-hold-timer" would more clearly indicate our restrictions on hold timers. If I see "minimum-hold-timer 30" in the configuration, I understand that this device has some limitations. If I see "keepalive 10", it doesn't tell me anything about restrictions, only that this device will send keepalives every 10 secs. P.S. I haven't dealt with mailing lists before, so forgive me if I reply to the wrong thread. This is the thread I;m replying to: https://bird.network.cz/pipermail/bird-users/2022-April/016071.html

4 8