February 2021 - tor-commits - lists.torproject.org

[torspec/master] Update path-spec.txt for CBT estimator fixes for #40168.
by asn＠torproject.org 19 Feb '21

19 Feb '21

commit df031d7bf33f68948b2c915d681b08ca59c1da37 Author: Mike Perry <mikeperry-git(a)torproject.org> Date: Tue Nov 3 16:28:52 2020 -0600 Update path-spec.txt for CBT estimator fixes for #40168. Also clarify and improve wording of the timeout calculation section. --- path-spec.txt | 202 ++++++++++++++++++++++++++++++++++------------------------ 1 file changed, 117 insertions(+), 85 deletions(-) diff --git a/path-spec.txt b/path-spec.txt index 483e37d..c16ef50 100644 --- a/path-spec.txt +++ b/path-spec.txt @@ -361,112 +361,147 @@ of their choices. 2.4. Learning when to give up ("timeout") on circuit construction - Since version 0.2.2.8-alpha, Tor attempts to learn when to give up on - circuits based on network conditions. + Since version 0.2.2.8-alpha, Tor clients attempt to learn when to give + up on circuits based on network conditions. -2.4.1. Distribution choice and parameter estimation +2.4.1. Distribution choice Based on studies of build times, we found that the distribution of - circuit build times appears to be a Frechet distribution. However, - estimators and quantile functions of the Frechet distribution are - difficult to work with and slow to converge. So instead, since we - are only interested in the accuracy of the tail, we approximate - the tail of the distribution with a Pareto curve. + circuit build times appears to be a Frechet distribution (and a multi-modal + Frechet distribution, if more than one guard or bridge is used). However, + estimators and quantile functions of the Frechet distribution are difficult + to work with and slow to converge. So instead, since we are only interested + in the accuracy of the tail, clients approximate the tail of the multi-modal + distribution with a single Pareto curve. - We calculate the parameters for a Pareto distribution fitting the data - using the estimators in equation 4 from: - http://portal.acm.org/citation.cfm?id=1647962.1648139 +2.4.2. How much data to record + + From our observations, the minimum number of circuit build times for a + reasonable fit appears to be on the order of 100. However, to keep a + good fit over the long term, clients store 1000 most recent circuit build + times in a circular array. - This is: + The Tor client should build test circuits at a rate of one every 'cbttestfreq' + (10 seconds) until 'cbtmincircs' (100 circuits) are built, with a maximum of + 'cbtmaxopencircs' (default: 10) circuits open at once. This allows a fresh + Tor to have a CircuitBuildTimeout estimated within 30 minutes after install + or network change (see section 2.4.5 below). - alpha_m = s/(ln(U(X)/Xm^n)) + Timeouts are stored on disk in a histogram of 10ms bin width, the same + width used to calculate the Xm value above. This histogram must be shuffled + after being read from disk, to preserve a proper expiration of old values + after restart. - where s is the total number of completed circuits we have seen, and + Thus, some build time resolution is lost during restart. Implementations may + choose a different persistence mechanism than this histogram, but be aware + that build time binning is still needed for parameter estimation. - U(X) = x_max^u * Prod_s{x_i} +2.4.3. Parameter estimation - with x_i as our i-th completed circuit time, x_max as the longest - completed circuit build time we have yet observed, u as the - number of unobserved timeouts that have no exact value recorded, - and n as u+s, the total number of circuits that either timeout or - complete. + Once 'cbtmincircs' build times are recorded, Tor clients update the + distribution parameters and recompute the timeout every circuit completion + (though see section 2.4.5 for when to pause and reset timeout due to + network change or connectivity loss). - Using log laws, we compute this as the sum of logs to avoid - overflow and ln(1.0+epsilon) precision issues: + Tor clients calculate the parameters for a Pareto distribution fitting the + data using the maximum likelihood estimator. For derivation, see: + https://en.wikipedia.org/wiki/Pareto_distribution#Estimation_of_parameters - alpha_m = s/(u*ln(x_max) + Sum_s{ln(x_i)} - n*ln(Xm)) + Because build times are not a true Pareto distribution, we alter how Xm is + computed. In a max likelihood estimator, the mode of the distribution is + used directly as Xm. - This estimator is closely related to the parameters present in: - http://en.wikipedia.org/wiki/Pareto_distribution#Parameter_estimation - except they are adjusted to handle the fact that our samples are - right-censored at the timeout cutoff. + Instead of using the mode of discrete build times directly, Tor clients + compute the Xm parameter using the weighted average of the the midpoints + of the 'cbtnummodes' (10) most frequently occurring 10ms histogram bins. + (The use of 10 modes was found to minimize error from the selected + cbtquantile, with 10ms bins for quantiles 60-80, compared to many other + heuristics). - Additionally, because this is not a true Pareto distribution, we alter - how Xm is computed. The Xm parameter is computed as the midpoint of the most - frequently occurring 50ms histogram bin, until the point where 1000 - circuits are recorded. After this point, the weighted average of the top - 'cbtnummodes' (default: 3) midpoint modes is used as Xm. All times below - this value are counted as having the midpoint value of this weighted average - bin. + To avoid ln(1.0+epsilon) precision issues, use log laws to rewrite the + estimator for 'alpha' as the sum of logs followed by subtraction, rather + than multiplication and division: + + alpha = n/(Sum_n{ln(MAX(Xm, x_i))} - n*ln(Xm)) + + In this, n is the total number of build times that have completed, x_i is + the ith recorded build time, and Xm is the modes of x_i as above. + + All times below Xm are counted as having the Xm value via the MAX(), + because in Pareto estimators, Xm is supposed to be the lowest value. + However, since clients use mode averaging to estimatre Xm, there can be + values below our Xm. Effectively, the Pareto estimator then treats that + everything smaller than Xm happened at Xm. One can also see that if + clients did not do this, alpha could underflow to become negative, which + results in an exponential curve, not a Pareto probability distribution. The timeout itself is calculated by using the Pareto Quantile function (the inverted CDF) to give us the value on the CDF such that 80% of the mass - of the distribution is below the timeout value. + of the distribution is below the timeout value (parameter 'cbtquantile'). - Thus, we expect that the Tor client will accept the fastest 80% of - the total number of paths on the network. + The Pareto Quantile Function (inverse CDF) is: -2.4.2. How much data to record + F(q) = Xm/((1.0-q)^(1.0/alpha)) - From our observations, the minimum number of circuit build times for a - reasonable fit appears to be on the order of 100. However, to keep a - good fit over the long term, we store 1000 most recent circuit build times - in a circular array. + Thus, clients obtain their circuit build timeout by computing: - The Tor client should build test circuits at a rate of one per - minute up until 100 circuits are built. This allows a fresh Tor to have - a CircuitBuildTimeout estimated within 1.5 hours after install, - upgrade, or network change (see below). + timeout_ms = F(0.8) # 'cbtquantile' == 0.8 - Timeouts are stored on disk in a histogram of 50ms bin width, the same - width used to calculate the Xm value above. This histogram must be shuffled - after being read from disk, to preserve a proper expiration of old values - after restart. + With this, we expect that the Tor client will accept the fastest 80% of the + total number of paths on the network. + + Clients obtain the circuit close time to completely abandon circuits as: + + close_ms = F(0.99) # 'cbtclosequantile' == 0.99 + + To avoid waiting an unreasonably long period of time for circuits that + simply have relays that are down, Tor clients cap timeout_ms at the max + build time actually observed so far, and cap close_ms at twice this max, + but at least 60 seconds: -2.4.3. How to record timeouts + timeout_ms = MIN(timeout_ms, max_observed_timeout) + close_ms = MAX(MIN(close_ms, 2*max_observed_timeout), 'cbtinitialtimeout') - Circuits that pass the timeout threshold should be allowed to continue - building until a time corresponding to the point 'cbtclosequantile' - (default 95) on the Pareto curve, or 60 seconds, whichever is greater. +2.4.4. How to record timeouts - The actual completion times for these circuits should be recorded. - Implementations should completely abandon a circuit and record a value - as an 'unknown' timeout if the total build time exceeds this threshold. + Pareto estimators begin to lose their accuracy if the tail is omitted. + Hence, Tor clients actually calculate two timeouts: a usage timeout, and a + close timeout. - The reason for this is that right-censored pareto estimators begin to lose - their accuracy if more than approximately 5% of the values are censored. - Since we wish to set the cutoff at 20%, we must allow circuits to continue - building past this cutoff point up to the 95th percentile. + Circuits that pass the usage timeout are marked as measurement circuits, + and are allowed to continue to build until the close timeout corresponding + to the point 'cbtclosequantile' (default 99) on the Pareto curve, or 60 + seconds, whichever is greater. -2.4.4. Detecting Changing Network Conditions + The actual completion times for these measurements circuits should be + recorded. - We attempt to detect both network connectivity loss and drastic + Implementations should completely abandon a circuit and ignore the circuit + if the total build time exceeds the close threshold. Such closed circuits + should be ignored, as this typically means one of the relays in the path is + offline. + +2.4.5. Detecting Changing Network Conditions + + Tor clients attempt to detect both network connectivity loss and drastic changes in the timeout characteristics. - We assume that we've had network connectivity loss if a circuit - times out and we've received no cells or TLS handshakes since that - circuit began. We then temporarily stop counting timeouts until - network activity resumes. + Clients assume that they have had network connectivity loss if a circuit + times out and have received no cells or TLS handshakes since that + circuit began. Clients then temporarily stop counting timeouts until + network activity resumes (ie: until a TLS handshake completes or a cell + arrives at the client). - To detect changing network conditions, we keep a history of - the timeout or non-timeout status of the past 20 circuits that - successfully completed at least one hop. If more than 90% of - these circuits timeout, we discard all buildtimes history, reset - the timeout to 60, and then begin recomputing the timeout. + To detect changing network conditions, clients keep a history of + the timeout or non-timeout status of the past 'cbtrecentcount' circuits + (20 circuits) that successfully completed at least one hop. If more than + 90% of these circuits timeout, the client discards all buildtimes history, + resets the timeout to 'cbtinitialtimeout' (60 seconds), and then begins + recomputing the timeout. - If the timeout was already 60 or higher, we double the timeout. + If the timeout was already 60 or higher, the client doubles the timeout. -2.4.5. Consensus parameters governing behavior +2.4.6. Consensus parameters governing behavior Clients that implement circuit build timeout learning should obey the following consensus parameters that govern behavior, in order to allow @@ -483,14 +518,13 @@ of their choices. emergency situations only. cbtnummodes - Default: 3 + Default: 10 Min: 1 Max: 20 Effect: This value governs how many modes to use in the weighted - average calculation of Pareto parameter Xm. A value of 3 introduces - some bias (2-5% of CDF) under ideal conditions, but allows for better - performance in the event that a client chooses guard nodes of radically - different performance characteristics. + average calculation of Pareto parameter Xm. Selecting Xm as the + average of multiple modes improves accuracy of the Pareto tail + for quantile cutoffs from 60-80% (see cbtquantile). cbtrecentcount Default: 20 @@ -522,7 +556,7 @@ of their choices. timeout value. It is a percent (10-99). cbtclosequantile - Default: 95 + Default: 99 Min: Value of cbtquantile parameter Max: 99 Effect: This is the position on the quantile curve to use to set the @@ -530,7 +564,7 @@ of their choices. percent (0-99). cbttestfreq - Default: 60 + Default: 10 Min: 1 Max: 2147483647 (INT32_MAX) Effect: Describes how often in seconds to build a test circuit to @@ -538,12 +572,10 @@ of their choices. have been recorded. cbtmintimeout - Default: 2000 - Min: 500 + Default: 10 + Min: 10 Max: 2147483647 (INT32_MAX) Effect: This is the minimum allowed timeout value in milliseconds. - The minimum is to prevent rounding to 0 (we only check once - per second). cbtinitialtimeout Default: 60000

