CS Atlas GATE 2027
Computer Networks course
0 / 90 complete

Computer Networks/Phase 4 · Transport Layer (TCP)

Lesson 4.2.3 · Item 64 of 90

Go-Back-N (GBN): Ws ≤ 2ᵏ−1, cumulative ACKs & retransmission counting

Read at your own pace. Try the questions before opening the answers.

On this page

Recall warm-up

  1. In the universal window bound W_s + W_r ≤ 2ᵏ, what do we get for W_s if the receiver window is W_r = 1?
    Stuck? Peek at 4.2.2 Sliding window protocols, pipelining & k-bit sequence numbers
    • Sliding-window utilisation: η = min(1, N / (1 + 2a)); full utilisation at N = ⌈1 + 2a⌉.
    • k-bit sequence space: 0 .. 2ᵏ − 1 (2ᵏ numbers); universal bound: Ws + Wr ≤ 2ᵏ.

    Read lesson 4.2.2

  2. In Stop-and-Wait ARQ, what happens when the sender’s timeout timer expires?
    Stuck? Peek at 4.2.1 Stop-and-Wait ARQ, 1-bit sequence numbers & link utilisation
    • Stop-and-Wait ARQ: 1 packet in flight; uses 1-bit sequence numbers (0, 1) to discard duplicates when ACKs are lost.
    • Utilisation: η = Tt / (Tt + 2·Tp) = 1 / (1 + 2a), where a = Tp / Tt (with losses of prob p: (1 − p)/(1 + 2a)).
    • Throughput: η × B = L / (Tt + 2·Tp).

    Read lesson 4.2.1

  3. If a sender transmits frames 1, 2, 3, 4 back-to-back and frame 2 is lost, in what order do frames 1, 3, 4 arrive at the receiver?
    Stuck? Peek at 1.3.2 Propagation, queuing and processing delay; multi-hop pipelining
    • Tp = d / v, v = 2 × 10⁸ m/s default; independent of size and rate.
    • Nodal delay = d_proc + d_queue + Tt + Tp.
    • One packet, h equal links: h·Tt + h·Tp.
    • N packets, h equal links: (N + h − 1)·Tt + h·Tp (+ (h − 1)·d_proc).
    • Unequal links: first packet ΣTt + ΣTp, then + (N − 1) × max Tt.
    • Traffic intensity L·a/R → 1: queues explode.

    Read lesson 1.3.2

The Hook

What is the simplest possible receiver for a pipelined sliding-window protocol? A receiver with zero out-of-order buffer space (Wr = 1)! If the receiver is waiting for Frame 2 and Frame 3 arrives instead, the receiver simply throws Frame 3 in the bin and keeps saying "I still want Frame 2!"

Because the receiver discarded Frames 3, 4, 5 after Frame 2 was lost, when the sender times out on Frame 2 it must go back to Frame 2 and retransmit Frame 2 AND all subsequent frames in the window. That is Go-Back-N (GBN) — a top GATE numerical favourite!

Predict First

With a 2-bit sequence number (k = 2, so sequence numbers are 0, 1, 2, 3), suppose a GBN sender illegally sets its window size to Ws = 2² = 4 and sends frames 0, 1, 2, 3. All four reach the receiver (which now expects new frame 0), and the receiver sends ACKs, but all ACKs are lost! When the sender times out and retransmits old frame 0, what disaster happens at the receiver?

,

Because the receiver already accepted 0, 1, 2, 3, its window has wrapped around and is now waiting for new frame 0 (the 5th frame)! When the retransmitted old frame 0 arrives, the receiver accepts it as the 5th frame (silent data corruption/duplication)! Limiting Ws ≤ 2ᵏ − 1 = 3 prevents this completely.

Core Concept

Rules of Go-Back-N (GBN) ARQ

