add karsten's proposal 155, after giving it a more unique name

svn:r17032

1 files changed, 122 insertions, 0 deletions

diff --git a/proposals/155-four-hidden-service-improvements.txt b/proposals/155-four-hidden-service-improvements.txt
new file mode 100644
index 0000000..6d681f8
--- /dev/null
+++ b/proposals/155-four-hidden-service-improvements.txt
@@ -0,0 +1,122 @@
+Filename: 155-four-hidden-service-improvements.txt
+Title: Four Improvements of Hidden Service Performance
+Version: $Revision$
+Last-Modified: $Date$
+Author: Karsten Loesing, Christian Wilms
+Created: 25-Sep-2008
+Status: Open
+Target: 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 lead 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
+