type

The type field describes the type of packet.

It can be one of:

ST_DATA = 0

regular data packet. Socket is in connected state and has datato send. An ST_DATA packet always has a data payload.

ST_FIN = 1

Finalize the connection. This is the last packet. It closesthe connection, similar to TCP FIN flag.This connection will never have a sequence number greater thanthe sequence number in this packet. The socket records this sequencenumber as

eof_pkt. This lets the socket wait for packets thatmight still be missing and arrive out of order even after receivingthe ST_FIN packet.

ST_STATE = 2

State packet. Used to transmit an ACK with no data. Packets that don'tinclude any payload do not increase the

seq_nr.

ST_RESET = 3

Terminate connection forcefully. Similar to TCP RST flag. The remotehost does not have any state for this connection. It is stale and shouldbe terminated.

ST_SYN = 4

Connect SYN. Similar to TCP SYN flag, this packet initiates a connection.The sequence number is initialized to 1. The connection ID is initializedto a random number. The syn packet is special, all subsequent packets senton this connection (except for re-sends of the ST_SYN) are sent with theconnection ID + 1. The connection ID is what the other end is expected touse in its responses.

When receiving an ST_SYN, the new socket should be initialized with theID in the packet header. The send ID for the socket should be initializedto the ID + 1. The sequence number for the return channel is initializedto a random number. The other end expects an ST_STATE packet (only an ACK)in response.

seq_nr

This is the sequence number of this packet. As opposed to TCP, uTP sequencenumbers are not referring to bytes, but packets. The sequence number tells theother end in which order packets should be served back to the application layer.

ack_nr

This is the sequence number the sender of the packet last received in the otherdirection.

connection setup

Here is a diagram illustrating the exchanges and states to initiatea connection. The c.* refers to a state in the socket itself, pkt.*refers to a field in the packet header.

initiating endpoint                           accepting endpoint          | c.state = CS_SYN_SENT                         |          | c.seq_nr = 1                                  |          | c.conn_id_recv = rand()                       |          | c.conn_id_send = c.conn_id_recv + 1           |          |                                               |          |                                               |          | ST_SYN                                        |          |   seq_nr=c.seq_nr++                           |          |   ack_nr=*                                    |          |   conn_id=c.rcv_conn_id                       |          | >-------------------------------------------> |          |             c.receive_conn_id = pkt.conn_id+1 |          |             c.send_conn_id = pkt.conn_id      |          |             c.seq_nr = rand()                 |          |             c.ack_nr = pkt.seq_nr             |          |             c.state = CS_CONNECTED            |          |                                               |          |                                               |          |                                               |          |                                               |          |                     ST_STATE                  |          |                       seq_nr=c.seq_nr++       |          |                       ack_nr=c.ack_nr         |          |                       conn_id=c.send_conn_id  |          | <------------------------------------------<  |          | c.state = CS_CONNECTED                        |          | c.ack_nr = pkt.seq_nr                         |          |                                               |          |                                               | connection established     .. ..|.. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..|.. ..          |                                               |          |                                               |          | ST_DATA                                       |          |   seq_nr=c.seq_nr++                           |          |   ack_nr=c.ack_nr                             |          |   conn_id=c.conn_id_send                      |          | >-------------------------------------------> |          |                         c.ack_nr = pkt.seq_nr |          |                                               |          |                                               |          |                                               |          |                     ST_DATA                   |          |                       seq_nr=c.seq_nr++       |          |                       ack_nr=c.ack_nr         |          |                       conn_id=c.send_conn_id  |          | <------------------------------------------<  |          | c.ack_nr = pkt.seq_nr                         |          |                                               |          |                                               |          V                                               V

Connections are identified by their conn_id header. If the connection ID of a newconnection collides with an existing connection, the connection attempt will fails, sincethe ST_SYN packet will be unexpected in the existing stream, and ignored.

packet loss

If the packet with sequence number (seq_nr - cur_window) has not been acked(this is the oldest packet in the send buffer, and the next one expected to be acked),but 3 or more packets have been acked past it (through SelectiveACK), the packet is assumed to have been lost. Similarly, when receiving 3 duplicateacks, ack_nr + 1 is assumed to have been lost (if a packet with that sequence numberhas been sent).

This is applied to selective acks as well. Each packet that is acked in the selectiveack message counts as one duplicate ack, which, if it 3 or more, should trigger are-send of packets that had at least 3 packets acked after them.

When a packet is lost, the max_window is multiplied by 0.78. TCP multiplies by0.5, but since this is a much less likely event in uTP, and since the uTP ramp-upis slower than TCP, this is a reasonable optimization.

