June 2020 - tor-commits - lists.torproject.org

[sbws/maint-1.1] chg: v3bwfile: Exclude relays without observed bw
by juga＠torproject.org 29 Jun '20

29 Jun '20

commit a44ffcb20d0efcd68b3a80b080494f3c7a5da1e2 Author: juga0 <juga(a)riseup.net> Date: Sun May 17 13:30:03 2020 +0000 chg: v3bwfile: Exclude relays without observed bw and without consensus bw from scaling. Part of #33871, closes #33831. --- sbws/lib/v3bwfile.py | 7 +++++++ 1 file changed, 7 insertions(+) diff --git a/sbws/lib/v3bwfile.py b/sbws/lib/v3bwfile.py index 263a285..56925cb 100644 --- a/sbws/lib/v3bwfile.py +++ b/sbws/lib/v3bwfile.py @@ -773,6 +773,13 @@ class V3BWLine(object): desc_bw_obs_last = \ cls.desc_bw_obs_last_from_results(results_recent) + # Exclude also relays without consensus bandwidth nor observed + # bandwidth, since they can't be scaled + if (desc_bw_obs_last is None and consensus_bandwidth is None): + # This reason is not counted, not added in the file, but it will + # have vote = 0 + return(cls(node_id, 1), "no_consensus_no_observed_bw") + # For any line not excluded, do not include vote and unmeasured # KeyValues del kwargs['vote']

1 0

[sbws/maint-1.1] fix: test: Unrelated linter error
by juga＠torproject.org 29 Jun '20

29 Jun '20

commit b9e8fcd7fdcd931fe87a715d089c073d8fd3fe34 Author: juga0 <juga(a)riseup.net> Date: Tue May 19 14:28:20 2020 +0000 fix: test: Unrelated linter error --- tests/conftest.py | 1 + 1 file changed, 1 insertion(+) diff --git a/tests/conftest.py b/tests/conftest.py index 5d156f1..5f71b4a 100644 --- a/tests/conftest.py +++ b/tests/conftest.py @@ -116,6 +116,7 @@ def router_status(server_descriptor, router_statuses): ][0] return rs + # Because of the function scoped `args` in `tests.unit.conftest`, this has to # be function scoped too. @pytest.fixture(scope='function')

1 0

[sbws/maint-1.1] fix: docs: Move torflow scaling docstring to docs
by juga＠torproject.org 29 Jun '20

29 Jun '20

commit 54a1128af9670380d0c47d1f4d92994a662c1f3f Author: juga0 <juga(a)riseup.net> Date: Tue May 19 15:19:11 2020 +0000 fix: docs: Move torflow scaling docstring to docs so that it has its own page as it is too long as docstring and is harder to write latex with the docstring syntax. --- docs/source/torflow_aggr.rst | 150 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 150 insertions(+) diff --git a/docs/source/torflow_aggr.rst b/docs/source/torflow_aggr.rst new file mode 100644 index 0000000..6fc8fd1 --- /dev/null +++ b/docs/source/torflow_aggr.rst @@ -0,0 +1,150 @@ +.. _torflow_aggr: + +Torflow measurements aggregation +================================== + +From Torflow's README.spec.txt (section 2.2):: + + In this way, the resulting network status consensus bandwidth values # NOQA + are effectively re-weighted proportional to how much faster the node # NOQA + was as compared to the rest of the network. + +The variables and steps used in Torflow: + +**strm_bw**:: + + The strm_bw field is the average (mean) of all the streams for the relay # NOQA + identified by the fingerprint field. + strm_bw = sum(bw stream x)/|n stream| + +**filt_bw**:: + + The filt_bw field is computed similarly, but only the streams equal to # NOQA + or greater than the strm_bw are counted in order to filter very slow # NOQA + streams due to slow node pairings. + +**filt_sbw and strm_sbw**:: + + for rs in RouterStats.query.filter(stats_clause).\ + options(eagerload_all('router.streams.circuit.routers')).all(): # NOQA + tot_sbw = 0 + sbw_cnt = 0 + for s in rs.router.streams: + if isinstance(s, ClosedStream): + skip = False + #for br in badrouters: + # if br != rs: + # if br.router in s.circuit.routers: + # skip = True + if not skip: + # Throw out outliers < mean + # (too much variance for stddev to filter much) + if rs.strm_closed == 1 or s.bandwidth() >= rs.sbw: + tot_sbw += s.bandwidth() + sbw_cnt += 1 + + if sbw_cnt: rs.filt_sbw = tot_sbw/sbw_cnt + else: rs.filt_sbw = None + +**filt_avg, and strm_avg**:: + + Once we have determined the most recent measurements for each node, we # NOQA + compute an average of the filt_bw fields over all nodes we have measured. # NOQA + +:: + + filt_avg = sum(map(lambda n: n.filt_bw, nodes.itervalues()))/float(len(nodes)) # NOQA + strm_avg = sum(map(lambda n: n.strm_bw, nodes.itervalues()))/float(len(nodes)) # NOQA + +**true_filt_avg and true_strm_avg**:: + + for cl in ["Guard+Exit", "Guard", "Exit", "Middle"]: + true_filt_avg[cl] = filt_avg + true_strm_avg[cl] = strm_avg + +In the non-pid case, all types of nodes get the same avg + +**n.fbw_ratio and n.fsw_ratio**:: + + for n in nodes.itervalues(): + n.fbw_ratio = n.filt_bw/true_filt_avg[n.node_class()] + n.sbw_ratio = n.strm_bw/true_strm_avg[n.node_class()] + +**n.ratio**:: + + These averages are used to produce ratios for each node by dividing the # NOQA + measured value for that node by the network average. + +:: + + # Choose the larger between sbw and fbw + if n.sbw_ratio > n.fbw_ratio: + n.ratio = n.sbw_ratio + else: + n.ratio = n.fbw_ratio + +**desc_bw**: + +It is the minimum of all the descriptor bandwidth values:: + + bws = map(int, g) + bw_observed = min(bws) + + return Router(ns.idhex, ns.nickname, bw_observed, dead, exitpolicy, + ns.flags, ip, version, os, uptime, published, contact, rate_limited, # NOQA + ns.orhash, ns.bandwidth, extra_info_digest, ns.unmeasured) + + self.desc_bw = max(bw,1) # Avoid div by 0 + +**new_bw**:: + + These ratios are then multiplied by the most recent observed descriptor # NOQA + bandwidth we have available for each node, to produce a new value for # NOQA + the network status consensus process. + +:: + + n.new_bw = n.desc_bw*n.ratio + +The descriptor observed bandwidth is multiplied by the ratio. + +**Limit the bandwidth to a maximum**:: + + NODE_CAP = 0.05 + +:: + + if n.new_bw > tot_net_bw*NODE_CAP: + plog("INFO", "Clipping extremely fast "+n.node_class()+" node "+n.idhex+"="+n.nick+ # NOQA + " at "+str(100*NODE_CAP)+"% of network capacity ("+ + str(n.new_bw)+"->"+str(int(tot_net_bw*NODE_CAP))+") "+ + " pid_error="+str(n.pid_error)+ + " pid_error_sum="+str(n.pid_error_sum)) + n.new_bw = int(tot_net_bw*NODE_CAP) + +However, tot_net_bw does not seems to be updated when not using pid. +This clipping would make faster relays to all have the same value. + +All of that can be expressed as: + +.. math:: + + bwn_i =& min\\left(bwnew_i, + \\sum_{i=1}^{n}bwnew_i \\times 0.05\\right) \\ + + &= min\\left( + \\left(min\\left(bwobs_i, bwavg_i, bwbur_i \\right) \\times r_i\\right), + \\sum_{i=1}^{n}\\left(min\\left(bwobs_i, bwavg_i, bwbur_i \\right) \\times r_i\\right) + \\times 0.05\\right)\\ + + &= min\\left( + \\left(min\\left(bwobs_i, bwavg_i, bwbur_i \\right) \\times max\\left(rf_i, rs_i\\right)\\right), + \\sum_{i=1}^{n}\\left(min\\left(bwobs_i, bwavg_i, bwbur_i \\right) \\times + max\\left(rf_i, rs_i\\right)\\right) \\times 0.05\\right)\\ + + &= min\\left( + \\left(min\\left(bwobs_i, bwavg_i, bwbur_i \\right) \\times max\\left(\\frac{bwfilt_i}{bwfilt}, + \\frac{bw_i}{bwstrm}\\right)\\right), + \\sum_{i=1}^{n}\\left(min\\left(bwobs_i, bwavg_i, bwbur_i \\right) \\times + max\\left(\\frac{bwfilt_i}{bwfilt}, + \\frac{bw_i}{bwstrm}\\right)\\right) \\times 0.05\\right)

