tor-parallel-relay-conn/doc/spec/proposals/155-four-hidden-service-improvements.txt

Filename: 155-four-hidden-service-improvements.txt
Title: Four Improvements of Hidden Service Performance
Author: Karsten Loesing, Christian Wilms
Created: 25-Sep-2008
Status: Finished
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