In Go-Back-N with k-bit sequence numbers:

  • Sender Window: Ws ≤ 2ᵏ − 1.
  • Receiver Window: Wr = 1 (accepts frames strictly in order; silently discards any out-of-order frame, even if error-free!).
  • Cumulative Acknowledgements: An ACK for sequence number n confirms that all frames up through n have arrived in order. (If ACK 1 and ACK 2 are lost on the link, but ACK 3 arrives before the timer for Frame 1 expires, ACK 3 acknowledges Frames 1, 2, AND 3 at once — no retransmission needed!)
  • Timeout Action: When the oldest unacknowledged frame f times out, the sender goes back and retransmits f and all subsequent frames already sent in the current window.
Sender (Ws = 3, k = 2)Receiver (Wr = 1)Frame 0 (accepted, deliver)✕Frame 1 (LOST!)Frame 2 (out of order → DISCARDED!)ACK 0 (still waiting for Frame 1)Frame 3 (out of order → DISCARDED!)Timeout for Frame 1! Go back to 1:Retransmit Frame 1, then 2, then 3
Go-Back-N on loss of Frame 1 (with Ws = 3): Frames 2 and 3 arrived intact but are discarded because Wr = 1!

Proof of Why Ws ≤ 2ᵏ − 1 in GBN

Why is Ws = 2ᵏ − 1 safe while Ws = 2ᵏ fails? Compare both when all ACKs in a full window are lost:

Ws = 2ᵏ − 1 = 3 (k=2) — SAFE
Sender sends 0, 1, 2. Receiver accepts 0, 1, 2 and now expects 3. All ACKs are lost! Sender times out and resends 0, 1, 2. Receiver expects 3, sees 0 ≠ 3 → discards duplicates cleanly!
Ws = 2ᵏ = 4 (k=2) — FAILS!
Sender sends 0, 1, 2, 3. Receiver accepts 0, 1, 2, 3 and now expects 0 (wrapped around!). All ACKs are lost! Sender resends old 0 → Receiver accepts old 0 as new 0!
Why GBN max sender window is 2ᵏ − 1 (and minimum bits for window N is k = ⌈log₂(N + 1)⌉).

GATE Favourite: Counting Total Transmissions when Every K-th Frame is Lost

A classic GATE NAT problem states: "Sender uses GBN with window size N to send M frames, and every K-th transmitted frame is lost. How many total transmissions are required?"

The Mechanical GBN Trace Rule:
When frame f is transmitted as the K-th transmission (so it is lost), the sender does not know yet! Before timing out on f, the sender transmits the remaining frames in its window starting at f: namely f + 1, f + 2, …, min(M, f + N − 1) (each of which increments the transmission counter and is discarded at the receiver). Then the timeout fires and the sender restarts at f!
Burst / WindowFrames Transmitted (Tx # in brackets)What happened?Delivered so far
Initial flow1(tx1), 2(tx2), 3(tx3), 4(tx4)All 4 succeed!1, 2, 3, 4
Loss at Frame 5 (N=3)5(tx5 LOST!), 6(tx6 disc), 7(tx7 disc)5 is 5th tx (lost); 6, 7 fill window of 3 and are discarded1..4
Retry from 5 + slide5(tx8), 6(tx9), 7(tx10 LOST!), 8(tx11 disc), 9(tx12 disc)5, 6 succeed; 7 is 10th tx (lost); 8, 9 discarded1..6
Retry from 7 + slide7(tx13), 8(tx14), 9(tx15 LOST!), 10(tx16 disc)7, 8 succeed; 9 is 15th tx (lost); 10 discarded (cap at M=10!)1..8
Retry from 99(tx17), 10(tx18)9 and 10 succeed! Done!1..10 (Total = 18 tx)
Complete trace of sending M = 10 frames with GBN window N = 3 when every 5th transmission is lost: 18 total transmissions!

Putting it together

  • Go-Back-N uses a simple receiver with W_r = 1 (in-order acceptance only) and cumulative ACKs.
  • To avoid wrap-around ambiguity when all ACKs are lost, the sender window must satisfy W_s ≤ 2ᵏ − 1 (so k = ⌈log₂(N + 1)⌉).
  • When frame f is lost, the remaining frames in the window after f are discarded by the receiver and must be retransmitted after timeout.

Visual

Frame f sent at tx = m·K
LOST on link!
Sender finishes window
sends f+1 .. min(M, f+N−1) (all discarded)
Timeout for f fires
Go-Back-N!
Restart sending from f
continuing tx counter
Exact recipe for tracing GBN "every K-th packet lost" problems without error.

Worked Examples

Easy

A Go-Back-N protocol uses a 4-bit sequence number field (k = 4). What is the maximum permissible sender window size Ws, and what is the receiver window size Wr?

Show the full solution

Ws = 2⁴ − 1 = 16 − 1 = 15; Wr = 1.

Medium

A link has a = Tp / Tt = 4. If Go-Back-N is used and must achieve 100% link utilisation, what is the minimum number of bits k needed in the sequence number field?

Show the full solution

1) For 100% utilisation, minimum window size is N = 1 + 2a = 1 + 8 = 9.
2) In GBN, we need 2ᵏ − 1 ≥ N = 9 → 2ᵏ ≥ 10 → k = ⌈log₂(10)⌉ = 4 bits (which allows up to Ws = 15).