timeouts

Every packet that is ACKed, either by falling in the range (last_ack_nr, ack_nr]or by explicitly being acked by a Selective ACK message, should be used to updatean rtt (round trip time) and rtt_var (rtt variance) measurement.last_ack_nr here is the last ack_nr received on the socket before the current packet,and ack_nr is the field in the currently received packet.

The rtt and rtt_var is only updated for packets that were sent only once.This avoids problems with figuring out which packet was acked, the first or thesecond one.

rtt and rtt_var are calculated by the following formula, every time a packetis ACKed:

delta = rtt - packet_rttrtt_var += (abs(delta) - rtt_var) / 4;rtt += (packet_rtt - rtt) / 8;

The default timeout for packets associated with the socket is also updated every timertt and rtt_var is updated. It is set to:

timeout = max(rtt + rtt_var * 4, 500);

Where timeout is specified in milliseconds. i.e. the minimum timeout for a packet is1/2 second.

Every time a socket sends or receives a packet, it updates its timeout counter. Ifno packet has arrived within timeout number of milliseconds from the lasttimeout counter reset, the socket triggers a timeout. It will set its packet_sizeand max_window to the smallest packet size (150 bytes). This allows it to sendone more packet, and this is how the socket gets started again if the window sizegoes down to zero.

The initial timeout is set to 1000 milliseconds, and later updated according tothe formula above. For every packet consecutive subsequent packet that times out,the timeout is doubled.

packet sizes

In order to have as little impact as possible on slow congested links, uTP adjustsits packet size down to as small as 150 bytes per packet. Using packets that smallhas the benefit of not clogging a slow up-link, with long serialization delay.The cost of using packets that small is that the overhead from the packet headersbecome significant. At high rates, large packet sizes are used, at slow rates,small packet sizes are used.

congestion control

The overall goal of the uTP congestion control is to use one way buffer delay as themain congestion measurement, as well as packet loss, like TCP. The point is to avoidrunning with full send buffers whenever data is being sent. This is specifically aproblem for DSL/Cable modems, where the send buffer in the modem often has room formultiple seconds worth of data. The ideal buffer utilization for uTP (or any backgroundtraffic protocol) is to run at 0 bytes buffer utilization. i.e. any other trafficcan at any time send without being obstructed by background traffic clogging up thesend buffer. In practice, the uTP target delay is set to 100 ms. Each socket aims tonever see more than 100 ms delay on the send link. If it does, it will throttle back.

This effectively makes uTP yield to any TCP traffic.

This is achieved by including a high resolution timestamp in every packet that's sentover uTP, and the receiving end calculates the difference between its own high resolutiontimer and the timestamp in the packet it received. This difference is then fed back to theoriginal sender of the packet (timestamp_difference_microseconds). This value is not meaningfulas an absolute value. The clocks in the machines are most likely not synchronized,especially not down to microsecond resolution, and the time the packet is in transit isalso included in the difference of these timestamps. However, the value is useful incomparison to previous values.

Each socket keeps a sliding minimum of the lowest value for the last two minutes. This valueis called base_delay, and is used as a baseline, the minimum delay between the hosts.When subtracting the base_delay from the timestamp difference in each packet you get ameasurement of the current buffering delay on the socket. This measurement is called our_delay.It has a lot of noise it it, but is used as the driver to determine whether to increase ordecrease the send window (which controls the send rate).

The CCONTROL_TARGET is the buffering delay that the uTP accepts on the up-link. Currently thedelay target is set to 100 ms. off_target is how far the actual measured delay is from thetarget delay (calculated from CCONTROL_TARGET - our_delay).

The window size in the socket structure specifies the number of bytes we may have in flight(not acked) in total, on the connection. The send rate is directly correlated to this windowsize. The more bytes in flight, the faster send rate. In the code, the window size is calledmax_window. Its size is controlled, roughly, by the following expression:

delay_factor = off_target / CCONTROL_TARGET;window_factor = outstanding_packet / max_window;scaled_gain = MAX_CWND_INCREASE_PACKETS_PER_RTT * delay_factor * window_factor;

Where the first factor scales the off_target to units of target delays.

The scaled_gain is then added to the max_window:

max_window += scaled_gain;

This will make the window smaller if off_target is greater than 0 and grow the window ifoff target is less than 0.

If max_window becomes less than 0, it is set to 0. A window size of zero means that thesocket may not send any packets. In this state, the socket will trigger a timeout andforce the window size to one packet size, and send one packet. See the section on timeoutsfor more information.