1 0

[sbws/maint-1.1] fix: doc: Add differences between Torflow and sbws
by juga＠torproject.org 29 Jun '20

29 Jun '20

commit f531c57c7f67d72a597e3299a9cb2ec053d58d8d Author: juga0 <juga(a)riseup.net> Date: Wed May 20 13:44:59 2020 +0000 fix: doc: Add differences between Torflow and sbws Closes #33871. --- docs/source/torflow_aggr.rst | 36 ++++++++++++++++++++++++++++++++++++ 1 file changed, 36 insertions(+) diff --git a/docs/source/torflow_aggr.rst b/docs/source/torflow_aggr.rst index 10b12a8..5b4b3fd 100644 --- a/docs/source/torflow_aggr.rst +++ b/docs/source/torflow_aggr.rst @@ -385,6 +385,42 @@ Per relay scaled bandwidth rounding Finally, the new scaled bandwidth is expressed in kilobytes and rounded a number of digits. +Differences between Torflow aggregation and sbws scaling (May 2020) +------------------------------------------------------------------- + +Torflow does not exclude relays because of having "few" measurements or "close" +to each other for that relay. + +If there are not new measurements for a relay, Torflow uses the previous +calculated bandwidth, instead of the new value:: + + # If there is a new sample, let's use it for all but guards + if n.measured_at > prev_votes.vote_map[n.idhex].measured_at: + + [snip] + + else: + # Reset values. Don't vote/sample this measurement round. + n.revert_to_vote(prev_votes.vote_map[n.idhex]) + +The oldest measurements Toflow seems to take are from 4 weeks ago, while sbws +oldest measurements are 5 days old:: + + GUARD_SAMPLE_RATE = 2*7*24*60*60 # 2wks + + [snip] + + MAX_AGE = 2*GUARD_SAMPLE_RATE + + [snip] + + # old measurements are probably + # better than no measurements. We may not + # measure hibernating routers for days. + # This filter is just to remove REALLY old files + if time.time() - timestamp > MAX_AGE: + + .. _README.spec.txt: https://gitweb.torproject.org/torflow.git/tree/NetworkScanners/BwAuthority/… .. _PID Controller: https://en.wikipedia.org/wiki/PID_controller .. _SQLSupport.py: https://gitweb.torproject.org/pytorctl.git/tree/SQLSupport.py#n493

1 0

[sbws/maint-1.1] fix: docs: Remove unneeded linter exception
by juga＠torproject.org 29 Jun '20

29 Jun '20

