Reliable Data Transfer Protocols

Reliable data transfer is one of the most critical challenges in computer networking. Because the underlying network layers (such as the IP layer) are inherently connectionless and best-effort, packets can be corrupted, lost, duplicated, or delivered out of order. This curriculum document details the theoretical design of reliable data transfer protocols, transitioning from basic stop-and-wait models to highly optimized sliding window protocols, and concluding with their real-world implementation within the Transmission Control Protocol (TCP).

1. Principles of Reliable Data Transfer

To design a reliable data transfer protocol, we must establish mechanisms that bridge the gap between a reliable upper-layer channel and an unreliable underlying channel.

text

       +---------------------------------------------+
       |             Application Layer               |
       +---------------------------------------------+
               | send_data()         ^ deliver_data()
               v                     |
       +---------------------------------------------+
       |             Transport Layer                 | <--- Reliable Data Transfer
       +---------------------------------------------+      (Flow & Error Control)
               | ip_send()           ^ ip_recv()
               v                     |
       +---------------------------------------------+
       |               Network Layer                 | <--- Unreliable Channel
       +---------------------------------------------+

Addressing: Port Numbers and Socket Addresses

At the transport layer, communication is process-to-process. While IP addresses route packets to a specific host machine, port numbers are used to select the specific application process.

Well-Known Ports: Ports $0$ to $1023$ are reserved for standard services (e.g., HTTP is port $80$ , TFTP is port $69$ , and SNMP uses ports $161$ and $162$ ).
Registered Ports: Ports $1024$ to $49151$ are registered for specific user processes.

A Socket Address uniquely identifies a process across the global network and is defined as:

$\text{Socket Address} = (\text{IP Address}, \text{Port Number})$

Core Control Mechanisms

Flow Control: Flow control balances the rate at which the producer (sender) generates data with the rate at which the consumer (receiver) processes it. This prevents the receiver's buffer from overflowing.
Error Control: Error control ensures the entire stream of data is delivered to the application without error, packet loss, or duplication. This is achieved using three primary tools:
- Checksums for detecting payload corruption.
- Acknowledgments (ACKs) to confirm error-free delivery.
- Timers and Time-outs to prompt retransmissions when packets or ACKs are lost.

2. Stop-and-Wait Protocol

The Stop-and-Wait Protocol is the simplest protocol with flow and error control. The sender transmits a single packet and stops, waiting for a feedback acknowledgment from the receiver before initiating the next transmission.

Design and Modulo Arithmetic

To distinguish between a new packet and a retransmitted duplicate, packets are sequentially numbered. In Stop-and-Wait, sequence numbers are calculated using modulo-2 arithmetic:

$\text{Sequence Number} \in \{0, 1\}$

The acknowledgment number always specifies the sequence number of the next packet expected by the receiver.

text

SENDER                                                     RECEIVER
  |                                                           |
  |--- Send Packet 0 ---------------------------------------->| (Expected: 0)
  |                                                           |-- Process & Ack
  |<-- Send ACK 1 --------------------------------------------| (Expects 1 next)
  |                                                           |
  |--- Send Packet 1 ---------------------------------------->| (Expected: 1)
  |    (Packet Lost)                                          |
  |    X                                                      |
  |                                                           |
  |--[Timer Expires]--                                        |
  |--- Retransmit Packet 1 ---------------------------------->| (Expected: 1)
  |                                                           |-- Process & Ack
  |<-- Send ACK 0 --------------------------------------------| (Expects 0 next)

Mathematical Link Utilization Analysis

While robust, the Stop-and-Wait protocol is highly inefficient on channels with a high bandwidth-delay product.

Let:

$L$ = Length of the packet (bits)
$R$ = Transmission rate of the link (bps)
$T_{\text{prop}}$ = One-way propagation delay (seconds)
$RTT$ = Round-Trip Time ( $2 \cdot T_{\text{prop}}$ )

The transmission time of a single packet ( $T_{\text{trans}}$ ) is:

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

The total time to complete one cycle of packet transmission and acknowledgment is $T_{\text{total}} = T_{\text{trans}} + RTT$ . The link utilization ( $U$ ) is defined as:

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

Example Calculation:

Assume a link bandwidth of $1\text{ Mbps}$ , and a round-trip propagation delay ( $RTT$ ) of $20\text{ ms}$ .

Let the packet size $L = 1000\text{ bits}$ .
$T_{\text{trans}} = \frac{1000\text{ bits}}{10^6\text{ bps}} = 1\text{ ms}$ .

