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 <[email protected]> > --- > 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