commit 3edf2fe2a739af4a2ccc8f128e45245347bce265 Author: juga0 <juga(a)riseup.net> Date: Tue May 19 15:22:13 2020 +0000 fix: docs: Remove unneeded linter exception --- docs/source/index.rst | 1 + docs/source/torflow_aggr.rst | 30 ++++----- sbws/lib/v3bwfile.py | 147 +------------------------------------------ 3 files changed, 17 insertions(+), 161 deletions(-) diff --git a/docs/source/index.rst b/docs/source/index.rst index 342e857..58c3911 100644 --- a/docs/source/index.rst +++ b/docs/source/index.rst @@ -45,6 +45,7 @@ Included in the config config_tor sbws + torflow_aggr implementation bandwidth_distribution tor_bandwidth_files diff --git a/docs/source/torflow_aggr.rst b/docs/source/torflow_aggr.rst index 6fc8fd1..49441b4 100644 --- a/docs/source/torflow_aggr.rst +++ b/docs/source/torflow_aggr.rst @@ -5,28 +5,28 @@ Torflow measurements aggregation From Torflow's README.spec.txt (section 2.2):: - In this way, the resulting network status consensus bandwidth values # NOQA - are effectively re-weighted proportional to how much faster the node # NOQA + In this way, the resulting network status consensus bandwidth values + are effectively re-weighted proportional to how much faster the node was as compared to the rest of the network. The variables and steps used in Torflow: **strm_bw**:: - The strm_bw field is the average (mean) of all the streams for the relay # NOQA + The strm_bw field is the average (mean) of all the streams for the relay identified by the fingerprint field. strm_bw = sum(bw stream x)/|n stream| **filt_bw**:: - The filt_bw field is computed similarly, but only the streams equal to # NOQA - or greater than the strm_bw are counted in order to filter very slow # NOQA + The filt_bw field is computed similarly, but only the streams equal to + or greater than the strm_bw are counted in order to filter very slow streams due to slow node pairings. **filt_sbw and strm_sbw**:: for rs in RouterStats.query.filter(stats_clause).\ - options(eagerload_all('router.streams.circuit.routers')).all(): # NOQA + options(eagerload_all('router.streams.circuit.routers')).all(): tot_sbw = 0 sbw_cnt = 0 for s in rs.router.streams: @@ -48,13 +48,13 @@ The variables and steps used in Torflow: **filt_avg, and strm_avg**:: - Once we have determined the most recent measurements for each node, we # NOQA - compute an average of the filt_bw fields over all nodes we have measured. # NOQA + Once we have determined the most recent measurements for each node, we + compute an average of the filt_bw fields over all nodes we have measured. :: - filt_avg = sum(map(lambda n: n.filt_bw, nodes.itervalues()))/float(len(nodes)) # NOQA - strm_avg = sum(map(lambda n: n.strm_bw, nodes.itervalues()))/float(len(nodes)) # NOQA + filt_avg = sum(map(lambda n: n.filt_bw, nodes.itervalues()))/float(len(nodes)) + strm_avg = sum(map(lambda n: n.strm_bw, nodes.itervalues()))/float(len(nodes)) **true_filt_avg and true_strm_avg**:: @@ -72,7 +72,7 @@ In the non-pid case, all types of nodes get the same avg **n.ratio**:: - These averages are used to produce ratios for each node by dividing the # NOQA + These averages are used to produce ratios for each node by dividing the measured value for that node by the network average. :: @@ -91,15 +91,15 @@ It is the minimum of all the descriptor bandwidth values:: bw_observed = min(bws) return Router(ns.idhex, ns.nickname, bw_observed, dead, exitpolicy, - ns.flags, ip, version, os, uptime, published, contact, rate_limited, # NOQA + ns.flags, ip, version, os, uptime, published, contact, rate_limited, ns.orhash, ns.bandwidth, extra_info_digest, ns.unmeasured) self.desc_bw = max(bw,1) # Avoid div by 0 **new_bw**:: - These ratios are then multiplied by the most recent observed descriptor # NOQA - bandwidth we have available for each node, to produce a new value for # NOQA + These ratios are then multiplied by the most recent observed descriptor + bandwidth we have available for each node, to produce a new value for the network status consensus process. :: @@ -115,7 +115,7 @@ The descriptor observed bandwidth is multiplied by the ratio. :: if n.new_bw > tot_net_bw*NODE_CAP: - plog("INFO", "Clipping extremely fast "+n.node_class()+" node "+n.idhex+"="+n.nick+ # NOQA + plog("INFO", "Clipping extremely fast "+n.node_class()+" node "+n.idhex+"="+n.nick+ " at "+str(100*NODE_CAP)+"% of network capacity ("+ str(n.new_bw)+"->"+str(int(tot_net_bw*NODE_CAP))+") "+ " pid_error="+str(n.pid_error)+ diff --git a/sbws/lib/v3bwfile.py b/sbws/lib/v3bwfile.py index 56925cb..a585bb7 100644 --- a/sbws/lib/v3bwfile.py +++ b/sbws/lib/v3bwfile.py @@ -1207,152 +1207,7 @@ class V3BWFile(object): Obtain final bandwidth measurements applying Torflow's scaling method. - From Torflow's README.spec.txt (section 2.2):: - - In this way, the resulting network status consensus bandwidth values # NOQA - are effectively re-weighted proportional to how much faster the node # NOQA - was as compared to the rest of the network. - - The variables and steps used in Torflow: - - **strm_bw**:: - - The strm_bw field is the average (mean) of all the streams for the relay # NOQA - identified by the fingerprint field. - strm_bw = sum(bw stream x)/|n stream| - - **filt_bw**:: - - The filt_bw field is computed similarly, but only the streams equal to # NOQA - or greater than the strm_bw are counted in order to filter very slow # NOQA - streams due to slow node pairings. - - **filt_sbw and strm_sbw**:: - - for rs in RouterStats.query.filter(stats_clause).\ - options(eagerload_all('router.streams.circuit.routers')).all(): # NOQA - tot_sbw = 0 - sbw_cnt = 0 - for s in rs.router.streams: - if isinstance(s, ClosedStream): - skip = False - #for br in badrouters: - # if br != rs: - # if br.router in s.circuit.routers: - # skip = True - if not skip: - # Throw out outliers < mean - # (too much variance for stddev to filter much) - if rs.strm_closed == 1 or s.bandwidth() >= rs.sbw: - tot_sbw += s.bandwidth() - sbw_cnt += 1 - - if sbw_cnt: rs.filt_sbw = tot_sbw/sbw_cnt - else: rs.filt_sbw = None - - **filt_avg, and strm_avg**:: - - Once we have determined the most recent measurements for each node, we # NOQA - compute an average of the filt_bw fields over all nodes we have measured. # NOQA - - :: - - filt_avg = sum(map(lambda n: n.filt_bw, nodes.itervalues()))/float(len(nodes)) # NOQA - strm_avg = sum(map(lambda n: n.strm_bw, nodes.itervalues()))/float(len(nodes)) # NOQA - - **true_filt_avg and true_strm_avg**:: - - for cl in ["Guard+Exit", "Guard", "Exit", "Middle"]: - true_filt_avg[cl] = filt_avg - true_strm_avg[cl] = strm_avg - - In the non-pid case, all types of nodes get the same avg - - **n.fbw_ratio and n.fsw_ratio**:: - - for n in nodes.itervalues(): - n.fbw_ratio = n.filt_bw/true_filt_avg[n.node_class()] - n.sbw_ratio = n.strm_bw/true_strm_avg[n.node_class()] - - **n.ratio**:: - - These averages are used to produce ratios for each node by dividing the # NOQA - measured value for that node by the network average. - - :: - - # Choose the larger between sbw and fbw - if n.sbw_ratio > n.fbw_ratio: - n.ratio = n.sbw_ratio - else: - n.ratio = n.fbw_ratio - - **desc_bw**: - - It is the minimum of all the descriptor bandwidth values:: - - bws = map(int, g) - bw_observed = min(bws) - - return Router(ns.idhex, ns.nickname, bw_observed, dead, exitpolicy, - ns.flags, ip, version, os, uptime, published, contact, rate_limited, # NOQA - ns.orhash, ns.bandwidth, extra_info_digest, ns.unmeasured) - - self.desc_bw = max(bw,1) # Avoid div by 0 - - **new_bw**:: - - These ratios are then multiplied by the most recent observed descriptor # NOQA - bandwidth we have available for each node, to produce a new value for # NOQA - the network status consensus process. - - :: - - n.new_bw = n.desc_bw*n.ratio - - The descriptor observed bandwidth is multiplied by the ratio. - - **Limit the bandwidth to a maximum**:: - - NODE_CAP = 0.05 - - :: - - if n.new_bw > tot_net_bw*NODE_CAP: - plog("INFO", "Clipping extremely fast "+n.node_class()+" node "+n.idhex+"="+n.nick+ # NOQA - " at "+str(100*NODE_CAP)+"% of network capacity ("+ - str(n.new_bw)+"->"+str(int(tot_net_bw*NODE_CAP))+") "+ - " pid_error="+str(n.pid_error)+ - " pid_error_sum="+str(n.pid_error_sum)) - n.new_bw = int(tot_net_bw*NODE_CAP) - - However, tot_net_bw does not seems to be updated when not using pid. - This clipping would make faster relays to all have the same value. - - All of that can be expressed as: - - .. math:: - - bwn_i =& min\\left(bwnew_i, - \\sum_{i=1}^{n}bwnew_i \\times 0.05\\right) \\ - - &= min\\left( - \\left(min\\left(bwobs_i, bwavg_i, bwbur_i \\right) \\times r_i\\right), - \\sum_{i=1}^{n}\\left(min\\left(bwobs_i, bwavg_i, bwbur_i \\right) \\times r_i\\right) - \\times 0.05\\right)\\ - - &= min\\left( - \\left(min\\left(bwobs_i, bwavg_i, bwbur_i \\right) \\times max\\left(rf_i, rs_i\\right)\\right), - \\sum_{i=1}^{n}\\left(min\\left(bwobs_i, bwavg_i, bwbur_i \\right) \\times - max\\left(rf_i, rs_i\\right)\\right) \\times 0.05\\right)\\ - - &= min\\left( - \\left(min\\left(bwobs_i, bwavg_i, bwbur_i \\right) \\times max\\left(\\frac{bwfilt_i}{bwfilt}, - \\frac{bw_i}{bwstrm}\\right)\\right), - \\sum_{i=1}^{n}\\left(min\\left(bwobs_i, bwavg_i, bwbur_i \\right) \\times - max\\left(\\frac{bwfilt_i}{bwfilt}, - \\frac{bw_i}{bwstrm}\\right)\\right) \\times 0.05\\right) - + See details in :ref:`torflow_aggr`. """ log.info("Calculating relays' bandwidth using Torflow method.") bw_lines_tf = copy.deepcopy(bw_lines)

