# Flow Control and Sliding Window — Stop-and-Wait, Go-Back-N and Selective Repeat with Numericals

Source: https://skills101.in/learn/computer-networks/cn-flow-control-sliding-window — Skills101 free tutorial (Computer Networks). Updated 2026-11-21.

A fast laptop can send data far faster than a slow phone can process it. If the sender does not slow down, the receiver's buffer fills up and packets are dropped. **Flow control** is the set of rules that stops a sender from overwhelming a receiver. This lesson covers the three classic protocols that university exams and GATE ask about, and the numericals that come with them.

## 1. Two times you must know

Every numerical in this topic uses two times:

| Term | Meaning | Formula |
|---|---|---|
| **Transmission time (Tt)** | time to push all bits of a frame onto the wire | frame size ÷ bandwidth |
| **Propagation time (Tp)** | time for one bit to travel to the other end | distance ÷ signal speed |

Think of a train. Tt is how long the train takes to pass the station gate (it depends on the train's length). Tp is how long the engine takes to reach the next city (it depends on the distance).

The ratio **a = Tp / Tt** decides how wasteful a protocol is. A long link with small frames has a large a.

**Example.** Frame = 1,000 bytes, bandwidth = 1 Mbps, distance = 2,000 km, signal speed = 2 × 10⁸ m/s.

- Tt = 8,000 bits ÷ 10⁶ bits/s = **8 ms**
- Tp = 2 × 10⁶ m ÷ 2 × 10⁸ m/s = **10 ms**
- a = 10 / 8 = **1.25**

## 2. Stop-and-wait

The simplest protocol: send **one** frame, then wait for its **ACK** (acknowledgement) before sending the next one. If the ACK does not arrive before a **timer** runs out, send the frame again.

One cycle takes Tt (sending) + Tp (frame travels) + Tp (ACK travels back; the ACK is tiny, so its own Tt is ignored). The sender is busy only for Tt of that time:

**Efficiency η = Tt / (Tt + 2Tp) = 1 / (1 + 2a)**

For our link: η = 1 / (1 + 2.5) = **28.6%**. The useful throughput is 0.286 × 1 Mbps ≈ **286 kbps**, even though the line can carry 1 Mbps. For more than 70% of the time the sender is idle, waiting.

Stop-and-wait needs only a **1-bit** sequence number (frames 0, 1, 0, 1…). The receiver uses it to spot a duplicate frame when an ACK is lost and the sender resends.

## 3. Sliding window: keep the pipe full

The fix is to send **several frames** before the first ACK returns. The sender may have up to **N** unacknowledged frames in flight; N is the **window size**. As each ACK arrives, the window **slides** forward and one more frame can go.

**Efficiency η = N / (1 + 2a)**, capped at 100%.

![Bar chart of link efficiency for window sizes 1 to 5 when a equals 1.25: 28.6, 57.1 and 85.7 percent, then 100 percent from window 4 onwards](https://skills101.in/learn-img/computer-networks/window-efficiency.svg)

To reach 100%, the window must cover one full round trip: **N ≥ 1 + 2a**. Here 1 + 2a = 3.5, so a window of **4** frames keeps the link busy all the time.

The same numbers in Python:

```python
Tt = 1000 * 8 / 1e6        # seconds
Tp = 2000e3 / 2e8          # seconds
a = Tp / Tt
print("a =", a)
for N in (1, 2, 3, 4):
    eff = min(1.0, N / (1 + 2 * a))
    print(f"N = {N}: efficiency {eff * 100:.1f}%")
```

```text
a = 1.25
N = 1: efficiency 28.6%
N = 2: efficiency 57.1%
N = 3: efficiency 85.7%
N = 4: efficiency 100.0%
```

## 4. Go-Back-N (GBN)

What happens when a frame in the middle of the window is lost? Go-Back-N keeps the receiver simple:

- The receiver accepts frames **only in order**. If frame 2 is missing, it **discards** frames 3, 4, 5 even if they arrive perfectly.
- ACKs are **cumulative**: "ACK 2" means "I have everything before 2".
- When the timer for frame 2 expires, the sender **goes back** and resends frame 2 **and every frame after it**.

![Go-Back-N with window 4 and frame 2 lost: frames 0 to 5 are sent, then 2, 3, 4 and 5 are sent again, then frame 6 — eleven transmissions for seven frames](https://skills101.in/learn-img/computer-networks/gbn-timeline.svg)

Why are 4 and 5 sent before the sender notices? ACKs for frames 0 and 1 arrive normally, so the window slides to cover frames 2–5. The sender sends 4 and 5, and only then does frame 2's timer expire.

A short simulation that counts the transmissions:

```python
def gbn_transmissions(n_frames, window, lost):
    sends, base, lost = [], 0, sorted(lost)
    while base < n_frames:
        nxt = next((f for f in lost if f >= base), None)
        last = n_frames - 1 if nxt is None else min(nxt + window - 1, n_frames - 1)
        sends += list(range(base, last + 1))
        if nxt is None:
            break
        lost.remove(nxt)   # each lost frame is lost only once
        base = nxt
    return sends

s = gbn_transmissions(7, 4, [2])
print(s)
print("total:", len(s))
```

```text
[0, 1, 2, 3, 4, 5, 2, 3, 4, 5, 6]
total: 11
```

Seven frames needed **11** transmissions — the 3 good frames after the lost one were wasted.

## 5. Selective Repeat (SR)

Selective Repeat makes the receiver smarter:

- The receiver **buffers** out-of-order frames (3, 4, 5 are kept).
- It sends an **individual ACK** (or a NAK, negative acknowledgement) for each frame.
- The sender resends **only** the lost frame.

In the example above, SR needs only **8** transmissions (7 frames + 1 resend). The cost is a bigger buffer and more complex logic at the receiver.

## 6. Window size and sequence numbers

With **k** bits for the sequence number, frames are numbered 0 to 2ᵏ − 1 and then wrap around. The window must be small enough that the receiver never confuses an old frame with a new one:

| Protocol | Sender window | Receiver window | With k = 3 |
|---|---|---|---|
| Stop-and-wait | 1 | 1 | — (k = 1 is enough) |
| Go-Back-N | at most 2ᵏ − 1 | 1 | 7 |
| Selective Repeat | at most 2ᵏ⁻¹ | same as sender | 4 |

**Why not 2ᵏ for GBN?** With k = 2 (numbers 0–3) and a window of 4, the sender sends 0, 1, 2, 3. Suppose all four arrive but all four ACKs are lost. The receiver now expects the **next** frame 0. The sender times out and resends the **old** frame 0 — and the receiver accepts it as new. A window of 3 avoids this.

**Exam pattern.** "a = 1.25. How many sequence-number bits are needed for 100% efficiency with GBN?" → N must be at least 3.5, so N = 4. GBN needs 2ᵏ − 1 ≥ 4, so **k = 3**. For SR, 2ᵏ⁻¹ ≥ 4 also gives **k = 3**.

## 7. How TCP does it

TCP uses a sliding window counted in **bytes**, not frames. Every ACK carries a **window size** field (lesson 9) — the free space in the receiver's buffer. If the receiver advertises 0, the sender stops and sends small **window probes** until space opens up. TCP behaves like a mix of the two protocols: cumulative ACKs like GBN, but receivers keep out-of-order data, and the SACK option lets the sender resend only missing pieces, like SR.

Flow control protects the **receiver**. Protecting the **network** in the middle is a different job — congestion control, the next lesson.

## Common mistakes

- Forgetting the factor 2 in 1 + 2a — the ACK has to travel back too.
- Using bytes and bits together: convert the frame size to bits before dividing by bandwidth.
- Saying GBN resends only the lost frame — it resends the lost frame **and everything after it**.
- Using 2ᵏ as the GBN window. The maximum is 2ᵏ − 1 for GBN and 2ᵏ⁻¹ for SR.
- Mixing up flow control (receiver's buffer) with congestion control (the network).

## Quick recap

- Tt = frame size ÷ bandwidth; Tp = distance ÷ speed; a = Tp / Tt.
- Stop-and-wait efficiency = 1 / (1 + 2a); sliding window = N / (1 + 2a), at most 100%.
- 100% needs N ≥ 1 + 2a.
- GBN: receiver window 1, cumulative ACKs, resend from the lost frame onwards; window ≤ 2ᵏ − 1.
- SR: receiver buffers, resend only lost frames; window ≤ 2ᵏ⁻¹.
- TCP uses a byte-based sliding window advertised by the receiver.


Practice quiz and free certificate: https://skills101.in/learn/computer-networks/cn-flow-control-sliding-window