- Bird-users - Mailing Lists

Babel: Clarifications on seqno request handling in bird
by dxld＠darkboxed.org 28 Feb '23

28 Feb '23

Hi Ondrej, Toke, Juliusz and lists, I'm working on v4 of my bird route selection patch[1] and I just have a couple babel spec and bird implementation questions. [1]: http://trubka.network.cz/pipermail/bird-users/2023-January/016621.html Just a quick recap for anyone not following my "Replace internal route selection" patch: the idea is to install every feasible route into the bird core and let it give us a callback (rt_notify) with the optimal route it picked instead of doing this in the babel protocol. As Toke noted up to my v3 patch I break sending seqno requests when we loose the last feasible route (RFC8966 section 3.8.2.1.) because I accidentally removed the code which deals with that together with the babel_select_route function. To fix this I tried to move that code to our rt_notify callback instead. In testing I've found a major problem with this approach however. Say the babel proto is currently exporting a route to the core, then a more preferred route is exported by some other protocol (say "static") and then the babel route expires. In this case we ought to send a seqno request when the babel routes go away but rt_notify doesn't get called since the selected (static) route didn't change at all. I don't think RFC8966 is really framed in bird's "multi protocol" mindset so it's unclear to me whether this is something we have to fix or not. Section 3.8.2.1. says: > A node that has lost all feasible routes to a given destination but still > has unexpired unfeasible routes to that destination MUST send a seqno > request; I could for example read this as the above mentioned static route constituting a feasible route received from a bird "internal" babel neighbour which would make the behaviour described above perfectly fine, no? @Juliusz what's your opinion of this interpretation? Any suggestions on how to deal with this? @Bird folks: can anyone think of a way to be notified of any and all changes in rt_notify? I assume it's not possible from some light reading of the nest code but figured I might as well ask. If all else fails I can reinstate parts of the babel proto internal route selection or try to simply count available feasible routes instead of doing the full selection, just want to keep things as simple as possible. -- Further, looking at the code implementing RFC section 3.8.2.2 in babel_handle_update: if (!feasible && (metric != BABEL_INFINITY) && (!best || (r == best) || (metric < best->metric))) /*^ */ babel_generate_seqno_request(p, e, s->router_id, s->seqno + 1, nbr); It's unclear to me what the (!best) condition corresponds to from the RFC text. The r==best check clearly corresponds to "... when it receives an unfeasible update for a route that is currently selected" and (metric < best->metric) is for "... that is preferable to the currently selected route". But why do we always send a seqno request when there isn't a selected route when that isn't called for in the RFC? Thanks, --Daniel

4 7

[PATCH 3/3] babel: Add route metric smoothing
by Toke Høiland-Jørgensen 27 Feb '23

27 Feb '23

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(a)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); 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

2 1

[PATCH v5] Babel: Replace internal route selection by bird's nest
by Daniel Gröber 27 Feb '23

27 Feb '23

