📡 Tutorial 4: Principles of Reliable Data Transfer – Advanced

University‑level treatment – COMP347 (TrustOpen University)

📘 1. The Reliable Data Transfer Problem

Consider a sender that wants to send a stream of data to a receiver across an unreliable channel. The channel may:

• Corrupt bits (bit errors).
• Lose packets (packet drops).
• Reorder packets (out‑of‑order delivery).
• Duplicate packets (due to retransmissions).

The goal of a reliable data transfer protocol is to ensure that the receiver delivers an exact, in‑order copy of the sender’s data to the application, despite these imperfections. The protocol operates at the transport layer, using the network layer’s unreliable service.

We abstract the sender and receiver as two processes that exchange messages (packets) over an unreliable channel. The protocol is defined by the actions taken upon events: data from the application, packet arrival from the network, and timeout expiration.

📘 2. Formal Modeling with Finite‑State Machines

A finite‑state machine (FSM) is a mathematical model used to specify the behaviour of a protocol. It consists of:

• A finite set of states.
• A set of transitions triggered by events.
• Actions that occur during transitions (e.g., send a packet, start a timer).

For a reliable data transfer protocol, we typically model the sender and receiver separately. Each has an FSM that describes its response to events. For example, the sender might have states: Wait for data from application, Wait for ACK, etc. Transitions occur on events like rdt_send(data) (application calls send), rdt_rcv(packet) (a packet arrives from the network), and timeout.

FSMs are crucial for proving correctness and detecting design flaws. They are also used in protocol specification documents.

+-----------------------------------+
|  Wait for call from above         |
|  (state: ready)                   |
+-----------------------------------+
   | event: rdt_send(data)
   | action: make_packet, send, start_timer
   v
+-----------------------------------+
|  Wait for ACK/NAK                 |
|  (state: waiting)                 |
+-----------------------------------+
   | event: rdt_rcv(ACK)
   | action: stop_timer, deliver to app, go to ready
   | event: rdt_rcv(NAK) or timeout
   | action: retransmit, restart_timer, stay in waiting
        

📘 3. Basic Mechanisms

3.1 Error Detection

To detect corrupted packets, we add a checksum field to the packet. The receiver verifies the checksum; if it fails, the packet is discarded. This is the first line of defence against bit errors.

3.2 Acknowledgments (ACKs) and Negative Acknowledgments (NAKs)

• ACK: The receiver sends a positive acknowledgment to confirm correct receipt.
• NAK: The receiver sends a negative acknowledgment to indicate that the packet was corrupted.

Using ACKs, the sender knows when to send the next packet. Using NAKs, the sender can retransmit a corrupted packet without waiting for a timeout (though timeouts are still needed for lost packets).

3.3 Sequence Numbers

Sequence numbers are used to distinguish between different packets, especially when retransmissions occur. Without sequence numbers, the receiver could not tell if an incoming packet is a new packet or a duplicate. For stop‑and‑wait, a 1‑bit sequence number (0 and 1) is sufficient because only one packet is outstanding at a time.

3.4 Timeouts and Retransmissions

If a packet or its ACK is lost, the sender will never receive an acknowledgment. To recover, the sender sets a timer when sending a packet. If the timer expires before an ACK arrives, the sender retransmits the packet. This is the fundamental mechanism for handling packet loss.

📘 4. Stop‑and‑Wait Protocol (rdt3.0)

The stop‑and‑wait protocol (also called rdt3.0) is the simplest reliable protocol that handles packet loss and corruption. It works as follows:

• The sender sends one packet and then waits for an ACK.
• It uses a 1‑bit sequence number to detect duplicates.
• It uses a checksum for error detection.
• The receiver sends an ACK if the packet is correctly received; if corrupted, it discards and waits (no NAK).
• The sender uses a timeout to retransmit if no ACK arrives within a certain period.

The sender FSM has two main states: Wait for call from above (ready to send) and Wait for ACK (packet sent, timer running). The receiver FSM has one state: Wait for packet.

The protocol handles:

• Corruption: checksum detects corruption, packet discarded, sender times out and retransmits.
• Loss: timer expires, sender retransmits.
• Duplicate ACKs/packets: sequence numbers allow receiver to discard duplicates and sender to ignore duplicate ACKs.

Despite its correctness, stop‑and‑wait is inefficient for high‑bandwidth or long‑distance networks because the sender spends most of the time waiting for ACKs.

📘 5. Performance Analysis of Stop‑and‑Wait

The performance of stop‑and‑wait is determined by the utilization (or efficiency) of the link:

U = t_trans / (t_trans + 2 * t_prop)

where:

• t_trans = transmission time of the packet (L / R, where L is packet size in bits, R is bandwidth).
• t_prop = propagation delay (distance / speed of light).
• The factor 2 accounts for the round‑trip time (RTT) = 2 * t_prop (assuming negligible processing and queueing).

This formula ignores the time to transmit the ACK (which is usually small).

The maximum throughput is U * R. For example, with a 1 Gbps link, 100 ms RTT, and 1500‑byte packets, the utilization is about 0.012%, meaning the effective throughput is only ~120 kbps. This is clearly insufficient.

The key limitation is the bandwidth‑delay product: the amount of data that can be in transit (BDP = R * RTT). For stop‑and‑wait to fully utilise the link, the packet size must be at least as large as BDP, which is often impractical.

📘 6. The Bandwidth‑Delay Product and Link Utilization

The bandwidth‑delay product (BDP) is the number of bits that can be in the pipeline (in transit) at any time. To achieve 100% utilization, the sender must have enough data in flight to fill the pipe. In stop‑and‑wait, the amount of data in flight is at most one packet. If the packet size is smaller than BDP, the link is underutilized.

To improve utilization, we need a protocol that allows multiple packets to be outstanding simultaneously – a pipelined protocol. This is the motivation for Go‑Back‑N and Selective Repeat, covered in the next tutorial.

📘 7. Limitations and the Need for Pipelining

Stop‑and‑wait has several drawbacks:

• Low throughput: for large BDP, utilization is very low.
• Inefficient for long RTT: even with moderate bandwidth, long RTTs cause poor performance.
• Limited by packet size: even with large packets, the waiting time dominates.

These limitations led to the development of pipelined protocols, where the sender can transmit multiple packets before waiting for ACKs. The window size determines how many packets can be in flight, allowing the sender to fill the BDP. We will explore Go‑Back‑N and Selective Repeat in Tutorial 5.

📘 8. Advanced Topics: Duplicate Suppression and Cumulative ACKs

8.1 Duplicate Suppression

In stop‑and‑wait, sequence numbers (0 and 1) are sufficient to avoid ambiguity between a new packet and a retransmission. However, if the sender receives a duplicate ACK (e.g., because the receiver sent an ACK that was delayed), the sender must ignore it. The FSM design ensures that duplicate ACKs are simply ignored because the sender only transitions on the first ACK.

8.2 Cumulative ACKs (preview)

In pipelined protocols, cumulative ACKs (where an ACK acknowledges all packets up to a sequence number) reduce the number of ACKs sent and simplify receiver logic. This concept is central to TCP and will be covered in detail later.

8.3 Timer Management

In stop‑and‑wait, a single timer is sufficient. In pipelined protocols, multiple timers or a single timer for the oldest packet may be used (as in Go‑Back‑N). The choice affects performance.

📝 Quiz

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

🛠️ Exercises

Apply your understanding with these 15 exercises. Solutions are provided below each.

📚 Homework

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