$U = \frac{1\text{ ms}}{1\text{ ms} + 20\text{ ms}} = \frac{1}{21} \approx 4.76\%$

The channel is idle for over $95\%$ of the transmission cycle. To reclaim this wasted capacity, we must use pipelined sliding window protocols.

3. Go-Back-N (GBN) Protocol

The Go-Back-N (GBN) protocol improves link utilization by allowing the sender to transmit multiple packets before waiting for an acknowledgment. This pipelining technique relies on an abstract sliding window.

Sliding Windows in GBN

Sequence numbers in GBN are modulo $2^m$ , where $m$ is the bit-width of the sequence number field.

Send Window ( $S_{\text{size}}$ ): An imaginary box containing outstanding unacknowledged packets. The maximum send window size is constrained by:

$S_{\text{size}} = 2^m - 1$

Receive Window ( $R_{\text{size}}$ ): In GBN, the receive window is always fixed at $1$ . It only accepts the single, in-order packet currently expected ( $R_n$ ).

text

    <--- Sent, ACKed ---> [ Outstanding, UnACKed ] <--- Can Send --->
   +-----+-----+-----+---+-----+-----+-----+-----+---+-----+-----+-----+
   | 0   | 1   | 2   | 3 |  4  |  5  |  6  |  7  | 0 |  1  |  2  |  3  |
   +-----+-----+-----+---+-----+-----+-----+-----+---+-----+-----+-----+
                           ^                 ^
                           |                 |
                           Sf                Sn
    * Sf (Send window First): Oldest outstanding, unacknowledged packet.
    * Sn (Send window Next): Sequence number of the next packet to be sent.

Cumulative Acknowledgments

In GBN, acknowledgments are cumulative. When the receiver sends an $ACK(k)$ , it declares that all packets up to and including $k-1$ have been received correctly, and that it is expecting packet $k$ next.

If a packet in the middle of a pipeline sequence is lost, the receiver discards all subsequent packets (even if they arrive undamaged) because they are received out-of-order. When the sender's timer for the oldest unacknowledged packet ( $S_f$ ) expires, the sender must go back and retransmit the entire window starting from $S_f$ .

text

SENDER (S_size = 4)                                        RECEIVER (R_size = 1)
  |                                                           |
  |--- Send Packet 0 ---------------------------------------->| (Expected: 0) -> ACK 1
  |--- Send Packet 1 ---------------------------------------->| (Expected: 1) -> Lost!
  |--- Send Packet 2 ---------------------------------------->| (Expected: 1) -> Discard, ACK 1
  |--- Send Packet 3 ---------------------------------------->| (Expected: 1) -> Discard, ACK 1
  |                                                           |
  |--[Timer for Packet 1 Expires]--                            |
  |--- Go Back & Resend Packet 1 ---------------------------->| (Expected: 1) -> ACK 2
  |--- Resend Packet 2 -------------------------------------->| (Expected: 2) -> ACK 3
  |--- Resend Packet 3 -------------------------------------->| (Expected: 3) -> ACK 4

4. Selective-Repeat (SR) Protocol

While GBN utilizes link bandwidth much more efficiently than Stop-and-Wait, it performs poorly on lossy links because a single dropped packet triggers the retransmission of many correctly received packets. The Selective-Repeat (SR) protocol addresses this inefficiency.

Design and Window Size Constrains

In Selective-Repeat, both the sender and the receiver maintain sliding windows.

The receiver accepts out-of-order packets and buffers them locally, waiting for the missing packets to fill the gaps before delivering them in-order to the application.
Symmetric Window Constraints: To avoid sequence number ambiguity under lossy conditions, the sender and receiver window sizes are bound by:

$S_{\text{size}} = R_{\text{size}} \le 2^{m-1}$

text

Why SR window size must be <= 2^(m-1):
Suppose m = 2 (Sequence numbers: 0, 1, 2, 3). If window size = 3 (violating 2^(2-1) = 2):
1. Sender transmits Packets 0, 1, 2.
2. Receiver receives all, buffers them, slides window to expect 3, 0, 1. Sends ACKs.
3. All ACKs are lost.
4. Sender's timer expires, resends Packet 0.
5. Receiver (expecting 3, 0, 1) accepts this retransmitted Packet 0 as a brand new packet.
   This leads to duplicate, corrupted data delivery.
If window size was <= 2, the receiver would expect 2, 3, preventing this overlap.

Individual Acknowledgments