GATE

A sender uses Go-Back-N ARQ with sender window size N = 4 to transmit M = 9 frames (numbered 1 to 9). Every 5th transmitted frame (i.e. transmission #5, #10, #15, #20, …) is lost, while ACKs are never lost. How many total frame transmissions take place until all 9 frames are acknowledged?

Show the full solution

Trace with the window-of-4 rule (when frame f is lost, up to 3 subsequent frames f+1 .. min(9, f+3) are sent and discarded):
• 1(tx1), 2(tx2), 3(tx3), 4(tx4) — delivered 1..4.
• 5(tx5 LOST), followed by 6(tx6), 7(tx7), 8(tx8) (discarded).
• Timeout → 5(tx9) [ok], 6(tx10 LOST), followed by 7(tx11), 8(tx12), 9(tx13) (discarded).
• Timeout → 6(tx14) [ok], 7(tx15 LOST), followed by 8(tx16), 9(tx17) (only 2 left up to 9, discarded).
• Timeout → 7(tx18) [ok], 8(tx19) [ok], 9(tx20 LOST) (0 frames after 9).
• Timeout → 9(tx21) [ok].
Total transmissions = 21!

GATE Traps

  • The N = 2ᵐ trap! If required window size is N = 8, students write log₂(8) = 3 bits — WRONG! With 3 bits, GBN max window is 2³ − 1 = 7 < 8, so you MUST use 4 bits!
  • Lost ACK ≠ Automatic Retransmission in GBN! Because GBN uses cumulative ACKs, if ACK 2 is lost but ACK 3 arrives before Frame 2's timer expires, Frame 2 is NOT retransmitted!

Memory Hook

GBN: Wr = 1, Ws ≤ 2ᵏ − 1 (k = ⌈log₂(N + 1)⌉), cumulative ACKs, and one lost packet wastes the whole window behind it!

Connect the Dots

In Example 3, losing 4 packets forced us to transmit 21 times because GBN threw away good out-of-order packets! Next question (4.2.4): What if we give the receiver a buffer of size Wr = Ws so it can keep out-of-order packets and only retransmit the exact packet that was lost?

Self-Test

  1. NAT

    In a Go-Back-N ARQ protocol, the required sender window size for full link utilisation is N = 8 frames. What is the minimum number of bits k required in the sequence number field?

    Write your answer before opening the key.

  2. NAT

    A sender uses Go-Back-N with sender window size N = 3 to send M = 10 frames. Every 5th transmitted frame (5th, 10th, 15th, …) is lost. How many total frame transmissions are needed to deliver all 10 frames?

    Write your answer before opening the key.

  3. MCQ

    In Go-Back-N ARQ with window size W_s = 4, the sender transmits frames 0, 1, 2, 3. All four frames arrive intact at the receiver, and the receiver sends ACK 0, ACK 1, ACK 2, ACK 3. Suppose ACK 1 and ACK 2 are lost on the link, but ACK 3 arrives at the sender before any timer expires. How many frames does the sender retransmit?

    1. 0 frames (none)
    2. 1 frame (Frame 1)
    3. 2 frames (Frames 1 and 2)
    4. 3 frames (Frames 1, 2, and 3)
  4. MSQ

    Which of the following statements about Go-Back-N (GBN) ARQ are TRUE?

    1. The receiver window size W_r is always 1.
    2. With k-bit sequence numbers, the maximum sender window size is 2ᵏ − 1.
    3. If frame 2 is lost, the receiver buffers frames 3 and 4 so they do not need to be retransmitted.
    4. GBN uses cumulative acknowledgements.

Rule Card

  • Go-Back-N bounds: Wr = 1, Ws ≤ 2ᵏ − 1 ⇒ minimum bits for window N is k = ⌈log₂(N + 1)⌉.
  • Cumulative ACK: confirms all frames up to that number (survives lost earlier ACKs).
  • On loss of frame f: receiver discards f+1 .. min(M, f+N−1); sender times out and retransmits from f.

Concept Ledger

  • Go-Back-N (GBN)
  • Ws ≤ 2ᵏ − 1
  • Wr = 1
  • cumulative ACK
  • GBN retransmission counting

Answer Vault

Try the questions first. Open when you are ready to check.

Warm-up answers

  1. W_s ≤ 2ᵏ − 1.
  2. The sender retransmits the unacknowledged frame.
  3. Frame 1 arrives in order, followed by frames 3 and 4 which arrive out of order (since frame 2 is missing).

Self-test answers

  1. 4 — In GBN, 2ᵏ − 1 ≥ N = 8 → 2ᵏ ≥ 9 → minimum integer k = 4 bits (since 3 bits only allow W_s = 7).
  2. 18 — As traced in the lesson table: tx 1..4 (1..4 ok); tx 5..7 (5 lost, 6,7 disc); tx 8,9 (5,6 ok); tx 10..12 (7 lost, 8,9 disc); tx 13,14 (7,8 ok); tx 15,16 (9 lost, 10 disc); tx 17,18 (9,10 ok) → 18 transmissions.
  3. A — GBN uses cumulative acknowledgements: ACK 3 confirms that all frames up to 3 (including 1 and 2) have been received in order, so 0 frames are retransmitted!
    • B: Cumulative ACK 3 covers Frame 1.
    • C: Cumulative ACK 3 covers both Frame 1 and Frame 2.
    • D: Timeout never fires because ACK 3 arrives in time.
  4. ABD — In GBN, W_r = 1, W_s ≤ 2ᵏ − 1, and ACKs are cumulative. Out-of-order frames (like 3 and 4 when 2 is lost) are discarded, not buffered.
    • C: In Go-Back-N, W_r = 1 so out-of-order frames are discarded, not buffered.

Flashcards

  1. In Go-Back-N with k-bit sequence numbers, what are max W_s and W_r?
    Reveal answerMax W_s = 2ᵏ − 1; W_r = 1.
  2. Formula for minimum sequence-number bits k in GBN for window size N?
    Reveal answerk = ⌈log₂(N + 1)⌉.
  3. Why doesn’t a lost ACK necessarily cause a retransmission in GBN?
    Reveal answerBecause ACKs are cumulative: a later ACK arriving before timeout acknowledges all earlier frames too.

Exam shortcuts

  • Minimum bits for GBN window N: k = ⌈log₂(N + 1)⌉ (don't forget the + 1! If N = 8, 2³ − 1 = 7 < 8, so you need k = 4 bits!). — every GATE question where N = 2ᵐ.
  • End-of-file cap in GBN retx: When frame f is lost near the end of M frames, only min(N − 1, M − f) extra frames are transmitted before timeout, NOT always N − 1! — getting the exact count on the last 1–2 losses.
ONE MORE CONNECTION MADE

Ready for the next idea?

Mark this item complete when you’ve finished reading and working through it.