151-path-selection-improvements.txt 6.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147
  1. Filename: 151-path-selection-improvements.txt
  2. Title: Improving Tor Path Selection
  3. Author: Fallon Chen, Mike Perry
  4. Created: 5-Jul-2008
  5. Status: Finished
  6. Overview
  7. The performance of paths selected can be improved by adjusting the
  8. CircuitBuildTimeout and avoiding failing guard nodes. This proposal
  9. describes a method of tracking buildtime statistics at the client, and
  10. using those statistics to adjust the CircuitBuildTimeout.
  11. Motivation
  12. Tor's performance can be improved by excluding those circuits that
  13. have long buildtimes (and by extension, high latency). For those Tor
  14. users who require better performance and have lower requirements for
  15. anonymity, this would be a very useful option to have.
  16. Implementation
  17. Gathering Build Times
  18. Circuit build times are stored in the circular array
  19. 'circuit_build_times' consisting of uint32_t elements as milliseconds.
  20. The total size of this array is based on the number of circuits
  21. it takes to converge on a good fit of the long term distribution of
  22. the circuit builds for a fixed link. We do not want this value to be
  23. too large, because it will make it difficult for clients to adapt to
  24. moving between different links.
  25. From our observations, the minimum value for a reasonable fit appears
  26. to be on the order of 500 (MIN_CIRCUITS_TO_OBSERVE). However, to keep
  27. a good fit over the long term, we store 5000 most recent circuits in
  28. the array (NCIRCUITS_TO_OBSERVE).
  29. The Tor client will build test circuits at a rate of one per
  30. minute (BUILD_TIMES_TEST_FREQUENCY) up to the point of
  31. MIN_CIRCUITS_TO_OBSERVE. This allows a fresh Tor to have
  32. a CircuitBuildTimeout estimated within 8 hours after install,
  33. upgrade, or network change (see below).
  34. Long Term Storage
  35. The long-term storage representation is implemented by storing a
  36. histogram with BUILDTIME_BIN_WIDTH millisecond buckets (default 50) when
  37. writing out the statistics to disk. The format this takes in the
  38. state file is 'CircuitBuildTime <bin-ms> <count>', with the total
  39. specified as 'TotalBuildTimes <total>'
  40. Example:
  41. TotalBuildTimes 100
  42. CircuitBuildTimeBin 25 50
  43. CircuitBuildTimeBin 75 25
  44. CircuitBuildTimeBin 125 13
  45. ...
  46. Reading the histogram in will entail inserting <count> values
  47. into the circuit_build_times array each with the value of
  48. <bin-ms> milliseconds. In order to evenly distribute the values
  49. in the circular array, the Fisher-Yates shuffle will be performed
  50. after reading values from the bins.
  51. Learning the CircuitBuildTimeout
  52. Based on studies of build times, we found that the distribution of
  53. circuit buildtimes appears to be a Frechet distribution. However,
  54. estimators and quantile functions of the Frechet distribution are
  55. difficult to work with and slow to converge. So instead, since we
  56. are only interested in the accuracy of the tail, we approximate
  57. the tail of the distribution with a Pareto curve starting at
  58. the mode of the circuit build time sample set.
  59. We will calculate the parameters for a Pareto distribution
  60. fitting the data using the estimators at
  61. http://en.wikipedia.org/wiki/Pareto_distribution#Parameter_estimation.
  62. The timeout itself is calculated by using the Quartile function (the
  63. inverted CDF) to give us the value on the CDF such that
  64. BUILDTIME_PERCENT_CUTOFF (80%) of the mass of the distribution is
  65. below the timeout value.
  66. Thus, we expect that the Tor client will accept the fastest 80% of
  67. the total number of paths on the network.
  68. Detecting Changing Network Conditions
  69. We attempt to detect both network connectivity loss and drastic
  70. changes in the timeout characteristics.
  71. We assume that we've had network connectivity loss if 3 circuits
  72. timeout and we've received no cells or TLS handshakes since those
  73. circuits began. We then set the timeout to 60 seconds and stop
  74. counting timeouts.
  75. If 3 more circuits timeout and the network still has not been
  76. live within this new 60 second timeout window, we then discard
  77. the previous timeouts during this period from our history.
  78. To detect changing network conditions, we keep a history of
  79. the timeout or non-timeout status of the past RECENT_CIRCUITS (20)
  80. that successfully completed at least one hop. If more than 75%
  81. of these circuits timeout, we discard all buildtimes history,
  82. reset the timeout to 60, and then begin recomputing the timeout.
  83. Testing
  84. After circuit build times, storage, and learning are implemented,
  85. the resulting histogram should be checked for consistency by
  86. verifying it persists across successive Tor invocations where
  87. no circuits are built. In addition, we can also use the existing
  88. buildtime scripts to record build times, and verify that the histogram
  89. the python produces matches that which is output to the state file in Tor,
  90. and verify that the Pareto parameters and cutoff points also match.
  91. We will also verify that there are no unexpected large deviations from
  92. node selection, such as nodes from distant geographical locations being
  93. completely excluded.
  94. Dealing with Timeouts
  95. Timeouts should be counted as the expectation of the region of
  96. of the Pareto distribution beyond the cutoff. This is done by
  97. generating a random sample for each timeout at points on the
  98. curve beyond the current timeout cutoff.
  99. Future Work
  100. At some point, it may be desirable to change the cutoff from a
  101. single hard cutoff that destroys the circuit to a soft cutoff and
  102. a hard cutoff, where the soft cutoff merely triggers the building
  103. of a new circuit, and the hard cutoff triggers destruction of the
  104. circuit.
  105. It may also be beneficial to learn separate timeouts for each
  106. guard node, as they will have slightly different distributions.
  107. This will take longer to generate initial values though.
  108. Issues
  109. Impact on anonymity
  110. Since this follows a Pareto distribution, large reductions on the
  111. timeout can be achieved without cutting off a great number of the
  112. total paths. This will eliminate a great deal of the performance
  113. variation of Tor usage.