Effect of Tor window size on performance

[Csaba Kiraly]

Roger Dingledine wrote:
> On Wed, Feb 04, 2009 at 10:25:31AM +0100, Csaba Kiraly wrote:
>   
>> http://disi.unitn.it/locigno/preprints/TR-DISI-08-041.pdf
>>     
> [snip]
>   
[snip]
>>> So the next question is an implementation one. Right now the window sizes
>>> are hard-coded at both ends. I've been meaning to extend the protocol
>>> so sendme cells have a number in them, and so the initial window sizes
>>> are specified in the 'create' and 'created' cells for circuits and the
>>> 'begin' and 'connected' cells for streams. But we haven't really fleshed
>>> out the details of those designs, or how they could be phased in and still
>>> handle clients and relays that don't use (or know about) the numbers.
>>>
>>> So the big deployment question is: is it worth it to work on a design
>>> for the above, and then either shrink the default window sizes or do
>>> something smarter like variable window sizes, or should we just be
>>> patient until a UDP-based solution is more within reach?
>>>
>>> One answer is that if you were interested in working on a design proposal
>>> and patch, it would be much more likely to get implemented. :)
>>>  
>>>       
>> We are doing verifications on this. Our lab experiments (the ones in the 
>> tech report) show that there is a huge gain on the user side in delays, 
>> while throughput is untouched. Throughput is capped with a static window 
>> size, but I think the cap can be chosen better than what it is now. 
>> There should also be a big gain in the memory consumption of ORs, 
>> although we didn't measure it yet. Since the Tor network is kind of 
>> overloaded all the time, memory usage should decrease almost linearly 
>> with the window size.
>>
>> Currently we are verifying one-side modification of the circuit, i.e. 
>> whether one side of the connection can reduce the widow size on its own, 
>> without explicitly notifying the other side.  From the  code it seems to 
>> me that this will work, and if so, phasing in a smaller window size in a 
>> new release should not be a problem.
>>     
>
> Hey, that's a really good point. We don't have to change much code at
> all if we want to use a *smaller* package window than we are allowed. We
> simply pretend that the package window started out smaller, and either
> side can do that independently!
>
> Do you have a patch in mind for this? It would seem that if we
> change init_circuit_base() so it sets circ->package_window to some
> lower number x, and change connection_exit_begin_conn() so it sets
> nstream->package_window to some even lower number y, that should be it.
> The client side will send sendme's like normal, and the only difference
> is that no more than y cells will ever be 'in flight' for a given stream.
>   
Its not even that "complicated", you already have the defines in or.h :-)
#define CIRCWINDOW_START 1000
#define CIRCWINDOW_INCREMENT 100
#define STREAMWINDOW_START 500
#define STREAMWINDOW_INCREMENT 50

In our test code we've also changed some other things to have a better 
control of the test environment, but the modification needed is only to 
change these.

> So here are the questions we need to consider:
>
> 1) What values of x and y are best? Presumably as we reduce them from
> 1000 and 500, the performance gets better, but at some point they become
> so low that performance gets worse (because each round-trip through the
> network takes extra time). As sample numbers, if we start x at 100 and
> y at 50, then we need another round-trip for any stream that delivers
> more than 24900 bytes, and/or for every 49800 bytes on the circuit.
> Should our choices be influenced by the 'typical' Tor stream that the
> network is seeing right now? (Not that we have those numbers, but maybe
> we should get them.) What other factors are there?
>   
Note that changing y would also change our overhead. Currently with 100 
it is 1% (1 send_me sent back for every 100 cells received). This extra 
traffic is on the "backward" path, so in the typical download scenario, 
the overhead would be on the ADSL uplink. Increasing it too much would 
be bad, but I think 5% is still fine.
What points in the direction of reducing y is that with a lower y we 
have less burstiness in the traffic pumped in the circuit by the exit 
node, which typically improves performance.

Another thing to consider is the x/y ratio. Currently it is 10. Lets see 
some considerations:
- 2 seems a bit low: Say A and B are the two ends of the circuit and 
traffic flows mainly from A to B. Assuming that one-way delays are equal 
in both directions (this is reasonable since we have asymmetry only in 
the A-B traffic, but overlay links of the same path are used by other 
circuits in the reverse direction as well), the send_me cell is sent 
from B when half of the cells arrives. The send_me arrives back to A 
when all the cells have arrived to B. At this point A can start pumping 
in new cells, which might be a bit late.
- 10 might be a bit large, I don't think we have such asymmetries in the 
network, between OR nodes that justify such a high factor.

I think 500 is a safe bet for x to start with, but from our measurements 
it seems that even 200 would do fine with nice performance improvements. 
Of course we are working on more measurements to be on the safe side.

> 2) What are the effects of this patch in a hybrid Tor network? If some
> exit relays use package windows of 1000, and newer ones use package
> windows of 100, will the newer ones get 'clobbered' by the old ones?
> That is, should we expect to see even more slow-down in the network
> while the relays transition? Is there anything we can do about that,
> since it will take a year or more for everybody to transition?
>   
We've already done measurements on what we call the asymmetric scenario, 
i.e. where the client is the old one and the exit node is the new one. 
It seems that performance improvements are there. We are currently 
thinking of some "fairness" tests; we have some ideas, but it is not yet 
exactly clear how to perform them. Anyway, from current numbers it seems 
that the 'clobbered' ones would be the old ones, so at least we have one 
more incentive for people to change version :-)

Note that in this scenario y is practically 100 (client side matters), 
while have done tests with x (server side) from 10000 down to 200. We 
will add 100, just to see how things go bad with that.
> 3) Should we reduce the package_windows on the client side too? It would
> be easy to do. How do we decide whether it's worth it?
>   
I think it would be better to do it symmetrically, not differentiating 
between the two sides. On one hand, with the typical client use, i.e. 
web browsing, upload traffic is small so the value does not really 
matter. Browsers do some pipelining of HTTP requests in 1.1,  but that 
should still be small amount of data. On the other hand, if a "client" 
starts to do some nasty things, or just uploads a file, a lower window 
value should be beneficial,  just like in the exit node's case. I don't 
think there are any asymmetries in the circuits. As said before, they 
are bottlenecked because of the OR-OR connections traversed, and theses 
are bottlenecked both ways because of the many circuits passing through 
them.
> Anything I missed?
>
> Thanks!
> --Roger
>   
I think thats all. We are doing some more measurements, and coming up 
with the results soon. As I said, the code modification is at the level 
of changing defines and simple recompile, but we should better verify 
more scenarios before making the change.
Thanks for the questions and ideas!
Csaba