TCP Flow, Error, and Congestion Control

The Transport Layer is the backbone of process-to-process communication in the TCP/IP protocol suite. Operating directly between the application layer and the network layer, transport protocols convert the unreliable, connectionless packet-delivery service of IP into a reliable, ordered stream-delivery service for client-server processes.

While the User Datagram Protocol (UDP) offers minimal overhead by sacrificing reliability, the Transmission Control Protocol (TCP) implements complex flow, error, and congestion control algorithms to guarantee robust data transfer over unpredictable networks.

1. Fundamentals of sliding window protocols

To understand how TCP provides reliability and flow regulation, we must first study the generic sliding window models that form the mathematical basis of transport layer protocols.

1.1 The concept of link utilization

In a simple Stop-and-Wait protocol, the sender transmits a single packet and must wait for an acknowledgment (ACK) before sending the next. If we analyze this using a network link with transmission rate $R$ (bps), propagation delay $T_{\text{prop}}$ (seconds), and packet size $L$ (bits), the packet transmission time $T_{\text{trans}}$ is defined as:

$T_{\text{trans}} = \frac{L}{R}$

The round-trip time ( $RTT$ ) for the link is:

$RTT = 2 \cdot T_{\text{prop}}$

The total time required to send a packet and receive its acknowledgment is $T_{\text{total}} = T_{\text{trans}} + RTT$ . The link utilization ( $U$ ) is the fraction of time the link is actively transmitting data:

$U = \frac{T_{\text{trans}}}{T_{\text{trans}} + RTT} = \frac{L/R}{L/R + 2 \cdot T_{\text{prop}}}$

For high-bandwidth or high-delay links (known as networks with a large bandwidth-delay product $BDP = R \cdot RTT$ ), the utilization of a Stop-and-Wait protocol is extremely low.

text

Stop-and-Wait Timeline:
Sender                                     Receiver
  | -- [ Packet (L bits) ] ------------->     |
  |=========T_trans=========                  |
  |                                           |  (Propagation Delay T_prop)
  |                                           |
  |                                           v
  |                                     [Packet Arrives]
  |                                           |
  | <--------- [ ACK ] ---------------------- |
  |                                           |
  |<------------------ RTT ------------------>|
  v                                           v

1.2 Sliding window models: GBN and SR

To solve the inefficiency of Stop-and-Wait, sliding window protocols allow the sender to transmit multiple packets before receiving an acknowledgment. The maximum number of outstanding packets is defined by the window size ( $W$ ).

text

Go-Back-N (GBN) sliding window at the sender:
 
          Sent & ACKed      Outstanding (Sent, Not ACKed)     Can Send Immediately
        [===============] [=============================] [=========================]
       +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
  ...  | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12| 13| 14| 15| 16| 17| 18| ...
       +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
                         ^                               ^
                         |-- Sf (First outstanding)      |-- Sn (Next to send)
                         |<--------- Window Size -------->|

Go-Back-N (GBN):
- Sender Window Size ( $W_S$ ): Maximum of $2^m - 1$ (where $m$ is the number of bits in the sequence number field).
- Receiver Window Size ( $W_R$ ): Exactly .

2. TCP segment structure and connection dynamics

TCP operates on a stream of bytes rather than discrete packets. It groups these bytes into logical units called segments for transmission.

2.1 The TCP segment format

The standard TCP segment consists of a header (typically 20 to 60 bytes) followed by the application payload.

text

 0                   1                   2                   3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|          Source Port          |       Destination Port        |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                        Sequence Number                        |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                     Acknowledgment Number                     |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|  Data |           |U|A|P|R|S|F|                               |
| Offset| Reserved  |R|C|S|S|Y|I|            Window             |
|       |           |G|K|H|T|N|N|                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|           Checksum            |         Urgent Pointer        |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                    Options (0 to 40 bytes)                    |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                             Data                              |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Sequence Number (32 bits): Defines the sequence number assigned to the first data byte contained in the segment. Initial sequence numbers (ISNs) are generated randomly during connection setup.
Acknowledgment Number (32 bits): Represents the cumulative byte sequence number that the receiver expects to receive next. If $ACK = N$ , it implies all bytes up to $N-1$ have been received.
Control Flags (6 bits):
- URG: Urgent pointer field is valid.
- ACK: Acknowledgment field is valid (always set after connection establishment).
- PSH: Push function; requests that the receiver deliver data immediately to the application without waiting for buffers to fill.
- RST: Reset the connection.

