Sequencing

#How Sequence Numbers are assigned

###Why sequence numbers? Tor is typically a stream-like protocol: bits on in on one side, and the come out in order (thanks to TCP) on the other side. htpt is not like this. There are many transient connections as it is requesting data over HTTP, where each request requires its own connection. As such, htpt needs some way of reordering transmitted segments.

The obvious way to do this is with a sequence number and a simple sliding window. The smallest maximum amount of data in a particular encoding scheme is expected to be on the order of 36-bytes in a frame - URL encoding of 40 bytes, with 4 control bytes - so using a 16-bit sequence number and a 15-bit sliding window, htpt is able to have at least 11 MB outstanding (32768 * 36). As such, the sliding window can be smaller and still allow for significant amounts of data outstanding.

###Requesting sequence numbers Since all the Encoding Modules are independent, having a centralized location for the Sequence Numbers is necessary. To accomplish this, the Encoding Decision Module maintains the sequence numbers. They are requested using the GetSequenceAndIncrement() function.

###How everything stays in order Thankfully, the Upstream connection from Tor can be considered a byte stream, which makes sequencing significantly easier.

Take the case where there is 1000 bytes being sent to the URL Encoding Module. Since it can only encode roughly 40 bytes per frame, it will need at least 25 frames to encode this, requiring at least 25 sequence numbers. These are requested individually, not in bulk, so it must be the only Encoding Module requesting sequence numbers at that time. But, in htpt's case, this comes for free.

Since there is only one send thread, there's no extra work. The 1000 bytes is sent down the the URL Encoding Module, the Encoding Module takes the first 40 bytes, requests a Sequence Number, packages it, and sends it. It then takes the next 40 bytes, and repeats the process. After the 25 or so frames, control finally returns to the Encoding Decision Module, which can finally send the next chunk of data.

###Reassembly Reassembly happens on the remote side, based on the sequence numbers. This happens after decoding, when reordering happens. If a segment comes in out of order, it is buffered, and sent to Tor after the previous segments come in. This is very similar to what happens in TCP.