commit 6af9a2d4b4d6f6f1283d2049b4e9145bca9d1f3f Author: Roger Dingledine arma@torproject.org Date: Sun Nov 4 18:29:03 2012 -0500
add proposal 213 (remove stream-level sendmes from the design) --- proposals/213-remove-stream-sendmes.txt | 122 +++++++++++++++++++++++++++++++ 1 files changed, 122 insertions(+), 0 deletions(-)
diff --git a/proposals/213-remove-stream-sendmes.txt b/proposals/213-remove-stream-sendmes.txt new file mode 100644 index 0000000..d8d517d --- /dev/null +++ b/proposals/213-remove-stream-sendmes.txt @@ -0,0 +1,122 @@ +Filename: 213-remove-stream-sendmes.txt +Title: Remove stream-level sendmes from the design +Author: Roger Dingledine +Created: 4-Nov-2012 +Status: Open + +1. Motivation + + Tor uses circuit-level sendme cells to handle congestion / flow + fairness at the circuit level, but it has a second stream-level + flow/congestion/fairness layer under that to share a given circuit + between multiple streams. + + The circuit-level flow control, or something like it, is needed + because different users are competing for the same resources. But the + stream-level flow control has a different threat model, since all the + streams belong to the same user. + + When the circuit has only one active stream, the downsides are a) + that we waste 2% of our bandwidth sending stream-level sendmes, and b) + because of the circuit-level and stream-level window parameters we + picked, we end up sending only half the cells we might otherwise send. + + When the circuit has two active streams, they each get to send 500 + cells for their window, because the circuit window is 1000. We still + spend the 2% overhead. + + When the circuit has three or more active streams, they're all typically + limited by the circuit window, since the stream-level window won't + kick in. We still spend the 2% overhead though. And depending on their + sending pattern, we could experience cases where a given stream might + be able to send more data on the circuit, but it chooses not to because + its stream-level window is empty. + + More generally, we don't have a good handle on the interactions between + all the layers of congestion control in Tor. It would behoove us to + simplify in the case where we're not clear on what it buys us. + +2. Design + + We should strip all aspects of this stream-level flow control from + the Tor design and code. + +2.1. But doesn't having a lower stream window than circuit window save + room for new streams? + + It could be that a feature of the stream window is that there's always + space in the circuit window for another begin cell, so new streams + will open faster than otherwise. But first, if there are two or more + active streams going, there won't be any extra space. Second, since + begin cells are client-to-exit, and typical circuits don't fill their + outbound circuit windows very often anyway, and also since we're hoping + to move to a world where we isolate more activities between circuits, + I'm not inclined to worry much about losing this maybe-feature. + + See also proposal 168, "reduce default circuit window" -- it's + interesting to note that proposal 168 was unknowingly dabbling in + exactly this question, since reducing the default circuit window to + 500 or less made stream windows moot. It might be worth resurrecting + the proposal 168 experiments once this proposal is implemented. + +2.2. If we dump stream windows, we're effectively doubling them. + + Right now the circuit window starts at 1000, and the stream window + starts at 500. So if we just rip out stream windows, we'll effectively + change the stream window default to 1000, doubling the amount of data + in flight and potentially clogging up the network more. + + We could either live with that, or we could change the default circuit + window to 500 (which is easy to do even in a backward compatible way, + since the edge connection can simply choose to not send as many cells). + +3. Evaluation + + It would be wise to have some plan for making sure we didn't screw + up the network too much with this change. The main trouble there is + that torperf et al only do one stream at a time, so we really have no + good baseline, or measurement tools, to capture network performance + for multiple parallel streams. + + Maybe we should resolve task 7168 before the transition, so we're + more prepared. + +4. Transition + + Option one is to do a two-phase transition. In the first phase, + edges stop enforcing the deliver window (i.e. stop closing circuits + when the stream deliver goes negative, but otherwise they send and + receive stream-level sendmes as now). In the second phase (once all + old versions are gone), we can start disobeying the deliver window, + and also stop sending stream-level sendmes back. + + That approach takes a while before it will matter. As an optimization, + since clients can know which relay versions support the new behavior, + we could have relays interpret violating the deliver window as signaling + support for removed stream-level sendmes: the relay would then stop + sending or expecting sendmes. That optimization is somewhat klunky + though, first because web-browsing clients don't generally finish out + a stream window in the upstream direction (so the klunky trick will + probably never happen by accident), and second because if we lower + the circuit window to 500 (see Sec 2.2), there's now no way to violate + stream deliver windows. + + Option two is to introduce another relay cell type, which the client + sends before opening any streams to let the other side know that + it shouldn't use or expect stream-level sendmes. A variation here + is to extend either the create cell or the begin cell (ha -- and they + thought I was crazy when I included the explicit \0 at the end of the + current begin cell payload), so we can specify our circuit preferences + without any extra overhead. + + Option three is to wait until we switch to a new circuit protocol + (e.g. when we move to ntor or ace), and use that as the signal to + drop stream-level sendmes from the design. And hey, if we're lucky, + by then we'll have sorted out the n23 questions (see ticket 4506) + and we might be dumping circuit-level sendmes at that point too. + + Options two or three seem way better than option one. + + And since it's not super-urgent, I suggest we hold off on option two + to see if option three makes sense. +