This introduces the ability to filter routes from specific interfaces and neighbours. With the current internal route selection proto babel exports only up to one route and an admin cannot do fine-grained filtering. To fix this we rip out the internal route selection entirely and export evey babel route as a distinct route into the bird's nest instead. In the presence of esoteric route filters this change may be observable by users however we feel the additional filtering power is more important. A release note entry for this change is recommended. --- Changes in v5: - Fix crash due missing rt_lock_source from rte_src pruning - Fix broken rt_notify retraction logic (!internal) which would just crash proto/babel/babel.c | 285 ++++++++++++++++++++------------------------ proto/babel/babel.h | 3 + 2 files changed, 135 insertions(+), 153 deletions(-) diff --git a/proto/babel/babel.c b/proto/babel/babel.c index 04613788..c030784a 100644 --- a/proto/babel/babel.c +++ b/proto/babel/babel.c @@ -28,10 +28,12 @@ * possible routes for the prefix are tracked as &babel_route entries and the * feasibility distance is maintained through &babel_source structures. * - * The main route selection is done in babel_select_route(). This is called when - * an entry is updated by receiving updates from the network or when modified by - * internal timers. The function selects from feasible and reachable routes the - * one with the lowest metric to be announced to the core. + * The main route selection is done by bird's nest (heh). For each prefix we + * export all feasible routes to the core with a distinct source (rte_src) per + * neihbour so bird handles them as distinct routes. Nest will then notify us of + * one best route for each prefix, either our own (internal) or from another + * protocol, by calling babel_rt_notify. For internal best routes we remember + * which babel_route it selected in babel_entry.selected. * * Supported standards: * RFC 8966 - The Babel Routing Protocol @@ -59,8 +61,8 @@ static inline int gt_mod64k(uint a, uint b) { return ge_mod64k(a, b) && a != b; } 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_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); static void babel_update_cost(struct babel_neighbor *n); @@ -178,9 +180,7 @@ static inline void babel_retract_route(struct babel_proto *p, struct babel_route *r) { r->metric = r->advert_metric = BABEL_INFINITY; - - if (r == r->e->selected) - babel_select_route(p, r->e, r); + babel_announce_rte(p, r->e, r); } static void @@ -192,9 +192,6 @@ babel_flush_route(struct babel_proto *p UNUSED, struct babel_route *r) rem_node(NODE r); rem_node(&r->neigh_route); - if (r->e->selected == r) - r->e->selected = NULL; - sl_free(r); } @@ -210,6 +207,7 @@ babel_expire_route(struct babel_proto *p, struct babel_route *r) { r->metric = r->advert_metric = BABEL_INFINITY; r->expires = current_time() + cf->hold_time; + babel_announce_rte(p, r->e, r); } else { @@ -239,8 +237,6 @@ babel_expire_routes_(struct babel_proto *p, struct fib *rtable) loop: FIB_ITERATE_START(rtable, &fit, struct babel_entry, e) { - int changed = 0; - WALK_LIST_DELSAFE(r, rx, e->routes) { if (r->refresh_time && r->refresh_time <= now_) @@ -248,23 +244,12 @@ loop: if (r->expires && r->expires <= now_) { - changed = changed || (r == e->selected); + FIB_ITERATE_PUT(&fit); babel_expire_route(p, r); + goto loop; } } - if (changed) - { - /* - * We have to restart the iteration because there may be a cascade of - * synchronous events babel_select_route() -> nest table change -> - * babel_rt_notify() -> rtable change, invalidating hidden variables. - */ - FIB_ITERATE_PUT(&fit); - babel_select_route(p, e, NULL); - goto loop; - } - /* Clean up stale entries */ if ((e->valid == BABEL_ENTRY_STALE) && ((e->updated + cf->hold_time) <= now_)) e->valid = BABEL_ENTRY_DUMMY; @@ -273,7 +258,7 @@ loop: if (e->unreachable && (!e->valid || (e->router_id == p->router_id))) { FIB_ITERATE_PUT(&fit); - babel_announce_retraction(p, e); + babel_rte_update_unreachable(p, e, 0); goto loop; } @@ -457,6 +442,8 @@ babel_get_neighbor(struct babel_iface *ifa, ip_addr addr) nbr = mb_allocz(ifa->pool, sizeof(struct babel_neighbor)); nbr->ifa = ifa; + nbr->src = rt_get_source(&p->p, idm_alloc(&p->src_ids)); + rt_lock_source(nbr->src); nbr->addr = addr; nbr->rxcost = BABEL_INFINITY; nbr->txcost = BABEL_INFINITY; @@ -484,6 +471,9 @@ babel_flush_neighbor(struct babel_proto *p, struct babel_neighbor *nbr) } nbr->ifa = NULL; + + rt_unlock_source(nbr->src); + idm_free(&p->src_ids, nbr->src->private_id); rem_node(NODE nbr); mb_free(nbr); } @@ -663,11 +653,47 @@ done: WALK_LIST2(r, n, nbr->routes, neigh_route) { r->metric = babel_compute_metric(nbr, r->advert_metric); - babel_select_route(p, r->e, r); + babel_announce_rte(p, r->e, r); } } } +/** + * This function handles announcing the special unreachable route we insert for + * a prefix whenever we have no more feasible routes available as per RFC8966 + * section 3.5.4 as well as retracting it when such routes are available + * again. + * + * We also remember if we inserted an unreachable route in e->unreachable in + * order to clean it up later in babel_expire_routes_. + */ +static void +babel_rte_update_unreachable(struct babel_proto *p, struct babel_entry *e, u8 announce) +{ + struct channel *c = (e->n.addr->type == NET_IP4) ? p->ip4_channel : p->ip6_channel; + rte *rte = NULL; + + if (announce) { + rta a0 = { + .source = RTS_BABEL, + .scope = SCOPE_UNIVERSE, + .dest = RTD_UNREACHABLE, + .pref = 1, + }; + + rta *a = rta_lookup(&a0); + rte = rte_get_temp(a, p->p.main_source); + } + + e->unreachable = announce; + + /* Unlike the regular per-neighbour routes we only want one unreachable route + * for each prefix. This is mainly due to the lifetime of the unreachable rte + * exceeding that of the neighbour's rte_src ID as the babal neighbour may be + * flushed before the unreachable route is retracted. */ + rte_update2(c, e->n.addr, rte, p->p.main_source); +} + /** * babel_announce_rte - announce selected route to the core * @p: Babel protocol instance @@ -678,12 +704,11 @@ done: * the entry is valid and ours, the unreachable route is announced instead. */ static void -babel_announce_rte(struct babel_proto *p, struct babel_entry *e) +babel_announce_rte(struct babel_proto *p, struct babel_entry *e, struct babel_route *r) { - struct babel_route *r = e->selected; struct channel *c = (e->n.addr->type == NET_IP4) ? p->ip4_channel : p->ip6_channel; - if (r) + if (r->metric != BABEL_INFINITY && r->feasible) { rta a0 = { .source = RTS_BABEL, @@ -727,122 +752,24 @@ babel_announce_rte(struct babel_proto *p, struct babel_entry *e) a0.nh.flags = RNF_ONLINK; rta *a = rta_lookup(&a0); - rte *rte = rte_get_temp(a, p->p.main_source); - - e->unreachable = 0; - rte_update2(c, e->n.addr, rte, p->p.main_source); - } - else if (e->valid && (e->router_id != p->router_id)) - { - /* Unreachable */ - rta a0 = { - .source = RTS_BABEL, - .scope = SCOPE_UNIVERSE, - .dest = RTD_UNREACHABLE, - .pref = 1, - }; - - rta *a = rta_lookup(&a0); - rte *rte = rte_get_temp(a, p->p.main_source); - - e->unreachable = 1; - rte_update2(c, e->n.addr, rte, p->p.main_source); - } - else - { - /* Retraction */ - e->unreachable = 0; - rte_update2(c, e->n.addr, NULL, p->p.main_source); - } -} - -/* Special case of babel_announce_rte() just for retraction */ -static inline void -babel_announce_retraction(struct babel_proto *p, struct babel_entry *e) -{ - struct channel *c = (e->n.addr->type == NET_IP4) ? p->ip4_channel : p->ip6_channel; - e->unreachable = 0; - rte_update2(c, e->n.addr, NULL, p->p.main_source); -} - - -/** - * babel_select_route - select best route for given route entry - * @p: Babel protocol instance - * @e: Babel entry to select the best route for - * @mod: Babel route that was modified or NULL if unspecified - * - * Select the best reachable and feasible route for a given prefix among the - * routes received from peers, and propagate it to the nest. This just selects - * the reachable and feasible route with the lowest metric, but keeps selected - * the old one in case of tie. - * - * If no feasible route is available for a prefix that previously had a route - * selected, a seqno request is sent to try to get a valid route. If the entry - * is valid and not owned by us, the unreachable route is announced to the nest - * (to blackhole packets going to it, as per section 2.8). It is later removed - * by babel_expire_routes(). Otherwise, the route is just removed from the nest. - * - * Argument @mod is used to optimize best route calculation. When specified, the - * function can assume that only the @mod route was modified to avoid full best - * route selection and announcement when non-best route was modified in minor - * way. The caller is advised to not call babel_select_route() when no change is - * done (e.g. periodic route updates) to avoid unnecessary announcements of the - * same best route. The caller is not required to call the function in case of a - * retraction of a non-best route. - * - * Note that the function does not active triggered updates. That is done by - * babel_rt_notify() when the change is propagated back to Babel. - */ -static void -babel_select_route(struct babel_proto *p, struct babel_entry *e, struct babel_route *mod) -{ - struct babel_route *r, *best = e->selected; + rte *rte = rte_get_temp(a, r->neigh->src); - /* 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) - best = mod; - else - return; + rte_update2(c, e->n.addr, rte, r->neigh->src); + if (e->unreachable) + babel_rte_update_unreachable(p, e, 0); } else { - /* Selected route may be modified and no longer admissible */ - if (!best || (best->metric == BABEL_INFINITY) || !best->feasible) - best = NULL; + if (e->selected == r) + /* We NULL e->selected here rather than wait for babel_rt_notify in order + * to stay in a sync context. This is to be prepared for async rt_notify + * in BIRD 3. This is critical as RFC8966 demands unfeasible or infinite + * metric routes never being selected (see section 3.6 Route + * Selection). */ + e->selected = NULL; - /* Find the best feasible route from all routes */ - WALK_LIST(r, e->routes) - if ((r->metric < (best ? best->metric : BABEL_INFINITY)) && r->feasible) - 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); + rte_update2(c, e->n.addr, NULL, r->neigh->src); } - else if (e->selected) - { - /* - * We have lost all feasible routes. We have to broadcast seqno request - * (Section 3.8.2.1) and keep unreachable route for a while (section 2.8). - * The later is done automatically by babel_announce_rte(). - */ - - TRACE(D_EVENTS, "Lost feasible route for prefix %N", e->n.addr); - if (e->valid && (e->selected->router_id == e->router_id)) - babel_add_seqno_request(p, e, e->selected->router_id, e->selected->seqno + 1, 0, NULL); - } - else - return; - - e->selected = best; - babel_announce_rte(p, e); } /* @@ -1405,7 +1332,12 @@ babel_handle_update(union babel_msg *m, struct babel_iface *ifa) /* * RFC 8966 3.8.2.2 - dealing with unfeasible updates. Generate a one-off * (not retransmitted) unicast seqno request to the originator of this update. - * Note: !feasible -> s exists, check for 's' is just for clarity / safety. + * + * Notes: + * - (!feasible) implies (s) is non-NULL, check for (s) is just for clarity + * and safety. + * - (!best) condition is not explicitly recommeded by RFCC8966 text but was + * in the old version, RFC6126. */ if (!feasible && s && (metric != BABEL_INFINITY) && (!best || (r == best) || (metric < best->metric))) @@ -1439,7 +1371,7 @@ babel_handle_update(union babel_msg *m, struct babel_iface *ifa) e->updated = current_time(); } - babel_select_route(p, e, r); + babel_announce_rte(p, e, r); } void @@ -2122,7 +2054,7 @@ static void babel_dump_entry(struct babel_entry *e) { struct babel_source *s; - struct babel_route *r; + struct babel_route *r, *best = e->selected; debug("Babel: Entry %N:\n", e->n.addr); @@ -2132,7 +2064,7 @@ babel_dump_entry(struct babel_entry *e) WALK_LIST(r,e->routes) { debug(" "); - if (r == e->selected) debug("*"); + if (r == best) debug("*"); babel_dump_route(r); } } @@ -2303,7 +2235,7 @@ babel_show_entries_(struct babel_proto *p, struct fib *rtable) FIB_WALK(rtable, struct babel_entry, e) { - struct babel_route *r = NULL; + struct babel_route *r = NULL, *best = e->selected; uint rts = 0, srcs = 0; node *n; @@ -2316,7 +2248,7 @@ babel_show_entries_(struct babel_proto *p, struct fib *rtable) if (e->valid) cli_msg(-1025, "%-*N %-23lR %6u %5u %7u %7u", width, e->n.addr, e->router_id, e->metric, e->seqno, rts, srcs); - else if (r = e->selected) + else if (r = best) cli_msg(-1025, "%-*N %-23lR %6u %5u %7u %7u", width, e->n.addr, r->router_id, r->metric, r->seqno, rts, srcs); else @@ -2353,10 +2285,10 @@ babel_show_routes_(struct babel_proto *p, struct fib *rtable) FIB_WALK(rtable, struct babel_entry, e) { - struct babel_route *r; + struct babel_route *r, *best = e->selected; WALK_LIST(r, e->routes) { - char c = (r == e->selected) ? '*' : (r->feasible ? '+' : ' '); + char c = (r == best) ? '*' : (r->feasible ? '+' : ' '); btime time = r->expires ? r->expires - current_time() : 0; cli_msg(-1025, "%-*N %-25I %-10s %5u %c %5u %7t", width, e->n.addr, r->next_hop, r->neigh->ifa->ifname, @@ -2428,8 +2360,9 @@ babel_preexport(struct channel *C, struct rte *new) } /* - * babel_rt_notify - core tells us about new route (possibly our own), - * so store it into our data structures. + * babel_rt_notify - BIRD core notifis us of changes in the selected optimal + * route. We can either get one of the routes back we exported or one from a + * different protocol. */ static void babel_rt_notify(struct proto *P, struct channel *c UNUSED, struct network *net, @@ -2437,15 +2370,19 @@ babel_rt_notify(struct proto *P, struct channel *c UNUSED, struct network *net, { struct babel_proto *p = (void *) P; struct babel_entry *e; + struct babel_iface *ifa; + struct babel_neighbor *n; if (new) { /* Update */ + uint internal = new->src->proto == P; uint rt_seqno; uint rt_metric = ea_get_int(new->attrs->eattrs, EA_BABEL_METRIC, 0); u64 rt_router_id = 0; + struct babel_route *best; - if (new->src->proto == P) + if (internal) { rt_seqno = ea_find(new->attrs->eattrs, EA_BABEL_SEQNO)->u.data; eattr *e = ea_find(new->attrs->eattrs, EA_BABEL_ROUTER_ID); @@ -2454,6 +2391,8 @@ babel_rt_notify(struct proto *P, struct channel *c UNUSED, struct network *net, } else { + /* If the selected route isn't one of ours we inject a new route into the + * babel domain as per RFC8966 section 3.7 */ rt_seqno = p->update_seqno; rt_router_id = p->router_id; } @@ -2467,6 +2406,27 @@ babel_rt_notify(struct proto *P, struct channel *c UNUSED, struct network *net, e = babel_get_entry(p, net->n.addr); + best = e->selected; + if (internal) { + ifa = babel_find_iface(p, new->attrs->nh.iface); + n = ifa ? babel_find_neighbor(ifa, new->attrs->from) : NULL; + best = n ? babel_get_route(p, e, n) : NULL; + ASSERT(best); /* Note: We think this can't happen but the lifetimes of the + * involved objects are complicated so we're not yet + * completely convinced. */ + } + else + { + best = NULL; + } + + if (best && 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); + + e->selected = best; + /* Activate triggered updates */ if ((e->valid != BABEL_ENTRY_VALID) || (e->router_id != rt_router_id)) @@ -2488,8 +2448,26 @@ babel_rt_notify(struct proto *P, struct channel *c UNUSED, struct network *net, if (!e || e->valid != BABEL_ENTRY_VALID) return; + if (e->selected) { + TRACE(D_EVENTS, "Lost all feasible routes for prefix %N", e->n.addr); + /* We had a feasible route, but now it's gone. We must send a seqno + * request (Section 3.8.2.1). As allowed by RFC8966 we choose to always do + * so even if we don't have any more unfeasible routes and we use the + * simple unconditional multicast strategy. + */ + if (e->valid && (e->selected->router_id == e->router_id)) + babel_add_seqno_request( + p, e, e->selected->router_id, e->selected->seqno + 1, 0, NULL); + } + + e->valid = BABEL_ENTRY_STALE; e->metric = BABEL_INFINITY; + e->selected = NULL; + + /* Install an unreachable route for prefix hold time as per RFC8966 section + * 3.5.4. */ + babel_rte_update_unreachable(p, e, 1); babel_trigger_update(p); e->updated = current_time(); @@ -2581,6 +2559,7 @@ babel_start(struct proto *P) p->source_slab = sl_new(P->pool, sizeof(struct babel_source)); p->msg_slab = sl_new(P->pool, sizeof(struct babel_msg_node)); p->seqno_slab = sl_new(P->pool, sizeof(struct babel_seqno_request)); + idm_init(&p->src_ids, P->pool, 8); p->log_pkt_tbf = (struct tbf){ .rate = 1, .burst = 5 }; diff --git a/proto/babel/babel.h b/proto/babel/babel.h index edde4cab..3868d7c4 100644 --- a/proto/babel/babel.h +++ b/proto/babel/babel.h @@ -25,6 +25,7 @@ #include "lib/socket.h" #include "lib/string.h" #include "lib/timer.h" +#include "lib/idm.h" #define EA_BABEL_METRIC EA_CODE(PROTOCOL_BABEL, 0) #define EA_BABEL_ROUTER_ID EA_CODE(PROTOCOL_BABEL, 1) @@ -191,6 +192,7 @@ struct babel_proto { slab *source_slab; slab *msg_slab; slab *seqno_slab; + struct idm src_ids; struct tbf log_pkt_tbf; /* TBF for packet messages */ }; @@ -233,6 +235,7 @@ struct babel_iface { struct babel_neighbor { node n; struct babel_iface *ifa; + struct rte_src *src; ip_addr addr; u16 rxcost; /* Sent in last IHU */ -- 2.30.2

1 0

Binding 2 VRFs to the same BGP instance
by Ramanathan Selvamani 27 Feb '23

27 Feb '23

Hi Team, I am using linux kernel 4.14 and trying to bind 2 vrfs to the same BGP instance. The BGP session is established. But the second VRF binding over-writes the first VRF binding. Do bird support this 2 vrf binding to the same BGP instance ? R1 ====== ipv4 table T_VRF_RED; ipv4 table T_VRF_BLUE; function oro_set_bgp_local_as() { bgp_path.prepend(100); return true; } function redistribute_proto() { if ((source = RTS_BGP)) then { return true; } if (net=0.0.0.0/0) then { return false;} if ((source = RTS_DEVICE)) then { return false; } if (source = RTS_STATIC) then { if(net=0.0.0.0/0) then { return false;} if (ifname = "lo") then { return false; } else { return false; } } if ((source = RTS_CFGSET)) then { return false; } if ((source = RTS_IAPVPN)) then { return false; } if ((source = RTS_OAP)) then { return false; } if (source = RTS_OSPF) then { return false; } if (source = RTS_OSPF_IA) then { return false; } if (source = RTS_OSPF_EXT1) then { return false; } if (source = RTS_OSPF_EXT2) then { return false; } if ((source = RTS_OSPF) || (source = RTS_OSPF_IA) || (source = RTS_OSPF_EXT1) || (source = RTS_OSPF_EXT2)) then { return false; } return false; } protocol kernel K_VRF_RED { vrf "red"; kernel table 100; scan time 20; ipv4 { table T_VRF_RED; import all; export all; }; } protocol kernel K_VRF_BLUE { vrf "blue"; kernel table 200; scan time 20; ipv4 { table T_VRF_BLUE; import all; export all; }; } protocol direct C_VRF_RED { vrf "red"; ipv4 { table T_VRF_RED; }; } protocol direct C_VRF_BLUE { vrf "blue"; ipv4 { table T_VRF_BLUE; }; } protocol static S_VRF_RED { vrf "red"; ipv4 { table T_VRF_RED; }; route 10.10.1.0/24 blackhole; } protocol static S_VRF_BLUE { vrf "blue"; ipv4 { table T_VRF_BLUE; }; route 10.10.1.0/24 blackhole; } protocol bgp B_VRF_RED { vrf "red"; vrf "blue"; router id 10.16.44.216; local 50.0.12.1 as 100; neighbor 50.0.12.2 as 100; enable as4 on; hold time 90; keepalive time 30; direct; # regular IPv4 unicast (1/1) ipv4 { table T_VRF_RED; table T_VRF_BLUE; import all; export all; }; } R2 ====== ipv4 table T_VRF_RED; ipv4 table T_VRF_BLUE; function oro_set_bgp_local_as() { bgp_path.prepend(100); return true; } function redistribute_proto() { if ((source = RTS_BGP)) then { return true; } if (net=0.0.0.0/0) then { return false;} if ((source = RTS_DEVICE)) then { return false; } if (source = RTS_STATIC) then { if(net=0.0.0.0/0) then { return false;} if (ifname = "lo") then { return false; } else { return false; } } if ((source = RTS_CFGSET)) then { return false; } if ((source = RTS_IAPVPN)) then { return false; } if ((source = RTS_OAP)) then { return false; } if (source = RTS_OSPF) then { return false; } if (source = RTS_OSPF_IA) then { return false; } if (source = RTS_OSPF_EXT1) then { return false; } if (source = RTS_OSPF_EXT2) then { return false; } if ((source = RTS_OSPF) || (source = RTS_OSPF_IA) || (source = RTS_OSPF_EXT1) || (source = RTS_OSPF_EXT2)) then { return false; } return false; } protocol kernel K_VRF_RED { vrf "red"; kernel table 100; scan time 20; ipv4 { table T_VRF_RED; import all; export all; }; } protocol kernel K_VRF_BLUE { vrf "blue"; kernel table 200; scan time 20; ipv4 { table T_VRF_BLUE; import all; export all; }; } protocol direct C_VRF_RED { vrf "red"; ipv4 { table T_VRF_RED; }; } protocol direct C_VRF_BLUE { vrf "blue"; ipv4 { table T_VRF_BLUE; }; } protocol static S_VRF_RED { vrf "red"; ipv4 { table T_VRF_RED; }; route 10.10.1.0/24 blackhole; } protocol static S_VRF_BLUE { vrf "blue"; ipv4 { table T_VRF_BLUE; }; route 10.10.1.0/24 blackhole; } protocol bgp B_VRF_RED { vrf "red"; vrf "blue"; router id 10.16.44.217; local 50.0.12.2 as 100; neighbor 50.0.12.1 as 100; enable as4 on; hold time 90; keepalive time 30; direct; # regular IPv4 unicast (1/1) ipv4 { table T_VRF_RED; table T_VRF_BLUE; import all; export all; }; } Thanks, Ramanathan

1 0

[PATCH v4] Babel: Replace internal route selection by bird's nest
by Daniel Gröber 26 Feb '23

26 Feb '23

This introduces the ability to filter routes from specific interfaces and neighbours. With the current internal route selection proto babel exports only up to one route and an admin cannot do fine-grained filtering. To fix this we rip out the internal route selection entirely and export evey babel route as a distinct route into the bird's nest instead. In the presence of esoteric route filters this change may be observable by users however we feel the additional filtering power is more important. A release note entry for this change is recommended. --- Changes in v4: - We've seen the light, use FIB_ITERATE as intended, thanks Ondrej. - Reinstate seqno request logic on loss of all feasible routes, thanks Toke. Discussion of behaviour still ongoing, see[1] - Try to prepare for async rt_notify in BIRD 3, thanks Maria. [1]: http://trubka.network.cz/pipermail/bird-users/2023-February/016689.html proto/babel/babel.c | 278 ++++++++++++++++++++------------------------ proto/babel/babel.h | 3 + 2 files changed, 128 insertions(+), 153 deletions(-) diff --git a/proto/babel/babel.c b/proto/babel/babel.c index ff8b6b52..eb347a85 100644 --- a/proto/babel/babel.c +++ b/proto/babel/babel.c @@ -29,10 +29,12 @@ * possible routes for the prefix are tracked as &babel_route entries and the * feasibility distance is maintained through &babel_source structures. * - * The main route selection is done in babel_select_route(). This is called when - * an entry is updated by receiving updates from the network or when modified by - * internal timers. The function selects from feasible and reachable routes the - * one with the lowest metric to be announced to the core. + * The main route selection is done by bird's nest (heh). For each prefix we + * export all feasible routes to the core with a distinct source (rte_src) per + * neihbour so bird handles them as distinct routes. Nest will then notify us of + * one best route for each prefix, either our own (internal) or from another + * protocol, by calling babel_rt_notify. For internal best routes we remember + * which babel_route it selected in babel_entry.selected. */ #include <stdlib.h> @@ -50,8 +52,8 @@ static inline int ge_mod64k(uint a, uint b) { return (u16)(a - b) < 0x8000; } 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_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); static void babel_update_cost(struct babel_neighbor *n); @@ -168,9 +170,7 @@ static inline void babel_retract_route(struct babel_proto *p, struct babel_route *r) { r->metric = r->advert_metric = BABEL_INFINITY; - - if (r == r->e->selected) - babel_select_route(p, r->e, r); + babel_announce_rte(p, r->e, r); } static void @@ -182,9 +182,6 @@ babel_flush_route(struct babel_proto *p UNUSED, struct babel_route *r) rem_node(NODE r); rem_node(&r->neigh_route); - if (r->e->selected == r) - r->e->selected = NULL; - sl_free(r); } @@ -200,6 +197,7 @@ babel_expire_route(struct babel_proto *p, struct babel_route *r) { r->metric = r->advert_metric = BABEL_INFINITY; r->expires = current_time() + cf->hold_time; + babel_announce_rte(p, r->e, r); } else { @@ -229,8 +227,6 @@ babel_expire_routes_(struct babel_proto *p, struct fib *rtable) loop: FIB_ITERATE_START(rtable, &fit, struct babel_entry, e) { - int changed = 0; - WALK_LIST_DELSAFE(r, rx, e->routes) { if (r->refresh_time && r->refresh_time <= now_) @@ -238,23 +234,12 @@ loop: if (r->expires && r->expires <= now_) { - changed = changed || (r == e->selected); + FIB_ITERATE_PUT(&fit); babel_expire_route(p, r); + goto loop; } } - if (changed) - { - /* - * We have to restart the iteration because there may be a cascade of - * synchronous events babel_select_route() -> nest table change -> - * babel_rt_notify() -> rtable change, invalidating hidden variables. - */ - FIB_ITERATE_PUT(&fit); - babel_select_route(p, e, NULL); - goto loop; - } - /* Clean up stale entries */ if ((e->valid == BABEL_ENTRY_STALE) && ((e->updated + cf->hold_time) <= now_)) e->valid = BABEL_ENTRY_DUMMY; @@ -263,7 +248,7 @@ loop: if (e->unreachable && (!e->valid || (e->router_id == p->router_id))) { FIB_ITERATE_PUT(&fit); - babel_announce_retraction(p, e); + babel_rte_update_unreachable(p, e, 0); goto loop; } @@ -447,6 +432,7 @@ babel_get_neighbor(struct babel_iface *ifa, ip_addr addr) nbr = mb_allocz(ifa->pool, sizeof(struct babel_neighbor)); nbr->ifa = ifa; + nbr->src = rt_get_source(&p->p, idm_alloc(&p->src_ids)); nbr->addr = addr; nbr->rxcost = BABEL_INFINITY; nbr->txcost = BABEL_INFINITY; @@ -474,6 +460,8 @@ babel_flush_neighbor(struct babel_proto *p, struct babel_neighbor *nbr) } nbr->ifa = NULL; + + idm_free(&p->src_ids, nbr->src->private_id); rem_node(NODE nbr); mb_free(nbr); } @@ -634,11 +622,47 @@ done: WALK_LIST2(r, n, nbr->routes, neigh_route) { r->metric = babel_compute_metric(nbr, r->advert_metric); - babel_select_route(p, r->e, r); + babel_announce_rte(p, r->e, r); } } } +/** + * This function handles announcing the special unreachable route we insert for + * a prefix whenever we have no more feasible routes available as per RFC8966 + * section 3.5.4 as well as retracting it when such routes are available + * again. + * + * We also remember if we inserted an unreachable route in e->unreachable in + * order to clean it up later in babel_expire_routes_. + */ +static void +babel_rte_update_unreachable(struct babel_proto *p, struct babel_entry *e, u8 announce) +{ + struct channel *c = (e->n.addr->type == NET_IP4) ? p->ip4_channel : p->ip6_channel; + rte *rte = NULL; + + if (announce) { + rta a0 = { + .source = RTS_BABEL, + .scope = SCOPE_UNIVERSE, + .dest = RTD_UNREACHABLE, + .pref = 1, + }; + + rta *a = rta_lookup(&a0); + rte = rte_get_temp(a, p->p.main_source); + } + + e->unreachable = announce; + + /* Unlike the regular per-neighbour routes we only want one unreachable route + * for each prefix. This is mainly due to the lifetime of the unreachable rte + * exceeding that of the neighbour's rte_src ID as the babal neighbour may be + * flushed before the unreachable route is retracted. */ + rte_update2(c, e->n.addr, rte, p->p.main_source); +} + /** * babel_announce_rte - announce selected route to the core * @p: Babel protocol instance @@ -649,12 +673,11 @@ done: * the entry is valid and ours, the unreachable route is announced instead. */ static void -babel_announce_rte(struct babel_proto *p, struct babel_entry *e) +babel_announce_rte(struct babel_proto *p, struct babel_entry *e, struct babel_route *r) { - struct babel_route *r = e->selected; struct channel *c = (e->n.addr->type == NET_IP4) ? p->ip4_channel : p->ip6_channel; - if (r) + if (r->metric != BABEL_INFINITY && r->feasible) { rta a0 = { .source = RTS_BABEL, @@ -698,122 +721,23 @@ babel_announce_rte(struct babel_proto *p, struct babel_entry *e) a0.nh.flags = RNF_ONLINK; rta *a = rta_lookup(&a0); - rte *rte = rte_get_temp(a, p->p.main_source); - - e->unreachable = 0; - rte_update2(c, e->n.addr, rte, p->p.main_source); - } - else if (e->valid && (e->router_id != p->router_id)) - { - /* Unreachable */ - rta a0 = { - .source = RTS_BABEL, - .scope = SCOPE_UNIVERSE, - .dest = RTD_UNREACHABLE, - .pref = 1, - }; - - rta *a = rta_lookup(&a0); - rte *rte = rte_get_temp(a, p->p.main_source); - - e->unreachable = 1; - rte_update2(c, e->n.addr, rte, p->p.main_source); - } - else - { - /* Retraction */ - e->unreachable = 0; - rte_update2(c, e->n.addr, NULL, p->p.main_source); - } -} - -/* Special case of babel_announce_rte() just for retraction */ -static inline void -babel_announce_retraction(struct babel_proto *p, struct babel_entry *e) -{ - struct channel *c = (e->n.addr->type == NET_IP4) ? p->ip4_channel : p->ip6_channel; - e->unreachable = 0; - rte_update2(c, e->n.addr, NULL, p->p.main_source); -} - - -/** - * babel_select_route - select best route for given route entry - * @p: Babel protocol instance - * @e: Babel entry to select the best route for - * @mod: Babel route that was modified or NULL if unspecified - * - * Select the best reachable and feasible route for a given prefix among the - * routes received from peers, and propagate it to the nest. This just selects - * the reachable and feasible route with the lowest metric, but keeps selected - * the old one in case of tie. - * - * If no feasible route is available for a prefix that previously had a route - * selected, a seqno request is sent to try to get a valid route. If the entry - * is valid and not owned by us, the unreachable route is announced to the nest - * (to blackhole packets going to it, as per section 2.8). It is later removed - * by babel_expire_routes(). Otherwise, the route is just removed from the nest. - * - * Argument @mod is used to optimize best route calculation. When specified, the - * function can assume that only the @mod route was modified to avoid full best - * route selection and announcement when non-best route was modified in minor - * way. The caller is advised to not call babel_select_route() when no change is - * done (e.g. periodic route updates) to avoid unnecessary announcements of the - * same best route. The caller is not required to call the function in case of a - * retraction of a non-best route. - * - * Note that the function does not active triggered updates. That is done by - * babel_rt_notify() when the change is propagated back to Babel. - */ -static void -babel_select_route(struct babel_proto *p, struct babel_entry *e, struct babel_route *mod) -{ - struct babel_route *r, *best = e->selected; + rte *rte = rte_get_temp(a, r->neigh->src); - /* 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) - best = mod; - else - return; + rte_update2(c, e->n.addr, rte, r->neigh->src); + if (e->unreachable) + babel_rte_update_unreachable(p, e, 0); } - else - { - /* Selected route may be modified and no longer admissible */ - if (!best || (best->metric == BABEL_INFINITY) || !best->feasible) - best = NULL; + else { + if (e->selected == r) + /* We NULL e->selected here rather than wait for babel_rt_notify in order + * to stay in a sync context. This is to be prepared for async rt_notify + * in BIRD 3. This is critical as RFC8966 demands unfeasible or infinite + * metric routes never being selected (see section 3.6 Route + * Selection). */ + e->selected = NULL; - /* Find the best feasible route from all routes */ - WALK_LIST(r, e->routes) - if ((r->metric < (best ? best->metric : BABEL_INFINITY)) && r->feasible) - best = r; + rte_update2(c, e->n.addr, NULL, r->neigh->src); } - - 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); - } - else if (e->selected) - { - /* - * We have lost all feasible routes. We have to broadcast seqno request - * (Section 3.8.2.1) and keep unreachable route for a while (section 2.8). - * The later is done automatically by babel_announce_rte(). - */ - - TRACE(D_EVENTS, "Lost feasible route for prefix %N", e->n.addr); - if (e->valid && (e->selected->router_id == e->router_id)) - babel_add_seqno_request(p, e, e->selected->router_id, e->selected->seqno + 1, 0, NULL); - } - else - return; - - e->selected = best; - babel_announce_rte(p, e); } /* @@ -1338,7 +1262,7 @@ babel_handle_update(union babel_msg *m, struct babel_iface *ifa) e->updated = current_time(); } - babel_select_route(p, e, r); + babel_announce_rte(p, e, r); } void @@ -2006,7 +1930,7 @@ static void babel_dump_entry(struct babel_entry *e) { struct babel_source *s; - struct babel_route *r; + struct babel_route *r, *best = e->selected; debug("Babel: Entry %N:\n", e->n.addr); @@ -2016,7 +1940,7 @@ babel_dump_entry(struct babel_entry *e) WALK_LIST(r,e->routes) { debug(" "); - if (r == e->selected) debug("*"); + if (r == best) debug("*"); babel_dump_route(r); } } @@ -2186,7 +2110,7 @@ babel_show_entries_(struct babel_proto *p, struct fib *rtable) FIB_WALK(rtable, struct babel_entry, e) { - struct babel_route *r = NULL; + struct babel_route *r = NULL, *best = e->selected; uint rts = 0, srcs = 0; node *n; @@ -2199,7 +2123,7 @@ babel_show_entries_(struct babel_proto *p, struct fib *rtable) if (e->valid) cli_msg(-1025, "%-*N %-23lR %6u %5u %7u %7u", width, e->n.addr, e->router_id, e->metric, e->seqno, rts, srcs); - else if (r = e->selected) + else if (r = best) cli_msg(-1025, "%-*N %-23lR %6u %5u %7u %7u", width, e->n.addr, r->router_id, r->metric, r->seqno, rts, srcs); else @@ -2236,10 +2160,10 @@ babel_show_routes_(struct babel_proto *p, struct fib *rtable) FIB_WALK(rtable, struct babel_entry, e) { - struct babel_route *r; + struct babel_route *r, *best = e->selected; WALK_LIST(r, e->routes) { - char c = (r == e->selected) ? '*' : (r->feasible ? '+' : ' '); + char c = (r == best) ? '*' : (r->feasible ? '+' : ' '); btime time = r->expires ? r->expires - current_time() : 0; cli_msg(-1025, "%-*N %-25I %-10s %5u %c %5u %7t", width, e->n.addr, r->next_hop, r->neigh->ifa->ifname, @@ -2316,19 +2240,23 @@ babel_preexport(struct channel *C, struct rte *new) */ static void babel_rt_notify(struct proto *P, struct channel *c UNUSED, struct network *net, - struct rte *new, struct rte *old UNUSED) + struct rte *new, struct rte *old) { struct babel_proto *p = (void *) P; struct babel_entry *e; + struct babel_iface *ifa; + struct babel_neighbor *n; if (new) { /* Update */ + uint internal = new->src->proto == P; uint rt_seqno; uint rt_metric = ea_get_int(new->attrs->eattrs, EA_BABEL_METRIC, 0); u64 rt_router_id = 0; + struct babel_route *best; - if (new->src->proto == P) + if (internal) { rt_seqno = ea_find(new->attrs->eattrs, EA_BABEL_SEQNO)->u.data; eattr *e = ea_find(new->attrs->eattrs, EA_BABEL_ROUTER_ID); @@ -2350,6 +2278,25 @@ babel_rt_notify(struct proto *P, struct channel *c UNUSED, struct network *net, e = babel_get_entry(p, net->n.addr); + best = e->selected; + if (internal) { + ifa = babel_find_iface(p, new->attrs->nh.iface); + n = ifa ? babel_find_neighbor(ifa, new->attrs->from) : NULL; + best = n ? babel_get_route(p, e, n) : NULL; + ASSERT(best); /* Note: We think this can't happen but the lifetimes of the + * involved objects are complicated so we're not yet + * completely convinced. */ + } else { + best = NULL; + } + + if (best && 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); + + e->selected = best; + /* Activate triggered updates */ if ((e->valid != BABEL_ENTRY_VALID) || (e->router_id != rt_router_id)) @@ -2365,14 +2312,38 @@ babel_rt_notify(struct proto *P, struct channel *c UNUSED, struct network *net, } else { + uint internal = old->src->proto == P; + /* Withdraw */ e = babel_find_entry(p, net->n.addr); if (!e || e->valid != BABEL_ENTRY_VALID) return; + if (e->selected || !internal) { + TRACE(D_EVENTS, "Lost all feasible routes for prefix %N", e->n.addr); + /* We had a feasible route, but now it's gone. We must send a seqno + * request (Section 3.8.2.1). As allowed by RFC8966 we choose to always do + * so even if we don't have any more unfeasible routes and we use the + * simple unconditional multicast strategy. + * + * Note we interpret "feasible route" to include external routes from + * other protocols. You can think of these as being routes announced by + * neighbours internal to the bird implementation. + */ + if (e->valid && (e->selected->router_id == e->router_id)) + babel_add_seqno_request( + p, e, e->selected->router_id, e->selected->seqno + 1, 0, NULL); + } + + e->valid = BABEL_ENTRY_STALE; e->metric = BABEL_INFINITY; + e->selected = NULL; + + /* Install an unreachable route for prefix hold time as per RFC8966 section + * 3.5.4. */ + babel_rte_update_unreachable(p, e, 1); babel_trigger_update(p); e->updated = current_time(); @@ -2464,6 +2435,7 @@ babel_start(struct proto *P) p->source_slab = sl_new(P->pool, sizeof(struct babel_source)); p->msg_slab = sl_new(P->pool, sizeof(struct babel_msg_node)); p->seqno_slab = sl_new(P->pool, sizeof(struct babel_seqno_request)); + idm_init(&p->src_ids, P->pool, 8); p->log_pkt_tbf = (struct tbf){ .rate = 1, .burst = 5 }; diff --git a/proto/babel/babel.h b/proto/babel/babel.h index da8386b3..16d9c7d0 100644 --- a/proto/babel/babel.h +++ b/proto/babel/babel.h @@ -25,6 +25,7 @@ #include "lib/socket.h" #include "lib/string.h" #include "lib/timer.h" +#include "lib/idm.h" #define EA_BABEL_METRIC EA_CODE(PROTOCOL_BABEL, 0) #define EA_BABEL_ROUTER_ID EA_CODE(PROTOCOL_BABEL, 1) @@ -174,6 +175,7 @@ struct babel_proto { slab *source_slab; slab *msg_slab; slab *seqno_slab; + struct idm src_ids; struct tbf log_pkt_tbf; /* TBF for packet messages */ }; @@ -216,6 +218,7 @@ struct babel_iface { struct babel_neighbor { node n; struct babel_iface *ifa; + struct rte_src *src; ip_addr addr; u16 rxcost; /* Sent in last IHU */ -- 2.30.2

1 1

[PATCH 1/3] lib/timer: Add current_time_now() function for immediate timestamp
by Toke Høiland-Jørgensen 26 Feb '23

26 Feb '23

Add a current_time_now() function which gets an immediate monotonic timestamp instead of using the cached value from the event loop. This is useful for callers that need precise times, such as the Babel RTT measurement code. Signed-off-by: Toke Høiland-Jørgensen <toke(a)toke.dk> --- lib/timer.c | 13 +++++++++++++ lib/timer.h | 1 + 2 files changed, 14 insertions(+) diff --git a/lib/timer.c b/lib/timer.c index c47e0bbc8b78..a96b051aaf9c 100644 --- a/lib/timer.c +++ b/lib/timer.c @@ -76,6 +76,19 @@ current_time(void) return timeloop_current()->last_time; } +btime +current_time_now(void) +{ + struct timespec ts; + int rv; + + rv = clock_gettime(CLOCK_MONOTONIC, &ts); + if (rv < 0) + die("clock_gettime: %m"); + + return ts.tv_sec S + ts.tv_nsec NS; +} + btime current_real_time(void) { diff --git a/lib/timer.h b/lib/timer.h index c5ea430cdb81..bfd9904e04b6 100644 --- a/lib/timer.h +++ b/lib/timer.h @@ -44,6 +44,7 @@ static inline timer *timers_first(struct timeloop *loop) extern struct timeloop main_timeloop; btime current_time(void); +btime current_time_now(void); btime current_real_time(void); //#define now (current_time() TO_S) -- 2.39.1

1 0

Bird MPLS route issue on Centos 7
by Charles Butera 22 Feb '23

22 Feb '23

Hello, I am unable to get bird static routes with MPLS labels installed in the kernel routing table on Centos 7 (with upgraded kernel 5.12). Steps to set this up: 1. Load necessary MPLS kernel modules & sysctl setting modprobe mpls_router modprobe mpls_iptunnel sysctl -w net.mpls.platform_labels=1048575 2. Install bird2 3. Set static route in bird configuration then birdc configure (Everything else is default config) [root@centos7 ~]$ cat /etc/bird.conf | grep "protocol static" -A 4 protocol static { vrf default; ipv4; route 1.1.1.1/32 via "ens192" mpls 299792; } [cbutera@telegraf-edge001 ~]$ ip route ls 1.1.1.1 1.1.1.1 dev ens192 proto bird scope link metric 32 You can see in the output above that there is no encap mpls instruction on the route Following the same procedure on Debian 11 or Centos 8 work successfully. See output below [root@centos8 ~] cat /etc/bird.conf | grep "protocol static" -A 4 protocol static { ipv4; vrf default; route 1.1.1.1/32 via "ens192" mpls 299792; } [root@localhost ~] ip route ls 1.1.1.1 1.1.1.1 encap mpls 299792 dev ens192 proto bird scope link metric 32 Note: On Centos 7 adding the route with ip route add command works - Also confirmed that the server is in fact sending packets with MPLS labels [root@centos7 ~] ip route add 8.8.8.8/32 encap mpls 299793 dev ens192 [root@centos7 ~] ip route ls 8.8.8.8 8.8.8.8 encap mpls 299793 dev ens192 scope link MPLS Kernel modules needed for this were introduced in Kernel version 4.3. I have tested on the two versions listed below: - 5.12.9-1.el7.elrepo.x86_646. - 2.0-1.el7.elrepo.x86_64 Thanks you, Charlie

2 1

https://github.com/CZ-NIC/bird repo sync
by Alexander Chernikov 21 Feb '23

21 Feb '23

Dear bird team, The GitHub cz-nic/bird repository mirror looks stale - the last commit there is from October 5, 2020? Is this intentional? If not, would it be possible to make it track the current bird git repo? One of the big benefits of GitHub (for me) is an easy standard mechanism of tracking the changes - everyone with GitHub account can subscribe for the commits notification with a single click. /Alexander

2 2

Binding to some interfaces only for multihop bgp
by Sebastian Hahn 20 Feb '23

20 Feb '23

Hi, I would like bird to bind to some interfaces only, but use some multihop neighbours. Is there any easy way to achieve such a configuration? The strict bind option is incompatible with multihop, and I haven't seen anything where i can give a positive or negative list of interfaces to bind to / not to bind to. Thanks Sebastian

3 5

BIRD BGP Local pref control
by Shun Murayama 17 Feb '23

17 Feb '23

Hello bird users, I'm testing BIRD in my test environment. I have two problems and would you please share your knowledge. 1. Don't you know the regex to control as_path in the BGP BIRD? I'd like to set if as-path much "^neighborAS_Tier1AS", then set the higher local preference. BIRD's bgp_path attribute appears to support bgp_path.first and bgp_path.last. 2. Someone use the previous computer to run the BIRD BGP? I'll try to performance receive BGP Full-Route, advertise few route and sent 10G+ traffic. If you run BIRD BGP using the previous Xeon CPU(like E5 series) in the Linux servers and Linux kernel, let me know how much traffic can control. I hope you have any knowledge. Best reguard, Shun ----------------------------- Shun Murayama Internet Initiative Japan Inc. Mail:shun-m@iij.ad.jp

1 0