-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Hi Nick, this proposal contains the four design changes to improve performance of hidden services. The first patch is attached, too. - --Karsten -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.6 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFI22KM0M+WPffBEmURAqtlAKDWeltZbmvmi4q8U3OKlSQjnsNncgCeLPV9 1wQHHkU2dSg8sPZxMM+RFsE= =Q0dJ -----END PGP SIGNATURE-----
Index: /home/karsten/tor/tor-trunk-155-patches/ChangeLog
===================================================================
--- /home/karsten/tor/tor-trunk-155-patches/ChangeLog (revision 16962)
+++ /home/karsten/tor/tor-trunk-155-patches/ChangeLog (working copy)
@@ -71,6 +71,8 @@
servers.
- Drop the requirement to have an open dir port for storing and serving
v2 hidden service descriptors.
+ - Reduce extension timeout for introduction circuits from 60 to 30
+ seconds.
o Code simplifications and refactoring:
- Revise the connection_new functions so that a more typesafe variant
Index: /home/karsten/tor/tor-trunk-155-patches/src/or/circuituse.c
===================================================================
--- /home/karsten/tor/tor-trunk-155-patches/src/or/circuituse.c (revision 16962)
+++ /home/karsten/tor/tor-trunk-155-patches/src/or/circuituse.c (working copy)
@@ -251,8 +251,11 @@
circuit_expire_building(time_t now)
{
circuit_t *victim, *circ = global_circuitlist;
- time_t cutoff = now - get_options()->CircuitBuildTimeout;
+ time_t cutoff;
+ time_t general_cutoff = now - get_options()->CircuitBuildTimeout;
time_t begindir_cutoff = now - get_options()->CircuitBuildTimeout/2;
+#define REND_INTRO_CIRC_TIMEOUT 30
+ time_t introrend_cutoff = now - REND_INTRO_CIRC_TIMEOUT;
cpath_build_state_t *build_state;
while (circ) {
@@ -263,11 +266,21 @@
continue;
build_state = TO_ORIGIN_CIRCUIT(victim)->build_state;
- if (victim->timestamp_created >
- ((build_state && build_state->onehop_tunnel) ?
- begindir_cutoff : cutoff))
+ if (build_state && build_state->onehop_tunnel)
+ cutoff = begindir_cutoff;
+ else if (victim->purpose == CIRCUIT_PURPOSE_C_INTRODUCING)
+ cutoff = introrend_cutoff;
+ else
+ cutoff = general_cutoff;
+ if (victim->timestamp_created > cutoff)
continue; /* it's still young, leave it alone */
+ if (victim->purpose == CIRCUIT_PURPOSE_C_INTRODUCING &&
+ victim->timestamp_created <= introrend_cutoff &&
+ victim->timestamp_created > general_cutoff)
+ log_info(LD_REND|LD_CIRC, "Timing out introduction circuit which we "
+ "would not have done if it had been a general circuit.");
+
#if 0
/* some debug logs, to help track bugs */
if (victim->purpose >= CIRCUIT_PURPOSE_C_INTRODUCING &&
Filename: xxx-hidden-service-performance.txt Title: Improvements of Hidden Service Performance Version: $Revision$ Last-Modified: $Date$ Author: Karsten Loesing, Christian Wilms Created: 25-Sep-2008 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
Attachment:
patch-155-1.txt.sig
Description: Binary data
Attachment:
xxx-hidden-service-performance.txt.sig
Description: Binary data