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 timing 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 the 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 the 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?

Answer 1

What extra work is the version in Kurose doing as compared to the one given in the Forouzan text?

Think about the changes over the years. RFC 793, Transmission Control Protocol was published in September 1981 with no mention of fast recovery, but there have been various RFCs related to TCP congestion control released over the years since. For example, RFC 2001, TCP Slow Start, Congestion Avoidance, Fast Retransmit, and Fast Recovery Algorithms was published in January 1997, and it was obsoleted by RFC 2581, TCP Congestion Control which was updated by RFC 3990, Increasing TCP's Initial Window and completely obsoleted by RFC 5681, TCP Congestion Control.

RFC 793, itself, has been updated by other RFCs (1122, 3168, 6093, 6528). As you can see, the official way TCP deals with this has changed at various points in time, and books, articles, and documents released at different times will have different information. There probably are also various editions to some books that update the information in previous editions. You need to pay attention to the published dates and see if there are more recent editions.

Also, remember that not all OSes will be immediately updated to support a new RFC, if at all (Windows still does not support RFC 3021, Using 31-Bit Prefixes on IPv4 Point-to-Point Links that was published in December 2000).

If you really want to understand TCP, study RFC 793 (all implementations should support it). When you grasp all the concepts in that RFC, start going through all the other RFCs covering TCP (you may want to skip the ones that have been obsoleted).

The original (and only official one I know) TCP state machine from RFC 793:

                              +---------+ ---------\      active OPEN
                              |  CLOSED |            \    -----------
                              +---------+<---------\   \   create TCB
                                |     ^              \   \  snd SYN
                   passive OPEN |     |   CLOSE        \   \
                   ------------ |     | ----------       \   \
                    create TCB  |     | delete TCB         \   \
                                V     |                      \   \
                              +---------+            CLOSE    |    \
                              |  LISTEN |          ---------- |     |
                              +---------+          delete TCB |     |
                   rcv SYN      |     |     SEND              |     |
                  -----------   |     |    -------            |     V
 +---------+      snd SYN,ACK  /       \   snd SYN          +---------+
 |         |<-----------------           ------------------>|         |
 |   SYN   |                    rcv SYN                     |   SYN   |
 |   RCVD  |<-----------------------------------------------|   SENT  |
 |         |                    snd ACK                     |         |
 |         |------------------           -------------------|         |
 +---------+   rcv ACK of SYN  \       /  rcv SYN,ACK       +---------+
   |           --------------   |     |   -----------
   |                  x         |     |     snd ACK
   |                            V     V
   |  CLOSE                   +---------+
   | -------                  |  ESTAB  |
   | snd FIN                  +---------+
   |                   CLOSE    |     |    rcv FIN
   V                  -------   |     |    -------
 +---------+          snd FIN  /       \   snd ACK          +---------+
 |  FIN    |<-----------------           ------------------>|  CLOSE  |
 | WAIT-1  |------------------                              |   WAIT  |
 +---------+          rcv FIN  \                            +---------+
   | rcv ACK of FIN   -------   |                            CLOSE  |
   | --------------   snd ACK   |                           ------- |
   V        x                   V                           snd FIN V
 +---------+                  +---------+                   +---------+
 |FINWAIT-2|                  | CLOSING |                   | LAST-ACK|
 +---------+                  +---------+                   +---------+
   |                rcv ACK of FIN |                 rcv ACK of FIN |
   |  rcv FIN       -------------- |    Timeout=2MSL -------------- |
   |  -------              x       V    ------------        x       V
    \ snd ACK                 +---------+delete TCB         +---------+
     ------------------------>|TIME WAIT|------------------>| CLOSED  |
                              +---------+                   +---------+

                      TCP Connection State Diagram
                               Figure 6.