Computers can’t be fully advised about whole network performance as its different parts may be in different conditions. Some of them closer, some of them farther. And initially, you can not predict the condition of the network device you are connecting to.

TCP protocol relies on metric called RTT(Round Trip Time), which is used to determine remote device performance, basically it is just a time that packet needs to travel from client to server. But what’s up on client side? Yes, client sends a packet and at that time a new timer is started. This timer associated exactly with this packet and it counts till… it not receives the segment in response. But what happens if initial one is lost, how long should we wait?

Okay, there are some algorithms those can help to answer to this question and one of them is standardized under RFC 6298(it’s a revision of RFC 2988). It explicitly defines algorithm for retransmission of the packets and estimation of the RTT. Of course there are some assumptions, requirements and some of the must be required to be rfc-compliant and for others there may be a flexibility to choose. It’s better to refer to source RFC and exactly the in-place use of the key words, like “MUST”, “REQUIRED”, “SHALL” and etc. For simplicity, there will be no exact links to them.

Returning back to initial question, we should wait till the packet has not received in a desired time and then retransmit it. This time delay after those we should retransmit initial packet is called RTO(retransmission timeout).

Jacobson algorithm for RTT variance estimation

TCP sender maintains two state variables - $latex SRTT$ (Smoothed Round-Trip Time) and $latex RTT_{VAR}$ (Round Trip Time variation). The use of latter one variable, $latex RTT_{VAR}$, was originated by Van Jacobson [Jac88]. This is something different from Jacobson TCP header compression algorithm.

First measurement

On the first RTT measurement $latex R$ host must update estimates :

$latex SRTT \leftarrow R \\ RTT_{VAR} \leftarrow R/2 \\ RTO \leftarrow SRTT + max (G, K*RTT_{VAR}) \\ $

where $latex K = 4$ and $latex G$ is a granularity of clock in a seconds.

Subsequent RTT measurements

On subsequent $latex R’$ measurements the following estimates are used :

\[ RTT_{VAR} \leftarrow (1 - beta) * RTT_{VAR} + beta * |SRTT - R'| \\ SRTT \leftarrow (1 - alpha) * SRTT + alpha * R' \\ RTO \leftarrow SRTT + max (G, K*RTT_{VAR}) \]

$latex alpha$ and $latex beta$ are constants that show how “responsive” would be $latex SRTT$ and $latex RTT_{VAR}$. For example, formula for $latex SRTT$ estimation says, that it should take into account not only the new measurement, but also all previous measurements. For factor $alpha$ closer to 1 $SRTT$ will be much more responsive for network congestion problem.

RFC 6298 recommends to use $latex alpha = 1/8$ and $latex beta = 1/4$.

Also if $latex RTO < 1$, then it is better to round it to 1 second. The upper bound for $latex RTO$ value is 60 seconds.

Karn's algorithm

Process of accurate measurement of RTT face with difficulties when retransmission occurs. So, suppose we have retransmitted packet that have not been acknowledged. After that time we cannot completely know which of the packets will be acknowledged - initial one or subsequent retransmitted. Phil Karn proposed an idea for RTT estimation - ignore packets that have been retransmitted and rely only on packets that have been sent once and been acknowledged.

Proposed idea has one disadvantage. Consider when for some reason RTT estimation value have not been updated – for example all subsequent packets have been retransmitted. But hey, probably if a packet have been retransmitted once, it’s retransmission may fail in all subsequent cases just because actual RTO for receiving this responding packet is slightly bigger than it was at initial stage!

Solution for this problem called a timer back-off strategy.

Need back-off!

It is a simple technique for multiplying RTO by some factor when sent segment has not been ACK-ed and we are going to make retransmission. Usually, this factor is a fixed number - RFC specifies a factor of 2, so after retransmission of initial packet we will wait a responding packet twice more time:

\[ RTO \leftarrow RTO * 2 \]

In some papers, this technique also referred as exponential back-off.

After first successive retransmission happened, each $latex RTO$ timeout should be set twice as previous one and Jacobson estimation formulas should be used on a ACK-ed packets.