📡 Tutorial 7: TCP Reliable Data Transfer and Flow Control (Advanced)

University‑level treatment – COMP347 (TrustOpen University)

📘 1. Overview of TCP Reliable Data Transfer

TCP provides reliable, ordered delivery of a byte stream. It achieves this by:

• Using sequence numbers to identify each byte in the stream.
• Using cumulative acknowledgments (ACKs) to indicate the next expected byte.
• Maintaining a sliding window to manage flow and congestion (though congestion control is covered later).
• Using retransmission timers to detect lost segments.
• Using duplicate ACKs to trigger fast retransmit without waiting for a timeout.
• Employing flow control via the advertised window to prevent receiver buffer overflow.

TCP’s reliability is a hybrid of Go‑Back‑N (cumulative ACKs) and Selective Repeat (fast retransmit for individual packets), with SACK providing even finer granularity.

📘 2. TCP Sender Finite‑State Machine

The TCP sender can be modeled as a finite‑state machine with the following states and transitions:

• State: Ready – waiting for data from application or ACKs from receiver.
• Events:
  • rdt_send(data) – application passes data to send.
  • rdt_rcv(ACK) – an ACK segment arrives.
  • timeout – retransmission timer expires.
• Actions:
  • On rdt_send: if window not full, segment and send; if first segment, start timer.
  • On ACK receipt: if cumulative ACK acknowledges new data, update send window; if duplicate ACK, increment duplicate ACK count.
  • On timeout: retransmit oldest unacknowledged segment, restart timer.

The sender also maintains variables: SendBase (oldest unacknowledged byte), NextSeqNum (next byte to send), and window (min(cwnd, rwnd)).

2.1 Sender Pseudocode

Initialize: SendBase = 0, NextSeqNum = 0, dupACKcount = 0

rdt_send(data):
    if NextSeqNum < SendBase + window:
        create segment with seq = NextSeqNum, send it
        if SendBase == NextSeqNum: start timer
        NextSeqNum += length(data)
    else:
        buffer data (or block)

rdt_rcv(ACK):
    if ACKnum > SendBase:
        SendBase = ACKnum
        if SendBase == NextSeqNum: stop timer
        else: restart timer
        dupACKcount = 0
    else if ACKnum == SendBase:
        dupACKcount += 1
        if dupACKcount == 3:
            retransmit segment with seq = SendBase
            dupACKcount = 0
            // (fast retransmit)
    // ignore if ACKnum < SendBase

timeout:
    retransmit segment with seq = SendBase
    restart timer
    // (exponential backoff may apply)
    

📘 3. TCP Receiver Behaviour and ACK Generation

The receiver’s actions are defined in RFC 5681:

• On receipt of an in‑order segment that fills a gap: send cumulative ACK for the next expected byte.
• On receipt of an out‑of‑order segment: buffer it and send a duplicate ACK (the ACK for the last in‑order byte).
• On receipt of a segment with data that overlaps already received data (duplicate): discard and send ACK for the next expected byte.
• Delayed ACK: may delay sending an ACK for up to 500 ms, hoping to piggyback on outgoing data.

The receiver maintains the variable ExpectedSeqNum (the next byte expected). When a segment arrives with sequence number exactly ExpectedSeqNum, it delivers the data and advances ExpectedSeqNum past any contiguous buffered data, then sends a cumulative ACK.

📘 4. Timer Management and Retransmission Strategies

TCP uses a single retransmission timer for the oldest unacknowledged segment. When that segment’s ACK arrives, the timer is restarted for the next oldest segment. This is simpler than per‑packet timers.

On timeout:

• Retransmit the oldest unacknowledged segment.
• Restart the timer (with exponential backoff: RTO is doubled to reduce network load).
• Set SendBase to the sequence number of the retransmitted segment (no change if using cumulative ACKs).

Exponential backoff: After a timeout, the RTO is doubled (up to a maximum) to avoid repeated retransmissions when the network is congested.

📘 5. Fast Retransmit and Fast Recovery

Fast retransmit: When the sender receives 3 duplicate ACKs (i.e., 4 total ACKs for the same byte), it assumes the segment with sequence number SendBase was lost and retransmits it immediately, without waiting for the timeout. This reduces recovery time significantly.

Fast recovery (in TCP Reno): After fast retransmit, the sender sets ssthresh = cwnd/2 and cwnd = ssthresh + 3*MSS (to account for the segments already ACKed), then enters congestion avoidance. This avoids the slow start phase after a loss, improving throughput.

These mechanisms are critical for TCP performance in modern networks.

📘 6. Flow Control: The Advertised Window (rwnd)

Flow control is a separate mechanism from congestion control. The receiver advertises a receive window (rwnd) in each ACK, indicating the amount of free buffer space. The sender limits the amount of unacknowledged data to min(cwnd, rwnd).

The receiver’s buffer is divided into:

• Data already delivered to application.
• Data received but not yet delivered (in‑order).
• Data received out‑of‑order (buffered).
• Free space.

The advertised window is computed as:

rwnd = buffer size - (LastByteReceived - LastByteRead)

where LastByteReceived is the highest sequence number received, and LastByteRead is the highest sequence number read by the application.

📘 7. Zero‑Window Probing and Persistent Timer

If rwnd = 0, the sender stops sending data. However, the receiver may later free buffer space and send an ACK with a non‑zero window. If that ACK is lost, the sender would wait forever. To prevent deadlock, the sender uses a persistent timer. When the persistent timer expires, the sender sends a zero‑window probe (a single byte of data) to the receiver. The receiver responds with an ACK containing the current window. If the window is still zero, the persistent timer is reset with exponential backoff.

📘 8. Silly Window Syndrome (SWS) Avoidance

Silly Window Syndrome occurs when the receiver advertises very small windows (e.g., a few bytes), and the sender sends tiny segments, leading to poor network utilization. Both sides take action:

• Receiver‑side SWS avoidance: The receiver should not advertise a window that is smaller than either a full‑size segment (MSS) or a certain fraction of the buffer (e.g., half the buffer). It delays sending window updates until the window grows sufficiently.
• Sender‑side SWS avoidance: The sender should not send a segment smaller than the MSS unless it has a full buffer or it has been a certain time since the last send (Nagle’s algorithm also helps).

These mechanisms prevent the inefficient transmission of many small packets.

📘 9. TCP Buffering and Window Update Semantics

The send buffer holds data sent but not yet ACKed. The receive buffer holds data received but not yet read. When the application reads data, the receiver’s window opens. The receiver may send a window update (an ACK with a new rwnd) even without receiving new data to inform the sender of the increased space. This is called a window update.

📘 10. Advanced Topics: ACK Clocking, Cumulative vs. Selective ACKs

ACK clocking: In steady state, TCP’s transmission is paced by the rate of incoming ACKs. Each ACK allows the sender to transmit a new segment (if window permits). This self‑clocking helps maintain smooth traffic and is important for congestion control.

Cumulative ACKs are simple but can cause unnecessary retransmissions if multiple packets are lost. Selective ACKs (SACK) allow the receiver to inform the sender of non‑contiguous blocks of received data, enabling selective retransmission and improving performance under loss.

📝 Quiz

Test your understanding with these 35 questions. Answers are hidden below each.

🛠️ Exercises

Apply your knowledge with these 20 exercises. Solutions are provided below each.

📚 Homework

These advanced problems require synthesis, research, and quantitative analysis. Sample answers are provided below.