doc/spec/proposals/155-four-hidden-service-improvements.txt

   1 Filename: 155-four-hidden-service-improvements.txt
   2 Title: Four Improvements of Hidden Service Performance
   3 Version: $Revision$
   4 Last-Modified: $Date$
   5 Author: Karsten Loesing, Christian Wilms
   6 Created: 25-Sep-2008
   7 Status: Finished
   8 Implemented-In: 0.2.1.x
   9
  10 Change history:
  11
  12   25-Sep-2008  Initial proposal for or-dev
  13
  14 Overview:
  15
  16   A performance analysis of hidden services [1] has brought up a few
  17   possible design changes to reduce advertisement time of a hidden service
  18   in the network as well as connection establishment time. Some of these
  19   design changes have side-effects on anonymity or overall network load
  20   which had to be weighed up against individual performance gains. A
  21   discussion of seven possible design changes [2] has led to a selection
  22   of four changes [3] that are proposed to be implemented here.
  23
  24 Design:
  25
  26   1. Shorter Circuit Extension Timeout
  27
  28   When establishing a connection to a hidden service a client cannibalizes
  29   an existing circuit and extends it by one hop to one of the service's
  30   introduction points. In most cases this can be accomplished within a few
  31   seconds. Therefore, the current timeout of 60 seconds for extending a
  32   circuit is far too high.
  33
  34   Assuming that the timeout would be reduced to a lower value, for example
  35   30 seconds, a second (or third) attempt to cannibalize and extend would
  36   be started earlier. With the current timeout of 60 seconds, 93.42% of all
  37   circuits can be established, whereas this fraction would have been only
  38   0.87% smaller at 92.55% with a timeout of 30 seconds.
  39
  40   For a timeout of 30 seconds the performance gain would be approximately 2
  41   seconds in the mean as opposed to the current timeout of 60 seconds. At
  42   the same time a smaller timeout leads to discarding an increasing number
  43   of circuits that might have been completed within the current timeout of
  44   60 seconds.
  45
  46   Measurements with simulated low-bandwidth connectivity have shown that
  47   there is no significant effect of client connectivity on circuit
  48   extension times. The reason for this might be that extension messages are
  49   small and thereby independent of the client bandwidth. Further, the
  50   connection between client and entry node only constitutes a single hop of
  51   a circuit, so that its influence on the whole circuit is limited.
  52
  53   The exact value of the new timeout does not necessarily have to be 30
  54   seconds, but might also depend on the results of circuit build timeout
  55   measurements as described in proposal 151.
  56
  57   2. Parallel Connections to Introduction Points
  58
  59   An additional approach to accelerate extension of introduction circuits
  60   is to extend a second circuit in parallel to a different introduction
  61   point. Such parallel extension attempts should be started after a short
  62   delay of, e.g., 15 seconds in order to prevent unnecessary circuit
  63   extensions and thereby save network resources. Whichever circuit
  64   extension succeeds first is used for introduction, while the other
  65   attempt is aborted.
  66
  67   An evaluation has been performed for the more resource-intensive approach
  68   of starting two parallel circuits immediately instead of waiting for a
  69   short delay. The result was a reduction of connection establishment times
  70   from 27.4 seconds in the original protocol to 22.5 seconds.
  71
  72   While the effect of the proposed approach of delayed parallelization on
  73   mean connection establishment times is expected to be smaller,
  74   variability of connection attempt times can be reduced significantly.
  75
  76   3. Increase Count of Internal Circuits
  77
  78   Hidden services need to create or cannibalize and extend a circuit to a
  79   rendezvous point for every client request. Really popular hidden services
  80   require more than two internal circuits in the pool to answer multiple
  81   client requests at the same time. This scenario was not yet analyzed, but
  82   will probably exhibit worse performance than measured in the previous
  83   analysis. The number of preemptively built internal circuits should be a
  84   function of connection requests in the past to adapt to changing needs.
  85   Furthermore, an increased number of internal circuits on client side
  86   would allow clients to establish connections to more than one hidden
  87   service at a time.
  88
  89   Under the assumption that a popular hidden service cannot make use of
  90   cannibalization for connecting to rendezvous points, the circuit creation
  91   time needs to be added to the current results. In the mean, the
  92   connection establishment time to a popular hidden service would increase
  93   by 4.7 seconds.
  94
  95   4. Build More Introduction Circuits
  96
  97   When establishing introduction points, a hidden service should launch 5
  98   instead of 3 introduction circuits at the same time and use only the
  99   first 3 that could be established. The remaining two circuits could still
 100   be used for other purposes afterwards.
 101
 102   The effect has been simulated using previously measured data, too.
 103   Therefore, circuit establishment times were derived from log files and
 104   written to an array. Afterwards, a simulation with 10,000 runs was
 105   performed picking 5 (4, 6) random values and using the 3 lowest values in
 106   contrast to picking only 3 values at random. The result is that the mean
 107   time of the 3-out-of-3 approach is 8.1 seconds, while the mean time of
 108   the 3-out-of-5 approach is 4.4 seconds.
 109
 110   The effect on network load is minimal, because the hidden service can
 111   reuse the slower internal circuits for other purposes, e.g., rendezvous
 112   circuits. The only change is that a hidden service starts establishing
 113   more circuits at once instead of subsequently doing so.
 114
 115 References:
 116
 117   [1] http://freehaven.net/~karsten/hidserv/perfanalysis-2008-06-15.pdf
 118
 119   [2] http://freehaven.net/~karsten/hidserv/discussion-2008-07-15.pdf
 120
 121   [3] http://freehaven.net/~karsten/hidserv/design-2008-08-15.pdf
 122