[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 robgjansen):

 I've run some experiments with [http://shadow.cs.umn.edu/cloud/ Shadow on
 EC2] and attached the __performance__ and __timing__ results. Before
 explaining things, please note that the Tor model used for these
 experiments is currently under development and may change in future
 versions of Shadow. I'd be happy to re-run the experiments once the model
 is "final" (for various definitions of final).

 '''The network''':
 Topology forms a complete graph between all countries. Bandwidth of nodes
 in each country taken from netindex.com data. Latency of links between
 countries taken from planetlab pairwise node ping measurements, where
 countries are clustered by geographical region. Packet loss and jitter
 also taken from netindex data.

 '''The nodes''':
 50 servers, 50 relays, 475 web clients, 25 bulk clients. Relay bandwidths
 are taken from real consensus and rate limits from real server
 descriptors. Web clients "think" for a time between 1 and 20 seconds,
 selected uniformly at random, between 320 KiB downloads. Bulk clients
 continuously download 5 MiB files. Servers have 100 MiB/s connections and
 are placed according to alexa's reported most popular servers.

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

 Overall, the performance graphs look favorable for multiple refills per
 second. Notice the weird "stairstep" behavior when scheduling once per
 second.

 '''Web performance''': Time to first byte of payload increases regardless
 of the intervals tested. Time to last byte seems to improve most when
 jumping to refilling every 10 ms (100/s). The difference in performance
 for EWMA vs RR seems insignificant for web downloaders.

 '''Bulk performance''': Time to first byte improves when scheduling with
 EWMA, but does not improve when scheduling with RR. This is mostly because
 RR is outperforming EWMA quite significantly to begin with. Similarly,
 time to last byte only improves when scheduling with EWMA, but actually
 hurts performance when scheduling with RR. Again, RR appears to beat out
 EWMA for bulk clients.

 '''Timing''' data is also attached. Experiment time is only slightly
 increased when refilling every 100 ms (10 times per second), but much more
 so when refilling every 10 ms (100 times per second). Time is ''insane''
 for 1 ms refills. Note that this is aggregate simulation time, which
 includes overhead for handling the simulations discrete events. I am
 working on [https://github.com/shadow/shadow/issues/40 tracking CPU time
 on a per-node basis], which should help us draw conclusions more
 concretely regarding timing.

 '''The verdict''':
 I am not giving one;) Although based on these graphs alone, it would
 appear Tor should be scheduling with RR and refilling every 10-100 ms
 (maybe 50?).

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