Instead of cumulative ACKs, SR uses individual acknowledgments. An acknowledgment number $ACK(k)$ confirms only that the specific packet with sequence number $k$ was received correctly. It does not imply the receipt of any prior packets.

text

SENDER (S_size = 4)                                        RECEIVER (R_size = 4)
  |                                                           |
  |--- Send Packet 0 ---------------------------------------->| (Expect: 0..3) -> Buffers 0, ACK 0
  |--- Send Packet 1 ---------------------------------------->| (Expect: 1..4) -> Lost!
  |--- Send Packet 2 ---------------------------------------->| (Expect: 1..4) -> Buffers 2, ACK 2
  |--- Send Packet 3 ---------------------------------------->| (Expect: 1..4) -> Buffers 3, ACK 3
  |                                                           |
  |--[Timer for Packet 1 Expires]--                            |
  |--- Resend Packet 1 ONLY --------------------------------->| (Expect: 1..4) -> Buffers 1, ACK 1
  |                                                           |   (Delivers 0, 1, 2, 3 in-order)

5. TCP Reliable Data Delivery

The transmission mechanisms detailed above are directly implemented and optimized in the Transmission Control Protocol (TCP).

TCP Segment and Numbering

Unlike the packet-oriented protocols studied conceptually, TCP is a stream-oriented protocol. It numbers the individual bytes of data being transferred, rather than numbering the packet segments.

Sequence Number Field: The sequence number in a TCP header specifies the sequence number of the first data byte carried within that segment.
Acknowledgment Number Field: Specifies the sequence number of the next byte expected. TCP ACKs are cumulative.
TCP Header Structure:

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)                    |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Connection State transitions (Three-Way Handshake)

TCP establishes a virtual connection using a three-way handshake:

text

CLIENT (Active Open)                                      SERVER (Passive Open)
  |                                                           | (State: LISTEN)
  |--- SYN (seq=x, ACK=0) ----------------------------------->| (State: SYN_RCVD)
  |                                                           |
  |<-- SYN-ACK (seq=y, ack=x+1) ------------------------------|
  |                                                           |
  |--- ACK (seq=x+1, ack=y+1) ------------------------------->| (State: ESTABLISHED)

During connection termination, TCP uses a four-way handshake to gracefully close each direction of the bidirectional link separately:

text

CLIENT                                                       SERVER
  |--- FIN -------------------------------------------------->| (State: CLOSE_WAIT)
  |<-- ACK ---------------------------------------------------|
  |                                                           |
  |<-- FIN ---------------------------------------------------| (State: LAST_ACK)
  |--- ACK --------------------------------------------------->| (State: CLOSED)

To guarantee that the final ACK was delivered and to prevent delayed duplicate segments from corrupting future connections, the initiating client enters the TIME-WAIT state for a duration of $2 \cdot MSL$ (Maximum Segment Lifetime).

Silly Window Syndrome (SWS)

Silly Window Syndrome occurs when either the sender writes data very slowly or the receiver consumes data very slowly, resulting in the exchange of extremely small TCP segments (sometimes containing only a 1-byte payload wrapped in 40 bytes of header).

1. Sender-Side SWS: Nagle's Algorithm

Nagle’s algorithm prevents the sender from emitting tiny segments by waiting to buffer data based on the network's feedback speed:

python

# Pseudo-code for Nagle's Algorithm
def on_application_write(data):
    append_to_send_buffer(data)
    if length(send_buffer) >= MSS:
        send_segment(get_bytes(send_buffer, MSS))
    else:
        if no_unacknowledged_data_in_flight():
            send_segment(clear_buffer(send_buffer))
        else:
            # Keep buffering until an ACK arrives or we reach MSS
            hold_in_buffer()

2. Receiver-Side SWS: Clark's Solution and Delayed ACKs

Clark's Solution: The receiver prevents SWS by advertising a window size of $0$ when its internal buffer is full or near-empty. It continues to advertise a window size of $0$ until the application processes enough data to create room for either a Maximum Segment Size (MSS) segment or at least half of the total receiver buffer.
Delayed Acknowledgments: The receiver delays sending an ACK for up to $500\text{ ms}$ , waiting for either another segment to arrive (allowing a single cumulative ACK for both segments) or for its application layer to consume data, which can then be announced on a piggybacked ACK segment.

6. TCP Error and Congestion Control

TCP couples flow control, error control, and congestion control to maximize network throughput while preventing congestion collapse.

Retransmission Timeout (RTO) Calculations

