| blob | d97c45e9094cb509ff741131613f401f96f6884a |
1 Filename: 174-optimistic-data-server.txt
2 Title: Optimistic Data for Tor: Server Side
3 Author: Ian Goldberg
4 Created: 2-Aug-2010
5 Status: Open
7 Overview:
9 When a SOCKS client opens a TCP connection through Tor (for an HTTP
10 request, for example), the query latency is about 1.5x higher than it
11 needs to be. Simply, the problem is that the sequence of data flows
12 is this:
14 1. The SOCKS client opens a TCP connection to the OP
15 2. The SOCKS client sends a SOCKS CONNECT command
16 3. The OP sends a BEGIN cell to the Exit
17 4. The Exit opens a TCP connection to the Server
18 5. The Exit returns a CONNECTED cell to the OP
19 6. The OP returns a SOCKS CONNECTED notification to the SOCKS client
20 7. The SOCKS client sends some data (the GET request, for example)
21 8. The OP sends a DATA cell to the Exit
22 9. The Exit sends the GET to the server
23 10. The Server returns the HTTP result to the Exit
24 11. The Exit sends the DATA cells to the OP
25 12. The OP returns the HTTP result to the SOCKS client
27 Note that the Exit node knows that the connection to the Server was
28 successful at the end of step 4, but is unable to send the HTTP query to
29 the server until step 9.
31 This proposal (as well as its upcoming sibling concerning the client
32 side) aims to reduce the latency by allowing:
33 1. SOCKS clients to optimistically send data before they are notified
34 that the SOCKS connection has completed successfully
35 2. OPs to optimistically send DATA cells on streams in the CONNECT_WAIT
36 state
37 3. Exit nodes to accept and queue DATA cells while in the
38 EXIT_CONN_STATE_CONNECTING state
40 This particular proposal deals with #3.
42 In this way, the flow would be as follows:
44 1. The SOCKS client opens a TCP connection to the OP
45 2. The SOCKS client sends a SOCKS CONNECT command, followed immediately
46 by data (such as the GET request)
47 3. The OP sends a BEGIN cell to the Exit, followed immediately by DATA
48 cells
49 4. The Exit opens a TCP connection to the Server
50 5. The Exit returns a CONNECTED cell to the OP, and sends the queued GET
51 request to the Server
52 6. The OP returns a SOCKS CONNECTED notification to the SOCKS client,
53 and the Server returns the HTTP result to the Exit
54 7. The Exit sends the DATA cells to the OP
55 8. The OP returns the HTTP result to the SOCKS client
57 Motivation:
59 This change will save one OP<->Exit round trip (down to one from two).
60 There are still two SOCKS Client<->OP round trips (negligible time) and
61 two Exit<->Server round trips. Depending on the ratio of the
62 Exit<->Server (Internet) RTT to the OP<->Exit (Tor) RTT, this will
63 decrease the latency by 25 to 50 percent. Experiments validate these
64 predictions. [Goldberg, PETS 2010 rump session; see
65 https://thunk.cs.uwaterloo.ca/optimistic-data-pets2010-rump.pdf ]
67 Design:
69 The current code actually correctly handles queued data at the Exit; if
70 there is queued data in a EXIT_CONN_STATE_CONNECTING stream, that data
71 will be immediately sent when the connection succeeds. If the
72 connection fails, the data will be correctly ignored and freed. The
73 problem with the current server code is that the server currently
74 drops DATA cells on streams in the EXIT_CONN_STATE_CONNECTING state.
75 Also, if you try to queue data in the EXIT_CONN_STATE_RESOLVING state,
76 bad things happen because streams in that state don't yet have
77 conn->write_event set, and so some existing sanity checks (any stream
78 with queued data is at least potentially writable) are no longer sound.
80 The solution is to simply not drop received DATA cells while in the
81 EXIT_CONN_STATE_CONNECTING state. Also do not send SENDME cells in this
82 state, so that the OP cannot send more than one window's worth of data
83 to be queued at the Exit. Finally, patch the sanity checks so that
84 streams in the EXIT_CONN_STATE_RESOLVING state that have buffered data
85 can pass.
87 If no clients ever send such optimistic data, the new code will never be
88 executed, and the behaviour of Tor will not change. When clients begin
89 to send optimistic data, the performance of those clients' streams will
90 improve.
92 After discussion with nickm, it seems best to just have the server
93 version number be the indicator of whether a particular Exit supports
94 optimistic data. (If a client sends optimistic data to an Exit which
95 does not support it, the data will be dropped, and the client's request
96 will fail to complete.) What do version numbers for hypothetical future
97 protocol-compatible implementations look like, though?
99 Security implications:
101 Servers (for sure the Exit, and possibly others, by watching the
102 pattern of packets) will be able to tell that a particular client
103 is using optimistic data. This will be discussed more in the sibling
104 proposal.
106 On the Exit side, servers will be queueing a little bit extra data, but
107 no more than one window. Clients today can cause Exits to queue that
108 much data anyway, simply by establishing a Tor connection to a slow
109 machine, and sending one window of data.
111 Specification:
113 tor-spec section 6.2 currently says:
115 The OP waits for a RELAY_CONNECTED cell before sending any data.
116 Once a connection has been established, the OP and exit node
117 package stream data in RELAY_DATA cells, and upon receiving such
118 cells, echo their contents to the corresponding TCP stream.
119 RELAY_DATA cells sent to unrecognized streams are dropped.
121 It is not clear exactly what an "unrecognized" stream is, but this last
122 sentence would be changed to say that RELAY_DATA cells received on a
123 stream that has processed a RELAY_BEGIN cell and has not yet issued a
124 RELAY_END or a RELAY_CONNECTED cell are queued; that queue is processed
125 immediately after a RELAY_CONNECTED cell is issued for the stream, or
126 freed after a RELAY_END cell is issued for the stream.
128 The earlier part of this section will be addressed in the sibling
129 proposal.
131 Compatibility:
133 There are compatibility issues, as mentioned above. OPs MUST NOT send
134 optimistic data to Exit nodes whose version numbers predate (something).
135 OPs MAY send optimistic data to Exit nodes whose version numbers match
136 or follow that value. (But see the question about independent server
137 reimplementations, above.)
139 Implementation:
141 Here is a simple patch. It seems to work with both regular streams and
142 hidden services, but there may be other corner cases I'm not aware of.
143 (Do streams used for directory fetches, hidden services, etc. take a
144 different code path?)
146 diff --git a/src/or/connection.c b/src/or/connection.c
147 index 7b1493b..f80cd6e 100644
148 --- a/src/or/connection.c
149 +++ b/src/or/connection.c
150 @@ -2845,7 +2845,13 @@ _connection_write_to_buf_impl(const char *string, size_t len,
151 return;
152 }
154 - connection_start_writing(conn);
155 + /* If we receive optimistic data in the EXIT_CONN_STATE_RESOLVING
156 + * state, we don't want to try to write it right away, since
157 + * conn->write_event won't be set yet. Otherwise, write data from
158 + * this conn as the socket is available. */
159 + if (conn->state != EXIT_CONN_STATE_RESOLVING) {
160 + connection_start_writing(conn);
161 + }
162 if (zlib) {
163 conn->outbuf_flushlen += buf_datalen(conn->outbuf) - old_datalen;
164 } else {
165 @@ -3382,7 +3388,11 @@ assert_connection_ok(connection_t *conn, time_t now)
166 tor_assert(conn->s < 0);
168 if (conn->outbuf_flushlen > 0) {
169 - tor_assert(connection_is_writing(conn) || conn->write_blocked_on_bw ||
170 + /* With optimistic data, we may have queued data in
171 + * EXIT_CONN_STATE_RESOLVING while the conn is not yet marked to writing.
172 + * */
173 + tor_assert(conn->state == EXIT_CONN_STATE_RESOLVING ||
174 + connection_is_writing(conn) || conn->write_blocked_on_bw ||
175 (CONN_IS_EDGE(conn) && TO_EDGE_CONN(conn)->edge_blocked_on_circ));
176 }
178 diff --git a/src/or/relay.c b/src/or/relay.c
179 index fab2d88..e45ff70 100644
180 --- a/src/or/relay.c
181 +++ b/src/or/relay.c
182 @@ -1019,6 +1019,9 @@ connection_edge_process_relay_cell(cell_t *cell, circuit_t *circ,
183 relay_header_t rh;
184 unsigned domain = layer_hint?LD_APP:LD_EXIT;
185 int reason;
186 + int optimistic_data = 0; /* Set to 1 if we receive data on a stream
187 + that's in the EXIT_CONN_STATE_RESOLVING
188 + or EXIT_CONN_STATE_CONNECTING states.*/
190 tor_assert(cell);
191 tor_assert(circ);
192 @@ -1038,9 +1041,20 @@ connection_edge_process_relay_cell(cell_t *cell, circuit_t *circ,
193 /* either conn is NULL, in which case we've got a control cell, or else
194 * conn points to the recognized stream. */
196 - if (conn && !connection_state_is_open(TO_CONN(conn)))
197 - return connection_edge_process_relay_cell_not_open(
198 - &rh, cell, circ, conn, layer_hint);
199 + if (conn && !connection_state_is_open(TO_CONN(conn))) {
200 + if ((conn->_base.state == EXIT_CONN_STATE_CONNECTING ||
201 + conn->_base.state == EXIT_CONN_STATE_RESOLVING) &&
202 + rh.command == RELAY_COMMAND_DATA) {
203 + /* We're going to allow DATA cells to be delivered to an exit
204 + * node in state EXIT_CONN_STATE_CONNECTING or
205 + * EXIT_CONN_STATE_RESOLVING. This speeds up HTTP, for example. */
206 + log_warn(domain, "Optimistic data received.");
207 + optimistic_data = 1;
208 + } else {
209 + return connection_edge_process_relay_cell_not_open(
210 + &rh, cell, circ, conn, layer_hint);
211 + }
212 + }
214 switch (rh.command) {
215 case RELAY_COMMAND_DROP:
216 @@ -1090,7 +1104,9 @@ connection_edge_process_relay_cell(cell_t *cell, circuit_t *circ,
217 log_debug(domain,"circ deliver_window now %d.", layer_hint ?
218 layer_hint->deliver_window : circ->deliver_window);
220 - circuit_consider_sending_sendme(circ, layer_hint);
221 + if (!optimistic_data) {
222 + circuit_consider_sending_sendme(circ, layer_hint);
223 + }
225 if (!conn) {
226 log_info(domain,"data cell dropped, unknown stream (streamid %d).",
227 @@ -1107,7 +1123,9 @@ connection_edge_process_relay_cell(cell_t *cell, circuit_t *circ,
228 stats_n_data_bytes_received += rh.length;
229 connection_write_to_buf(cell->payload + RELAY_HEADER_SIZE,
230 rh.length, TO_CONN(conn));
231 - connection_edge_consider_sending_sendme(conn);
232 + if (!optimistic_data) {
233 + connection_edge_consider_sending_sendme(conn);
234 + }
235 return 0;
236 case RELAY_COMMAND_END:
237 reason = rh.length > 0 ?
239 Performance and scalability notes:
241 There may be more RAM used at Exit nodes, as mentioned above, but it is
242 transient.