1 0

[tor/master] Raise the circuit close time quantile to 99.
by asn＠torproject.org 19 Feb '21

19 Feb '21

commit c90b0cb6fb4e5fd2dcc1b711f5ee5ca04576646e Author: Mike Perry <mikeperry-git(a)torproject.org> Date: Tue Nov 3 14:28:43 2020 -0600 Raise the circuit close time quantile to 99. This should allow us to more accurately estimate pareto parameters without relying on "right-censorship" of circuit build timeout values. --- src/core/or/circuitstats.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/src/core/or/circuitstats.h b/src/core/or/circuitstats.h index 1cd16b6f2b..e7262e9e82 100644 --- a/src/core/or/circuitstats.h +++ b/src/core/or/circuitstats.h @@ -78,7 +78,7 @@ void circuit_build_times_mark_circ_as_measurement_only(origin_circuit_t *circ); * How long to wait before actually closing circuits that take too long to * build in terms of CDF quantile. */ -#define CBT_DEFAULT_CLOSE_QUANTILE 95 +#define CBT_DEFAULT_CLOSE_QUANTILE 99 #define CBT_MIN_CLOSE_QUANTILE CBT_MIN_QUANTILE_CUTOFF #define CBT_MAX_CLOSE_QUANTILE CBT_MAX_QUANTILE_CUTOFF

