[tor-dev] Channel incoming queue

[Ian Goldberg]

On Sat, May 04, 2013 at 12:13:09PM -0400, MF Nowlan wrote:
> What you're saying about HOL blocking in the output queue for a relay makes sense if the receive window fills up, but I didn't explain how uTCP actually works. uTCP (and paired with uTLS) is a kernel patch that will expose to the application (in this case, Tor) segments that have arrived even if they are NOT the next logical segments in the stream. uTCP breaks TCP's delivery semantics, without affecting the on-the-wire protocol. Thus, it prevents HOL blocking from occurring in the TCP receive buffer. Now, it should be clear why the queue is important: I need to keep unordered cells in the queue if they are out of order within a circuit, but if they are the "next expected cell" for its circuit, then I can process it, regardless of whether it came in order or out of order from TCP.
> 
> I'm implementing this by changing the wire format to include a sequence number for each cell. The sequence number increments within a circuit. The receiver increments its "expected" sequence number with each in order arrival within a circuit.

Ah, that sounds similar to the code we wrote for Conflux (to appear at
PETS 2013).  In Conflux, streams can be split across mutiple circuits
that share an exit node.  Then cells on any given stream can arrive in
the wrong order at the endpoints (OP and exit), and must be reassembled.
Conflux is end-to-end at the stream level, rather than your hop-by-hop
at the circuit level, and of course addresses a different problem (what
happens if there are lots of low-bandwidth bridges, say because of Flash
Proxies, for example).

> It makes sense why the code is written as it is to process cells immediately, since, as you point out, the HOL issue has already been resolved by the time it gets to Tor. I was really just trying to manually inject some cell reordering to test Tor's ability to handle cells from different circuits out-of-order with respect to how TCP delivered them. But I'll skip this testing step and go to the next one, which is just running it atop uTCP/uTLS directly and using the incoming_queue to hold cells as needed.  I'll have to change a bit more of the code, particularly the asserts that the incoming_queue is empty after a call to channel_process_cells(…).

You also have to make sure to stay asleep, even if there are cells in
the input queue, I suppose.

   - Ian