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