[PATCH] babel: Rework seqno request handling to track sender, not destination
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@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
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.
This paragraph is not entirely clear to me. Do you mean that the neighbour on behalf of which we're forwarding the request has gone away?
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.
Note however that Babel is designed to run reasonably well with very large update intervals, so the next unfeasible update might not be coming soon. I agree that the request tracking is the most complex part of Babel, though, so it makes sense to take some shortcuts. (Actually, the protocol was designed so that all the intervals (Hello, IHU and Update) can vary dynamically, and it would make a lot of sense to increase the Update interval when we detect a large, stable network.) -- Juliusz
Juliusz Chroboczek <jch@irif.fr> writes:
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.
This paragraph is not entirely clear to me. Do you mean that the neighbour on behalf of which we're forwarding the request has gone away?
Yes. Before we were tying a request object to the neighbour we sent the request to, so if that neighbour went away (e.g., when the interface goes down), the request is cleared out as well and won't be resent. This patch moves the tracking so that the neighbour entry associated with a request is the one on whose behalf we are forwarding it. We could just clear it out, but because of duplicate suppression we don't know if that's premature (i.e., if another neighbour also send the same request). So the safe thing to do is keep the request object around so it can be retransmitted (if we don't get an update for the prefix before the timeout). Another option would be to explicitly track all neighbours we received a request for a particular prefix from. That gets a bit more complicated because of the many-to-many relationship, though: either we need to keep a list of all neighbours linked to a request, or we need to duplicate the request object. The latter would mess with duplicate suppression, and the former is annoying to do with the linked-list structures that Bird uses. Oh, and the reason we don't need to keep track of all neighbours is that when we satisfy a request we just trigger a global (multicast) update for the prefix instead of sending it individually to all neighbours we forwarded requests on behalf of.
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.
Note however that Babel is designed to run reasonably well with very large update intervals, so the next unfeasible update might not be coming soon. I agree that the request tracking is the most complex part of Babel, though, so it makes sense to take some shortcuts.
Hmm, right, well my reasoning was also that receiving an unfeasible update is not as "urgent" because we most likely have another route for the same prefix that is feasible already. Or is this intuition not correct?
(Actually, the protocol was designed so that all the intervals (Hello, IHU and Update) can vary dynamically, and it would make a lot of sense to increase the Update interval when we detect a large, stable network.)
Yeah, I've thought about playing with that on several occasions. Lengthening the update interval would also be a good way to handle very large routing tables without generating too much update traffic. Would be fun if we could propagate a full internet routing table over Babel :) -Toke
This paragraph is not entirely clear to me. Do you mean that the neighbour on behalf of which we're forwarding the request has gone away?
Yes.
[...]
Oh, and the reason we don't need to keep track of all neighbours is that when we satisfy a request we just trigger a global (multicast) update for the prefix instead of sending it individually to all neighbours we forwarded requests on behalf of.
Right. Babeld does the same. But in that case, I don't understand why you need to keep track of the neighbour in the first place. I haven't looked at this code in some time, but I seem to recall that in babeld, we simply retain the information that there's a pending request, we don't need to know on whose behalf it's being made.
Hmm, right, well my reasoning was also that receiving an unfeasible update is not as "urgent" because we most likely have another route for the same prefix that is feasible already. Or is this intuition not correct?
Consider the case of a well-connected cloud that is connected to the source through just one router: B1 / | / | S ---- A --B2 \ | \ | B3 If the metric of the route S-A increases by more than max_i(d(A,B_i)), then all of the updates sent by A become unfeasible for all of the B_i. Hence, all of the B_i remain unreachable until S originates a new seqno. A will forward a request on behalf of the B_i, and due to duplicate suppression, it will be forwarded only once. If the request A->B is lost, then you're waiting until the next unfeasible update sent by A. -- Juliusz
Juliusz Chroboczek <jch@irif.fr> writes:
This paragraph is not entirely clear to me. Do you mean that the neighbour on behalf of which we're forwarding the request has gone away?
Yes.
[...]
Oh, and the reason we don't need to keep track of all neighbours is that when we satisfy a request we just trigger a global (multicast) update for the prefix instead of sending it individually to all neighbours we forwarded requests on behalf of.
Right. Babeld does the same.
But in that case, I don't understand why you need to keep track of the neighbour in the first place. I haven't looked at this code in some time, but I seem to recall that in babeld, we simply retain the information that there's a pending request, we don't need to know on whose behalf it's being made.
Right, so after going after this a couple of times, I think I see the discrepancy here: in Bird we're currently doing retransmission at every hop; so since we're also retransmitting a request that we're forwarding, we need to keep track of which neighbour it came from so we're not sending it back to the originator. But reading the sections in the RFC again I can see how the section on forwarding doesn't actually say anything about retransmitting; and I guess it does make more sense that it's just the originator who does retransmission. So if we're just doing forwarding as a one-off then you're right, we don't need to keep the originating neighbour around. That should simplify things some :)
Hmm, right, well my reasoning was also that receiving an unfeasible update is not as "urgent" because we most likely have another route for the same prefix that is feasible already. Or is this intuition not correct?
Consider the case of a well-connected cloud that is connected to the source through just one router:
B1 / | / | S ---- A --B2 \ | \ | B3
If the metric of the route S-A increases by more than max_i(d(A,B_i)), then all of the updates sent by A become unfeasible for all of the B_i. Hence, all of the B_i remain unreachable until S originates a new seqno.
A will forward a request on behalf of the B_i, and due to duplicate suppression, it will be forwarded only once. If the request A->B is lost, then you're waiting until the next unfeasible update sent by A.
I this example will be covered by the starvation avoidance mechanism in 3.8.2.1, though? So do we really need to retransmit the unicast seqno requests sent in response to an unfeasible update (section 3.8.2.2)? If I'm reading the babeld source correctly it's not doing that either (nor is it suppressing such one-off updates if there's already another outstanding request)? -Toke
Right, so after going after this a couple of times, I think I see the discrepancy here: in Bird we're currently doing retransmission at every hop;
Yep, that's the intent of RFC 8966 Section 3.8.1 (I agree it's not perfectly clear): A single request MUST NOT be duplicated: it MUST NOT be forwarded to a multicast address, and it MUST NOT be forwarded to multiple neighbours. The goal is to have a bound on the number of requests in flight for a given prefix: it's at most equal to the number of routers that are at the border of the subnetwork for which the prefix became unfeasible. If you start resending requests within the network, you're multiplying a term that's exponential in the diameter of the feasible part of the network. And exponentials make me nervous. -- Juliusz
Juliusz Chroboczek <jch@irif.fr> writes:
Right, so after going after this a couple of times, I think I see the discrepancy here: in Bird we're currently doing retransmission at every hop;
Yep, that's the intent of RFC 8966 Section 3.8.1 (I agree it's not perfectly clear):
A single request MUST NOT be duplicated: it MUST NOT be forwarded to a multicast address, and it MUST NOT be forwarded to multiple neighbours.
The goal is to have a bound on the number of requests in flight for a given prefix: it's at most equal to the number of routers that are at the border of the subnetwork for which the prefix became unfeasible. If you start resending requests within the network, you're multiplying a term that's exponential in the diameter of the feasible part of the network. And exponentials make me nervous.
Right, makes sense. I'll send a v2 of the patch reworking the handling to only resend requests we originated (and get rid of the neighbour in the request state). -Toke
On Sat, Dec 17, 2022 at 03:54:32PM +0100, Juliusz Chroboczek via Bird-users wrote:
Oh, and the reason we don't need to keep track of all neighbours is that when we satisfy a request we just trigger a global (multicast) update for the prefix instead of sending it individually to all neighbours we forwarded requests on behalf of.
Right. Babeld does the same.
But in that case, I don't understand why you need to keep track of the neighbour in the first place. I haven't looked at this code in some time, but I seem to recall that in babeld, we simply retain the information that there's a pending request, we don't need to know on whose behalf it's being made.
Well, it is written in RFC: 3.2.7. The Table of Pending Seqno Requests ... This table is indexed by triples of the form (prefix, plen, router-id), and every entry in this table contains the following data: * the prefix, plen, router-id, and seqno being requested; * the neighbour, if any, on behalf of which we are forwarding this request; * a small integer indicating the number of times that this request will be resent if it remains unsatisfied. But it is true that since forwarded requests are not resent, i also do not see the need for this information.
Yep, that's the intent of RFC 8966 Section 3.8.1 (I agree it's not perfectly clear):
A single request MUST NOT be duplicated: it MUST NOT be forwarded to a multicast address, and it MUST NOT be forwarded to multiple neighbours.
I think that the text of section 3.2.7 (The Table of Pending Seqno Requests) is confusing with regard to this, as it describes resent counter for each entry without any qualifier that it is only used for originated requests and not for forwarded requests). -- Elen sila lumenn' omentielvo Ondrej 'Santiago' Zajicek (email: santiago@crfreenet.org) OpenPGP encrypted e-mails preferred (KeyID 0x11DEADC3, wwwkeys.pgp.net) "To err is human -- to blame it on a computer is even more so."
* the neighbour, if any, on behalf of which we are forwarding this request;
[...]
But it is true that since forwarded requests are not resent, i also do not see the need for this information.
Agreed on both counts.
I think that the text of section 3.2.7 (The Table of Pending Seqno Requests) is confusing with regard to this, as it describes resent counter for each entry without any qualifier that it is only used for originated requests and not for forwarded requests).
Right. The field is only necessary if you send an update only to the requesting node. Neither BIRD nor babeld currently implements that. Some background. The basic principle of Seqno requests is sound: the only entity that can reliably determine that it's suffering from starvation is the starving node itself, and hence Babel (like EIGRP, but unlike DSDV) uses an explicit request mechanism to resolve starvation when it happens. The mechanism is also provably complete: in the absence of persistent packet loss, the simple mechanism in Section 3.8.2.2 (sending a request when starving and receiving an unfeasible update) is enough to guarantee completeness. So from a purely theoretical point of view, all you need to do is (1) send a request when you're starving and receive an unfeasible update, and (2) forward each request at most once and only if you have a feasible route. However, if this is the only mechanism you implement, then the expected convergence time will be on the order of half the update interval multiplied by the distance (hop count) to the closest non-starving router. And that's in the absence of packet loss. Back in 2008-2010, I've spent a lot of time experimenting with various tradeoffs, and the RFC is confusing as a result of these experimentations. The algorithm described in the RFC works fairly well in practice, except during periods of very high instability in dense networks, in which case it tends to generate too many requests. We could certainly do better if somebody spent a year of their life working on the problem. Perhaps when I retire :-) -- Juliusz
participants (3)
-
Juliusz Chroboczek -
Ondrej Zajicek -
Toke Høiland-Jørgensen