- Bird-users - Mailing Lists

LDP and Bird
by Pim van Pelt 16 Jan '23

16 Jan '23

Hoi folks, I work on VPP (a fast userspace based dataplane implementation https://fd.io/) and helped contribute the ability for this dataplane to consume Netlink messages (github.com/pimvanpelt/lcpng) One thing that I've been asked about quite a bit is the ability to program the VPP dataplane with MPLS forwarding. I use Bird2 in my own deployment ( https://ipng.ch/s/articles/2021/09/21/vpp-7.html) and was wondering what the current thinking is for Bird to support signalling with LDP. Last I saw was: - https://bird.network.cz/pipermail/bird-users/2017-September/011528.html - https://birdofluck.livejournal.com/8996.html - https://git.nic.cz/redmine/projects/bird/repository/show?rev=mpls - https://bird.network.cz/pipermail/bird-users/2018-September/012760.html - https://bird.network.cz/ Maria, do you have pointers on the current state of the union for an LDP implementation for Bird? I'd like to add MPLS support to Linux Control Plane (https://ipng.ch/media/virtualnog/index.html) groet, Pim -- Pim van Pelt <pim(a)ipng.nl> PBVP1-RIPE - http://www.ipng.nl/

2 3

Potential OSPF authentication issues with Mikrotik routers
by Theera Kittichareonpot 14 Jan '23

14 Jan '23

Hello, I am very new to Bird so I could be doing something wrong. But it seems Bird 2.0.11 could have compatibility issues with Mikrotik routers when OSPF authentication is used. When simple authentication is used, the neighbor state stays at Init and doesn't change at all. When cryptographic password is used, the Mikrotik router gave errors about wrong SA/SP id: "ospf-instance-1 { version: 2 router-id: 192.168.120.1 } ospf-area-1 { 0.0.0.0 } interface { instance-id: 5 broadcast 192.168.10.1%br-lan } authentication failed from 192.168.10.197 wrong SA ID". I've tried md5 sha256 and sha512, but all gave the same error. Kindly let me know if I did something wrong or what additional info is needed. Thank you. The following is my bird.conf: log syslog all; #debug protocols all; #router id 192.168.10.197; ipv4 table master4; protocol device { } protocol direct direct4 { ipv4; # Connect to default IPv4 table } protocol kernel kernel4 { ipv4 { import all; export all; }; } protocol static static4 { ipv4; } protocol ospf v2 ospf4 { instance id 5; # set to the same as other routers' ipv4 { import all; export all; }; area 0 { interface "eth0" { type broadcast; hello 10; # same as other routers' retransmit 5; transmit delay 1; dead 40; #simple authentication doesn't work with Mikrotik either. The state stays at Init and doesn't change at all. #authentication simple; #password "12345678"; # cryptographic password doesn't seem to work with mikrotik too; got errors about wrong SA/SP id #authentication cryptographic; #password "12345678" { algorithm hmac sha512; }; }; }; } Theera K.

3 5

Babel on a wireless mesh
by Bernd Naumann 13 Jan '23

13 Jan '23

Hey *, Because Babel popped up on the list, I want to use the opportunity to drop a few questions I had over the last days... On my small home-network I currently use OSPFv3 for IPv4 and IPv6 to announce routes from Laptops and PCs, and the Router. (There are some "dumb APs", too in the network but routing happens only on "the router" and like I mentioned, PCs and Laptops. Some wired, some wireless only, some both.) Given the fact that both protocols, OSPFv3 and Babel, are using multicast; would I "gain anything" switching to Babel? Right now I'm only using OSPFv3 because I'm familiar with... And what really puzzles me, and I don't find "useful" answers: If I run a multicast based routing protocol on jittery wireless links, do I need to "tune" multicast options for the wireless radio? And if so, what options; to what value; based on what? (Regarding the multicast radio options of the access points, I'm running OpenWrt.) Thanks for pointers and hints. Bernd PS: Yes, I'm not even sure if I need to "tune" anything or not. Or what to expect. But I would like to "get the picture".

3 3

Question about babel over bird
by Oriol Rico 12 Jan '23

12 Jan '23

Hello: We have a series of wireless antennas deployed in mesh with the babel protocol using bird. Two of those antennas advertise the route 10.0.0.0/8. The rest of the antennas choose one of the two outputs depending on the babel protocol. How can I force it to go out through one or the other exit? Thanks Oriol

4 9

[PATCH] Log message before aborting
by Mike Crute 12 Jan '23

12 Jan '23

