Re: [RESEND PATCH v3] Babel: allow choosing link quality estimation algorithm
Nick Cao writes: > The presets are still handled, in babel_iface_finish of > proto/babel/config.Y. Ah, right, I was misreading that part of your patch, sorry about that. Looks like it is, indeed, doing the right thing wrt the old keywords, so no objections to merging this :) Acked-by: Toke Høiland-Jørgensen -Toke
Re: [RESEND PATCH v3] Babel: allow choosing link quality estimation algorithm
The presets are still handled, in babel_iface_finish of proto/babel/config.Y. On 11/9/23 05:25, Toke Høiland-Jørgensen wrote: Nick Cao via Bird-users writes: Resend of the patch in http://trubka.network.cz/pipermail/bird-users/2023-June/017058.html ETX link quality estimation algorithm is useful for link types other than wireless, especially when using babel with tunnels where packet losses do occur. --- doc/bird.sgml| 10 ++ proto/babel/babel.c | 8 +++- proto/babel/babel.h | 8 proto/babel/config.Y | 8 +++- 4 files changed, 28 insertions(+), 6 deletions(-) diff --git a/doc/bird.sgml b/doc/bird.sgml index f2063325..1a9bab87 100644 --- a/doc/bird.sgml +++ b/doc/bird.sgml @@ -2209,6 +2209,7 @@ protocol babel [] { rx buffer ; tx length ; check link ; + link quality ; next hop ipv4 ; next hop ipv6 ; extended next hop ; @@ -2312,6 +2313,15 @@ protocol babel [] { hardware drivers or platforms do not implement this feature. Default: yes. + link quality none|etx + This option specifies the link quality estimation algorithm for computing + costs based on Hello history: none or etx. The none (k-out-of-j) algorithm + is suitable for wired links that are either up, in which case they only + occasionally drop a packet, or down, in which case they drop all packets. + The Expected Transmission Cost algorithm, or etx, is suitable for wireless + links that exhibit continuous variation of the link quality. Default: etx for + wireless interfaces, none otherwise. + next hop ipv4 Set the next hop address advertised for IPv4 routes advertised on this interface. Default: the preferred IPv4 address of the interface. diff --git a/proto/babel/babel.c b/proto/babel/babel.c index 4187d258..f865c089 100644 --- a/proto/babel/babel.c +++ b/proto/babel/babel.c @@ -593,10 +593,9 @@ babel_update_cost(struct babel_neighbor *nbr) if (!rcv || !nbr->ifa->up) goto done; - switch (cf->type) + switch (cf->link_quality) { - case BABEL_IFACE_TYPE_WIRED: - case BABEL_IFACE_TYPE_TUNNEL: + case BABEL_IFACE_LINK_QUALITY_NONE: Sorry for missing this earlier, but it looks like with your patch bird will no longer honour the "wires" or "wireless" setting at all? Which will break old configs, so please don't do that. The right way to do this is to have "wired" and "wireless" serve as "presets", and then have the link quality override that setting. So that just setting "wireless" will get the same settings as today, but setting "wired + etx" will get you just the ETX setting. -Toke
Re: [RESEND PATCH v3] Babel: allow choosing link quality estimation algorithm
On Thu, Nov 09, 2023 at 11:25:10AM +0100, Toke Høiland-Jørgensen via Bird-users wrote: > Nick Cao via Bird-users writes: > > Sorry for missing this earlier, but it looks like with your patch bird > will no longer honour the "wires" or "wireless" setting at all? Which > will break old configs, so please don't do that. > > The right way to do this is to have "wired" and "wireless" serve as > "presets", and then have the link quality override that setting. So that > just setting "wireless" will get the same settings as today, but setting > "wired + etx" will get you just the ETX setting. Agreed. -- Elen sila lumenn' omentielvo Ondrej 'Santiago' Zajicek (email: santi...@crfreenet.org) OpenPGP encrypted e-mails preferred (KeyID 0x11DEADC3, wwwkeys.pgp.net) "To err is human -- to blame it on a computer is even more so."
Re: [RESEND PATCH v3] Babel: allow choosing link quality estimation algorithm
Nick Cao via Bird-users writes: > Resend of the patch in > http://trubka.network.cz/pipermail/bird-users/2023-June/017058.html > > ETX link quality estimation algorithm is useful for link types other than > wireless, > especially when using babel with tunnels where packet losses do occur. > --- > doc/bird.sgml| 10 ++ > proto/babel/babel.c | 8 +++- > proto/babel/babel.h | 8 > proto/babel/config.Y | 8 +++- > 4 files changed, 28 insertions(+), 6 deletions(-) > > diff --git a/doc/bird.sgml b/doc/bird.sgml > index f2063325..1a9bab87 100644 > --- a/doc/bird.sgml > +++ b/doc/bird.sgml > @@ -2209,6 +2209,7 @@ protocol babel [] { > rx buffer ; > tx length ; > check link ; > + link quality ; > next hop ipv4 ; > next hop ipv6 ; > extended next hop ; > @@ -2312,6 +2313,15 @@ protocol babel [] { >hardware drivers or platforms do not implement this feature. Default: >yes. > > + link quality none|etx > + This option specifies the link quality estimation algorithm for > computing > + costs based on Hello history: none or etx. The none (k-out-of-j) > algorithm > + is suitable for wired links that are either up, in which case they only > + occasionally drop a packet, or down, in which case they drop all > packets. > + The Expected Transmission Cost algorithm, or etx, is suitable for > wireless > + links that exhibit continuous variation of the link quality. Default: > etx for > + wireless interfaces, none otherwise. > + >next hop ipv4 >Set the next hop address advertised for IPv4 routes advertised on this >interface. Default: the preferred IPv4 address of the interface. > diff --git a/proto/babel/babel.c b/proto/babel/babel.c > index 4187d258..f865c089 100644 > --- a/proto/babel/babel.c > +++ b/proto/babel/babel.c > @@ -593,10 +593,9 @@ babel_update_cost(struct babel_neighbor *nbr) >if (!rcv || !nbr->ifa->up) > goto done; > > - switch (cf->type) > + switch (cf->link_quality) >{ > - case BABEL_IFACE_TYPE_WIRED: > - case BABEL_IFACE_TYPE_TUNNEL: > + case BABEL_IFACE_LINK_QUALITY_NONE: Sorry for missing this earlier, but it looks like with your patch bird will no longer honour the "wires" or "wireless" setting at all? Which will break old configs, so please don't do that. The right way to do this is to have "wired" and "wireless" serve as "presets", and then have the link quality override that setting. So that just setting "wireless" will get the same settings as today, but setting "wired + etx" will get you just the ETX setting. -Toke
Re: Babel RTT mechanism [Was: [RESEND PATCH v3] Babel: allow choosing link quality estimation] algorithm]
>> And babeld the reference implementation also allows enabling link quality >> estimation and the RTT extension at the same time, matching the current >> behavior of bird. Exactly right. > Considering that ETX estimates number of retransmissions, then for > algorithm that takes into account both RTT and packet loss it makes more > sense to have RTT metric multiplied by ETX coeficient? The current algorithm is described here: https://datatracker.ietf.org/doc/html/draft-ietf-babel-rtt-extension My intuition is that it doesn't matter much. The goal is not to have an accurate model of reality, the goal is to choose optimal paths. And I would guess that in any realistic topology, the two algorithms will yield the same or almost the same set of paths. It looks like your intuition is different from mine: that's exciting, and it means that we need to design an experiment in order to find out who's right. Can you design a topology in which the algorithm described in the draft and the algorithm that you propose yield different sets of paths, and where your proposed algorithm leads to significantly better performance? If it turns out that you're right, I'll be thrilled to write a successor RFC, perhaps with you as co-author. -- Juliusz
Re: Babel RTT mechanism [Was: [RESEND PATCH v3] Babel: allow choosing link quality estimation] algorithm]
On Wed, Nov 08, 2023 at 11:56:32AM -0500, Nick Cao wrote: > I think it is the intended design. Link quality is about packet losses, > while RTT is about, well, RTT, they cover different characteristics of the > link, which should all be taken into account for metric calculation. RTT has two sources, propagation delay (which is just a question of distance) and queuing/retransmission/MAC delay (which depends on link quality). On wifi with worsening link quality / congestion it starts with raising RTT (due to MAC delay and L2 retransmissions) and fluently continues with raising packet loss, so i would say that both packet loss and RTT are parameters of link quality and should be handled together by one mechanism, instead of two independent mechanisms. > And babeld the reference implementation also allows enabling link quality > estimation and the RTT extension at the same time, matching the current > behavior of bird. I agree that it make sense to handle both packet loss and RTT information for purposes of metric estimation. I just do not think it makes sense to estimate two separate metrics and then sum it. Considering that ETX estimates number of retransmissions, then for algorithm that takes into account both RTT and packet loss it makes more sense to have RTT metric multiplied by ETX coeficient? > On 11/8/23 11:44, Ondrej Zajicek wrote: > > On Sat, Oct 28, 2023 at 09:24:56PM -0400, Nick Cao via Bird-users wrote: > > > Resend of the patch in > > > http://trubka.network.cz/pipermail/bird-users/2023-June/017058.html > > > > > > ETX link quality estimation algorithm is useful for link types other than > > > wireless, > > > especially when using babel with tunnels where packet losses do occur. > > > > Hi > > > > I looked at your patch with intent of merging it, i like a separate > > option for selection of dynamic metric algorithm, but i noticed that i > > misunderstood how recently added RTT mechanism interacts with the rest. > > > > I thought we have three alternative link quality / metric estimation > > algorithms: > > > > - fixed (k-out-of-j) > > - ETX > > - RTT > > > > But in fact RTT is independent metric, which is added on top of fixed/ETX > > metric. > > > > Is this intentional? Does it make sense? > > > > (This is mainly a question for Toke or Juliusz) > > -- Elen sila lumenn' omentielvo Ondrej 'Santiago' Zajicek (email: santi...@crfreenet.org) OpenPGP encrypted e-mails preferred (KeyID 0x11DEADC3, wwwkeys.pgp.net) "To err is human -- to blame it on a computer is even more so."
Re: Babel RTT mechanism [Was: [RESEND PATCH v3] Babel: allow choosing link quality estimation] algorithm]
I think it is the intended design. Link quality is about packet losses, while RTT is about, well, RTT, they cover different characteristics of the link, which should all be taken into account for metric calculation. And babeld the reference implementation also allows enabling link quality estimation and the RTT extension at the same time, matching the current behavior of bird. On 11/8/23 11:44, Ondrej Zajicek wrote: On Sat, Oct 28, 2023 at 09:24:56PM -0400, Nick Cao via Bird-users wrote: Resend of the patch in http://trubka.network.cz/pipermail/bird-users/2023-June/017058.html ETX link quality estimation algorithm is useful for link types other than wireless, especially when using babel with tunnels where packet losses do occur. Hi I looked at your patch with intent of merging it, i like a separate option for selection of dynamic metric algorithm, but i noticed that i misunderstood how recently added RTT mechanism interacts with the rest. I thought we have three alternative link quality / metric estimation algorithms: - fixed (k-out-of-j) - ETX - RTT But in fact RTT is independent metric, which is added on top of fixed/ETX metric. Is this intentional? Does it make sense? (This is mainly a question for Toke or Juliusz)
Babel RTT mechanism [Was: [RESEND PATCH v3] Babel: allow choosing link quality estimation] algorithm]
On Sat, Oct 28, 2023 at 09:24:56PM -0400, Nick Cao via Bird-users wrote: > Resend of the patch in > http://trubka.network.cz/pipermail/bird-users/2023-June/017058.html > > ETX link quality estimation algorithm is useful for link types other than > wireless, > especially when using babel with tunnels where packet losses do occur. Hi I looked at your patch with intent of merging it, i like a separate option for selection of dynamic metric algorithm, but i noticed that i misunderstood how recently added RTT mechanism interacts with the rest. I thought we have three alternative link quality / metric estimation algorithms: - fixed (k-out-of-j) - ETX - RTT But in fact RTT is independent metric, which is added on top of fixed/ETX metric. Is this intentional? Does it make sense? (This is mainly a question for Toke or Juliusz) -- Elen sila lumenn' omentielvo Ondrej 'Santiago' Zajicek (email: santi...@crfreenet.org) OpenPGP encrypted e-mails preferred (KeyID 0x11DEADC3, wwwkeys.pgp.net) "To err is human -- to blame it on a computer is even more so."
[RESEND PATCH v3] Babel: allow choosing link quality estimation algorithm
Resend of the patch in http://trubka.network.cz/pipermail/bird-users/2023-June/017058.html ETX link quality estimation algorithm is useful for link types other than wireless, especially when using babel with tunnels where packet losses do occur. --- doc/bird.sgml| 10 ++ proto/babel/babel.c | 8 +++- proto/babel/babel.h | 8 proto/babel/config.Y | 8 +++- 4 files changed, 28 insertions(+), 6 deletions(-) diff --git a/doc/bird.sgml b/doc/bird.sgml index f2063325..1a9bab87 100644 --- a/doc/bird.sgml +++ b/doc/bird.sgml @@ -2209,6 +2209,7 @@ protocol babel [] { rx buffer ; tx length ; check link ; + link quality ; next hop ipv4 ; next hop ipv6 ; extended next hop ; @@ -2312,6 +2313,15 @@ protocol babel [] { hardware drivers or platforms do not implement this feature. Default: yes. + link quality none|etx + This option specifies the link quality estimation algorithm for computing + costs based on Hello history: none or etx. The none (k-out-of-j) algorithm + is suitable for wired links that are either up, in which case they only + occasionally drop a packet, or down, in which case they drop all packets. + The Expected Transmission Cost algorithm, or etx, is suitable for wireless + links that exhibit continuous variation of the link quality. Default: etx for + wireless interfaces, none otherwise. + next hop ipv4 Set the next hop address advertised for IPv4 routes advertised on this interface. Default: the preferred IPv4 address of the interface. diff --git a/proto/babel/babel.c b/proto/babel/babel.c index 4187d258..f865c089 100644 --- a/proto/babel/babel.c +++ b/proto/babel/babel.c @@ -593,10 +593,9 @@ babel_update_cost(struct babel_neighbor *nbr) if (!rcv || !nbr->ifa->up) goto done; - switch (cf->type) + switch (cf->link_quality) { - case BABEL_IFACE_TYPE_WIRED: - case BABEL_IFACE_TYPE_TUNNEL: + case BABEL_IFACE_LINK_QUALITY_NONE: /* k-out-of-j selection - Appendix 2.1 in the RFC. */ /* Link is bad if less than cf->limit/16 of expected hellos were received */ @@ -606,8 +605,7 @@ babel_update_cost(struct babel_neighbor *nbr) rxcost = cf->rxcost; txcost = nbr->txcost; break; - - case BABEL_IFACE_TYPE_WIRELESS: + case BABEL_IFACE_LINK_QUALITY_ETX: /* * ETX - Appendix 2.2 in the RFC. * diff --git a/proto/babel/babel.h b/proto/babel/babel.h index edde4cab..6a2968f1 100644 --- a/proto/babel/babel.h +++ b/proto/babel/babel.h @@ -118,6 +118,13 @@ enum babel_iface_type { BABEL_IFACE_TYPE_MAX }; +enum babel_iface_link_quality { + BABEL_IFACE_LINK_QUALITY_UNDEF = 0, + BABEL_IFACE_LINK_QUALITY_NONE= 1, + BABEL_IFACE_LINK_QUALITY_ETX = 2, + BABEL_IFACE_LINK_QUALITY_MAX +}; + enum babel_ae_type { BABEL_AE_WILDCARD= 0, BABEL_AE_IP4 = 1, @@ -145,6 +152,7 @@ struct babel_iface_config { u8 type; u8 limit;/* Minimum number of Hellos to keep link up */ u8 check_link; + u8 link_quality; uint port; uint hello_interval; /* Hello interval, in us */ uint ihu_interval; /* IHU interval, in us */ diff --git a/proto/babel/config.Y b/proto/babel/config.Y index b8af0267..285a3f33 100644 --- a/proto/babel/config.Y +++ b/proto/babel/config.Y @@ -26,7 +26,7 @@ CF_KEYWORDS(BABEL, INTERFACE, METRIC, RXCOST, HELLO, UPDATE, INTERVAL, PORT, TYPE, WIRED, WIRELESS, RX, TX, BUFFER, PRIORITY, LENGTH, CHECK, LINK, NEXT, HOP, IPV4, IPV6, BABEL_METRIC, SHOW, INTERFACES, NEIGHBORS, ENTRIES, RANDOMIZE, ROUTER, ID, AUTHENTICATION, NONE, MAC, PERMISSIVE, - EXTENDED, TUNNEL, RTT, MIN, MAX, DECAY, SEND, TIMESTAMPS) + EXTENDED, TUNNEL, RTT, MIN, MAX, DECAY, SEND, TIMESTAMPS, QUALITY, ETX) CF_GRAMMAR @@ -84,6 +84,8 @@ babel_iface_finish: BABEL_IFACE->hello_interval = BABEL_HELLO_INTERVAL_WIRELESS; if (!BABEL_IFACE->rxcost) BABEL_IFACE->rxcost = BABEL_RXCOST_WIRELESS; +if (!BABEL_IFACE->link_quality) + BABEL_IFACE->link_quality = BABEL_IFACE_LINK_QUALITY_ETX; } else { @@ -93,6 +95,8 @@ babel_iface_finish: BABEL_IFACE->rxcost = BABEL_RXCOST_WIRED; if (BABEL_IFACE->type == BABEL_IFACE_TYPE_TUNNEL && !BABEL_IFACE->rtt_cost) BABEL_IFACE->rtt_cost = BABEL_RXCOST_RTT; +if (!BABEL_IFACE->link_quality) + BABEL_IFACE->link_quality = BABEL_IFACE_LINK_QUALITY_NONE; } if (BABEL_IFACE->rtt_cost && !BABEL_IFACE->rtt_send) @@ -156,6 +160,8 @@ babel_iface_item: | TX tos { BABEL_IFACE->tx_tos = $2; } | TX PRIORITY expr { BABEL_IFACE->tx_priority = $3; } | CHECK LINK bool { BABEL_IFACE->check_link = $3; } + | LINK QUALITY NONE { BABEL_IFACE->link_quality = BABEL_IFACE_LINK_QUALITY_NONE; } + | LINK QUALITY ETX { BABEL_IFA