Filename: 155-four-hidden-service-improvements.txt
Title: Four Improvements of Hidden Service Performance
Author: Karsten Loesing, Christian Wilms
Created: 25-Sep-2008
Status: Closed
Implemented-In: 0.2.1.x
Change history:
25-Sep-2008 Initial proposal for or-dev
Overview:
A performance analysis of hidden services [1] has brought up a few
possible design changes to reduce advertisement time of a hidden service
in the network as well as connection establishment time. Some of these
design changes have side-effects on anonymity or overall network load
which had to be weighed up against individual performance gains. A
discussion of seven possible design changes [2] has led to a selection
of four changes [3] that are proposed to be implemented here.
Design:
1. Shorter Circuit Extension Timeout
When establishing a connection to a hidden service a client cannibalizes
an existing circuit and extends it by one hop to one of the service's
introduction points. In most cases this can be accomplished within a few
seconds. Therefore, the current timeout of 60 seconds for extending a
circuit is far too high.
Assuming that the timeout would be reduced to a lower value, for example
30 seconds, a second (or third) attempt to cannibalize and extend would
be started earlier. With the current timeout of 60 seconds, 93.42% of all
circuits can be established, whereas this fraction would have been only
0.87% smaller at 92.55% with a timeout of 30 seconds.
For a timeout of 30 seconds the performance gain would be approximately 2
seconds in the mean as opposed to the current timeout of 60 seconds. At
the same time a smaller timeout leads to discarding an increasing number
of circuits that might have been completed within the current timeout of
60 seconds.
Measurements with simulated low-bandwidth connectivity have shown that
there is no significant effect of client connectivity on circuit
extension times. The reason for this might be that extension messages are
small and thereby independent of the client bandwidth. Further, the
connection between client and entry node only constitutes a single hop of
a circuit, so that its influence on the whole circuit is limited.
The exact value of the new timeout does not necessarily have to be 30
seconds, but might also depend on the results of circuit build timeout
measurements as described in proposal 151.
2. Parallel Connections to Introduction Points
An additional approach to accelerate extension of introduction circuits
is to extend a second circuit in parallel to a different introduction
point. Such parallel extension attempts should be started after a short
delay of, e.g., 15 seconds in order to prevent unnecessary circuit
extensions and thereby save network resources. Whichever circuit
extension succeeds first is used for introduction, while the other
attempt is aborted.
An evaluation has been performed for the more resource-intensive approach
of starting two parallel circuits immediately instead of waiting for a
short delay. The result was a reduction of connection establishment times
from 27.4 seconds in the original protocol to 22.5 seconds.
While the effect of the proposed approach of delayed parallelization on
mean connection establishment times is expected to be smaller,
variability of connection attempt times can be reduced significantly.
3. Increase Count of Internal Circuits
Hidden services need to create or cannibalize and extend a circuit to a
rendezvous point for every client request. Really popular hidden services
require more than two internal circuits in the pool to answer multiple
client requests at the same time. This scenario was not yet analyzed, but
will probably exhibit worse performance than measured in the previous
analysis. The number of preemptively built internal circuits should be a
function of connection requests in the past to adapt to changing needs.
Furthermore, an increased number of internal circuits on client side
would allow clients to establish connections to more than one hidden
service at a time.
Under the assumption that a popular hidden service cannot make use of
cannibalization for connecting to rendezvous points, the circuit creation
time needs to be added to the current results. In the mean, the
connection establishment time to a popular hidden service would increase
by 4.7 seconds.
4. Build More Introduction Circuits
When establishing introduction points, a hidden service should launch 5
instead of 3 introduction circuits at the same time and use only the
first 3 that could be established. The remaining two circuits could still
be used for other purposes afterwards.
The effect has been simulated using previously measured data, too.
Therefore, circuit establishment times were derived from log files and
written to an array. Afterwards, a simulation with 10,000 runs was
performed picking 5 (4, 6) random values and using the 3 lowest values in
contrast to picking only 3 values at random. The result is that the mean
time of the 3-out-of-3 approach is 8.1 seconds, while the mean time of
the 3-out-of-5 approach is 4.4 seconds.
The effect on network load is minimal, because the hidden service can
reuse the slower internal circuits for other purposes, e.g., rendezvous
circuits. The only change is that a hidden service starts establishing
more circuits at once instead of subsequently doing so.
References:
[1] http://freehaven.net/~karsten/hidserv/perfanalysis-2008-06-15.pdf
[2] http://freehaven.net/~karsten/hidserv/discussion-2008-07-15.pdf
[3] http://freehaven.net/~karsten/hidserv/design-2008-08-15.pdf