Flow Control and Reliable Transmission

Flow Control Overview

Flow control is one of the core functions of the data link layer. It coordinates the rate difference between sender and receiver so that a fast sender cannot overwhelm a slow receiver, overflow its buffer, and lose data.

Flow control is closely tied to error control; together they form the reliable transmission mechanism. The core idea of reliable transmission is to use acknowledgment (ACK) and timeout retransmission so that data arrives at the receiver correctly and in order.

Stop-and-Wait Protocol

Stop-and-wait is the simplest reliable transmission protocol.

How It Works

1. After sending one frame, the sender stops sending and waits for the receiver’s acknowledgment (ACK)
2. After receiving a correct frame, the receiver sends an ACK back to the sender
3. Only after receiving the ACK does the sender transmit the next frame
4. If the sender does not receive the ACK within the timeout period (timeout timer), it retransmits that frame

To deal with duplicate frames — the ACK is lost, the sender retransmits, and the receiver ends up with two identical frames — frames must be numbered. Stop-and-wait uses a 1-bit sequence number (0 and 1), and the ACK carries a sequence number too, indicating “the sequence number of the next frame expected”.

Channel Utilization Analysis

The biggest problem with stop-and-wait is low efficiency. The channel sits idle while the sender waits for the ACK.

Let:

• $T_t$: the frame transmission delay (time to send one frame) = frame length / data rate
• $T_p$: the signal propagation delay = link length / signal propagation speed
• $T_a$: the transmission delay of the ACK (usually very small and negligible)

A complete cycle is: sending the frame $T_t$ + propagation to the receiver $T_p$ + sending the ACK $T_a$ + propagation of the ACK back to the sender $T_p$

The channel utilization (the fraction of the cycle during which the sender is busy) is:

$U = \frac{T_t}{T_t + 2T_p + T_a} \approx \frac{T_t}{T_t + 2T_p}$

Sliding Window Protocol

The sliding window protocol allows the sender to transmit several frames in a row before any acknowledgment arrives, which greatly increases channel utilization.

Basic Concepts

• Send window: the range of sequence numbers for frames the sender may transmit but has not yet had acknowledged. The window size is denoted $W_T$.
• Receive window: the range of sequence numbers for frames the receiver is willing to accept. The window size is denoted $W_R$.
• Window sliding: when the sender receives an ACK the send window slides forward; when the receiver receives a frame and sends an ACK the receive window slides forward.

Sequence Number Space

Frame sequence numbers are represented by $n$ bits, giving a range of $0 \sim 2^n - 1$. To avoid confusing old and new frame sequence numbers — that is, to avoid the receiver being unable to tell a retransmitted old frame from a new one — the send window size must satisfy:

$W_T + W_R \leq 2^n$

For the GBN protocol, $W_R = 1$, so $W_T \leq 2^n - 1$. For the SR protocol, $W_T = W_R$, so $W_T \leq 2^{n-1}$.

Go-Back-N (GBN) Protocol

GBN is an implementation of the sliding window protocol in which the receive window size is 1, meaning the receiver accepts frames strictly in order.

How It Works

1. The sender may transmit several frames from its send window without waiting for acknowledgments
2. The receiver accepts only frames that arrive in order. If an out-of-order frame arrives (because an earlier frame was lost), the receiver discards that frame and sends a duplicate ACK for the last in-order frame received
3. When the sender receives a duplicate ACK or times out, it retransmits the erroneous frame and every frame sent after it that has not yet been acknowledged — that is, it “goes back N frames”

Cumulative Acknowledgment

GBN uses cumulative acknowledgment: ACK $n$ means that frame $n$ and all frames before it have been received correctly. As a result, if an ACK is lost, a later ACK can piggyback the confirmation of the earlier frames.

Characteristics

• Advantages: simple receiver implementation (no buffering of out-of-order frames), and the cumulative acknowledgment mechanism is robust
• Disadvantages: on error it may retransmit frames that were already received correctly, wasting bandwidth; inefficient in environments with a high error rate
• Suitable for: networks with a low error rate, such as wired networks

Selective Repeat (SR) Protocol

SR is the other sliding window protocol, in which the receive window size is greater than 1, so the receiver can buffer frames that arrive out of order.

How It Works

1. The sender may transmit several frames from its send window
2. The receiver sends an individual ACK for every correctly received frame (not a cumulative acknowledgment). A frame that arrives out of order but is correct is buffered and not yet delivered to the layer above
3. The sender maintains an independent timeout timer for each frame. If a frame times out, only that frame is retransmitted (the frames after it are not)
4. Once the missing frame arrives correctly, the receiver delivers the buffered frames to the layer above in order

Characteristics

• Advantages: retransmits only the erroneous frame, which avoids unnecessary retransmissions and is efficient in environments with a high error rate
• Disadvantages: the receiver must buffer out-of-order frames, which complicates the implementation; each frame needs individual acknowledgment and timing
• Suitable for: networks with a high error rate, such as wireless networks

Comparison of the Three Protocols

Worked Examples

Example 1: Channel Utilization of Stop-and-Wait

On a channel with a data rate of 1 Mbps and a propagation delay of 20 ms, the stop-and-wait protocol transmits frames of 1000 bytes. Find the channel utilization. If the sliding window protocol is used instead, what is the minimum window size that achieves a channel utilization of 80%?

Example 2: Sequence Numbers and Windows in GBN

A GBN protocol uses 3-bit sequence numbers and a send window size of 5. At a certain moment the sender’s send window is [2, 3, 4, 5, 6] (the sequence numbers of frames sent but not yet acknowledged). The sender then receives ACK 4. (1) What is the new send window? (2) Which sequence numbers may the sender transmit next?

Example 3: The Sequence Number Space of SR

A selective repeat protocol uses 4-bit sequence numbers, and the send window and the receive window have equal sizes. What is the maximum window size? What goes wrong if the window size is set to 9?

---

Exercises

Exercise 1

Compare the stop-and-wait, GBN, and SR protocols in terms of their retransmission policies and receiver buffering.

Exercise 2

On a channel with a data rate of 10 Mbps and a propagation delay of 5 ms, the stop-and-wait protocol transmits frames of 1500 bytes. Find the channel utilization.

---

Glossary