161-computing-bandwidth-adjustments.txt 6.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174
  1. Title: Computing Bandwidth Adjustments
  2. Filename: 161-computing-bandwidth-adjustments.txt
  3. Author: Mike Perry
  4. Created: 12-May-2009
  5. Target: 0.2.2.x
  6. Status: Open
  7. 1. Motivation
  8. There is high variance in the performance of the Tor network. Despite
  9. our efforts to balance load evenly across the Tor nodes, some nodes are
  10. significantly slower and more overloaded than others.
  11. Proposal 160 describes how we can augment the directory authorities to
  12. vote on measured bandwidths for routers. This proposal describes what
  13. goes into the measuring process.
  14. 2. Measurement Selection
  15. The general idea is to determine a load factor representing the ratio
  16. of the capacity of measured nodes to the rest of the network. This load
  17. factor could be computed from three potentially relevant statistics:
  18. circuit failure rates, circuit extend times, or stream capacity.
  19. Circuit failure rates and circuit extend times appear to be
  20. non-linearly proportional to node load. We've observed that the same
  21. nodes when scanned at US nighttime hours (when load is presumably
  22. lower) exhibit almost no circuit failure, and significantly faster
  23. extend times than when scanned during the day.
  24. Stream capacity, however, is much more uniform, even during US
  25. nighttime hours. Moreover, it is a more intuitive representation of
  26. node capacity, and also less dependent upon distance and latency
  27. if amortized over large stream fetches.
  28. 3. Average Stream Bandwidth Calculation
  29. The average stream bandwidths are obtained by dividing the network into
  30. slices of 50 nodes each, grouped according to advertised node bandwidth.
  31. Two hop circuits are built using nodes from the same slice, and a large
  32. file is downloaded via these circuits. The file sizes are set based
  33. on node percentile rank as follows:
  34. 0-10: 2M
  35. 10-20: 1M
  36. 20-30: 512k
  37. 30-50: 256k
  38. 50-100: 128k
  39. These sizes are based on measurements performed during test scans.
  40. This process is repeated until each node has been chosen to participate
  41. in at least 5 circuits.
  42. 4. Ratio Calculation
  43. The ratios are calculated by dividing each measured value by the
  44. network-wide average.
  45. 5. Ratio Filtering
  46. After the base ratios are calculated, a second pass is performed
  47. to remove any streams with nodes of ratios less than X=0.5 from
  48. the results of other nodes. In addition, all outlying streams
  49. with capacity of one standard deviation below a node's average
  50. are also removed.
  51. The final ratio result will be greater of the unfiltered ratio
  52. and the filtered ratio.
  53. 6. Pseudocode for Ratio Calculation Algorithm
  54. Here is the complete pseudocode for the ratio algorithm:
  55. Slices = {S | S is 50 nodes of similar consensus capacity}
  56. for S in Slices:
  57. while exists node N in S with circ_chosen(N) < 7:
  58. fetch_slice_file(build_2hop_circuit(N, (exit in S)))
  59. for N in S:
  60. BW_measured(N) = MEAN(b | b is bandwidth of a stream through N)
  61. Bw_stddev(N) = STDDEV(b | b is bandwidth of a stream through N)
  62. Bw_avg(S) = MEAN(b | b = BW_measured(N) for all N in S)
  63. for N in S:
  64. Normal_Streams(N) = {stream via N | bandwidth >= BW_measured(N)}
  65. BW_Norm_measured(N) = MEAN(b | b is a bandwidth of Normal_Streams(N))
  66. Bw_net_avg(Slices) = MEAN(BW_measured(N) for all N in Slices)
  67. Bw_Norm_net_avg(Slices) = MEAN(BW_Norm_measured(N) for all N in Slices)
  68. for N in all Slices:
  69. Bw_net_ratio(N) = Bw_measured(N)/Bw_net_avg(Slices)
  70. Bw_Norm_net_ratio(N) = BW_Norm_measured(N)/Bw_Norm_net_avg(Slices)
  71. ResultRatio(N) = MAX(Bw_net_ratio(N), Bw_Norm_net_ratio(N))
  72. 7. Security implications
  73. The ratio filtering will deal with cases of sabotage by dropping
  74. both very slow outliers in stream average calculations, as well
  75. as dropping streams that used very slow nodes from the calculation
  76. of other nodes.
  77. This scheme will not address nodes that try to game the system by
  78. providing better service to scanners. The scanners can be detected
  79. at the entry by IP address, and at the exit by the destination fetch
  80. IP.
  81. Measures can be taken to obfuscate and separate the scanners' source
  82. IP address from the directory authority IP address. For instance,
  83. scans can happen offsite and the results can be rsynced into the
  84. authorities. The destination server IP can also change.
  85. Neither of these methods are foolproof, but such nodes can already
  86. lie about their bandwidth to attract more traffic, so this solution
  87. does not set us back any in that regard.
  88. 8. Parallelization
  89. Because each slice takes as long as 6 hours to complete, we will want
  90. to parallelize as much as possible. This will be done by concurrently
  91. running multiple scanners from each authority to deal with different
  92. segments of the network. Each scanner piece will continually loop
  93. over a portion of the network, outputting files of the form:
  94. node_id=<idhex> SP strm_bw=<BW_measured(N)> SP
  95. filt_bw=<BW_Norm_measured(N)> ns_bw=<CurrentConsensusBw(N)> NL
  96. The most recent file from each scanner will be periodically gathered
  97. by another script that uses them to produce network-wide averages
  98. and calculate ratios as per the algorithm in section 6. Because nodes
  99. may shift in capacity, they may appear in more than one slice and/or
  100. appear more than once in the file set. The most recently measured
  101. line will be chosen in this case.
  102. 9. Integration with Proposal 160
  103. The final results will be produced for the voting mechanism
  104. described in Proposal 160 by multiplying the derived ratio by
  105. the average published consensus bandwidth during the course of the
  106. scan, and taking the weighted average with the previous consensus
  107. bandwidth:
  108. Bw_new = Round((Bw_current * Alpha + Bw_scan_avg*Bw_ratio)/(Alpha + 1))
  109. The Alpha parameter is a smoothing parameter intended to prevent
  110. rapid oscillation between loaded and unloaded conditions. It is
  111. currently fixed at 0.333.
  112. The Round() step consists of rounding to the 3 most significant figures
  113. in base10, and then rounding that result to the nearest 1000, with
  114. a minimum value of 1000.
  115. This will produce a new bandwidth value that will be output into a
  116. file consisting of lines of the form:
  117. node_id=<idhex> SP bw=<Bw_new> NL
  118. The first line of the file will contain a timestamp in UNIX time()
  119. seconds. This will be used by the authority to decide if the
  120. measured values are too old to use.
  121. This file can be either copied or rsynced into a directory readable
  122. by the directory authority.