1 0

[sbws/maint-1.1] Merge branch 'maint-1.1_bug33871_scaling_03' into 'maint-1.1'
by juga＠torproject.org 29 Jun '20

29 Jun '20

commit 02861e103119b17821e78fcacbcfdf24f568ec69 Merge: 3033421 ce0449a Author: Georg Koppen <gk(a)torproject.org> Date: Mon Jun 15 07:14:43 2020 +0000 Merge branch 'maint-1.1_bug33871_scaling_03' into 'maint-1.1' Maint 1.1 bug33871 scaling 03 See merge request tpo/network-health/sbws!9 docs/source/index.rst | 1 + docs/source/torflow_aggr.rst | 429 +++++++++++++++++++++ sbws/lib/bwfile_health.py | 2 + sbws/lib/scaling.py | 19 + sbws/lib/v3bwfile.py | 386 ++++++++---------- tests/conftest.py | 1 + tests/unit/lib/data/results_0_consensus_bw.txt | 1 + tests/unit/lib/data/results_no_consensus_bw.txt | 1 + tests/unit/lib/data/results_no_desc_bw_avg.txt | 1 + tests/unit/lib/data/results_no_desc_bw_avg_obs.txt | 1 + tests/unit/lib/data/results_no_desc_bw_obs.txt | 1 + tests/unit/lib/test_scaling.py | 13 + tests/unit/lib/test_v3bwfile.py | 49 ++- 13 files changed, 680 insertions(+), 225 deletions(-)

1 0

[sbws/maint-1.1] fix: v3bwfile: linter error with new flake version
by juga＠torproject.org 29 Jun '20

29 Jun '20

commit ce0449a2efa4e341abb2bb985972423f878f0ef6 Author: juga0 <juga(a)riseup.net> Date: Wed May 20 15:39:46 2020 +0000 fix: v3bwfile: linter error with new flake version --- sbws/lib/bwfile_health.py | 2 ++ sbws/lib/v3bwfile.py | 2 ++ 2 files changed, 4 insertions(+) diff --git a/sbws/lib/bwfile_health.py b/sbws/lib/bwfile_health.py index 793e08e..95d37ee 100644 --- a/sbws/lib/bwfile_health.py +++ b/sbws/lib/bwfile_health.py @@ -1,4 +1,6 @@ """Expected bandwidth file values for KeyValues.""" +# flake8: noqa: E741 +# (E741 ambiguous variable name), when using l. import logging from stem import descriptor diff --git a/sbws/lib/v3bwfile.py b/sbws/lib/v3bwfile.py index a585bb7..071dc94 100644 --- a/sbws/lib/v3bwfile.py +++ b/sbws/lib/v3bwfile.py @@ -1,6 +1,8 @@ # -*- coding: utf-8 -*- """Classes and functions that create the bandwidth measurements document (v3bw) used by bandwidth authorities.""" +# flake8: noqa: E741 +# (E741 ambiguous variable name), when using l. import copy import logging

1 0

[sbws/maint-1.1] fix: doc: Update/clarify Torflow aggregation
by juga＠torproject.org 29 Jun '20

29 Jun '20

commit 5a44410af282b3193298518783e492e1a3cdae4b Author: juga0 <juga(a)riseup.net> Date: Wed May 20 13:21:23 2020 +0000 fix: doc: Update/clarify Torflow aggregation --- docs/source/torflow_aggr.rst | 351 ++++++++++++++++++++++++++++++++++++------- 1 file changed, 297 insertions(+), 54 deletions(-) diff --git a/docs/source/torflow_aggr.rst b/docs/source/torflow_aggr.rst index 49441b4..10b12a8 100644 --- a/docs/source/torflow_aggr.rst +++ b/docs/source/torflow_aggr.rst @@ -3,27 +3,34 @@ Torflow measurements aggregation ================================== -From Torflow's README.spec.txt (section 2.2):: +Torflow aggregation or scaling goal is: + +From Torflow's `README.spec.txt`_ (section 2.2):: In this way, the resulting network status consensus bandwidth values are effectively re-weighted proportional to how much faster the node was as compared to the rest of the network. -The variables and steps used in Torflow: +With and without PID control +---------------------------- + +Per relay measurements' bandwidth +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -**strm_bw**:: +They are calculated in the same way whether or not `PID controller`_ feedback +is used. + +From Torflow's `README.spec.txt`_ (section 1.6):: The strm_bw field is the average (mean) of all the streams for the relay identified by the fingerprint field. - strm_bw = sum(bw stream x)/|n stream| - -**filt_bw**:: The filt_bw field is computed similarly, but only the streams equal to or greater than the strm_bw are counted in order to filter very slow streams due to slow node pairings. -**filt_sbw and strm_sbw**:: +In the code, `SQLSupport.py`_, ``strm_bw`` is ``sbw`` and +``filt_bw`` is ``filt_sbws``:: for rs in RouterStats.query.filter(stats_clause).\ options(eagerload_all('router.streams.circuit.routers')).all(): @@ -46,36 +53,73 @@ The variables and steps used in Torflow: if sbw_cnt: rs.filt_sbw = tot_sbw/sbw_cnt else: rs.filt_sbw = None -**filt_avg, and strm_avg**:: +This is also expressed in pseudocode in the `bandwidth file spec`_, section B.4 +step 1. + +Calling ``bw_i`` to ``strm_bw`` and ``bwfilt_i`` to ``filt_bw``, +if ``bw_j`` is a measurement for a relay ``i`` and ``m`` is the number of +measurements for that relay, then: + +.. math:: + + bw_i = \mu(bw_j) = \frac{\sum_{j=1}^{m}bw_j}{m} + +.. math:: + + bwfilt_i &= \mu(max(\mu(bw_j), bw_j)) + = \frac{\sum_{j=1}^{m} max\left(\frac{\sum_{j=1}^{m}bw_j}{m}, bw_j\right)}{m} + +Network measurements' bandwidth average +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +From `README.spec.txt`_ (section 2.1):: Once we have determined the most recent measurements for each node, we compute an average of the filt_bw fields over all nodes we have measured. -:: +In Torflow's `aggregate.py`_ code:: filt_avg = sum(map(lambda n: n.filt_bw, nodes.itervalues()))/float(len(nodes)) strm_avg = sum(map(lambda n: n.strm_bw, nodes.itervalues()))/float(len(nodes)) -**true_filt_avg and true_strm_avg**:: +Both in the code with PID and without, all types of nodes get the same +average. - for cl in ["Guard+Exit", "Guard", "Exit", "Middle"]: - true_filt_avg[cl] = filt_avg - true_strm_avg[cl] = strm_avg +This is also expressed in pseudocode in the `bandwidth file spec`_, section B.4 +step 2. -In the non-pid case, all types of nodes get the same avg +Calling ``bwstrm`` to ``strm_avg`` and ``bwfilt`` to ``fitl_avg``, if ``n`` is +the number of relays in the network, then: -**n.fbw_ratio and n.fsw_ratio**:: +.. math:: + + bwstrm &= \mu(bw_i) + = \frac{\sum_{i=1}^{n}bw_i}{n} + = \frac{\sum_{i=1}^{n} \frac{\sum_{j=1}^{m}bw_j}{m} }{n} + +.. math:: + + bwfilt &= \mu(bwfilt_i) + = \frac{\sum_{i=1}^{n}bwfilt_i}{n} + = \frac{\sum_{i=1}^{n}\frac{\sum_{j=1}^{m}max(\mu(bw_j), bw_j)}{m}}{n} + = \frac{\sum_{i=1}^{n}\frac{\sum_{j=1}^{m}max\left(\frac{\sum_{j=1}^{m}bw_j}{m}, bw_j\right)}{m}}{n} - for n in nodes.itervalues(): - n.fbw_ratio = n.filt_bw/true_filt_avg[n.node_class()] - n.sbw_ratio = n.strm_bw/true_strm_avg[n.node_class()] -**n.ratio**:: +Per relay bandwidth ratio +~~~~~~~~~~~~~~~~~~~~~~~~~ + +From `README.spec.txt`_ (section 2.2):: These averages are used to produce ratios for each node by dividing the measured value for that node by the network average. -:: +In Torflow's `aggregate.py`_ code:: + + for n in nodes.itervalues(): + n.fbw_ratio = n.filt_bw/true_filt_avg[n.node_class()] + n.sbw_ratio = n.strm_bw/true_strm_avg[n.node_class()] + + [snip] # Choose the larger between sbw and fbw if n.sbw_ratio > n.fbw_ratio: @@ -83,68 +127,267 @@ In the non-pid case, all types of nodes get the same avg else: n.ratio = n.fbw_ratio -**desc_bw**: +This is also expressed in pseudocode in the `bandwidth file spec`_, section B.4 +step 2 and 3. -It is the minimum of all the descriptor bandwidth values:: +Calling ``rf_i`` to ``fbw_ratio`` and ``rs_i`` to ``sbw_ration`` and ``r_i`` +to ``ratio``: + +.. math:: + + rf_i = \frac{bwfilt_i}{bwfilt} + + rs_i = \frac{bw_i}{bwstrm} + + +.. math:: + + r_i = max(rf_i, rs_i) + = max\left(\frac{bwfilt_i}{bwfilt}, \frac{bw_i}{bwstrm}\right) + = max\left(\frac{bwfilt_i}{\mu(bwfilt_i)}, \frac{bw_i}{\mu(bwfilt_i)}\right) + +Per relay descriptors bandwidth +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +From `TorCtl.py`_ code, it is the minimum of all the descriptor bandwidth +values:: bws = map(int, g) bw_observed = min(bws) + [snip] + return Router(ns.idhex, ns.nickname, bw_observed, dead, exitpolicy, ns.flags, ip, version, os, uptime, published, contact, rate_limited, ns.orhash, ns.bandwidth, extra_info_digest, ns.unmeasured) +Because of the matched regular expression, ``bws`` is **not** all the descriptor +bandwidth values, but the observed bandwidth and the burst bandwidth, ie., it +does not take the average bandwidth, what seems to be a bug in Torflow. + +This is passed to ``Router``, in which the consensus bandwidth is assigned to the +descriptor bandwidth when there is no consensus bandwidth:: + + (idhex, name, bw, down, exitpolicy, flags, ip, version, os, uptime, + published, contact, rate_limited, orhash, + ns_bandwidth,extra_info_digest,unmeasured) = args + + [snip] + + if ns_bandwidth != None: + self.bw = max(ns_bandwidth,1) # Avoid div by 0 + else: + self.bw = max(bw,1) # Avoid div by 0 + + [snip] + self.desc_bw = max(bw,1) # Avoid div by 0 -**new_bw**:: +And written by `SQLSupport.py`_ as descriptor and conensus bandwidth:: + + f.write(" desc_bw="+str(int(cvt(s.avg_desc_bw,0)))) + f.write(" ns_bw="+str(int(cvt(s.avg_bw,0)))+"\n") + +Without PID control +------------------- + +Per relay scaled bandwidth +~~~~~~~~~~~~~~~~~~~~~~~~~~ + +From `README.spec.txt`_ (section 2.2):: These ratios are then multiplied by the most recent observed descriptor bandwidth we have available for each node, to produce a new value for the network status consensus process. -:: +In `aggregate.py`_ code:: n.new_bw = n.desc_bw*n.ratio -The descriptor observed bandwidth is multiplied by the ratio. +This is also expressed in pseudocode in the `bandwidth file spec`_, section B.4 +step 5. + +Calling ``bwnew_i`` to ``new_bw`` and ``descbw_i`` to ``use_bw``: + +.. math:: + + descbw_i = min\left(bwobs_i, bwavg_i, bwburst_i, measuredconsensusbw_i \right) + + bwnew_i =& descbw_i \times r_i \ + + &= min\left(bwobs_i, bwavg_i, bwburst_i, measuredconsensusbw_i \right) \times max(rf_i, rs_i) \ -**Limit the bandwidth to a maximum**:: + &= min\left(bwobs_i, bwavg_i, bwburst_i, measuredconsensusbw_i \right) \times max\left(\frac{bwfilt_i}{bwfilt}, \frac{bw_i}{bwstrm}\right) \ + + &= min\left(bwobs_i, bwavg_i, bwburst_i, measuredconsensusbw_i \right) \times max\left(\frac{bwfilt_i}{\mu(bwfilt_i)}, \frac{bw_i}{\mu(bw_i)}\right) + + +With PID control +---------------- + +Per relay descriptors bandwidth +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +Even though `README.spec.txt`_ talks about the consensus bandwidth, in +`aggregate.py`_ code, the consensus bandwidth is never used, since +``use_desc_bw`` is initialized to True and never changed:: + + self.use_desc_bw = True + + [snip] + + if cs_junk.bwauth_pid_control: + if cs_junk.use_desc_bw: + n.use_bw = n.desc_bw + else: + n.use_bw = n.ns_bw + +Per relay scaled bandwidth +~~~~~~~~~~~~~~~~~~~~~~~~~~ + +From `README.spec.txt`_ section 3.1:: + + The bandwidth authorities measure F_node: the filtered stream + capacity through a given node (filtering is described in Section 1.6). + + [snip] + + pid_error = e(t) = (F_node - F_avg)/F_avg. + + [snip] + + new_consensus_bw = old_consensus_bw + + old_consensus_bw * K_p * e(t) + + old_consensus_bw * K_i * \integral{e(t)} + + old_consensus_bw * K_d * \derivative{e(t)} + + [snip] + + For the case where K_p = 1, K_i=0, and K_d=0, it can be seen that this + system is equivalent to the one defined in 2.2, except using consensus + bandwidth instead of descriptor bandwidth: + + new_bw = old_bw + old_bw*e(t) + new_bw = old_bw + old_bw*(F_node/F_avg - 1) + new_bw = old_bw*F_node/F_avg + new_bw = old_bw*ratio + +In Torflow's code, this is actually the case and most of the code is not +executed because the default ``K`` values. + +It seems then that ``F_node`` is ``filt_bw`` in Torflow's code or ``bwfilt_i`` +here, and ``F_avg`` is ``filt_avg`` in Torflow's code or ``bwfilt`` here. + +In `aggregate.py`_ code, pid error also depends on which of the ratios is +greater:: + + if cs_junk.use_best_ratio and n.sbw_ratio > n.fbw_ratio: + n.pid_error = (n.strm_bw - true_strm_avg[n.node_class()]) \ + / true_strm_avg[n.node_class()] + else: + n.pid_error = (n.filt_bw - true_filt_avg[n.node_class()]) \ + / true_filt_avg[n.node_class()] + + [snip] + + n.new_bw = n.use_bw + cs_junk.K_p*n.use_bw*n.pid_error + +Calling ``e_i`` to ``pid_error``, in the case that ``rs_i`` > ``rf_i``: + +.. math:: + + e_i = \frac{bw_i - bwstrm}{bwstrm} = \frac{bw_i}{bwstrm} - 1 + + bwn_i = descbw_i + descbw_i \times e_i = descbw_i \times (1 + e_i) + = descbw_i \times (1 + \frac{bw_i}{bwstrm} - 1) + = descbw_i \times \frac{bw_i}{bwstrm} = descbw_i \times rs_i + +And in the case that ``rs_i`` < ``rf_i``: + +.. math:: + + e_i = \frac{bwfilt_i - bwfilt}{bwfilt} = \frac{bwfilt_i}{bwfilt} - 1 + + bwn_i = descbw_i + descbw_i \times e_i = descbw_i \times (1 + e_i) + = descbw_i \times (1 + \frac{bwfilt_i}{bwfilt} - 1) + = descbw_i \times \frac{bwfilt_i}{bwfilt} = descbw_i \times rf_i + +So, it is the same as the scaled bandwidth in the case without PID controller, +ie.: + +.. math:: + + bwn_i = descbw_i \times max(rf_i, rs_i) + +With and without PID control +---------------------------- + +Per relay scaled bandwidth limit +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +Once each relay bandwidth is scaled, it is limited to a maximum, that is +calculated as the sum of all the relays in the current consensus scaled +bandwidth per 0.05. + +From `aggregate.py`_ code:: NODE_CAP = 0.05 -:: + [snip] + + if n.idhex in prev_consensus: + if prev_consensus[n.idhex].bandwidth != None: + prev_consensus[n.idhex].measured = True + tot_net_bw += n.new_bw + + [snip] if n.new_bw > tot_net_bw*NODE_CAP: - plog("INFO", "Clipping extremely fast "+n.node_class()+" node "+n.idhex+"="+n.nick+ - " at "+str(100*NODE_CAP)+"% of network capacity ("+ - str(n.new_bw)+"->"+str(int(tot_net_bw*NODE_CAP))+") "+ - " pid_error="+str(n.pid_error)+ - " pid_error_sum="+str(n.pid_error_sum)) + [snip] n.new_bw = int(tot_net_bw*NODE_CAP) -However, tot_net_bw does not seems to be updated when not using pid. -This clipping would make faster relays to all have the same value. -All of that can be expressed as: +.. math:: + + bwn_i =& min\left(bwnew_i, + \sum_{i=1}^{n}bwnew_i \times 0.05\right) \ + + &= min\left( + \left(min\left(bwobs_i, bwavg_i, bwburst_i, measuredconsensusbw_i \right) \times r_i\right), + \sum_{i=1}^{n}\left(min\left(bwobs_i, bwavg_i, bwburst_i, measuredconsensusbw_i \right) \times r_i\right) + \times 0.05\right)\ + + &= min\left( + \left(min\left(bwobs_i, bwavg_i, bwburst_i, measuredconsensusbw_i \right) \times max\left(rf_i, rs_i\right)\right), + \sum_{i=1}^{n}\left(min\left(bwobs_i, bwavg_i, bwburst_i, measuredconsensusbw_i \right) \times + max\left(rf_i, rs_i\right)\right) \times 0.05\right)\ + + &= min\left( + \left(min\left(bwobs_i, bwavg_i, bwburst_i, measuredconsensusbw_i \right) \times max\left(\frac{bwfilt_i}{bwfilt}, + \frac{bw_i}{bwstrm}\right)\right), + \sum_{i=1}^{n}\left(min\left(bwobs_i, bwavg_i, bwburst_i, measuredconsensusbw_i \right) \times + max\left(\frac{bwfilt_i}{bwfilt}, + \frac{bw_i}{bwstrm}\right)\right) \times 0.05\right) .. math:: - bwn_i =& min\\left(bwnew_i, - \\sum_{i=1}^{n}bwnew_i \\times 0.05\\right) \\ - - &= min\\left( - \\left(min\\left(bwobs_i, bwavg_i, bwbur_i \\right) \\times r_i\\right), - \\sum_{i=1}^{n}\\left(min\\left(bwobs_i, bwavg_i, bwbur_i \\right) \\times r_i\\right) - \\times 0.05\\right)\\ - - &= min\\left( - \\left(min\\left(bwobs_i, bwavg_i, bwbur_i \\right) \\times max\\left(rf_i, rs_i\\right)\\right), - \\sum_{i=1}^{n}\\left(min\\left(bwobs_i, bwavg_i, bwbur_i \\right) \\times - max\\left(rf_i, rs_i\\right)\\right) \\times 0.05\\right)\\ - - &= min\\left( - \\left(min\\left(bwobs_i, bwavg_i, bwbur_i \\right) \\times max\\left(\\frac{bwfilt_i}{bwfilt}, - \\frac{bw_i}{bwstrm}\\right)\\right), - \\sum_{i=1}^{n}\\left(min\\left(bwobs_i, bwavg_i, bwbur_i \\right) \\times - max\\left(\\frac{bwfilt_i}{bwfilt}, - \\frac{bw_i}{bwstrm}\\right)\\right) \\times 0.05\\right) + bwn_i = min\left( + \left(min\left(bwobs_i, bwavg_i, bwburst_i, measuredconsensusbw_i \right) \times max\left(\frac{bwfilt_i}{bwfilt}, + \frac{bw_i}{bwstrm}\right)\right), + \sum_{i=1}^{n}\left(min\left(bwobs_i, bwavg_i, bwburst_i, measuredconsensusbw_i \right) \times + max\left(\frac{bwfilt_i}{bwfilt}, + \frac{bw_i}{bwstrm}\right)\right) \times 0.05\right) + + +Per relay scaled bandwidth rounding +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +Finally, the new scaled bandwidth is expressed in kilobytes and rounded a number +of digits. + +.. _README.spec.txt: https://gitweb.torproject.org/torflow.git/tree/NetworkScanners/BwAuthority/… +.. _PID Controller: https://en.wikipedia.org/wiki/PID_controller +.. _SQLSupport.py: https://gitweb.torproject.org/pytorctl.git/tree/SQLSupport.py#n493 +.. _bandwidth file spec: https://gitweb.torproject.org/torspec.git/tree/bandwidth-file-spec.txt +.. _aggregate.py: https://gitweb.torproject.org/torflow.git/tree/NetworkScanners/BwAuthority/… +.. _TorCtly.py: https://gitweb.torproject.org/pytorctl.git/tree/TorCtl.py

