[PATCH 3/3] babel: Add route metric smoothing
Daniel Gröber
dxld at darkboxed.org
Mon Feb 27 22:52:45 CET 2023
Hi Toke,
See below.
On Sun, Feb 26, 2023 at 11:10:06PM +0100, Toke Høiland-Jørgensen via Bird-users wrote:
> The Babel RTT extension employs metric smoothing to dampen route
> oscillations in the face of varying RTT values between two peers[0].
>
> This patch implements such dampening in Bird, roughly following the
> implementation in babeld (i.e., using the same exponential function
> definition). The main difference is that we calculate everything in the
> native Bird microsecond time unit (and increase constants accordingly), and
> that we split out the smoothed metric calculation in two function variants,
> one that has no side effects and one that does.
>
> [0] https://arxiv.org/pdf/1403.3488.pdf
>
> Signed-off-by: Toke Høiland-Jørgensen <toke at toke.dk>
> ---
> doc/bird.sgml | 12 +++++
> proto/babel/babel.c | 121 ++++++++++++++++++++++++++++++++++++++++---
> proto/babel/babel.h | 16 ++++++
> proto/babel/config.Y | 10 +++-
> 4 files changed, 150 insertions(+), 9 deletions(-)
>
> diff --git a/doc/bird.sgml b/doc/bird.sgml
> index 451dff4031d5..82f0ded13133 100644
> --- a/doc/bird.sgml
> +++ b/doc/bird.sgml
> @@ -1915,6 +1915,7 @@ protocol babel [<name>] {
> ipv4 { <channel config> };
> ipv6 [sadr] { <channel config> };
> randomize router id <switch>;
> + metric decay <time>;
> interface <interface pattern> {
> type <wired|wireless|tunnel>;
> rxcost <number>;
> @@ -1965,6 +1966,17 @@ protocol babel [<name>] {
> router ID every time it starts up, which avoids this problem at the cost
> of not having stable router IDs in the network. Default: no.
>
> + <tag><label id="babel-metric-decay">metric decay <m/time/ s</tag>
> + The metric smoothing decay time. When route metrics vary (because of
> + varying quality of a wireless link, or varying RTT when timestamps are
> + enabled), Babel applies an exponential smoothing procedure to the metric
> + to dampen route oscillations. This parameter specifies the half-life of
> + the convergence of the smoothed metric to the actual metric of the route.
> + I.e., the distance between the smoothed and the actual metric will be
> + halfed for each time period specified here (until they converge). Set to 0
> + to disable metric smoothing; if set, the value must be in the interval
> + 1-180 s. Default: 4 s
> +
> <tag><label id="babel-type">type wired|wireless|tunnel </tag>
> This option specifies the interface type: Wired, wireless or tunnel. On
> wired interfaces a neighbor is considered unreachable after a small number
> diff --git a/proto/babel/babel.c b/proto/babel/babel.c
> index 04613788303c..a95e37f5c413 100644
> --- a/proto/babel/babel.c
> +++ b/proto/babel/babel.c
> @@ -144,6 +144,103 @@ babel_expire_sources(struct babel_proto *p UNUSED, struct babel_entry *e)
> }
> }
>
> +static u16
> +babel_calc_smoothed_metric(struct babel_proto *p, struct babel_route *r, u8 update)
> +{
> + struct babel_config *cf = (void *) p->p.cf;
> + uint metric = r->metric, smoothed_metric = r->smoothed_metric;
> + btime smoothed_time = r->smoothed_time, now = current_time();
> +
> + if (!cf->metric_decay || metric == BABEL_INFINITY ||
> + metric == smoothed_metric || !smoothed_time)
> + {
> + smoothed_metric = metric;
> + smoothed_time = now;
> + goto out;
> + }
> +
> + int diff = metric - smoothed_metric;
> +
> + /*
> + * The decay defines the half-life of the metric convergence, so first iterate
> + * in halving steps
> + */
> + while (smoothed_time < now - cf->metric_decay && diff) {
> + smoothed_metric += diff/2;
> + smoothed_time += cf->metric_decay;
> + diff = metric - smoothed_metric;
> + }
> +
> + /*
> + * Then, update remainder in BABEL_SMOOTHING_STEP intervals using the
> + * exponential function (approximated via the pre-computed reciprocal).
> + */
> + while (smoothed_time < now - BABEL_SMOOTHING_STEP && diff) {
> + smoothed_metric += (BABEL_SMOOTHING_STEP * diff *
> + (cf->smooth_recp - BABEL_SMOOTHING_UNIT) / BABEL_SMOOTHING_UNIT);
> + smoothed_time += BABEL_SMOOTHING_STEP;
> + diff = metric - smoothed_metric;
> + }
> +
> + /* Consider the metric converged once we're close enough */
> + if (ABS(diff) < BABEL_SMOOTHING_MIN_DIFF)
> + smoothed_metric = metric;
> +
> +out:
> + if (update) {
> + r->smoothed_metric = smoothed_metric;
> + r->smoothed_time = smoothed_time;
> + }
> +
> + return smoothed_metric;
> +}
> +
> +static u16
> +babel_update_smoothed_metric(struct babel_proto *p, struct babel_route *r)
> +{
> + if (!r->metric)
> + return 0;
> +
> + if (!r->smoothed_metric) {
> + r->smoothed_metric = r->metric;
> + r->smoothed_time = current_time();
> + return r->smoothed_metric;
> + }
> +
> + u16 smoothed = babel_calc_smoothed_metric(p, r, 1);
> + DBG("Updated smoothed metric for prefix %N: router-id %lR metric %d/%d\n",
> + r->e->n.addr, r->router_id, r->metric, smoothed);
> +
> + return smoothed;
> +}
> +
> +static u16
> +babel_smoothed_metric(struct babel_proto *p, struct babel_route *r)
> +{
> + return babel_calc_smoothed_metric(p, r, 0);
> +}
> +
> +static void
> +babel_update_metric(struct babel_proto *p, struct babel_route *r, u16 metric)
> +{
> + babel_update_smoothed_metric(p, r);
> + r->metric = metric;
> +}
> +
> +static inline u8
> +babel_route_better(struct babel_proto *p, struct babel_route *mod,
> + struct babel_route *best)
> +{
> + if (!mod->feasible)
> + return 0;
> +
> + if (!best)
> + return mod->metric < BABEL_INFINITY;
> +
> + return (mod->metric < best->metric &&
> + babel_smoothed_metric(p, mod) < babel_smoothed_metric(p, best));
> +}
> +
> static struct babel_route *
> babel_find_route(struct babel_entry *e, struct babel_neighbor *n)
> {
> @@ -161,8 +258,10 @@ babel_get_route(struct babel_proto *p, struct babel_entry *e, struct babel_neigh
> {
> struct babel_route *r = babel_find_route(e, nbr);
>
> - if (r)
> + if (r) {
> + babel_update_smoothed_metric(p, r);
What's this for? Seems to me the only call-site (babel_handle_update) will
also call babel_update_metric itself.
> return r;
> + }
>
> r = sl_allocz(p->route_slab);
>
> @@ -662,7 +761,7 @@ done:
> struct babel_route *r; node *n;
> WALK_LIST2(r, n, nbr->routes, neigh_route)
> {
> - r->metric = babel_compute_metric(nbr, r->advert_metric);
> + babel_update_metric(p, r, babel_compute_metric(nbr, r->advert_metric));
> babel_select_route(p, r->e, r);
> }
> }
> @@ -802,8 +901,7 @@ babel_select_route(struct babel_proto *p, struct babel_entry *e, struct babel_ro
> /* Shortcut if only non-best was modified */
> if (mod && (mod != best))
> {
> - /* Either select modified route, or keep old best route */
> - if ((mod->metric < (best ? best->metric : BABEL_INFINITY)) && mod->feasible)
> + if (babel_route_better(p, mod, best))
> best = mod;
> else
> return;
> @@ -814,17 +912,24 @@ babel_select_route(struct babel_proto *p, struct babel_entry *e, struct babel_ro
> if (!best || (best->metric == BABEL_INFINITY) || !best->feasible)
> best = NULL;
>
> + /* best will be compared to many routes below, make sure it's up-to-date */
> + if (best)
> + babel_update_smoothed_metric(p, best);
> +
> /* Find the best feasible route from all routes */
> WALK_LIST(r, e->routes)
> - if ((r->metric < (best ? best->metric : BABEL_INFINITY)) && r->feasible)
> + if (babel_route_better(p, r, best))
> best = r;
> }
>
> if (best)
> {
> if (best != e->selected)
> - TRACE(D_EVENTS, "Picked new route for prefix %N: router-id %lR metric %d",
> - e->n.addr, best->router_id, best->metric);
> + {
> + u16 smoothed = babel_update_smoothed_metric(p, best);
> + TRACE(D_EVENTS, "Picked new route for prefix %N: router-id %lR metric %d/%d",
> + e->n.addr, best->router_id, best->metric, smoothed);
> + }
> }
> else if (e->selected)
> {
> @@ -1425,9 +1530,9 @@ babel_handle_update(union babel_msg *m, struct babel_iface *ifa)
> return;
>
> /* Last paragraph above - update the entry */
> + babel_update_metric(p, r, metric);
> r->feasible = feasible;
> r->seqno = msg->seqno;
> - r->metric = metric;
> r->advert_metric = msg->metric;
> r->router_id = msg->router_id;
> r->next_hop = msg->next_hop;
> diff --git a/proto/babel/babel.h b/proto/babel/babel.h
> index edde4cabe6b1..7c4ea895e45c 100644
> --- a/proto/babel/babel.h
> +++ b/proto/babel/babel.h
> @@ -63,6 +63,18 @@
> #define BABEL_RTT_MAX (120 MS_)
> #define BABEL_RTT_DECAY 42
>
> +/*
> + * Constants for calculating metric smoothing. Chosen so that:
> + * log(2) = BABEL_SMOOTHING_CONSTANT / BABEL_SMOOTHING_UNIT, which means that
> + * log(2)/x can be calculated as BABEL_SMOOTHING_UNIT + BABEL_SMOOTHING_CONSTANT / x
> + */
> +#define BABEL_SMOOTHING_UNIT 0x10000000
> +#define BABEL_SMOOTHING_CONSTANT 186065279
> +#define BABEL_SMOOTHING_STEP (1 S_) /* smoothing calculated in this step size */
> +#define BABEL_SMOOTHING_MIN_DIFF 4 /* metric diff beneath this is converged */
> +#define BABEL_SMOOTHING_DECAY (4 S_)
> +#define BABEL_SMOOTHING_DECAY_MAX (180 S_)
> +
> /* Max interval that will not overflow when carried as 16-bit centiseconds */
> #define BABEL_TIME_UNITS 10000 /* On-wire times are counted in centiseconds */
> #define BABEL_MIN_INTERVAL (0x0001 * BABEL_TIME_UNITS)
> @@ -131,6 +143,8 @@ enum babel_ae_type {
> struct babel_config {
> struct proto_config c;
> list iface_list; /* List of iface configs (struct babel_iface_config) */
> + btime metric_decay;
> + uint smooth_recp; /* Reciprocal for exponential metric smoothing */
> uint hold_time; /* Time to hold stale entries and unreachable routes */
> u8 randomize_router_id;
>
> @@ -285,9 +299,11 @@ struct babel_route {
> u16 seqno;
> u16 metric;
> u16 advert_metric;
> + u16 smoothed_metric;
> u64 router_id;
> ip_addr next_hop;
> btime refresh_time;
> + btime smoothed_time;
> btime expires;
> };
>
> diff --git a/proto/babel/config.Y b/proto/babel/config.Y
> index b8af02679f0c..6e767e462b49 100644
> --- a/proto/babel/config.Y
> +++ b/proto/babel/config.Y
> @@ -37,6 +37,13 @@ babel_proto_start: proto_start BABEL
> this_proto = proto_config_new(&proto_babel, $1);
> init_list(&BABEL_CFG->iface_list);
> BABEL_CFG->hold_time = 1 S_;
> + BABEL_CFG->metric_decay = BABEL_SMOOTHING_DECAY;
> +};
> +
> +babel_proto_finish:
> +{
> + if (BABEL_CFG->metric_decay)
> + BABEL_CFG->smooth_recp = BABEL_SMOOTHING_UNIT + BABEL_SMOOTHING_CONSTANT / BABEL_CFG->metric_decay;
> };
>
> babel_proto_item:
> @@ -44,6 +51,7 @@ babel_proto_item:
> | proto_channel
> | INTERFACE babel_iface
> | RANDOMIZE ROUTER ID bool { BABEL_CFG->randomize_router_id = $4; }
> + | METRIC DECAY expr_us { BABEL_CFG->metric_decay = $3; if ($3 && (($3 < BABEL_SMOOTHING_STEP) || ($3 > BABEL_SMOOTHING_DECAY_MAX))) cf_error("Metric decay must be 0, or between 1-180s"); }
> ;
>
> babel_proto_opts:
> @@ -52,7 +60,7 @@ babel_proto_opts:
> ;
>
> babel_proto:
> - babel_proto_start proto_name '{' babel_proto_opts '}';
> + babel_proto_start proto_name '{' babel_proto_opts '}' babel_proto_finish;
>
>
> babel_iface_start:
> --
> 2.39.1
>
--Daniel
More information about the Bird-users
mailing list