1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
|
Filename: 151-path-selection-improvements.txt
Title: Improving Tor Path Selection
Version:
Last-Modified:
Author: Fallon Chen, Mike Perry
Created: 5-Jul-2008
Status: Draft
Overview
The performance of paths selected can be improved by adjusting the
CircuitBuildTimeout and avoiding failing guard nodes. This proposal
describes a method of tracking buildtime statistics, and using those
statistics to adjust the CircuitBuildTimeout and the number of guards.
Motivation
Tor's performance can be improved by excluding those circuits that
have long buildtimes (and by extension, high latency). For those Tor
users who require better performance and have lower requirements for
anonymity, this would be a very useful option to have.
Implementation
Learning the CircuitBuildTimeout
Based on studies of build times, we found that the distribution of
circuit buildtimes appears to be a Pareto distribution. The number
of circuits to observe (ncircuits_to_cutoff) before changing the
CircuitBuildTimeout will be tunable. From out measurements,
ncircuits_to_cuttoff appears to be on the order of 100.
In addition, the total number of circuits gathered
(ncircuits_to_observe) will also be tunable. It is likely that
ncircuits_to_observe will be somewhere on the order of 1000. The values
can be represented compactly in Tor in milliseconds as a circular array
of 16 bit integers. More compact long-term storage representations can
be implemented by simply storing a histogram with 50 millisecond buckets
when writing out the statistics to disk.
Calculating the preferred CircuitBuildTimeout
Circuits that have longer buildtimes than some x% of the estimated
CDF of the Pareto distribution will be excluded. x will be tunable
as well.
Circuit timeouts
In the event of a timeout, backoff values should include the 100-x%
of expected CDF of timeouts. Also, in the event of network failure,
the observation mechanism should stop collecting timeout data.
Dropping Failed Guards
In addition, we have noticed that some entry guards are much more
failure prone than others. In particular, the circuit failure rates for
the fastest entry guards was approximately 20-25%, where as slower
guards exhibit failure rates as high as 45-50%. In [1], it was
demonstrated that failing guard nodes can deliberately bias path
selection to improve their success at capturing traffic. For both these
reasons, failing guards should be avoided.
We propose increasing the number of entry guards to five, and gathering
circuit failure statistics on each entry guard. Any guards that exceed
the average failure rate of all guards by 10% after we have
gathered ncircuits_to_observe circuits will be replaced.
Issues
Impact on anonymity
Since this follows a Pareto distribution, large reductions on the
timeout can be achieved without cutting off a great number of the
total paths. However, hard statistics on which cutoff percentage
gives optimal performance have not yet been gathered.
Guard Turnover
We contend that the risk from failing guards biasing path selection
outweighs the risk of exposure to larger portions of the network
for the first hop. Furthermore, from our observations, it appears
that circuit failure is strongly correlated to node load. Allowing
clients to migrate away from failing guards should naturally
rebalance the network, and eventually clients should converge on
a stable set of reliable guards. It is also likely that once clients
begin to migrate away from failing guards, their load should go
down, causing their failure rates to drop as well.
[1] http://www.crhc.uiuc.edu/~nikita/papers/relmix-ccs07.pdf
|