1 0

[sbws/maint-1.1] chg: scaling: Add filtered bandwidth function
by juga＠torproject.org 29 Jun '20

29 Jun '20

commit 5159662a50b6ae97588e87423d6c56a9014ff91f Author: juga0 <juga(a)riseup.net> Date: Sat May 16 17:07:19 2020 +0000 chg: scaling: Add filtered bandwidth function to calculate the filtered bandwidth for each relay. --- sbws/lib/scaling.py | 19 +++++++++++++++++++ 1 file changed, 19 insertions(+) diff --git a/sbws/lib/scaling.py b/sbws/lib/scaling.py new file mode 100644 index 0000000..0fc3f84 --- /dev/null +++ b/sbws/lib/scaling.py @@ -0,0 +1,19 @@ +from statistics import mean + + +def bw_measurements_from_results(results): + return [ + dl['amount'] / dl['duration'] + for r in results for dl in r.downloads + ] + + +def bw_filt(bw_measurements): + """Filtered bandwidth for a relay. + + It is the equivalent to Torflow's ``filt_sbw``. + ``mu`` in this function is the equivalent to Torflow's ``sbw``. + """ + mu = mean(bw_measurements) + bws_gte_mean = filter(lambda bw: bw >= mu, bw_measurements) + return mean(bws_gte_mean)