1 0

[tor/master] Completely ignore abandoned circs from circ timeout calc
by asn＠torproject.org 19 Feb '21

19 Feb '21

commit 37b21591502d080b5f8ba9c1d0b37bd226b7f183 Author: Mike Perry <mikeperry-git(a)torproject.org> Date: Tue Oct 20 10:50:27 2020 -0500 Completely ignore abandoned circs from circ timeout calc This prevents the timeout curve from getting spread out as much, resulting in more accurate timeout values for quantiles from 60-80. --- src/core/or/circuitstats.c | 64 ++++++++++------------------------------------ src/test/test.c | 10 +------- 2 files changed, 15 insertions(+), 59 deletions(-) diff --git a/src/core/or/circuitstats.c b/src/core/or/circuitstats.c index 2cde21fa1f..d4eb23c966 100644 --- a/src/core/or/circuitstats.c +++ b/src/core/or/circuitstats.c @@ -1009,43 +1009,6 @@ circuit_build_times_shuffle_and_store_array(circuit_build_times_t *cbt, } } -/** - * Filter old synthetic timeouts that were created before the - * new right-censored Pareto calculation was deployed. - * - * Once all clients before 0.2.1.13-alpha are gone, this code - * will be unused. - */ -static int -circuit_build_times_filter_timeouts(circuit_build_times_t *cbt) -{ - int num_filtered=0, i=0; - double timeout_rate = 0; - build_time_t max_timeout = 0; - - timeout_rate = circuit_build_times_timeout_rate(cbt); - max_timeout = (build_time_t)cbt->close_ms; - - for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) { - if (cbt->circuit_build_times[i] > max_timeout) { - build_time_t replaced = cbt->circuit_build_times[i]; - num_filtered++; - cbt->circuit_build_times[i] = CBT_BUILD_ABANDONED; - - log_debug(LD_CIRC, "Replaced timeout %d with %d", replaced, - cbt->circuit_build_times[i]); - } - } - - log_info(LD_CIRC, - "We had %d timeouts out of %d build times, " - "and filtered %d above the max of %u", - (int)(cbt->total_build_times*timeout_rate), - cbt->total_build_times, num_filtered, max_timeout); - - return num_filtered; -} - /** * Load histogram from <b>state</b>, shuffling the resulting array * after we do so. Use this result to estimate parameters and @@ -1171,10 +1134,6 @@ circuit_build_times_parse_state(circuit_build_times_t *cbt, circuit_build_times_set_timeout(cbt); - if (!state->CircuitBuildAbandonedCount && cbt->total_build_times) { - circuit_build_times_filter_timeouts(cbt); - } - done: tor_free(loaded_times); return err ? -1 : 0; @@ -1215,14 +1174,15 @@ circuit_build_times_update_alpha(circuit_build_times_t *cbt) if (x[i] < cbt->Xm) { a += tor_mathlog(cbt->Xm); + n++; } else if (x[i] == CBT_BUILD_ABANDONED) { abandoned_count++; } else { a += tor_mathlog(x[i]); if (x[i] > max_time) max_time = x[i]; + n++; } - n++; } /* @@ -1231,11 +1191,11 @@ circuit_build_times_update_alpha(circuit_build_times_t *cbt) * performs this same check, and resets state if it hits it. If we * hit it at runtime, something serious has gone wrong. */ - if (n!=cbt->total_build_times) { + if (n!=cbt->total_build_times-abandoned_count) { log_err(LD_CIRC, "Discrepancy in build times count: %d vs %d", n, cbt->total_build_times); } - tor_assert(n==cbt->total_build_times); + tor_assert_nonfatal(n==cbt->total_build_times-abandoned_count); if (max_time <= 0) { /* This can happen if Xm is actually the *maximum* value in the set. @@ -1248,13 +1208,17 @@ circuit_build_times_update_alpha(circuit_build_times_t *cbt) return 0; } - a += abandoned_count*tor_mathlog(max_time); - + /* This is the "Maximum Likelihood Estimator" for parameter alpha of a Pareto + * Distribution. See: + * https://en.wikipedia.org/wiki/Pareto_distribution#Estimation_of_parameters + * + * The division in the estimator is done with subtraction outside the ln(), + * with the sum occurring in the for loop above. + * + * This done is to avoid the precision issues of logs of small values. + */ a -= n*tor_mathlog(cbt->Xm); - // Estimator comes from Eq #4 in: - // "Bayesian estimation based on trimmed samples from Pareto populations" - // by Arturo J. Fernández. We are right-censored only. - a = (n-abandoned_count)/a; + a = n/a; cbt->alpha = a; diff --git a/src/test/test.c b/src/test/test.c index 58b468775c..cd21a37409 100644 --- a/src/test/test.c +++ b/src/test/test.c @@ -384,7 +384,6 @@ test_circuit_timeout(void *arg) double timeout1, timeout2; or_state_t *state=NULL; int i, runs; - double close_ms; (void)arg; initialize_periodic_events(); @@ -406,18 +405,11 @@ test_circuit_timeout(void *arg) circuit_build_times_initial_alpha(&initial, CBT_DEFAULT_QUANTILE_CUTOFF/100.0, timeout0); - close_ms = MAX(circuit_build_times_calculate_timeout(&initial, - CBT_DEFAULT_CLOSE_QUANTILE/100.0), - CBT_DEFAULT_TIMEOUT_INITIAL_VALUE); do { for (i=0; i < CBT_DEFAULT_MIN_CIRCUITS_TO_OBSERVE; i++) { build_time_t sample = circuit_build_times_generate_sample(&initial,0,1); - if (sample > close_ms) { - circuit_build_times_add_time(&estimate, CBT_BUILD_ABANDONED); - } else { - circuit_build_times_add_time(&estimate, sample); - } + circuit_build_times_add_time(&estimate, sample); } circuit_build_times_update_alpha(&estimate); timeout1 = circuit_build_times_calculate_timeout(&estimate,

1 0

[tor/master] Lower min circ timeout from 1.5s to bin width (10ms)
by asn＠torproject.org 19 Feb '21

19 Feb '21

commit 761dd9f2ab240fb6ce80087e1c2feecd095d71f9 Author: Mike Perry <mikeperry-git(a)torproject.org> Date: Wed Oct 21 18:17:30 2020 -0500 Lower min circ timeout from 1.5s to bin width (10ms) --- src/core/or/circuitstats.c | 2 +- src/core/or/circuitstats.h | 4 ++-- 2 files changed, 3 insertions(+), 3 deletions(-) diff --git a/src/core/or/circuitstats.c b/src/core/or/circuitstats.c index d4eb23c966..7cc69b3b4c 100644 --- a/src/core/or/circuitstats.c +++ b/src/core/or/circuitstats.c @@ -1794,7 +1794,7 @@ circuit_build_times_set_timeout(circuit_build_times_t *cbt) return; if (cbt->timeout_ms < circuit_build_times_min_timeout()) { - log_info(LD_CIRC, "Set buildtimeout to low value %fms. Setting to %dms", + log_notice(LD_CIRC, "Set buildtimeout to low value %fms. Setting to %dms", cbt->timeout_ms, circuit_build_times_min_timeout()); cbt->timeout_ms = circuit_build_times_min_timeout(); if (cbt->close_ms < cbt->timeout_ms) { diff --git a/src/core/or/circuitstats.h b/src/core/or/circuitstats.h index 845d7b6722..1cd16b6f2b 100644 --- a/src/core/or/circuitstats.h +++ b/src/core/or/circuitstats.h @@ -119,8 +119,8 @@ double circuit_build_times_quantile_cutoff(void); #define CBT_MAX_TEST_FREQUENCY INT32_MAX /** Lowest allowable value for CircuitBuildTimeout in milliseconds */ -#define CBT_DEFAULT_TIMEOUT_MIN_VALUE (1500) -#define CBT_MIN_TIMEOUT_MIN_VALUE 500 +#define CBT_DEFAULT_TIMEOUT_MIN_VALUE (CBT_BIN_WIDTH) +#define CBT_MIN_TIMEOUT_MIN_VALUE CBT_BIN_WIDTH #define CBT_MAX_TIMEOUT_MIN_VALUE INT32_MAX /** Initial circuit build timeout in milliseconds */

1 0

[tor/master] Lower circuit build time bin width to 10ms.
by asn＠torproject.org 19 Feb '21

19 Feb '21

commit 406400a74d917ec997d26afdf4ae97d9826820fe Author: Mike Perry <mikeperry-git(a)torproject.org> Date: Wed Nov 4 12:30:50 2020 -0600 Lower circuit build time bin width to 10ms. 50ms is not enough resolution. CBT can be as low as 80ms in datacenter clients close to their relays. --- src/core/or/circuitstats.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/src/core/or/circuitstats.h b/src/core/or/circuitstats.h index e7262e9e82..15fe23641e 100644 --- a/src/core/or/circuitstats.h +++ b/src/core/or/circuitstats.h @@ -55,7 +55,7 @@ void circuit_build_times_mark_circ_as_measurement_only(origin_circuit_t *circ); #define CBT_NCIRCUITS_TO_OBSERVE 1000 /** Width of the histogram bins in milliseconds */ -#define CBT_BIN_WIDTH ((build_time_t)50) +#define CBT_BIN_WIDTH ((build_time_t)10) /** Number of modes to use in the weighted-avg computation of Xm */ #define CBT_DEFAULT_NUM_XM_MODES 3

1 0

[tor/master] Log circuit timeout in milliseconds
by asn＠torproject.org 19 Feb '21

19 Feb '21

commit 86acd4d940572db16c3a4ccfa6059f1b76a3f5f6 Author: Mike Perry <mikeperry-git(a)torproject.org> Date: Tue Nov 3 15:37:43 2020 -0600 Log circuit timeout in milliseconds --- src/core/or/circuitstats.c | 17 ++++++++--------- 1 file changed, 8 insertions(+), 9 deletions(-) diff --git a/src/core/or/circuitstats.c b/src/core/or/circuitstats.c index 7cc69b3b4c..d92f35fdc2 100644 --- a/src/core/or/circuitstats.c +++ b/src/core/or/circuitstats.c @@ -1626,9 +1626,8 @@ circuit_build_times_network_check_changed(circuit_build_times_t *cbt) log_notice(LD_CIRC, "Your network connection speed appears to have changed. Resetting " - "timeout to %lds after %d timeouts and %d buildtimes.", - tor_lround(cbt->timeout_ms/1000), timeout_count, - total_build_times); + "timeout to %ldms after %d timeouts and %d buildtimes.", + tor_lround(cbt->timeout_ms), timeout_count, total_build_times); return 1; } @@ -1812,9 +1811,9 @@ circuit_build_times_set_timeout(circuit_build_times_t *cbt) log_info(LD_CIRC, "Based on %d circuit times, it looks like we don't need to " "wait so long for circuits to finish. We will now assume a " - "circuit is too slow to use after waiting %ld seconds.", + "circuit is too slow to use after waiting %ld milliseconds.", cbt->total_build_times, - tor_lround(cbt->timeout_ms/1000)); + tor_lround(cbt->timeout_ms)); log_info(LD_CIRC, "Circuit timeout data: %fms, %fms, Xm: %d, a: %f, r: %f", cbt->timeout_ms, cbt->close_ms, cbt->Xm, cbt->alpha, @@ -1823,18 +1822,18 @@ circuit_build_times_set_timeout(circuit_build_times_t *cbt) log_info(LD_CIRC, "Based on %d circuit times, it looks like we need to wait " "longer for circuits to finish. We will now assume a " - "circuit is too slow to use after waiting %ld seconds.", + "circuit is too slow to use after waiting %ld milliseconds.", cbt->total_build_times, - tor_lround(cbt->timeout_ms/1000)); + tor_lround(cbt->timeout_ms)); log_info(LD_CIRC, "Circuit timeout data: %fms, %fms, Xm: %d, a: %f, r: %f", cbt->timeout_ms, cbt->close_ms, cbt->Xm, cbt->alpha, timeout_rate); } else { log_info(LD_CIRC, - "Set circuit build timeout to %lds (%fms, %fms, Xm: %d, a: %f," + "Set circuit build timeout to %ldms (%fms, %fms, Xm: %d, a: %f," " r: %f) based on %d circuit times", - tor_lround(cbt->timeout_ms/1000), + tor_lround(cbt->timeout_ms), cbt->timeout_ms, cbt->close_ms, cbt->Xm, cbt->alpha, timeout_rate, cbt->total_build_times); }

1 0

[tor/master] Bug 40168 changes file
by asn＠torproject.org 19 Feb '21

19 Feb '21

commit 1fadb1bdf12610970af0ae9c7affd300830c3509 Author: Mike Perry <mikeperry-git(a)torproject.org> Date: Tue Nov 3 14:39:10 2020 -0600 Bug 40168 changes file --- changes/bug40168 | 16 ++++++++++++++++ 1 file changed, 16 insertions(+) diff --git a/changes/bug40168 b/changes/bug40168 new file mode 100644 index 0000000000..c52a0352c2 --- /dev/null +++ b/changes/bug40168 @@ -0,0 +1,16 @@ + o Minor bugfixes (circuit build timeout): + - Improve the accuracy of our circuit build timeout calculation for 60%, + 70%, and 80% build rates for various guard choices. We now use a maximum + likelihood estimator for Pareto parameters of the circuit build time + distribution, instead of a "right-censored estimator". This causes + clients to ignore circuits that never finish building in their timeout + calculations. Previously, clients were counting such unfinished circuits + as having the highest possible build time value, when in reality these + circuits most likely just contain relays that are offline. We also now + wait a bit longer to let circuits complete for measurement purposes, + lower the minimum possible effective timeout from 1.5 seconds to 10ms, + and increase the resolution of the circuit build time histogram from + 50ms bin widths to 10ms bin widths. Additionally, we alter our estimate + Xm by taking the maximum of the top 10 most common build time values + of the 10ms histogram, and compute Xm as the average of these. + Fixes bug 40168; bugfix on 0.2.2.14-alpha.

1 0

[tor/master] Bug 34088: Changes file
by asn＠torproject.org 19 Feb '21

19 Feb '21

commit 525195a7153d47295de430002f28b4c27192b5c1 Author: Mike Perry <mikeperry-git(a)torproject.org> Date: Mon Nov 23 21:44:55 2020 -0600 Bug 34088: Changes file --- changes/bug34088 | 4 ++++ 1 file changed, 4 insertions(+) diff --git a/changes/bug34088 b/changes/bug34088 new file mode 100644 index 0000000000..172d890898 --- /dev/null +++ b/changes/bug34088 @@ -0,0 +1,4 @@ + o Minor bugfixes (circuit build timeout): + - Remove max_time calculation and associated warn from circuit build + timeout 'alpha' parameter estimation, as this is no longer needed + by our new estimator from 40168. Fixes bug 34088; bugfix on 0.2.2.9-alpha.

1 0

[tor/master] Fix Xm mode calculation to properly average N=10 modes.
by asn＠torproject.org 19 Feb '21

19 Feb '21

commit ed9d60cb92efbf5bc2a3c22ade6ffee4e1c8116a Author: Mike Perry <mikeperry-git(a)torproject.org> Date: Fri Nov 6 16:30:16 2020 -0600 Fix Xm mode calculation to properly average N=10 modes. This is still fast enough. ~100usec on my laptop with 1000 build times. --- src/core/or/circuitstats.c | 61 +++++++++++++++++++--------------------------- src/core/or/circuitstats.h | 2 +- 2 files changed, 26 insertions(+), 37 deletions(-) diff --git a/src/core/or/circuitstats.c b/src/core/or/circuitstats.c index d92f35fdc2..57d45d2240 100644 --- a/src/core/or/circuitstats.c +++ b/src/core/or/circuitstats.c @@ -853,58 +853,49 @@ circuit_build_times_create_histogram(const circuit_build_times_t *cbt, * Return the Pareto start-of-curve parameter Xm. * * Because we are not a true Pareto curve, we compute this as the - * weighted average of the N most frequent build time bins. N is either - * 1 if we don't have enough circuit build time data collected, or - * determined by the consensus parameter cbtnummodes (default 3). + * weighted average of the 10 most frequent build time bins. This + * heuristic allowed for the actual timeout rate to be closest + * to the chosen quantile cutoff, for quantiles 60-80%, out of + * many variant approaches (see #40157 for analysis). */ static build_time_t circuit_build_times_get_xm(circuit_build_times_t *cbt) { - build_time_t i, nbins; + build_time_t nbins = 0; build_time_t *nth_max_bin; - int32_t bin_counts=0; - build_time_t ret = 0; - uint32_t *histogram = circuit_build_times_create_histogram(cbt, &nbins); - int n=0; + build_time_t xm_total = 0; + build_time_t Xm = 0; + int32_t xm_counts=0; int num_modes = circuit_build_times_default_num_xm_modes(); + uint32_t *histogram = circuit_build_times_create_histogram(cbt, &nbins); tor_assert(nbins > 0); tor_assert(num_modes > 0); - // Only use one mode if < 1000 buildtimes. Not enough data - // for multiple. - if (cbt->total_build_times < CBT_NCIRCUITS_TO_OBSERVE) - num_modes = 1; - nth_max_bin = tor_calloc(num_modes, sizeof(build_time_t)); - /* Determine the N most common build times */ - for (i = 0; i < nbins; i++) { - if (histogram[i] >= histogram[nth_max_bin[0]]) { - nth_max_bin[0] = i; - } - - for (n = 1; n < num_modes; n++) { - if (histogram[i] >= histogram[nth_max_bin[n]] && - (!histogram[nth_max_bin[n-1]] - || histogram[i] < histogram[nth_max_bin[n-1]])) { + /* Determine the N most common build times, by selecting the + * nth largest mode, counting it, and removing it from the histogram. */ + for (int n = 0; n < num_modes; n++) { + /* Get nth mode */ + for (build_time_t i = 0; i < nbins; i++) { + if (histogram[i] > histogram[nth_max_bin[n]]) { nth_max_bin[n] = i; } } - } - for (n = 0; n < num_modes; n++) { - bin_counts += histogram[nth_max_bin[n]]; - ret += CBT_BIN_TO_MS(nth_max_bin[n])*histogram[nth_max_bin[n]]; - log_info(LD_CIRC, "Xm mode #%d: %u %u", n, CBT_BIN_TO_MS(nth_max_bin[n]), - histogram[nth_max_bin[n]]); + /* Update average */ + xm_counts += histogram[nth_max_bin[n]]; + xm_total += CBT_BIN_TO_MS(nth_max_bin[n])*histogram[nth_max_bin[n]]; + + /* Prevent from re-counting this value */ + histogram[nth_max_bin[n]] = 0; } - /* bin_counts can become zero if all of our last CBT_NCIRCUITS_TO_OBSERVE + /* xm_counts can become zero if all of our last CBT_NCIRCUITS_TO_OBSERVE * circuits were abandoned before they completed. This shouldn't happen, * though. We should have reset/re-learned a lower timeout first. */ - if (bin_counts == 0) { - ret = 0; + if (xm_counts == 0) { log_warn(LD_CIRC, "No valid circuit build time data out of %d times, %u modes, " "have_timeout=%d, %lfms", cbt->total_build_times, num_modes, @@ -912,15 +903,13 @@ circuit_build_times_get_xm(circuit_build_times_t *cbt) goto done; } - tor_assert(bin_counts > 0); - - ret /= bin_counts; + Xm = xm_total / xm_counts; done: tor_free(histogram); tor_free(nth_max_bin); - return ret; + return Xm; } /** diff --git a/src/core/or/circuitstats.h b/src/core/or/circuitstats.h index 15fe23641e..864b3b5f43 100644 --- a/src/core/or/circuitstats.h +++ b/src/core/or/circuitstats.h @@ -58,7 +58,7 @@ void circuit_build_times_mark_circ_as_measurement_only(origin_circuit_t *circ); #define CBT_BIN_WIDTH ((build_time_t)10) /** Number of modes to use in the weighted-avg computation of Xm */ -#define CBT_DEFAULT_NUM_XM_MODES 3 +#define CBT_DEFAULT_NUM_XM_MODES 10 #define CBT_MIN_NUM_XM_MODES 1 #define CBT_MAX_NUM_XM_MODES 20

1 0

[tor/master] Bug 34088: Remove max timeout calculation and warning.
by asn＠torproject.org 19 Feb '21

19 Feb '21

commit d16b3d12a140af11f313bee3f5c0fbddf6a4e19e Author: Mike Perry <mikeperry-git(a)torproject.org> Date: Mon Nov 23 21:37:51 2020 -0600 Bug 34088: Remove max timeout calculation and warning. With the maximum likelihood estimator for alpha from #40168, we no longer need max_time to calculate alpha. --- src/core/or/circuitstats.c | 14 -------------- 1 file changed, 14 deletions(-) diff --git a/src/core/or/circuitstats.c b/src/core/or/circuitstats.c index 57d45d2240..449c055973 100644 --- a/src/core/or/circuitstats.c +++ b/src/core/or/circuitstats.c @@ -1143,7 +1143,6 @@ circuit_build_times_update_alpha(circuit_build_times_t *cbt) build_time_t *x=cbt->circuit_build_times; double a = 0; int n=0,i=0,abandoned_count=0; - build_time_t max_time=0; /* http://en.wikipedia.org/wiki/Pareto_distribution#Parameter_estimation */ /* We sort of cheat here and make our samples slightly more pareto-like @@ -1168,8 +1167,6 @@ circuit_build_times_update_alpha(circuit_build_times_t *cbt) abandoned_count++; } else { a += tor_mathlog(x[i]); - if (x[i] > max_time) - max_time = x[i]; n++; } } @@ -1186,17 +1183,6 @@ circuit_build_times_update_alpha(circuit_build_times_t *cbt) } tor_assert_nonfatal(n==cbt->total_build_times-abandoned_count); - if (max_time <= 0) { - /* This can happen if Xm is actually the *maximum* value in the set. - * It can also happen if we've abandoned every single circuit somehow. - * In either case, tell the caller not to compute a new build timeout. */ - log_warn(LD_BUG, - "Could not determine largest build time (%d). " - "Xm is %dms and we've abandoned %d out of %d circuits.", max_time, - cbt->Xm, abandoned_count, n); - return 0; - } - /* This is the "Maximum Likelihood Estimator" for parameter alpha of a Pareto * Distribution. See: * https://en.wikipedia.org/wiki/Pareto_distribution#Estimation_of_parameters

1 0