2.2 TCP connection lifecycle (Three-Way Handshake)

Before exchanging data, TCP uses a three-way handshake to establish a connection. This process synchronizes sequence numbers and negotiates connection parameters like the Maximum Segment Size (MSS).

text

Client (Active Open)                                 Server (Passive Open)
       |                                                    |
       | ------ SYN (Seq=X, ACK=0) -----------------------> | (State: SYN-RCVD)
       |                                                    |
       | <----- SYN-ACK (Seq=Y, ACK=X+1) ------------------ | 
       |                                                    |
       | ------ ACK (Seq=X+1, ACK=Y+1) -------------------> | (State: ESTABLISHED)
       v                                                    v

SYN: The client sends a segment with the SYN flag set, containing its initial sequence number $X$ . This segment consumes 1 sequence number even though it contains no payload.
SYN-ACK: The server responds with a segment where both SYN and ACK flags are set. It contains the server's initial sequence number $Y$ , and acknowledges the client’s SYN by setting the acknowledgment number to $X+1$ . This segment also consumes exactly 1 sequence number.
ACK: The client sends an acknowledgment segment back to the server with ACK set and an acknowledgment number of $Y+1$ . This segment carries no data and does not consume a sequence number.

Connection termination uses a four-step sequence (or a three-way handshake with a combined FIN-ACK) to close both directions of the full-duplex communication channel. The terminating peer enters a TIME-WAIT state for a duration of $2 \times \text{MSL}$ (Maximum Segment Lifetime) to ensure that any delayed segments still in transit are discarded and do not corrupt subsequent connections.

3. TCP Flow control and sliding window mechanics

Flow control prevents a fast sender from overwhelming a slow receiver's buffer space. TCP implements flow control using a Sliding Window mechanism where the receiver dynamically regulates the sender's transmission rate via the advertised receive window ( $rwnd$ ).

text

Receiver Buffer State:
+-------------------------[ Receiver Buffer ]-------------------------+
|  Bytes Read  |        Bytes Received & Buffered       |    Free    |
|  by Process  |         (Waiting to be read)           |    Space   |
+--------------+----------------------------------------+------------+
               ^                                        ^            ^
               |                                        |            |
         LastByteRead                            LastByteRcvd   MaxBufSize
 
         * Active Receive Window (rwnd) = MaxBufSize - (LastByteRcvd - LastByteRead)

3.1 Sliding window dynamics

The sender maintains a send window whose effective size is determined by the minimum of the receive window ( $rwnd$ ) advertised by the receiver and the congestion window ( $cwnd$ ) calculated by the sender:

$\text{Effective Window Size} = \min(rwnd, cwnd)$

The boundaries of the sender's sliding window are tracked using three pointer variables:

$S_f$ : Sequence number of the first outstanding (sent but unacknowledged) byte.
$S_n$ : Sequence number of the next byte to be sent.
$S_{size}$ : The active send window size.

text

Sender Sliding Window Pointers:
            |<---------- S_size (rwnd) ---------->|
  +---------+--------------------+----------------+---------+
  |  ACKed  | Sent, Unacknowledged| Can Send Now   | Cannot  |
  +---------+--------------------+----------------+---------+
            ^                    ^                          
            |-- Sf               |-- Sn

3.2 Preventing window shrinking

To ensure reliable operation, the receiver must not shrink its window. Window shrinking occurs if the right-hand boundary of the send window moves to the left. To prevent this, the receiver must satisfy the following mathematical inequality across consecutive advertisements:

$\text{new\_ackNo} + \text{new\_rwnd} \ge \text{last\_ackNo} + \text{last\_rwnd}$

