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