proposals/168-reduce-circwindow.txt

   1 Filename: 168-reduce-circwindow.txt
   2 Title: Reduce default circuit window
   3 Author: Roger Dingledine
   4 Created: 12-Aug-2009
   5 Status: Open
   6 Target: 0.2.2
   7
   8 0. History
   9
  10
  11 1. Overview
  12
  13   We should reduce the starting circuit "package window" from 1000 to
  14   101. The lower package window will mean that clients will only be able
  15   to receive 101 cells (~50KB) on a circuit before they need to send a
  16   'sendme' acknowledgement cell to request 100 more.
  17
  18   Starting with a lower package window on exit relays should save on
  19   buffer sizes (and thus memory requirements for the exit relay), and
  20   should save on queue sizes (and thus latency for users).
  21
  22   Lowering the package window will induce an extra round-trip for every
  23   additional 50298 bytes of the circuit. This extra step is clearly a
  24   slow-down for large streams, but ultimately we hope that a) clients
  25   fetching smaller streams will see better response, and b) slowing
  26   down the large streams in this way will produce lower e2e latencies,
  27   so the round-trips won't be so bad.
  28
  29 2. Motivation
  30
  31   Karsten's torperf graphs show that the median download time for a 50KB
  32   file over Tor in mid 2009 is 7.7 seconds, whereas the median download
  33   time for 1MB and 5MB are around 50s and 150s respectively. The 7.7
  34   second figure is way too high, whereas the 50s and 150s figures are
  35   surprisingly low.
  36
  37   The median round-trip latency appears to be around 2s, with 25% of
  38   the data points taking more than 5s. That's a lot of variance.
  39
  40   We designed Tor originally with the original goal of maximizing
  41   throughput. We figured that would also optimize other network properties
  42   like round-trip latency. Looks like we were wrong.
  43
  44 3. Design
  45
  46   Wherever we initialize the circuit package window, initialize it to
  47   101 rather than 1000. Reducing it should be safe even when interacting
  48   with old Tors: the old Tors will receive the 101 cells and send back
  49   a sendme ack cell. They'll still have much higher deliver windows,
  50   but the rest of their deliver window will go unused.
  51
  52   You can find the patch at arma/circwindow. It seems to work.
  53
  54 3.1. Why not 100?
  55
  56   Tor 0.0.0 through 0.2.1.19 have a bug where they only send the sendme
  57   ack cell after 101 cells rather than the intended 100 cells.
  58
  59   Once 0.2.1.19 is obsolete we can change it back to 100 if we like. But
  60   hopefully we'll have moved to some datagram protocol long before
  61   0.2.1.19 becomes obsolete.
  62
  63 3.2. What about stream packaging windows?
  64
  65   Right now the stream packaging windows start at 500. The goal was to
  66   set the stream window to half the circuit window, to provide a crude
  67   load balancing between streams on the same circuit. Once we lower
  68   the circuit packaging window, the stream packaging window basically
  69   becomes redundant.
  70
  71   We could leave it in -- it isn't hurting much in either case. Or we
  72   could take it out -- people building other Tor clients would thank us
  73   for that step. Alas, people building other Tor clients are going to
  74   have to be compatible with current Tor clients, so in practice there's
  75   no point taking out the stream packaging windows.
  76
  77 3.3. What about variable circuit windows?
  78
  79   Once upon a time we imagined adapting the circuit package window to
  80   the network conditions. That is, we would start the window small,
  81   and raise it based on the latency and throughput we see.
  82
  83   In theory that crude imitation of TCP's windowing system would allow
  84   us to adapt to fill the network better. In practice, I think we want
  85   to stick with the small window and never raise it. The low cap reduces
  86   the total throughput you can get from Tor for a given circuit. But
  87   that's a feature, not a bug.
  88
  89 4. Evaluation
  90
  91   How do we know this change is actually smart? It seems intuitive that
  92   it's helpful, and some smart systems people have agreed that it's
  93   a good idea (or said another way, they were shocked at how big the
  94   default package window was before).
  95
  96   To get a more concrete sense of the benefit, though, Karsten has been
  97   running torperf side-by-side on exit relays with the old package window
  98   vs the new one. The results are mixed currently -- it is slightly faster
  99   for fetching 40KB files, and slightly slower for fetching 50KB files.
 100
 101   I think it's going to be tough to get a clear conclusion that this is
 102   a good design just by comparing one exit relay running the patch. The
 103   trouble is that the other hops in the circuits are still getting bogged
 104   down by other clients introducing too much traffic into the network.
 105
 106   Ultimately, we'll want to put the circwindow parameter into the
 107   consensus so we can test a broader range of values once enough relays
 108   have upgraded.
 109
 110 5. Transition and deployment
 111
 112   We should put the circwindow in the consensus (see proposal 167),
 113   with an initial value of 101. Then as more exit relays upgrade,
 114   clients should seamlessly get the better behavior.
 115
 116   Note that upgrading the exit relay will only affect the "download"
 117   package window. An old client that's uploading lots of bytes will
 118   continue to use the old package window at the client side, and we
 119   can't throttle that window at the exit side without breaking protocol.
 120
 121   The real question then is what we should backport to 0.2.1. Assuming
 122   this could be a big performance win, we can't afford to wait until
 123   0.2.2.x comes out before starting to see the changes here. So we have
 124   two options as I see them:
 125   a) once clients in 0.2.2.x know how to read the value out of the
 126   consensus, and it's been tested for a bit, backport that part to
 127   0.2.1.x.
 128   b) if it's too complex to backport, just pick a number, like 101, and
 129   backport that number.
 130
 131   Clearly choice (a) is the better one if the consensus parsing part
 132   isn't very complex. Let's shoot for that, and fall back to (b) if the
 133   patch turns out to be so big that we reconsider.
 134