Question

Suppose a TCP connection, with window size 1, loses every other packet. Those that do arrive have RTT \(=1\) second. What happens? What happens to TimeOut? Do this for two cases: (a) After a packet is eventually received, we pick up where we left off, resuming with EstimatedRTT initialized to its pretimeout value and TimeOut double that. (b) After a packet is eventually received, we resume with TimeOut initialized to the last exponentially backed-off value used for the timeout interval. In the following four exercises, the calculations involved are straightforward with a spreadsheet.

Short answer

Case (a): TimeOut doubles after loss and returns to EstimatedRTT, Case (b): TimeOut retains the double value after loss and doesn't reset.

Step-by-step solution

Title - Understand the Problem

Identify the problem context: A TCP connection with window size 1 where every other packet is lost. Given RTT is 1 second. We need to analyze the situations for two cases: resuming with either estimatedRTT or the backed-off TimeOut value.

Title - Case (a): Calculating EstimatedRTT and TimeOut

In case (a), after a packet is eventually received, the connection resumes with the EstimatedRTT set to its pre-timeout value and TimeOut doubled each time a packet is lost. For each cycle of loss and receipt, plot the TimeOut values. Initially, EstimatedRTT = 1 second. If a packet is lost, TimeOut doubles: 2 seconds, then 4 seconds, then 8 seconds, etc. When a packet is eventually received, EstimatedRTT stays at 1 second and TimeOut doubles.

Title - Case (b): Track Exponential Back-Off

In case (b), after a packet is eventually received, the resumption occurs with the TimeOut value initialized to the last exponentially backed-off value. This means to track the current TimeOut value which continues doubling until a packet is received. Post reception, TimeOut remains doubled and carries forward. For each cycle of loss and receipt, the TimeOut values will: 2 seconds, 4 seconds, 8 seconds, etc., and then continue to stay at that last value post packet receipt.

Title - Analyzing TimeOut and RTT

For both cases, calculate the patterns of TimeOut and RTT: For case (a) after each reception, TimeOut resets to the EstimatedRTT and gets doubled only if there's a subsequent loss. In case (b), TimeOut doubles but does not reset on reception and maintains the backed-off value.

Key concepts

TCP window size

In a TCP connection, the window size determines how many packets can be sent before waiting for an acknowledgment. Think of it as a buffer space for unacknowledged packets. In our exercise, the window size is 1, which means only one packet is sent at a time and the sender waits for its acknowledgment before sending the next packet.
A small window size, like 1, can slow down the transmission rate since the sender must wait for the acknowledgment after every single packet. This is especially impactful if there are delays, as seen in our scenario where packets are lost every other transmission.

Packet loss

Packet loss occurs when data packets traveling across a network fail to reach their destination. Packet loss can cause transmission delays because lost packets need to be resent. In our exercise, every other packet is lost, causing significant disruption.
The impact of packet loss is pronounced with a small TCP window size. Since only one packet is sent at a time, losing every other packet means frequent resending and waiting, which can drastically reduce effective throughput and increase the overall transmission time.

RTT calculation

Round-Trip Time (RTT) is the time it takes for a signal to go from the sender to the receiver and back again. In our problem, the RTT is given as 1 second. This means, under ideal conditions without packet loss, each packet acknowledgment should return within 1 second.
In the context of our scenario, lost packets will increase the effective RTT as the packets need to be resent, and each subsequent retry causes a delay.

Timeout calculation

Timeout is the duration a sender waits for an acknowledgment before assuming a packet is lost and resending it. Determining the timeout value is crucial and is usually based on RTT and its variations.
In case (a), after a packet is eventually received, the timeout doubles each time a packet is lost, which follows an exponential pattern: 2 seconds, 4 seconds, 8 seconds, and so forth. When a packet is finally received, the timeout resets, but still considers the EstimatedRTT.
In case (b), after a packet is received, the timeout resumes from the last exponentially backed-off value. This means it continuously doubles with each packet loss and carries this timeout value forward post-reception.

Exponential backoff

Exponential backoff is a strategy employed to manage network congestion by exponentially increasing the waiting time between subsequent attempts following packet loss. This is crucial to prevent overwhelming the network with retries.
In case (a), the exponential backoff is demonstrated through doubling the timeout period after each packet loss. Additionally, the EstimatedRTT is recalibrated to its pre-timeout value upon successful reception.
In case (b), the exponential backoff continues without resetting. This means if the timeout period was 8 seconds after a series of losses and then a packet was successfully received, the timeout retains the 8 seconds and continues to double if packet loss persists.