1 0

[sbws/maint-1.1] chg: v3bwfile: Calculate filtered bandwidth
by juga＠torproject.org 29 Jun '20

29 Jun '20

commit c030731ec25adeff750c8c00415b87521a10d581 Author: juga0 <juga(a)riseup.net> Date: Sat May 16 17:55:50 2020 +0000 chg: v3bwfile: Calculate filtered bandwidth for each relay, calculate the filtered mean for all relays and calculate the filtered ratio for each relay. --- sbws/lib/v3bwfile.py | 14 +++++++++++--- tests/unit/lib/test_scaling.py | 13 +++++++++++++ 2 files changed, 24 insertions(+), 3 deletions(-) diff --git a/sbws/lib/v3bwfile.py b/sbws/lib/v3bwfile.py index 245ffa6..9a303be 100644 --- a/sbws/lib/v3bwfile.py +++ b/sbws/lib/v3bwfile.py @@ -15,6 +15,7 @@ from sbws.globals import (SPEC_VERSION, BW_LINE_SIZE, SBWS_SCALE_CONSTANT, TORFLOW_SCALING, SBWS_SCALING, TORFLOW_BW_MARGIN, TORFLOW_OBS_LAST, TORFLOW_OBS_MEAN, PROP276_ROUND_DIG, MIN_REPORT, MAX_BW_DIFF_PERC) +from sbws.lib import scaling from sbws.lib.resultdump import ResultSuccess, _ResultType from sbws.util.filelock import DirectoryLock from sbws.util.timestamp import (now_isodt_str, unixts_to_isodt_str, @@ -631,8 +632,10 @@ class V3BWLine(object): assert node_id.startswith('$') self.node_id = node_id self.bw = bw + # For now, we do not want to add ``bw_filt`` to the bandwidth file, + # therefore it is set here but not added to ``BWLINE_KEYS_V1``. [setattr(self, k, v) for k, v in kwargs.items() - if k in BWLINE_KEYS_V1] + if k in BWLINE_KEYS_V1 + ["bw_filt"]] def __str__(self): return self.bw_strv1 @@ -762,7 +765,11 @@ class V3BWLine(object): if rtt: kwargs['rtt'] = rtt bw = cls.bw_median_from_results(results_recent) + # XXX: all the class functions could use the bw_measurements instead of + # obtaining them each time or use a class Measurements. + bw_measurements = scaling.bw_measurements_from_results(results_recent) kwargs['bw_mean'] = cls.bw_mean_from_results(results_recent) + kwargs['bw_filt'] = scaling.bw_filt(bw_measurements) kwargs['bw_median'] = cls.bw_median_from_results( results_recent) kwargs['desc_bw_avg'] = \ @@ -1311,7 +1318,8 @@ class V3BWFile(object): # mean (Torflow's strm_avg) mu = mean([l.bw_mean for l in bw_lines]) # filtered mean (Torflow's filt_avg) - muf = mean([max(l.bw_mean, mu) for l in bw_lines]) + muf = mean([l.bw_filt for l in bw_lines]) + # bw sum (Torflow's tot_net_bw or tot_sbw) sum_bw = sum([l.bw_mean for l in bw_lines]) # Torflow's clipping @@ -1369,7 +1377,7 @@ class V3BWFile(object): min_bandwidth = min(desc_bw, l.consensus_bandwidth) # Torflow's scaling ratio_stream = l.bw_mean / mu - ratio_stream_filtered = max(l.bw_mean, mu) / muf + ratio_stream_filtered = l.bw_filt / muf ratio = max(ratio_stream, ratio_stream_filtered) bw_scaled = ratio * min_bandwidth # round and convert to KB diff --git a/tests/unit/lib/test_scaling.py b/tests/unit/lib/test_scaling.py new file mode 100644 index 0000000..06fb71b --- /dev/null +++ b/tests/unit/lib/test_scaling.py @@ -0,0 +1,13 @@ +"""Unit tests for scaling.py.""" + +from sbws.lib import scaling + + +def test_bw_filt(): + bw_measurements = [ + 96700.00922329757, 70311.63051659254, 45531.743347556374, + 38913.97025485627, 55656.332364676025 + ] + fb = scaling.bw_filt(bw_measurements) + # This is greater than the mean, that is 61422.73714139576 + assert fb == 83505.81986994506

1 0