175-automatic-node-promotion.txt 10 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238
  1. Filename: 175-automatic-node-promotion.txt
  2. Title: Automatically promoting Tor clients to nodes
  3. Author: Steven Murdoch
  4. Created: 12-Mar-2010
  5. Status: Draft
  6. 1. Overview
  7. This proposal describes how Tor clients could determine when they
  8. have sufficient bandwidth capacity and are sufficiently reliable to
  9. become either bridges or Tor relays. When they meet this
  10. criteria, they will automatically promote themselves, based on user
  11. preferences. The proposal also defines the new controller messages
  12. and options which will control this process.
  13. Note that for the moment, only transitions between client and
  14. bridge are being considered. Transitions to public relay will
  15. be considered at a future date, but will use the same
  16. infrastructure for measuring capacity and reliability.
  17. 2. Motivation and history
  18. Tor has a growing user-base and one of the major impediments to the
  19. quality of service offered is the lack of network capacity. This is
  20. particularly the case for bridges, because these are gradually
  21. being blocked, and thus no longer of use to people within some
  22. countries. By automatically promoting Tor clients to bridges, and
  23. perhaps also to full public relays, this proposal aims to solve
  24. these problems.
  25. Only Tor clients which are sufficiently useful should be promoted,
  26. and the process of determining usefulness should be performed
  27. without reporting the existence of the client to the central
  28. authorities. The criteria used for determining usefulness will be
  29. in terms of bandwidth capacity and uptime, but parameters should be
  30. specified in the directory consensus. State stored at the client
  31. should be in no more detail than necessary, to prevent sensitive
  32. information being recorded.
  33. 3. Design
  34. 3.x Opt-in state model
  35. Tor can be in one of five node-promotion states:
  36. - off (O): Currently a client, and will stay as such
  37. - auto (A): Currently a client, but will consider promotion
  38. - bridge (B): Currently a bridge, and will stay as such
  39. - auto-bridge (AB): Currently a bridge, but will consider promotion
  40. - relay (R): Currently a public relay, and will stay as such
  41. The state can be fully controlled from the configuration file or
  42. controller, but the normal state transitions are as follows:
  43. Any state -> off: User has opted out of node promotion
  44. Off -> any state: Only permitted with user consent
  45. Auto -> auto-bridge: Tor has detected that it is sufficiently
  46. reliable to be a *bridge*
  47. Auto -> bridge: Tor has detected that it is sufficiently reliable
  48. to be a *relay*, but the user has chosen to remain a *bridge*
  49. Auto -> relay: Tor has detected that it is sufficiently reliable
  50. to be *relay*, and will skip being a *bridge*
  51. Auto-bridge -> relay: Tor has detected that it is sufficiently
  52. reliable to be a *relay*
  53. Note that this model does not support automatic demotion. If this
  54. is desirable, there should be some memory as to whether the
  55. previous state was relay, bridge, or auto-bridge. Otherwise the
  56. user may be prompted to become a relay, although he has opted to
  57. only be a bridge.
  58. 3.x User interaction policy
  59. There are a variety of options in how to involve the user into the
  60. decision as to whether and when to perform node promotion. The
  61. choice also may be different when Tor is running from Vidalia (and
  62. thus can readily prompt the user for information), and standalone
  63. (where Tor can only log messages, which may or may not be read).
  64. The option requiring minimal user interaction is to automatically
  65. promote nodes according to reliability, and allow the user to opt
  66. out, by changing settings in the configuration file or Vidalia user
  67. interface.
  68. Alternatively, if a user interface is available, Tor could prompt
  69. the user when it detects that a transition is available, and allow
  70. the user to choose which of the available options to select. If
  71. Vidalia is not available, it still may be possible to solicit an
  72. email address on install, and contact the operator to ask whether
  73. a transition to bridge or relay is permitted.
  74. Finally, Tor could by default not make any transition, and the user
  75. would need to opt in by stating the maximum level (bridge or
  76. relay) to which the node may automatically promote itself.
  77. 3.x Performance monitoring model
  78. To prevent a large number of clients activating as relays, but
  79. being too unreliable to be useful, clients should measure their
  80. performance. If this performance meets a parameterized acceptance
  81. criteria, a client should consider promotion. To measure
  82. reliability, this proposal adopts a simple user model:
  83. - A user decides to use Tor at times which follow a Poisson
  84. distribution
  85. - At each time, the user will be happy if the bridge chosen has
  86. adequate bandwidth and is reachable
  87. - If the chosen bridge is down or slow too many times, the user
  88. will consider Tor to be bad
  89. If we additionally assume that the recent history of relay
  90. performance matches the current performance, we can measure
  91. reliability by simulating this simple user.
  92. The following parameters are distributed to clients in the
  93. directory consensus:
  94. - min_bandwidth: Minimum self-measured bandwidth for a node to be
  95. considered useful, in bytes per second
  96. - check_period: How long, in seconds, to wait between checking
  97. reachability and bandwidth (on average)
  98. - num_samples: Number of recent samples to keep
  99. - num_useful: Minimum number of recent samples where the node was
  100. reachable and had at least min_bandwidth capacity, for a client
  101. to consider promoting to a bridge
  102. A different set of parameters may be used for considering when to
  103. promote a bridge to a full relay, but this will be the subject of a
  104. future revision of the proposal.
  105. 3.x Performance monitoring algorithm
  106. The simulation described above can be implemented as follows:
  107. Every 60 seconds:
  108. 1. Tor generates a random floating point number x in
  109. the interval [0, 1).
  110. 2. If x > (1 / (check_period / 60)) GOTO end; otherwise:
  111. 3. Tor sets the value last_check to the current_time (in seconds)
  112. 4. Tor measures reachability
  113. 5. If the client is reachable, Tor measures its bandwidth
  114. 6. If the client is reachable and the bandwidth is >=
  115. min_bandwidth, the test has succeeded, otherwise it has failed.
  116. 7. Tor adds the test result to the end of a ring-buffer containing
  117. the last num_samples results: measurement_results
  118. 8. Tor saves last_check and measurements_results to disk
  119. 9. If the length of measurements_results == num_samples and
  120. the number of successes >= num_useful, Tor should consider
  121. promotion to a bridge
  122. end.
  123. When Tor starts, it must fill in the samples for which it was not
  124. running. This can only happen once the consensus has downloaded,
  125. because the value of check_period is needed.
  126. 1. Tor generates a random number y from the Poisson distribution [1]
  127. with lambda = (current_time - last_check) * (1 / check_period)
  128. 2. Tor sets the value last_check to the current_time (in seconds)
  129. 3. Add y test failures to the ring buffer measurements_results
  130. 4. Tor saves last_check and measurements_results to disk
  131. In this way, a Tor client will measure its bandwidth and
  132. reachability every check_period seconds, on average. Provided
  133. check_period is sufficiently greater than a minute (say, at least an
  134. hour), the times of check will follow a Poisson distribution. [2]
  135. While this does require that Tor does record the state of a client
  136. over time, this does not leak much information. Only a binary
  137. reachable/non-reachable is stored, and the timing of samples becomes
  138. increasingly fuzzy as the data becomes less recent.
  139. On IP address changes, Tor should clear the ring-buffer, because
  140. from the perspective of users with the old IP address, this node
  141. might as well be a new one with no history. This policy may change
  142. once we start allowing the bridge authority to hand out new IP
  143. addresses given the fingerprint.
  144. 3.x Bandwidth measurement
  145. Tor needs to measure its bandwidth to test the usefulness as a
  146. bridge. A non-intrusive way to do this would be to passively measure
  147. the peak data transfer rate since the last reachability test. Once
  148. this exceeds min_bandwidth, Tor can set a flag that this node
  149. currently has sufficient bandwidth to pass the bandwidth component
  150. of the upcoming performance measurement.
  151. For the first version we may simply skip the bandwidth test,
  152. because the existing reachability test sends 500 kB over several
  153. circuits, and checks whether the node can transfer at least 50
  154. kB/s. This is probably good enough for a bridge, so this test
  155. might be sufficient to record a success in the ring buffer.
  156. 3.x New options
  157. 3.x New controller message
  158. 4. Migration plan
  159. We should start by setting a high bandwidth and uptime requirement
  160. in the consensus, so as to avoid overloading the bridge authority
  161. with too many bridges. Once we are confident our systems can scale,
  162. the criteria can be gradually shifted down to gain more bridges.
  163. 5. Related proposals
  164. 6. Open questions:
  165. - What user interaction policy should we take?
  166. - When (if ever) should we turn a relay into an exit relay?
  167. - What should the rate limits be for auto-promoted bridges/relays?
  168. Should we prompt the user for this?
  169. - Perhaps the bridge authority should tell potential bridges
  170. whether to enable themselves, by taking into account whether
  171. their IP address is blocked
  172. - How do we explain the possible risks of running a bridge/relay
  173. * Use of bandwidth/congestion
  174. * Publication of IP address
  175. * Blocking from IRC (even for non-exit relays)
  176. - What feedback should we give to bridge relays, to encourage then
  177. e.g. number of recent users (what about reserve bridges)?
  178. - Can clients back-off from doing these tests (yes, we should do
  179. this)
  180. [1] For algorithms to generate random numbers from the Poisson
  181. distribution, see: http://en.wikipedia.org/wiki/Poisson_distribution#Generating_Poisson-distributed_random_variables
  182. [2] "The sample size n should be equal to or larger than 20 and the
  183. probability of a single success, p, should be smaller than or equal to
  184. .05. If n >= 100, the approximation is excellent if np is also <= 10."
  185. http://www.itl.nist.gov/div898/handbook/pmc/section3/pmc331.htm (e-Handbook of Statistical Methods)
  186. % vim: spell ai et: