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
|
Filename: 183-refillintervals.txt
Title: Refill Intervals
Author: Florian Tschorsch and Björn Scheuermann
Created: 03-Dec-2010
Status: Closed
Implemented-In: 0.2.3.5-alpha
Overview:
In order to avoid additional queuing and bursty traffic, the refill
interval of the token bucket algorithm should be shortened. Thus we
propose a configurable parameter that sets the refill interval
accordingly.
Motivation and Background:
In Tor there exist multiple token buckets on different logical levels. They
all work independently. They are used to limit the up- and downstream of an
onion router. All token buckets are refilled every second with a constant
amount of tokens that depends on the configured bandwidth limits. The very
coarse-grained refill interval of one second has detrimental effects.
First, consider an onion router with multiple TLS connections over which
cells arrive. If there is high activity (i.e., many incoming cells in
total), then the coarse refill interval will cause unfairness. Assume (just
for simplicity) that C doesn't share its TLS connection with any other
circuit. Moreover, assume that C hasn't transmitted any data for some time
(e.g., due a typical bursty HTTP traffic pattern). Consequently, there are
no cells from this circuit in the incoming socket buffers. When the buckets
are refilled, the incoming token bucket will immediately spend all its
tokens on other incoming connections. Now assume that cells from C arrive
soon after. For fairness' sake, these cells should be serviced timely --
circuit C hasn't received any bandwidth for a significant time before.
However, it will take a very long time (one refill interval) before the
current implementation will fetch these cells from the incoming TLS
connection, because the token bucket will remain empty for a long time. Just
because the cells happened to arrive at the "wrong" point in time, they must
wait. Such situations may occur even though the configured admissible
incoming data rate is not exceeded by incoming cells: the long refill
intervals often lead to an operational state where all the cells that were
admissible during a given one-second period are queued until the end of this
second, before the onion router even just starts processing them. This
results in unnecessary, long queuing delays in the incoming socket buffers.
These delays are not visible in the Tor circuit queue delay statistics [1].
Finally, the coarse-grained refill intervals result in a very bursty outgoing
traffic pattern at the onion routers (one large chunk of data once per
second, instead of smooth transmission progress). This is undesirable, since
such a traffic pattern can interfere with TCP's control mechanisms and can
be the source of suboptimal TCP performance on the TLS links between onion
routers.
Specific Changes:
The token buckets should be refilled more often, with a correspondingly
smaller amount of tokens. For instance, the buckets might be refilled every
10 milliseconds with one-hundredth of the amount of data admissible per
second. This will help to overcome the problem of unfairness when reading
from the incoming socket buffers. At the same time it smoothes the traffic
leaving the onion routers. We are aware that this latter change has
apparently been discussed before [2]; we are not sure why this change has
not been implemented yet.
In particular we need to change the current implementation in Tor which
triggers refilling always after exactly one second. Instead the refill event
should fire more frequently. The smaller time intervals between each refill
action need to be taken into account for the number of tokens that are added
to the bucket.
With libevent 2.x and bufferevents enabled, smaller refill intervals are
already considered but hard coded. This should be changed to a configurable
parameter, too.
Conclusion:
This proposal can be implemented with moderate effort and requires changes
only at the points where the token bucket operations are currently
performed.
This change will also be a good starting point for further enhancements
to improve queuing times in Tor. I.e. it will pave the ground for other means
that tackle this problem.
Feedback is highly appreciated.
References:
[1] Karsten Loesing. Analysis of Circuit Queues in Tor. August 25, 2009.
[2] https://trac.torproject.org/projects/tor/wiki/sponsors/SponsorD/June2011
|
