[PATCH] [RFC] Babel: Implement route daming with fixed delay
Daniel Gröber
dxld at darkboxed.org
Fri Mar 3 03:19:32 CET 2023
In order to prevent RTT based routing from causing persistent traffic
oscillations we delay core rte announcement of each prefix by a
configurable but metric invariant amount of time.
Initial announcements and withdrawals will go through undelayed but a
chnage in route for a prefix will cancel the previous announcement and
reset the delay.
---
This is just quickly thrown together to demonstrate the idea of how to
replace metric smoothing with something more simplistic. Obviously the
performance of using a linked list for keeping the scheduled
announcements is suboptimal, our binary heap could be used instead.
I'm not quite sure all the logic works out but let's discuss the
concept before spending more time on it :)
This could be extended to make the delay depend on metric difference
if it turns out that's necessary I just skipped it for simplicity.
proto/babel/babel.c | 79 +++++++++++++++++++++++++++++++++++++++++++--
proto/babel/babel.h | 11 +++++--
2 files changed, 86 insertions(+), 4 deletions(-)
diff --git a/proto/babel/babel.c b/proto/babel/babel.c
index 2243fc89..d6d99a37 100644
--- a/proto/babel/babel.c
+++ b/proto/babel/babel.c
@@ -62,6 +62,7 @@ static inline int gt_mod64k(uint a, uint b)
static void babel_expire_requests(struct babel_proto *p, struct babel_entry *e);
static void babel_announce_rte(struct babel_proto *p, struct babel_entry *e, struct babel_route *r);
+static void babel_sched_announce_rte(struct babel_proto *p, struct babel_entry *e, struct babel_route *r);
static void babel_rte_update_unreachable(struct babel_proto *p, struct babel_entry *e, u8 announce);
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, struct babel_neighbor *n);
@@ -653,7 +654,7 @@ done:
WALK_LIST2(r, n, nbr->routes, neigh_route)
{
r->metric = babel_compute_metric(nbr, r->advert_metric);
- babel_announce_rte(p, r->e, r);
+ babel_sched_announce_rte(p, r->e, r);
}
}
}
@@ -772,6 +773,50 @@ babel_announce_rte(struct babel_proto *p, struct babel_entry *e, struct babel_ro
}
}
+/*
+ * When route damping is enabled we have to delay updates to the kernel FIB. We
+ * do this by queueing some updates before actually announcing them to core.
+ */
+static void
+babel_sched_announce_rte(struct babel_proto *p, struct babel_entry *e, struct babel_route *r)
+{
+ struct babel_config *cf = (void *) p->p.cf;
+
+ if (!cf->route_damping ||
+ !e->selected ||
+ e->selected->metric < r->metric ||
+ /*^ When the best route's metric is worse than the one we're about to
+ * announce it's safe to do so immediately even if route damping is on as
+ * it won't get exported to most other protocols. Note add-path BGP is
+ * still notified but we're not concerned about micromanaging the
+ * stability of exotic setups, only our local kernel FIB's impact. */
+ r->metric == BABEL_INFINITY || !r->feasible)
+ /*^ This checks if announce_rte will do a withdrawal. */
+ {
+ if (e->scheduled) {
+ rem_node(&e->sched);
+ e->scheduled = NULL;
+ }
+
+ babel_announce_rte(p, r->e, r);
+ }
+ else
+ {
+ struct babel_iface *ifa = r->neigh->ifa;
+
+ if (!e->scheduled)
+ add_tail(&ifa->sched_rtes, &e->sched);
+ e->scheduled = r;
+
+ r->sched_time = current_time() + cf->route_damping;
+
+ if (!ifa->want_sched) {
+ ifa->next_sched = r->sched_time;
+ ifa->want_sched = 1;
+ }
+ }
+}
+
/*
* Functions to send replies
*/
@@ -1371,7 +1416,7 @@ babel_handle_update(union babel_msg *m, struct babel_iface *ifa)
e->updated = current_time();
}
- babel_announce_rte(p, e, r);
+ babel_sched_announce_rte(p, e, r);
}
void
@@ -1683,6 +1728,32 @@ babel_iface_timer(timer *t)
p->triggered = 0;
}
+ if (ifa->want_sched && now_ >= ifa->next_sched) {
+ TRACE(D_EVENTS, "Announcing scheduled rtes on %s", ifa->ifname);
+
+ struct babel_entry *e, *ex;
+
+ ifa->next_sched = TIME_INFINITY;
+
+ u8 all_announced = 1;
+ WALK_LIST_DELSAFE(e, ex, ifa->sched_rtes) {
+ struct babel_route *r = e->scheduled;
+ ASSERT(r);
+ if (now_ >= r->sched_time) {
+ rem_node(&e->sched);
+ babel_announce_rte(p, e, r);
+ } else {
+ all_announced = 0;
+ if (r->sched_time < ifa->next_sched)
+ ifa->next_sched = r->sched_time;
+ }
+ }
+
+ if (all_announced) {
+ ifa->want_sched = 0;
+ }
+ }
+
btime next_event = MIN(ifa->next_hello, ifa->next_regular);
if (ifa->want_triggered) next_event = MIN(next_event, ifa->next_triggered);
tm_set(ifa->timer, next_event);
@@ -1862,6 +1933,8 @@ babel_add_iface(struct babel_proto *p, struct iface *new, struct babel_iface_con
init_list(&ifa->msg_queue);
ifa->send_event = ev_new_init(ifa->pool, babel_send_queue, ifa);
+ init_list(&ifa->sched_rtes);
+
struct object_lock *lock = olock_new(ifa->pool);
lock->type = OBJLOCK_UDP;
lock->addr = IP6_BABEL_ROUTERS;
@@ -2523,6 +2596,8 @@ babel_init(struct proto_config *CF)
P->rte_better = babel_rte_better;
P->rte_igp_metric = babel_rte_igp_metric;
+ cf->route_damping = 15 S_; // HACK for testing
+
return P;
}
diff --git a/proto/babel/babel.h b/proto/babel/babel.h
index 3868d7c4..186d4297 100644
--- a/proto/babel/babel.h
+++ b/proto/babel/babel.h
@@ -134,6 +134,7 @@ struct babel_config {
list iface_list; /* List of iface configs (struct babel_iface_config) */
uint hold_time; /* Time to hold stale entries and unreachable routes */
u8 randomize_router_id;
+ uint route_damping;
struct channel_config *ip4_channel;
struct channel_config *ip6_channel;
@@ -216,6 +217,7 @@ struct babel_iface {
int tx_length;
list neigh_list; /* List of neighbors seen on this iface (struct babel_neighbor) */
list msg_queue;
+ list sched_rtes; /* Scheduled rte announcments for route dampening */
u16 hello_seqno; /* To be increased on each hello */
@@ -226,7 +228,9 @@ struct babel_iface {
btime next_hello;
btime next_regular;
btime next_triggered;
- btime want_triggered;
+ u8 want_triggered;
+ btime next_sched;
+ u8 want_sched;
timer *timer;
event *send_event;
@@ -292,6 +296,7 @@ struct babel_route {
ip_addr next_hop;
btime refresh_time;
btime expires;
+ btime sched_time;
};
struct babel_seqno_request {
@@ -306,7 +311,9 @@ struct babel_seqno_request {
};
struct babel_entry {
- struct babel_route *selected;
+ node sched; /* for babel_iface.sched_rtes */
+
+ struct babel_route *selected, *scheduled;
list routes; /* Routes for this prefix (struct babel_route) */
list sources; /* Source entries for this prefix (struct babel_source). */
--
2.30.2
More information about the Bird-users
mailing list