Signed-off-by: Mike Crute <mike(a)crute.us> --- This is a really tiny patch but the behavior of aborting was very confusing to one of the Alpine Linux users and caused them to spend a lot of time creating and installing debug builds and tracing the BIRD process only to find a configuration error. Hopefully this patch will help to prevent such issues for future users while still providing proper debug info for developers. Original Alpine Issue: https://gitlab.alpinelinux.org/alpine/aports/-/issues/14408 Thanks! sysdep/unix/io.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/sysdep/unix/io.c b/sysdep/unix/io.c index 810e782d..57bed092 100644 --- a/sysdep/unix/io.c +++ b/sysdep/unix/io.c @@ -2129,7 +2129,7 @@ watchdog_sigalrm(int sig UNUSED) io_update_time(); /* We want core dump */ - abort(); + bug("Watchdog timer timed out."); } static inline void -- 2.39.0

3 5

Segfault on eval of case expression
by Jiten Kumar Pathy 07 Jan '23

07 Jan '23

Hello, The following filter causes bird2 to segfault: ```` filter test { case 2 { 1: accept; else: reject; } } ```` I have locally added `NEVER_CONSTANT` to `FI_SWITCH` instruction as a temporary workaround.

2 1

Fwd: SO_BINDTODEVICE: No such device for BGP with VRF configuration
by Ramanathan Selvamani 03 Jan '23

03 Jan '23

Hi all, I am using linux kernel 4.14.188. While i'm trying to configure VRF for BGP, i observed the below error and BGP session is not established. Kindly let me know if i am missing anything. At R1 ==== B_VRF_RED: Socket error: SO_BINDTODEVICE: No such device B_VRF_RED: Connection closed At R2 ==== B_VRF_RED: Socket error: SO_BINDTODEVICE: No such device R1 Configuration ============= function oro_set_bgp_local_as() { bgp_path.prepend(100); return true; } function bgp_aggr_nets() { } 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; } filter export_BGP_50_0_0_2 { if ((scope = SCOPE_HOST) && (dest != RTD_BLACKHOLE)) then { reject; } if (source = RTS_APP) then { reject; } if (source = RTS_REDIRECT) then { reject; } if (source = RTS_INHERIT) then { reject; } if ((source = RTS_OAP) && defined(oap_metric)) then { bgp_med = oap_metric; } if !redistribute_proto() then {reject;} if( rmap_r1(bgp_proto)) then {accept;} else{reject;} accept; } filter import_BGP_50_0_0_2 { if((source = RTS_BGP) && rmap_r1(bgp_proto)) then { accept; } else { reject; } } protocol bgp BGP_50_0_0_2 { router id 1.1.1.1; local as 100; neighbor 50.0.0.2 as 100; graceful restart off; graceful restart time 90; enable as4 on; hold time 90; keepalive time 30; prefer older on; ipv4 { preference 56; import table on; export table on; import filter import_BGP_50_0_0_2; export filter export_BGP_50_0_0_2; }; } R2 Configuration ============= ipv4 table T_VRF_RED; 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 direct C_VRF_RED { vrf "red"; ipv4 { table T_VRF_RED; }; interface "red"; } protocol static S_VRF_RED { vrf "red"; ipv4 { table T_VRF_RED; }; route 10.10.1.0/24 blackhole; } protocol bgp B_VRF_RED { vrf "red"; router id 2.2.2.2; local 50.0.0.2 as 100; neighbor 50.0.0.1 as 100; enable as4 on; hold time 90; keepalive time 30; multihop; strict bind yes; # regular IPv4 unicast (1/1) ipv4 { table T_VRF_RED; import all; export all; }; } Thanks, Ramanathan

2 1

[PATCH] Don't treat 0/8 and 240/4 specially in IPv4 classification
by Seth David Schoen 01 Jan '23

01 Jan '23