If the receiver violates this rule, bytes that were previously inside the sender's window (and potentially already transmitted) could suddenly fall outside the window, leading to severe synchronization errors.

3.3 Silly Window Syndrome (SWS) and mitigations

Silly Window Syndrome is a state where data is exchanged in very small segments (e.g., 1 byte of payload accompanied by 40 bytes of TCP/IP header, resulting in extremely low efficiency). SWS can be triggered by either the sender or the receiver.

A. Sender-Side SWS (Nagle's Algorithm)

If the application generates data slowly (e.g., keystrokes in a Telnet session), the sender might transmit numerous tiny segments. Nagle's Algorithm mitigates this by buffering small payloads until they can be sent as a larger segment:

text

Nagle's Algorithm Decision Tree:
                          +------------------------+
                          |   Application writes   |
                          |      data to TCP       |
                          +------------------------+
                                       |
                                       v
                    /------------------------------------\
                   /  Is outstanding data unACKed?       \--- No ---> [Send Segment
                   \                                     /             Immediately]
                    \------------------------------------/
                                       | Yes
                                       v
                    /------------------------------------\
                   /  Is accumulated data >= MSS?        \--- Yes --> [Send Segment
                   \                                     /             Immediately]
                    \------------------------------------/
                                       | No
                                       v
                           [Buffer data and wait
                            for ACK or more data]

B. Receiver-Side SWS (Clark's Solution & Delayed ACKs)

If the receiving application consumes data slowly, the receiver's buffer will fill up. When a single byte is read, the receiver might advertise a $rwnd$ of 1 byte. The sender immediately transmits a 1-byte segment, keeping the buffer full and trapping the connection in a loop of tiny segments.

Clark's Solution: The receiver prevents SWS by advertising a window size of $0$ until it has enough buffer space to hold a maximum-sized segment ( $MSS$ ) or at least half of its total buffer space ( $MaxBufSize / 2$ ).
Delayed Acknowledgments: The receiver delays sending an ACK for up to 500 ms. This allows more data to arrive so it can send a single cumulative ACK, and gives the application time to read buffer data so a larger $rwnd$ can be advertised.

4. TCP Error control and recovery

TCP provides reliable data delivery over unreliable channels using three main tools: checksums, cumulative/selective acknowledgments, and retransmission timers.

4.1 Retransmission triggers

TCP triggers a retransmission under two conditions:

Retransmission Timeout (RTO): If the sender does not receive an ACK for a segment before its private retransmission timer expires, it assumes the segment was lost and retransmits it.
Fast Retransmit: Because timeouts can introduce significant delays, TCP uses Fast Retransmit. If a segment is lost, subsequent segments arriving out-of-order cause the receiver to send duplicate ACKs for the last in-order segment. When the sender receives three duplicate ACKs (four ACKs total for the same sequence number), it assumes the segment was lost and retransmits it immediately without waiting for the timer to expire.

text

Fast Retransmit Scenario:
Sender                                     Receiver
  | -- [Segment 1] (Seq=1000) -------------> | (Receives Seg 1, ACK=2000)
  |                                          |
  | -- [Segment 2] (Seq=2000) --- LOST --->  | 
  |                                          |
  | -- [Segment 3] (Seq=3000) -------------> | (Receives Seg 3, Out-of-Order! Sends ACK=2000)
  |                                          |
  | -- [Segment 4] (Seq=4000) -------------> | (Receives Seg 4, Out-of-Order! Sends Duplicate ACK=2000)
  |                                          |
  | -- [Segment 5] (Seq=5000) -------------> | (Receives Seg 5, Out-of-Order! Sends Duplicate ACK=2000)
  |                                          |
  | <==== Receives 3 Duplicate ACKs! ======= | 
  |       [Retransmits Segment 2 (Seq=2000)] |
  v                                          v

4.2 Selective Acknowledgment (SACK)

By default, TCP uses cumulative acknowledgments. If segments 1000-2000 and 3000-4000 are received but 2000-3000 is lost, the receiver can only advertise $ACK = 2000$ . The sender must then either wait for a timeout or retransmit everything starting from 2000.

The Selective Acknowledgment (SACK) option solves this inefficiency. In the TCP options header, the receiver includes SACK blocks that specify the boundaries of out-of-order blocks it has already buffered. SACK blocks use a half-open interval $[L, R)$ representing bytes from sequence number $L$ up to $R-1$ .

5. TCP Congestion control algorithms

While flow control protects the receiver, congestion control protects the network from being overloaded by too many active senders. TCP dynamically adjusts its congestion window ( $cwnd$ ) based on network conditions.

5.1 The baseline congestion phases

The TCP congestion control state machine uses a threshold variable ( $ssthresh$ , slow-start threshold) and consists of three main phases:

text

TCP Congestion Policy State Diagram:
      +-------------------------------------------+
      |                 STARTUP                   |
      +-------------------------------------------+
                            |
                            v
               +-------------------------+
               |  Slow Start (Exponential)| <-------------+
               |     (cwnd < ssthresh)   |               |
               +-------------------------+               |
                            |                            | (Timeout)
                            | (cwnd >= ssthresh)         |
                            v                            |
               +-------------------------+               |
               |  Congestion Avoidance   |               |
               |   (Additive Increase)   | --------------+
               +-------------------------+
                            |
                            | (3 Duplicate ACKs)
                            v
               +-------------------------+
               |      Fast Recovery      |
               |      (TCP Reno)         |
               +-------------------------+

A. Slow Start Phase ( $cwnd < ssthresh$ )

At the start of a connection or after a timeout, the sender initializes its congestion window to a small value (typically $cwnd = 1 \text{ to } 10 \text{ MSS}$ ). To quickly probe the network's capacity, the sender increases $cwnd$ exponentially:

$\text{On receipt of each segment ACK: } cwnd \leftarrow cwnd + 1 \text{ MSS}$

This means that for every round-trip time ( $RTT$ ) where all outstanding packets are acknowledged, the congestion window doubles:

$cwnd_{\text{new}} = 2 \cdot cwnd_{\text{old}}$

B. Congestion Avoidance Phase ( $cwnd \ge ssthresh$ )

Once $cwnd$ reaches $ssthresh$ , the sender transitions to a more conservative linear increase phase to avoid causing network congestion. The congestion window increases by 1 MSS per RTT:

$\text{On receipt of each segment ACK: } cwnd \leftarrow cwnd + \frac{1 \text{ MSS}}{cwnd}$

This results in a total increase of $1 \text{ MSS}$ after a full window of segments has been successfully acknowledged:

$cwnd_{\text{new}} = cwnd_{\text{old}} + 1 \text{ MSS (per RTT)}$

5.2 Handling congestion events

TCP handles packet loss differently depending on whether it is detected by a timeout or by triple duplicate ACKs.

Case A: Loss Detected by Retransmission Timeout (RTO)

A timeout indicates severe network congestion. Both TCP Tahoe and TCP Reno react the same way:

The threshold is set to half of the current congestion window: $ssthresh \leftarrow \max\left(\frac{cwnd}{2}, 2 \cdot \text{MSS}\right)$
The congestion window is reset to :

Case B: Loss Detected by Triple Duplicate ACKs (Fast Retransmit)

Because duplicate ACKs indicate that subsequent segments are still getting through, the network is not completely congested.

TCP Tahoe: Treats this the same as a timeout (resets $cwnd$ to $1 \text{ MSS}$ and enters Slow Start).
TCP Reno (Fast Recovery): Implements Fast Recovery to maintain higher throughput:
1. The threshold is set to half of the current congestion window: $ssthresh \leftarrow \max\left(\frac{cwnd}{2}, 2 \cdot \text{MSS}\right)$

text

TCP Congestion Window (cwnd) Evolution (Sawtooth Behavior):
 
  cwnd (MSS)
    ^
 32 |                       /\
 24 |                      /  \ (Timeout: ssthresh=12, cwnd=1)
 16 |          /\         /    \
 12 |-------- /--\-------/----  \------------ ssthresh (after duplicate ACKs)
  8 |  /\    /    \     /        \
  4 | /  \  /      \---/          \
  1 |/____\/_______________________\__________> Time (RTTs)
    |<--->|<---------->|<--------->|
   Slow   Congestion   Fast        Slow Start
   Start  Avoidance    Recovery

6. TCP Timers and mathematical RTO calculation

To manage its operations, TCP uses several timers: the Persistence Timer (prevents deadlocks when the receive window is zero), the Keepalive Timer (detects dead connections), the TIME-WAIT Timer (ensures orderly connection teardown), and the Retransmission Timer (RTT).

6.1 The RTT estimation formulas

Because network conditions vary, TCP dynamically calculates its Retransmission Timeout ( $RTO$ ) using continuous measurements of the Sample Round-Trip Time ( $RTT_M$ ).

text

Measurement Timeline:
Sender                                     Receiver
  | -- [Segment X] (Record Transmit Time t1) -> |
  |                                             |
  | <--------- [ ACK X ] (Arrives at t2) ------ |
  v                                             v
  * Sample RTT Measurement (RTT_M) = t2 - t1

To smooth out measurement noise, TCP calculates a weighted moving average called the Smoothed RTT ( $RTT_S$ ):

$RTT_S = (1 - \alpha) \cdot RTT_S + \alpha \cdot RTT_M$

Typically, RFC 6298 recommends setting $\alpha = \frac{1}{8} = 0.125$ .

Next, TCP tracks network jitter by calculating the RTT Deviation ( $RTT_D$ ):

$RTT_D = (1 - \beta) \cdot RTT_D + \beta \cdot |RTT_S - RTT_M|$

Typically, RFC 6298 recommends setting $\beta = \frac{1}{4} = 0.25$ .

The Retransmission Timeout ( $RTO$ ) is then calculated as:

$RTO = RTT_S + 4 \cdot RTT_D$

Note: If the calculated $RTO$ is less than $1.0$ second, it is typically rounded up to $1.0$ second to avoid premature retransmissions.

6.2 Initialization rules

When the first segment (the SYN) is sent, no RTT measurements exist yet. The initial values are set as follows:

Initial $RTO = 6.0$ seconds (or $3.0$ seconds on modern systems).
Upon receiving the first measurement $RTT_M$ (from the SYN-ACK): $RTT_S \leftarrow RTT_M$

6.3 Mathematical calculation walk-through

Let's walk through an example of these calculations over multiple transmission rounds.

Round 0: Connection Setup

We start with no prior measurements. The connection is initialized with:

$RTT_S = \text{None}$
$RTT_D = \text{None}$

Round 1: First Measurement

The first SYN-ACK arrives, giving us a measured round-trip time of $RTT_M = 1.50 \text{ seconds}$ . Using our initialization rules:

$RTT_S = RTT_M = 1.50 \text{ seconds}$
$RTT_D = \frac{RTT_M}{2} = 0.75 \text{ seconds}$

Round 2: Second Measurement

The sender transmits a data segment and receives its acknowledgment, giving a new measurement of $RTT_M = 2.00 \text{ seconds}$ . We update our estimates using $\alpha = 0.125$ and $\beta = 0.25$ :

Calculate $RTT_S$ : $RTT_S = (1 - 0.125) \cdot 1.50 + 0.125 \cdot 2.00$

Summary

Sliding Window Protocols form the basis of transport layer flow control. Stop-and-Wait suffers from low link utilization on links with large bandwidth-delay products. Go-Back-N uses cumulative acknowledgments and discards out-of-order packets, while Selective-Repeat buffers out-of-order packets and retransmits only lost segments.
TCP Connections are established using a three-way handshake (SYN $\rightarrow$ SYN-ACK $\rightarrow$ ACK) and terminated using a four-way handshake (FIN $\rightarrow$ ACK $\rightarrow$ ), with a state to prevent duplicate segments from corrupting subsequent connections.

Assessed progress

TCP Flow, Error, and Congestion Control

Key Concepts

Sliding Window Protocol

Silly Window Syndrome

Fast Retransmit

Additive Increase / Multiplicative Decrease (AIMD)

Karn's Algorithm

Quick Check

Computer Networks

Computer Networks