To adapt to varying network paths, TCP continuously measures the round-trip time ( $RTT_M$ ) of transmitted segments and dynamically computes a Retransmission Timeout ( $RTO$ ).

Using the Jacobsson/Karels algorithm, let:

$RTT_S$ : Smoothed RTT (weighted moving average)
$RTT_D$ : RTT Deviation (variance estimate)
$\alpha$ : Smoothing factor ( $\approx 0.125$ )

For each successful, non-retransmitted segment measurement $RTT_M$ :

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

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

$RTO = RTT_S + 4 \cdot RTT_D$

Note: If a segment must be retransmitted, Karn’s algorithm dictates that the RTT of that retransmitted segment cannot be used to update $RTT_S$ and $RTT_D$ (due to acknowledgment ambiguity). Instead, the RTO is temporarily doubled for each subsequent timeout (exponential backoff).

Congestion Control Strategies

TCP implements a congestion window ( $cwnd$ ) to throttle transmission rates based on estimated network capacity.

text

    Congestion Window (cwnd)
      ^
      |                                              +-- Congestion Detected
      |                                             /    (3 Duplicate ACKs)
      |                                 +---+  +---+     --> cwnd = ssthresh
      |                             +---+   | /          --> Additive Increase
      |                         +---+       |/             (Congestion Avoid)
      |                     +---+           +
      |                 +---+
      |             +---+   <--- Exponential Increase
      |         +---+            (Slow Start)
      |     +---+
      | +---+
      +------------------------------------------------------------> Time

Slow Start: When a connection begins, the sender sets $cwnd = 1 \text{ MSS}$ . For each received ACK, the window increases by 1:

$cwnd \leftarrow cwnd + 1$

This leads to an exponential growth of the congestion window size each RTT, continuing until $cwnd$ reaches a slow start threshold ( $ssthresh$ ). 2. Congestion Avoidance: Once $cwnd \ge ssthresh$ , the window growth transitions to an additive increase phase. For each ACK received:

$cwnd \leftarrow cwnd + \frac{1}{cwnd}$

This results in an increase of $1 \text{ MSS}$ per RTT, allowing the sender to probe the network's capacity safely. 3. Congestion Detection and Policy:

On Timeout: Indicates severe congestion. TCP sets $ssthresh = \frac{cwnd}{2}$ , drops $cwnd$ back to $1 \text{ MSS}$ , and restarts the Slow Start phase.

7. Summary

Reliable Data Transfer: Requires robust addressing (socket addresses), flow control (rate balancing), and error control (detection and correction).
Stop-and-Wait: Simple flow control protocol restricted to a 1-bit sequence number space (modulo-2). However, it suffers from poor link utilization on high-latency or high-bandwidth links.
Go-Back-N: A pipelined sliding window protocol with a receiver window of size 1. If a packet is lost, the cumulative ACK design forces the sender to go back and retransmit all outstanding segments.
Selective-Repeat: Optimizes bandwidth usage on lossy links by allowing a receiver window greater than 1. This permits out-of-order buffering, and the sender only retransmits the specific segments that were lost.
TCP Implementation: TCP maps these concepts to byte-stream transfer, handling Silly Window Syndrome via Nagle's algorithm and Clark's solution, and estimating network conditions dynamically to calculate the RTO and adjust the congestion window ( $cwnd$ ).

Assessed progress

Reliable Data Transfer Protocols

Reliable Data Transfer Protocols

1. Principles of Reliable Data Transfer

Addressing: Port Numbers and Socket Addresses

Core Control Mechanisms

2. Stop-and-Wait Protocol

Design and Modulo Arithmetic

Mathematical Link Utilization Analysis

Example Calculation:

3. Go-Back-N (GBN) Protocol

Sliding Windows in GBN

Cumulative Acknowledgments

4. Selective-Repeat (SR) Protocol

Design and Window Size Constrains

Individual Acknowledgments

5. TCP Reliable Data Delivery

TCP Segment and Numbering

Connection State transitions (Three-Way Handshake)

Silly Window Syndrome (SWS)

1. Sender-Side SWS: Nagle's Algorithm

2. Receiver-Side SWS: Clark's Solution and Delayed ACKs

6. TCP Error and Congestion Control

Retransmission Timeout (RTO) Calculations

Congestion Control Strategies

7. Summary

Key Concepts

Stop-and-Wait Protocol

Go-Back-N (GBN) Protocol

Selective-Repeat (SR) Protocol

Sliding Window Mechanism

Flow and Error Control

Quick Check

Computer Networks

Computer Networks