With the exception of 0.0.0.0 and 255.255.255.255, which have additional special meanings, treat 0/8 and 240/4 as normal unicast addresses by default. This is because some people are experimenting with using these addresses as regular unicast (either for private addresses or for potential future public addresses). On the public Internet, they would still currently be regarded as bogons and one could make (maybe by default) a bogon-filtering rule in bird.conf that would not permit these addresses to be routed, e.g. with a pair of static routes route 0.0.0.0/8 prohibit; route 240.0.0.0/4 prohibit; or simply route 0.0.0.0/8 blackhole; route 240.0.0.0/4 blackhole; Dave Taht, who wrote a prior version of this patch, suggested that in any case it is better to have bogons defined in a configuration file than hard-coded in software. --- lib/ip.c | 7 +++++-- lib/ip.h | 2 +- 2 files changed, 6 insertions(+), 3 deletions(-) diff --git a/lib/ip.c b/lib/ip.c index 4c5fa47f..e13bbce0 100644 --- a/lib/ip.c +++ b/lib/ip.c @@ -87,8 +87,10 @@ ip4_classify(ip4_addr ad) if (b < 0xe0) { - if (b == 0x00) /* 0.0.0.0/8 This network */ + if (a == 0x00000000) /* 0.0.0.0/32 Unset address */ return IADDR_INVALID; + /* 0.0.0.0/8 is otherwise reserved, but + * some people are using it or trying to */ if (b == 0x7f) /* 127.0.0.0/8 Loopback address */ return IADDR_HOST | SCOPE_HOST; @@ -107,7 +109,8 @@ ip4_classify(ip4_addr ad) if (a == 0xffffffff) /* 255.255.255.255 Broadcast address */ return IADDR_BROADCAST | SCOPE_LINK; - return IADDR_HOST | SCOPE_SITE; /* 240.0.0.0/4 Reserved / private */ + return IADDR_HOST | SCOPE_UNIVERSE; /* 240.0.0.0/4 Reserved / private, but + * some people are using it or trying to */ } int diff --git a/lib/ip.h b/lib/ip.h index 9eef2e16..875b9f5e 100644 --- a/lib/ip.h +++ b/lib/ip.h @@ -245,7 +245,7 @@ static inline int ip6_is_v4mapped(ip6_addr a) #define ipa_is_link_local(x) ip6_is_link_local(x) static inline int ip4_is_unicast(ip4_addr a) -{ return _I(a) < 0xe0000000; } +{ return _I(a) < 0xe0000000 || (_I(a) >= 0xf0000000 && _I(a) != 0xffffffff); } /* XXXX remove */ static inline int ipa_classify_net(ip_addr a) -- 2.25.1

8 12

[PATCH v5] babel: Rework seqno request handling
by Toke Høiland-Jørgensen 24 Dec '22

24 Dec '22

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, and for triggering an update when satisfied. 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. Signed-off-by: Toke Høiland-Jørgensen <toke(a)toke.dk> --- v5: - Set an explicit duplicate suppression time for forwarded requests instead of repurposing the multi-expiry logic for forwarded requests v4: - Keep the last parameter of babel_add_seqno_request() as the request target and resolve it in the caller - Drop check for 0-valued hop count - Add a comment explaining why we expire forwarded requests but don't retransmit them v3: - Rework the dupliate suppression logic to avoid suppressing resends v2: - Get rid of the neighbour pointer in the request state tracking - Change the resend behaviour to only resend requests we originated ourselves. proto/babel/babel.c | 152 ++++++++++++++++++++++++++++---------------- proto/babel/babel.h | 6 +- 2 files changed, 101 insertions(+), 57 deletions(-) diff --git a/proto/babel/babel.c b/proto/babel/babel.c index ecfd2763d737..e8476ff5f72f 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,9 +288,6 @@ 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; } - /* * Add seqno request to the table of pending requests (RFC 6216 3.2.6) and send * it to network. Do nothing if it is already in the table. @@ -299,50 +296,82 @@ 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 *tgt) { struct babel_seqno_request *sr; + btime now_ = current_time(); 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)) + /* + * To suppress duplicates, check if we already have a newer (higher seqno) + * outstanding request. If we do, suppress this request if the outstanding + * request is one we originated ourselves. If the outstanding request is + * forwarded, suppress only if this request is also one we're forwarding + * *and* we're within the duplicate suppression time of that request (see + * below). + */ + if (ge_mod64k(sr->seqno, seqno) && + (!sr->forwarded || (tgt && now_ < sr->dup_suppress_time))) return; - /* Found older */ rem_node(NODE sr); - if (sr->nbr) - rem_node(&sr->nbr_node); + /* Allow upgrading from forwarded to non-forwarded */ + if (!tgt) + sr->forwarded = 0; goto found; } /* No entries found */ sr = sl_allocz(p->seqno_slab); + sr->forwarded = !!tgt; 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); + if (sr->forwarded) + { + /* + * We want to keep the entry around for a reasonable period of time so it + * can be used to trigger an update (through babel_satisfy_seqno_request()). + * However, duplicate suppression should only trigger for a short period of + * time so it suppresses duplicates from multiple sources, but not + * retransmissions from the same source. Hence we keep two timers. + */ + sr->expires = now_ + BABEL_SEQNO_FORWARD_EXPIRY; + sr->dup_suppress_time = now_ + BABEL_SEQNO_DUP_SUPPRESS_TIME; + } + else + { + sr->expires = now_ + BABEL_SEQNO_REQUEST_EXPIRY; + } add_tail(&e->requests, NODE sr); + babel_send_seqno_request(p, e, sr, tgt); +} - babel_send_seqno_request(p, e, sr); +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, &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,21 +401,14 @@ 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_) { - if (sr->count < BABEL_SEQNO_REQUEST_RETRY) + if (!sr->forwarded && sr->count < BABEL_SEQNO_REQUEST_RETRY) { sr->count++; sr->expires += (BABEL_SEQNO_REQUEST_EXPIRY << sr->count); - babel_send_seqno_request(p, e, sr); + babel_send_seqno_request(p, e, sr, NULL); } else { @@ -431,7 +453,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 +473,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 +920,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 +1303,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)) @@ -1353,6 +1374,32 @@ babel_handle_route_request(union babel_msg *m, struct babel_iface *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; +} + void babel_handle_seqno_request(union babel_msg *m, struct babel_iface *ifa) { @@ -1389,26 +1436,21 @@ 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; + struct babel_neighbor *nbr, *tgt; - /* Find best not necessary feasible route */ - if (!best2 || r->metric < best2->metric) - best2 = r; - } + nbr = babel_find_neighbor(ifa, msg->sender); + if (!nbr) + return; - /* If no route is found, do nothing */ - r = best1 ?: best2; - if (!r) + tgt = babel_find_seqno_request_tgt(e, nbr); + 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, msg->router_id, msg->seqno); 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, tgt); } } diff --git a/proto/babel/babel.h b/proto/babel/babel.h index 8b6da3c8ce91..b6e56ecb30a6 100644 --- a/proto/babel/babel.h +++ b/proto/babel/babel.h @@ -48,6 +48,8 @@ #define BABEL_ROUTE_REFRESH_FACTOR(X) ((btime)(X)*5/2) /* 2.5 */ #define BABEL_SEQNO_REQUEST_RETRY 4 #define BABEL_SEQNO_REQUEST_EXPIRY (2 S_) +#define BABEL_SEQNO_FORWARD_EXPIRY (10 S_) +#define BABEL_SEQNO_DUP_SUPPRESS_TIME (1 S_) #define BABEL_GARBAGE_INTERVAL (300 S_) #define BABEL_RXCOST_WIRED 96 #define BABEL_RXCOST_WIRELESS 256 @@ -240,7 +242,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 +277,8 @@ struct babel_seqno_request { u8 hop_count; u8 count; btime expires; - struct babel_neighbor *nbr; + btime dup_suppress_time; + u8 forwarded; }; struct babel_entry { -- 2.39.0

