[PATCH] babel: Rework seqno request handling to track sender, not destination
Toke Høiland-Jørgensen
toke at toke.dk
Sat Dec 17 02:02:23 CET 2022
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 at 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
More information about the Bird-users
mailing list