[tor-bugs] #4086 [Analysis]: Compare performance of TokenBucketRefillInterval params in simulated network

[Tor Bug Tracker & Wiki]

#4086: Compare performance of TokenBucketRefillInterval params in simulated
network
-------------------------------------+--------------------------------------
 Reporter:  arma                     |          Owner:       
     Type:  task                     |         Status:  new  
 Priority:  normal                   |      Milestone:       
Component:  Analysis                 |        Version:       
 Keywords:  performance flowcontrol  |         Parent:  #4465
   Points:                           |   Actualpoints:       
-------------------------------------+--------------------------------------

Comment(by kevin):

 '''Summary'''
 I ran a set of preliminary experiments on ExperimenTor with different
 TokenBucketRefillInterval values. In particular, the experiments compare
 refilling tokens once every 1000 milliseconds (once per second), once
 every 100 milliseconds (ten times per second), and once every 10
 milliseconds (100 times per second). Also,  experiments are run with EWMA
 on and off, to identify any interactions between token bucket refill
 interval and circuit-level scheduling policy.

 '''Results'''
 [http://www.cs.uwaterloo.ca/~k4bauer/volatile/experiments-tokenbucket.pdf
 Results are available here] (Note that the file is too large to upload to
 this page).

 '''The network model'''
 The network topology consists of pairwise links with delays configured by
 sampling from the King data set [1].

 '''The Tor router and client model'''
 200 destination servers, 50 relays, 950 web clients, 50 bulk clients.
 Relay bandwidths are taken from a real consensus document and rate limits
 from the corresponding relay descriptors.

 The web clients "think" for a time between 1 and 30 seconds, selected
 uniformly at random, between 300 KiB file downloads.

 Bulk clients continuously download 5 MiB files with no think time between
 fetches. The destination servers are configured to be faster than any of
 the relays or clients, so they are guaranteed not to be the bandwidth
 bottleneck.

 All clients bandwidths are assigned by sampling from the Ookla Speedtest
 data [2].

 '''Performance metrics'''
 To measure the client's performance, I measured time-to-first-byte and
 overall download time (equivalently, time-to-last-byte).

 '''Router configurations'''
 Tested was refilling every 1000 ms (1/s), 100 ms (10/s), and 10 ms (100/s)
 under otherwise default Tor client and router configurations. I ran two
 sets of these experiments: one with CircuitPriorityHalfLife of 30 (EWMA),
 and one with 0 (RR).

 '''High level observations'''
 These results generally support the results obtained by Shadow, even
 though slightly different assumptions were made in constructing the
 experiments (which is in and of itself interesting!).

 The performance graphs look favorable for multiple refills per second.
 Also, you'll see the familiar "stairstep" behavior in the time-to-first-
 byte graphs when scheduling once per second. More details:

 '''Results for web clients'''
 The most frequent token refill interval (every 10 ms) seems to offer the
 best time-to-first-byte and overall download times for web clients,
 regardless of whether EWMA is enabled.

 '''Results for bulk clients'''
 Bulk clients don't show an obvious improvement in time-to-first-byte with
 shorter refill intervals. Interestingly, 100 ms seems to offer the worst
 performance for the bulk clients when EWMA is disabled.

 '''References'''
 [1] King data set. http://pdos.csail.mit.edu/p2psim/kingdata/
 [2] Ookla Netindex Data. http://www.netindex.com/

-- 
Ticket URL: <https://trac.torproject.org/projects/tor/ticket/4086#comment:7>
Tor Bug Tracker & Wiki <https://trac.torproject.org/>
The Tor Project: anonymity online