2 2

[PATCH v3] babel: Rework seqno request handling
by Toke Høiland-Jørgensen 20 Dec '22

20 Dec '22

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, and for triggering an update when satisfied. 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(a)toke.dk> --- v3: - Rework the dupliate suppression logic to avoid suppressing resends v2: - Get rid of the neighbour pointer in the request state tracking - Change the resend behaviour to only resend requests we originated ourselves. proto/babel/babel.c | 155 +++++++++++++++++++++++++++++--------------- proto/babel/babel.h | 3 +- 2 files changed, 102 insertions(+), 56 deletions(-) diff --git a/proto/babel/babel.c b/proto/babel/babel.c index ecfd2763d737..325b30aa2f58 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,50 +322,85 @@ 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; + } + } + 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)) + /* + * To suppress duplicates, check if we already have a newer (higher seqno) + * outstanding request. If we do, suppress this request if the outstanding + * request is one we originated ourselves. If the outstanding request is + * forwarded, supress only if this request is also one we're forwarding + * *and* we're within the first expiry period of that request. The latter + * is to ensure we don't suppress retransmissions of the request from the + * same source. + */ + if (ge_mod64k(sr->seqno, seqno) && + (!sr->forwarded || (fwd_from && !sr->count))) return; - /* Found older */ rem_node(NODE sr); - if (sr->nbr) - rem_node(&sr->nbr_node); + /* Allow upgrading from forwarded to non-forwarded */ + if (!fwd_from) + sr->forwarded = 0; goto found; } /* No entries found */ sr = sl_allocz(p->seqno_slab); + sr->forwarded = !!fwd_from; 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); + /* + * Set the initial expiry time of forwarded requests to half the usual expiry + * time to be reasonably sure we expire it before it is resent by the source. + */ + sr->expires = current_time() + (sr->forwarded ? + (BABEL_SEQNO_REQUEST_EXPIRY/2) : + BABEL_SEQNO_REQUEST_EXPIRY); 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 +430,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 +437,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 +485,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 +505,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 +952,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 +1335,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 +1414,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 +1449,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

2 5