commit df031d7bf33f68948b2c915d681b08ca59c1da37
Author: Mike Perry <mikeperry-...@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
_______________________________________________
tor-commits mailing list
tor-commits@lists.torproject.org
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-commits
