Tearing down the FSM description of congestion control

Question

I was going through the text Computer Networking- A Top-Down Approach by Kurose and Ross, there I found subtleties with the TCP congestion control FSM which is shown below:

Mainly I am having difficulty in understanding the action transmit new segment(s), as allowed and transition to the Fast Recovery state.

I have read the equivalent portions from the textbook Data Communications and Networking by Forouzan but there though the explanation is easy but there is no FSM or a programmatic approach.

Now let us consider the slow start phase as shown in the Kurose & Ross text:

The time diagram which they explain about the $cwnd$ doubling after each transmission round is easy and is just like what the Forouzan text says. But I find it difficult to understand the implementation based on the arc labeled with :

in the slow start phase.

1. Suppose the sender starts with $cwnd = 1$ $MSS$ then sends this (1st) segment to the network layer and awaits the acknowledgment.
2. The sender gets "new ACK" for the previous packet and increases $cwnd$ to $2$ $MSS$. Then in accordance to "transmit new segment(s), as allowed", the sender sends $2$ segments (2nd and 3rd) to the network layer and awaits the acknowledgments.
3. Now the sender receives "new ACK" corresponding to 2nd segment and increases $cwnd$ to $3$ $MSS$. Then in accordance to "transmit new segment(s), as allowed", the sender sends $3$ segments to the network layer and awaits the acknowledgments.
4. Now the sender receives "new ACK" corresponding to 3rd segment and increases $cwnd$ to $4$ $MSS$. Then in accordance to "transmit new segment(s), as allowed", the sender sends $4$ segments to the network layer and awaits the acknowledgments.

From points 3 and 4, I find that the situation does not match with the slow start phase as shown in Fig 3.51. (i.e. the no. of segments sent are 1,2, 3,4 instead of 1,2,4)

---

I cannot understand the Fast recovery state's action. Specifically the Forouzan text says :

Most TCP implementations have two reactions:

1. If a time-out occurs, there is a stronger possibility of congestion; a segment has probably been dropped in the network, and there is no news about the sent segments. In this case TCP reacts strongly:

   a. It sets the value of the threshold to one-half of the current window size.

   b. It sets cwnd to the size of one segment.

   c. It starts the slow-start phase again.

2. If three ACKs are received, there is a weaker possibility of congestion; a segment may have been dropped, but some segments after that may have arrived safely since three ACKs are received. This is called fast transmission and fast recovery. In this case, TCP has a weaker reaction:

   a. It sets the value of the threshold to one-half of the current window size.

   b. It sets cwnd to the value of the threshold (some implementations add three segment sizes to the threshold).

   c. It starts the congestion avoidance phase.

In the Forouzan text, there is no such transition to the Fast Recovery state. But here in Kurose there is such a state and there is an arc labeled :

whose working I do not quite understand in detail.

What extra work is the version in Kurose doing as compared to the one given in the Forouzan text? Can anyone explain me the subtleties with a comprehensive example covering all the cases of the FSM, so that I can understand the thing better.

Answer 1

the thing that needs to be grasped is how sliding window interacts with congestion control.

Sliding Windows

Let's say for simplicity case that sequence numbers number segments starting from one ...

It is important to understand, that when ACK is received, two things can happen

• window is moved by one segment (segment is removed from sender window)
• window can increase/stay the same/decrease
  • if the window is not increased, one new packet can be sent (window end will be one segment, passed SND.NXT and this segment is sent)
  • if the window increases by N segments, one new packet from previous case + N extra packets can be sent (try moving window by one and then increasing by two - how many spaces open?)
  • if the window decreases, no packets can be sent (SND.NXT will be outside of window, and as long as it is outside of window, no packets are sent)

Slow Start

So, what happens with slow start:

Suppose the sender starts with cwnd=1 MSS then sends this (1st) segment to the network layer and awaits the acknowledgment.

window starts at 1st segment and is one segment long

The sender gets "new ACK" for the previous packet and increases cwnd to 2 MSS. Then in accordance to "transmit new segment(s), as allowed", the sender sends 2 segments (2nd and 3rd) to the network layer and awaits the acknowledgments.

window is moved to second segment, and is increased by one segment: 2 new segments are sent, window is [2,3] and packet 2 and 3 are sent

Now the sender receives "new ACK" corresponding to 2nd segment and increases cwnd to 3 MSS. Then in accordance to "transmit new segment(s), as allowed", the sender sends 3 segments to the network layer and awaits the acknowledgments.

now window moves to 3 and opens to 3 segments [3, 4, 5]. however, segment 3 is already sent, so only the new segments 4 and 5 can be sent, the sender starts sending 4, which will take some time.

Now the sender receives "new ACK" corresponding to 3rd segment and increases cwnd to 4 MSS. Then in accordance to "transmit new segment(s), as allowed", the sender sends 4 segments to the network layer and awaits the acknowledgments.

the window moves to 4 and opens by 4, so the sender can send [4, 5, 6, 7]. The delta from previous case is that segments 6 and 7 can also be sent.

Now, sending packets takes some time - t_s. Then two consequtive packets are delivered t_s time appart, are ACKed t_s times appart, and these ACKs arrive t_s time appart. So, what will happen in this two steps: segment 4 is sent, then almost simultaneously segment 5 is sent and ack for 3 is received, which makes segment 6 be transmitted as soon as 5 finishes and 7 as soon as 6 finished.

Fast recovery

this state is entered when 3 dupacks are received and ends, when acknowledgment for the missing segment, i.e., the one that caused 3 dupacks is received. it takes about 1 RTT and is not depicted on most congestion control diagrams. But it does exis. Although there may be better strategies for error recovery.

How sliding window works in fast recovery is answered here