Repository : ssh://git@diktynna/doc

On branch : master

commit 5af6ea98e3c2053759ae5c351a4bb1f844141ec4 Merge: a985ae6 36caac2 Author: Sven Eckelmann sven@narfation.org Date: Sat Mar 6 09:31:06 2021 +0100

Merge branch 'backup-redmine/2021-03-06'

5af6ea98e3c2053759ae5c351a4bb1f844141ec4 batman-adv/Gateway-Selection-Issue.rst | 161 +++++ batman-adv/bcast-3x.dia | Bin 1003 -> 7363 bytes batman-adv/bcast-arp-req-gw.dia | Bin 1478 -> 16476 bytes batman-adv/broadcast.dia | Bin 1677 -> 17059 bytes .../{Bw1.dia => gateway-selection-issue.dia} | 781 ++++++++++----------- batman-adv/gateway-selection-issue.svg | 64 ++ batman-adv/noflood-sign.dia | Bin 995 -> 5866 bytes 7 files changed, 609 insertions(+), 397 deletions(-)

diff --cc batman-adv/Gateway-Selection-Issue.rst index 0000000,0000000..60180cf new file mode 100644 --- /dev/null +++ b/batman-adv/Gateway-Selection-Issue.rst @@@ -1,0 -1,0 +1,161 @@@ ++.. SPDX-License-Identifier: GPL-2.0 ++ ++Gateway Selection Issue ++======================= ++ ++Scenario ++-------- ++ ++|image0| ++ ++*A batman-adv gateway client selecting a gateway behind the actual best ++gateway* ++ ++The scenario consists of BATMAN V nodes. GW1, GW2, GW3 and N1 have 1 ++Gbit/s links. While N2 is behind N1 with a considerably lower ++throughput, here 50 Mbit/s. ++ ++While node N1 selects the correct, best gateway it is directly connected ++to, node N1 only selects GW1 with a 33% chance. And by a 66% selects ++either GW2 or GW3. Leading to an unnecessarily long route. ++ ++Issue Description ++----------------- ++ ++On N1, the gateway table looks as follows: ++ ++:: ++ ++ <code> ++ N1$ batctl gw ++ client (selection class: 5.0 MBit) ++ N1$ batctl gwl ++ [B.A.T.M.A.N. adv openwrt-2019.2-10, MainIF/MAC: primary0/<orig-mac> (bat0/<bat0-mac> BATMAN_V)] ++ Router ( throughput) Next Hop [outgoingIf] Bandwidth ++ * GW1 ( 1000.0) GW1 [ mesh-vpn]: 1000.0/1000.0 MBit ++ GW2 ( 941.1) GW1 [ mesh-vpn]: 1000.0/1000.0 MBit ++ GW3 ( 941.1) GW1 [ mesh-vpn]: 1000.0/1000.0 MBit ++ </code> ++ ++Node N1 correctly selects GW1 as its best gateway thanks to the hop ++penalty which reduces the throughput by 230/255 = 5.9%. The difference ++is larger than the configured 5.0 MBit selection class, so node N1 will ++always select GW1 as its gateway for the unicasted DHCP packets. ++ ++On node N2 however the table gateway table looks as follows: ++ ++:: ++ ++ <code> ++ N2$ batctl gw ++ client (selection class: 5.0 MBit) ++ N2$ batctl gwl ++ [B.A.T.M.A.N. adv openwrt-2019.2-10, MainIF/MAC: primary0/<orig-mac> (bat0/<bat0-mac> BATMAN_V)] ++ Router ( throughput) Next Hop [outgoingIf] Bandwidth ++ * GW3 ( 50.0) GW1 [ wlan0]: 1000.0/1000.0 MBit ++ GW1 ( 50.0) GW1 [ wlan0]: 1000.0/1000.0 MBit ++ GW2 ( 50.0) GW1 [ wlan0]: 1000.0/1000.0 MBit ++ </code> ++ ++On node N2 the BATMAN V metric to all gateways is 50 MBit/s because ++BATMAN V calculates the minimum of the received throughput in the OGM ++(to GW1: 1000, to GW2: 941.1, to GW3: 941.1) and the link throughput ++towards the destination (50 Mbit/s). ++ ++This leads to node N2 selecting the gateway which it first heard an OGM ++from. So it "randomly" selects one of the three available gateways. The ++probability to select the correct, best gateway decreases the more ++gateways are behind GW1 for N2. ++ ++Node N1 had more, better information for selecting the best gateway ++which got lost by calculating the minimum. ++ ++In theory this issue could happen with BATMAN IV, too. However it is a ++lot less likely to happen because BATMAN IV multiplies the link quality ++to the received TQ value instead of calculating a minimum. Therefore for ++BATMAN IV the 5.9% lower TQ to GW2/GW3 created by the hop penalty will ++persist (as long as the hop penalty is not reduced / configured to a ++lower value). ++ ++Solution (approaches) ++--------------------- ++ ++Redirecting unicasted DHCP messages ++~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ++ ++Node N1 could detect that it knows a better gateway than the one N2 has ++selected: It could check the DHCP messages send by N2 via a batman-adv ++unicast frame and rewrite its destination to GW1. ++ ++Issue: Could probably loop? ++ ++Sinking unicasted DHCP messages. ++~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ++ ++A gateway server, here GW1, could check if it is about to forward a ++unicasted DHCP message to another gateway server. And if so, refrain ++from forwarding and deliver it to its own bat0 instead. ++ ++Issue: A DHCP client sends multiple messages to a DHCP server. We might ++break the DHCP handshake if the routes switched in between the ++handshake. ++ ++Filtering Gateway Announcements ++~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ++ ++Nodes could filter out gateway announcements from OGMs before forwarding ++them. A gateway server could always filter out gateway announcements ++from other gateways. A non-gateway-server node could filter out gateway ++announcements from OGMs from each gateway server which does **not** have ++the highest path throughput (or TQ for BATMAN IV). ++ ++Issue: The gateway announcement TVLV handler is called with ++BATADV_TVLV_HANDLER_OGM_CIFNOTFND. If a node were receiving OGMs from ++two different neighbors where one would have the gateway announcement ++TVLV and the other one wouldn���t then this would lead to gateway ++selection flapping with each received OGM. The ++BATADV_TVLV_HANDLER_OGM_CIFNOTFND would need to be removed and replaced ++by a timeout. Which however would lead to reduced responsiveness / ++delays if a gateway disabled its gateway server mode. And more ++importantly, it would break compatibility, it���d need yet another ++TVLV/flag to propagate this capability. And only if all nodes were ++announcing this capability nodes could change their behaviour. ++ ++Another issue is that it might render the stickiness client option void ++if for a forwarding node the gateway with the highest path throughput ++switches often. Which would lead to gateway flapping for gateway client ++even if it set a selection class / stickiness. ++ ++Flagging Best Gateway Announcements ++~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ++ ++An additional flag could be added to the gateway announcements. Instead ++of filtering gateway announcements a node would unset this flag if it is ++not from its "best" gateway. A gateway server forwarding gateway ++announcements of other gateway servers would always unset this flag. The ++original gateway server would always set the flag in its gateway ++announcements when originating them. ++ ++A gateway is considered "best" for keeping the flag set if: ++ ++- ++ ++Question: Should we re-set the flag when receiving a gateway ++announcement with the flag unset if it is our best gateway via a ++different neighbor? Or would we avoid resending this OGM anyway due to ++how the BATMAN algorithm works? ++ ++Issues: The stickiness would need to be disregarded for the first OGM ++sequence number(s) or would need to be disregarded periodically to be ++able to converge to the best gateway. ++ ++General issues with filtering or flagging: ++^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ++ ++While currently BATMAN V only takes the announced download bitrate into ++consideration, if a gateway client would want to select the best gateway ++by upload rate in the future that information would not be available ++anymore. In other words, a forwarding node might have other criteria for ++its best gateway than the final gateway clients. ++ ++.. |image0| image:: gateway-selection-issue.svg diff --cc batman-adv/bcast-3x.dia index 6ed7397,6ed7397..765c43f Binary files differ diff --cc batman-adv/bcast-arp-req-gw.dia index 0064923,0064923..036204c Binary files differ diff --cc batman-adv/broadcast.dia index 48131ae,48131ae..c74e2b4 Binary files differ diff --cc batman-adv/gateway-selection-issue.dia index b97b677,540f4a7..cabc5e3 Binary files differ diff --cc batman-adv/gateway-selection-issue.svg index 0000000,0000000..f9cd5a3 new file mode 100644 --- /dev/null +++ b/batman-adv/gateway-selection-issue.svg @@@ -1,0 -1,0 +1,64 @@@ ++<?xml version="1.0" encoding="UTF-8" standalone="no"?> ++<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.0//EN" "http://www.w3.org/TR/2001/PR-SVG-20010719/DTD/svg10.dtd"> ++<svg width="34cm" height="21cm" viewBox="319 229 662 412" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"> ++ <defs/> ++ <g id="Background"> ++ <ellipse style="fill: #ffa500; fill-opacity: 1; stroke-opacity: 1; stroke-width: 2; stroke: #000000" cx="610" cy="490" rx="30" ry="30"/> ++ <ellipse style="fill: #add8e6; fill-opacity: 1; stroke-opacity: 1; stroke-width: 2; stroke: #000000" cx="770" cy="570" rx="30" ry="30"/> ++ <ellipse style="fill: #ffa500; fill-opacity: 1; stroke-opacity: 1; stroke-width: 2; stroke: #000000" cx="430" cy="490" rx="30" ry="30"/> ++ <ellipse style="fill: #ffa500; fill-opacity: 1; stroke-opacity: 1; stroke-width: 2; stroke: #000000" cx="520" cy="350" rx="30" ry="30"/> ++ <ellipse style="fill: #add8e6; fill-opacity: 1; stroke-opacity: 1; stroke-width: 2; stroke: #000000" cx="950" cy="570" rx="30" ry="30"/> ++ <text font-size="12.8" style="fill: #000000; fill-opacity: 1; stroke: none;text-anchor:start;font-family:sans-serif;font-style:normal;font-weight:normal" x="412" y="492"> ++ <tspan x="412" y="492">GW2</tspan> ++ </text> ++ <text font-size="12.8" style="fill: #000000; fill-opacity: 1; stroke: none;text-anchor:start;font-family:sans-serif;font-style:normal;font-weight:normal" x="592" y="492"> ++ <tspan x="592" y="492">GW1</tspan> ++ </text> ++ <text font-size="12.8" style="fill: #000000; fill-opacity: 1; stroke: none;text-anchor:start;font-family:sans-serif;font-style:normal;font-weight:normal" x="502" y="352"> ++ <tspan x="502" y="352">GW3</tspan> ++ </text> ++ <text font-size="12.8" style="fill: #000000; fill-opacity: 1; stroke: none;text-anchor:start;font-family:sans-serif;font-style:normal;font-weight:normal" x="760" y="572"> ++ <tspan x="760" y="572">N1</tspan> ++ </text> ++ <text font-size="12.8" style="fill: #000000; fill-opacity: 1; stroke: none;text-anchor:start;font-family:sans-serif;font-style:normal;font-weight:normal" x="940" y="572"> ++ <tspan x="940" y="572">N2</tspan> ++ </text> ++ <line style="fill: none; stroke-opacity: 1; stroke-width: 10; stroke: #000000" x1="536.754" y1="376.062" x2="593.246" y2="463.938"/> ++ <line style="fill: none; stroke-opacity: 1; stroke-width: 10; stroke: #000000" x1="503.246" y1="376.062" x2="446.754" y2="463.938"/> ++ <line style="fill: none; stroke-opacity: 1; stroke-width: 10; stroke: #000000" x1="579.008" y1="490" x2="460.992" y2="490"/> ++ <line style="fill: none; stroke-opacity: 1; stroke-width: 10; stroke: #000000" x1="742.305" y1="556.152" x2="637.695" y2="503.848"/> ++ <line style="fill: none; stroke-opacity: 1; stroke-width: 2; stroke-dasharray: 4; stroke: #000000" x1="800.992" y1="570" x2="919.008" y2="570"/> ++ <text font-size="12.8" style="fill: #000000; fill-opacity: 1; stroke: none;text-anchor:start;font-family:sans-serif;font-style:normal;font-weight:normal" x="716" y="340"> ++ <tspan x="716" y="340">GW1, GW2, GW3: Gateway server mode</tspan> ++ </text> ++ <text font-size="12.8" style="fill: #000000; fill-opacity: 1; stroke: none;text-anchor:start;font-family:sans-serif;font-style:normal;font-weight:normal" x="780" y="360"> ++ <tspan x="780" y="360">N1, N2: Gateway client mode</tspan> ++ </text> ++ <line style="fill: none; stroke-opacity: 1; stroke-width: 10; stroke: #000000" x1="764" y1="384" x2="814" y2="384"/> ++ <text font-size="12.8" style="fill: #000000; fill-opacity: 1; stroke: none;text-anchor:start;font-family:sans-serif;font-style:normal;font-weight:normal" x="824" y="388"> ++ <tspan x="824" y="388">: 1000 Mbit/s link</tspan> ++ </text> ++ <text font-size="12.8" style="fill: #000000; fill-opacity: 1; stroke: none;text-anchor:start;font-family:sans-serif;font-style:normal;font-weight:normal" x="824" y="416"> ++ <tspan x="824" y="416">: 50 Mbit/s link</tspan> ++ </text> ++ <line style="fill: none; stroke-opacity: 1; stroke-width: 2; stroke-dasharray: 4; stroke: #000000" x1="764" y1="412" x2="814" y2="412"/> ++ <text font-size="12.8" style="fill: #000000; fill-opacity: 1; stroke: none;text-anchor:start;font-family:sans-serif;font-style:normal;font-weight:normal" x="640" y="630"> ++ <tspan x="640" y="630">Selected GW: GW1</tspan> ++ </text> ++ <g> ++ <path style="fill: none; stroke-opacity: 1; stroke-width: 2; stroke: #90ee90" d="M 748.786,591.214 A 96.8203,96.8203 0 0 1 612.024,529.486"/> ++ <polygon style="fill: #90ee90; fill-opacity: 1; stroke-opacity: 1; stroke-width: 2; stroke: #90ee90" fill-rule="evenodd" points="610.356,522.207 616.886,531.283 611.552,529.612 607.014,532.877 "/> ++ </g> ++ <text font-size="12.8" style="fill: #000000; fill-opacity: 1; stroke: none;text-anchor:start;font-family:sans-serif;font-style:normal;font-weight:normal" x="860" y="520"> ++ <tspan x="860" y="520">Selected GW: GW3</tspan> ++ </text> ++ <g> ++ <path style="fill: none; stroke-opacity: 1; stroke-width: 2; stroke: #ff3f00" d="M 925.2 551.4 C 885.2,521.4 823.334,540 780,530 C 736.666,520 670,480 640,460 C 610,440 661,350 560.736,350"/> ++ <polygon style="fill: #ff3f00; fill-opacity: 1; stroke-opacity: 1; stroke-width: 2; stroke: #ff3f00" fill-rule="evenodd" points="553.236,350 563.236,345 560.736,350 563.236,355 "/> ++ </g> ++ <ellipse style="fill: #ffffff; fill-opacity: 1; stroke-opacity: 1; stroke-width: 2; stroke: #000000" cx="350" cy="610" rx="30" ry="30"/> ++ <ellipse style="fill: #ffffff; fill-opacity: 1; stroke-opacity: 1; stroke-width: 2; stroke: #000000" cx="390" cy="260" rx="30" ry="30"/> ++ <line style="fill: none; stroke-opacity: 1; stroke-width: 10; stroke: #000000" x1="494.506" y1="332.35" x2="415.494" y2="277.65"/> ++ <line style="fill: none; stroke-opacity: 1; stroke-width: 10; stroke: #000000" x1="412.808" y1="515.789" x2="367.192" y2="584.211"/> ++ </g> ++</svg> diff --cc batman-adv/noflood-sign.dia index 1e63ecf,1e63ecf..ab1a0cf Binary files differ