Self-checkedTier 1 8 min readcn.sliding-window-protocols

Sliding window: stop-and-wait, Go-Back-N, Selective Repeat

Reliable delivery over a lossy link with acknowledgements, timeouts and sequence numbers: stop-and-wait, the sliding window idea that keeps the pipe full, Go-Back-N (cumulative acknowledgements, receiver window 1, resend everything from the lost frame) and Selective Repeat (individual acknowledgements, receiver buffers, resend only the lost frame), the utilisation min(1, N / (1 + 2a)), the window needed to fill the pipe, and the limits on the window for k-bit sequence numbers (2^k - 1 and 2^(k-1)); animations come from a slotted simulation of the protocols.

Why it exists

A link or a network can lose or damage frames (the CRC detects damaged ones, which are then dropped, error detection). To deliver data reliably, the receiver acknowledges what it receives, the sender keeps a copy until acknowledged and retransmits after a timeout. The simplest scheme sends one frame and waits for its acknowledgement. On a long fast link this leaves the channel idle almost all the time (performance metrics); sliding window protocols keep several frames in flight.

Prerequisites

You need transmission time, propagation delay and the bandwidth-delay product (performance metrics).

Precise definitions

Frames are numbered with sequence numbers. Let $t_t$ be the transmission time of a frame, $t_p$ the one-way propagation delay, $a = t_p / t_t$ . Acknowledgements are short (their transmission time is ignored) and the round-trip cycle of a frame is $t_t + 2 t_p = t_t (1 + 2a)$ .

Stop-and-wait. Send one frame, wait for its acknowledgement (or a timeout, then resend). Sequence numbers alternate $0, 1, 0, 1$ (1 bit) so that the receiver can tell a retransmission from a new frame. Utilisation $= 1/(1 + 2a)$ .

Sliding window. The sender may have up to $N$ frames outstanding (sent, not yet acknowledged): its window holds their sequence numbers; each acknowledgement slides the window forward. With a window of $N$ frames per cycle the utilisation (no errors) is

U = \min\Bigl(1,\ \frac{N}{1 + 2a}\Bigr),

and the window that keeps the sender busy all the time is $N \ge 1 + 2a$ (that is, the bandwidth-delay product in frames, plus one).

Go-Back-N (GBN). The receiver accepts frames only in order (receiver window $= 1$ ) and sends cumulative acknowledgements: acknowledgement $n$ means "all frames up to $n$ have arrived". If a frame is lost or damaged, the receiver discards all later frames and repeats the last acknowledgement; the sender's timer for the oldest unacknowledged frame expires and the sender goes back and retransmits that frame and all frames after it.

Selective Repeat (SR). The receiver accepts any frame inside its window (receiver window $= N$ ), stores out-of-order frames and acknowledges each frame individually; the sender keeps a timer per frame and retransmits only the frames that were not acknowledged. The receiver delivers frames to the upper layer in order.

Sequence number space. With $k$ -bit sequence numbers there are $2^k$ values, used modulo $2^k$ . The window size is limited so that old and new frames are never confused:

Go-Back-N: $N \le 2^k - 1$ ;
Selective Repeat: $N \le 2^{k-1}$ (half the sequence numbers);
stop-and-wait: $N = 1$ (so $1$ bit suffices).

How it works

Why windows

Utilisation of the sender with window size N: start

Computed by a script, not typed

link	transmission time tt	a = tp / tt	stop-and-wait	N = 7	N = 127	window to fill the pipe 1 + 2a
1000-bit frames, 1 Mbps, one-way 10 ms
8000-bit frames, 1 Mbps, one-way 10 ms
12000-bit frames, 100 Mbps, one-way 5 ms
12000-bit frames, 1 Gbps, one-way 25 ms

Step 0

Acknowledgements are short and take no transmission time, no frames are lost. Utilisation = min(1, N / (1 + 2a)).

0 / 4

computed by script: protocols are simulated slot by slot or round by round, sequence numbers use 32-bit arithmetic. python3 scripts/gen-cn4-traces.py

With $8000$ -bit frames at $1$ Mbps and a one-way delay of $10$ ms, $a = 10/8 = 1.25$ , stop-and-wait uses $1/(1 + 2.5) = 28.6$ percent of the channel; a window of $N = 7$ fills the pipe ( $7/3.5 \ge 1$ ). With $12000$ -bit frames at $1$ Gbps and $25$ ms, $a \approx 2083$ and one needs more than $4000$ frames in flight to use the link; even $127$ frames use only $3$ percent. This is why sequence numbers must be large on fast, long links.

Go-Back-N

Go-Back-N with a lost frame: start

Computed by a script, not typed

time	sender	receiver	frames sent: base .. next
slot 0
slot 1
slot 2
slot 3
slot 4
slot 5
slot 6
slot 7
slot 8
slot 9
slot 10
slot 11
slot 12
slot 13
slot 14
slot 15
slot 16
slot 17

Step 0

10 frames, window N = 4, one-way delay 2 slots (one slot is the transmission time of a frame), frame 3 is lost on its first transmission; timeout = one round trip (4 slots). Acknowledgements are not lost.

0 / 18

computed by script: protocols are simulated slot by slot or round by round, sequence numbers use 32-bit arithmetic. python3 scripts/gen-cn4-traces.py

Window $N = 4$ , round trip $4$ slots. Frame $3$ is lost. The receiver gets $4$ , $5$ and $6$ out of order and discards them, repeating the acknowledgement of frame $2$ ; the sender cannot slide its window past frame $3$ . When the timer for frame $3$ expires (one round trip after it was sent) the sender goes back and resends frames $3, 4, 5, 6$ . Frames $4, 5, 6$ had arrived once already and were thrown away: the capacity wasted is up to $N$ frames per loss.

Selective Repeat

Selective Repeat with a lost frame: start

Computed by a script, not typed

time	sender	receiver	frames sent: base .. next
slot 0
slot 1
slot 2
slot 3
slot 4
slot 5
slot 6
slot 7
slot 8
slot 9
slot 10
slot 11
slot 12
slot 13
slot 14
slot 15
slot 16
slot 17

Step 0

0 / 18

computed by script: protocols are simulated slot by slot or round by round, sequence numbers use 32-bit arithmetic. python3 scripts/gen-cn4-traces.py

The same loss: the receiver stores frames $4, 5, 6$ and acknowledges each of them; after the timeout the sender resends only frame $3$ . When it arrives the receiver can deliver $3$ to $6$ at once.

Frames sent and time in slots for the three protocols: start

Computed by a script, not typed

losses	stop-and-wait (frames / slots)	Go-Back-N	Selective Repeat
0 frame(s) lost
1 frame(s) lost (5)
2 frame(s) lost (5, 11)
3 frame(s) lost (5, 6, 11)

Step 0

The first transmission of the listed frames is lost. 'Frames' is the number of transmissions, 'slots' the time until the last frame is acknowledged.

0 / 4

computed by script: protocols are simulated slot by slot or round by round, sequence numbers use 32-bit arithmetic. python3 scripts/gen-cn4-traces.py

For $20$ frames: with one lost frame stop-and-wait needs $21$ transmissions (and $85$ slots), Go-Back-N $24$ transmissions, Selective Repeat $21$ (always $n$ plus the number of lost frames). Selective Repeat uses the channel more economically but needs a receiver with buffers and a timer per frame; on these small examples the finishing time is the same as Go-Back-N or slightly later, so its advantage is fewer transmissions, not speed. (If every transmission is lost with probability $p$ the textbook value for Selective Repeat is $1/(1 - p)$ transmissions per frame; Go-Back-N is larger because a loss costs up to $N$ retransmissions.)

Why the window is limited

Suppose all acknowledgements of a full window are lost. The sender will resend frame $0$ . In Go-Back-N the receiver, which has accepted $N$ frames, expects number $N \bmod 2^k$ ; it takes the old frame $0$ for a new one if $N \equiv 0$ , i.e. $N = 2^k$ : so $N \le 2^k - 1$ . In Selective Repeat the receiver's new window is $N, \dots, 2N - 1 \pmod{2^k}$ ; the old frame $0$ lies in it if $2N > 2^k$ : so $N \le 2^{k-1}$ .

Largest usable window for k-bit sequence numbers: start

Computed by a script, not typed

sequence number size	sequence numbers	Go-Back-N window	Selective Repeat window
1-bit sequence numbers
2-bit sequence numbers
3-bit sequence numbers
4-bit sequence numbers
5-bit sequence numbers
6-bit sequence numbers
7-bit sequence numbers
8-bit sequence numbers

Step 0

Stop-and-wait needs only 1 bit (window 1). In Go-Back-N the receiver window is 1, in Selective Repeat the receiver window equals the sender window.

0 / 8

computed by script: protocols are simulated slot by slot or round by round, sequence numbers use 32-bit arithmetic. python3 scripts/gen-cn4-traces.py

Worked examples

EX 1Stop-and-wait utilisation

Easy

$1000$ -bit frames at $1$ Mbps, one-way delay $10$ ms: $t_t = 1$ ms, $a = 10$ ; $U = 1/(1 + 20) = 4.76$ percent; the throughput is $47.6$ kbps.

EX 2Window to fill the pipe

Medium

Same link: $1 + 2a = 21$ frames must be outstanding for $100$ percent. With $N = 7$ : $U = 7/21 = 33.3$ percent. The sequence numbers needed: for Go-Back-N $N \le 2^k - 1$ with $N = 21$ needs $k = 5$ ( $31$ ); for Selective Repeat $2^{k-1} \ge 21$ needs $k = 6$ ( $2^5 = 32$ ).

EX 3Retransmissions after one loss

Medium

$N = 4$ ; frame $5$ is lost, frames $6, 7, 8$ were already sent. GBN resends $5, 6, 7, 8$ (four frames). SR resends only $5$ (one frame).

EX 4Typical questions

GATE level

(a) "Maximum window size of GBN with $3$ -bit sequence numbers?" $7$ . (b) "Of SR?" $4$ . (c) "Bits needed for a GBN window of $100$ ?" $2^k - 1 \ge 100$ : $k = 7$ . (d) "Bits for SR window $100$ ?" $2^{k-1} \ge 100$ : $k = 8$ . (e) "Receiver window size in GBN?" $1$ . (f) "Utilisation of stop-and-wait?" $1/(1 + 2a)$ . (g) "Efficiency of a window protocol with $N = 10$ and $a = 15$ ?" $10/(1 + 30) = 32.3$ percent.

Cheat box

$U = \min(1, N/(1 + 2a))$ , $a = t_p / t_t$ ; stop-and-wait $N = 1$ . Window to fill the pipe $= 1 + 2a$ .
GBN: receiver window $1$ , cumulative ack, resend from the lost frame; $N \le 2^k - 1$ .
SR: receiver window $N$ , individual acks, resend only the lost frame; $N \le 2^{k-1}$ .
Sequence numbers modulo $2^k$ .
Round-trip cycle $t_t + 2 t_p$ .

Traps and GATE patterns

Connections

Builds on

Delay, throughput and bandwidth-delay product

Unlocks

Delay, throughput and bandwidth-delay productimplemented by Hamming code (error correction)analogous to TCP: segments, handshake and teardownuses TCP flow controlPrerequisite of TCP flow controluses TCP congestion controluses

Across subjects

No cross-subject links yet.

Within this subject

Delay, throughput and bandwidth-delay productuses TCP flow controlimplemented-by Error detection: parity, checksum and CRCuses TCP: segments, handshake and teardownimplemented-by

TCP uses a sliding window with cumulative acknowledgements, plus receiver-advertised windows (TCP flow control) and a congestion window (TCP congestion control). Damaged frames are found by the CRC (error detection). The window needed is the bandwidth-delay product of performance metrics.

PYQs

19 previous year questions from your book. I re-solved each one myself (18 by running or simulating, 1 by reasoning only); the book's key is shown next to my answer. All PYQs

GATE 2026 · MCQQ2 · page 533 of the book

Consider the implementation of a sliding window
protocol over a lossless link, with a window size of
W frames, where each frame is of size 1000 bits
(including header).

The bandwidth of the link is 100 kbps (1k = 103)
and the one-way propagation delay is 100
milliseconds. Assume that processing times at the
sender and receiver are zero and the transmission
time of acknowledgements is also zero.

Which one of the following options gives the
minimum size of W (in number of frames) required
to achieve 100% link utilization?

(a)10
(b)21
(c)20
(d)11

GATE 2025 · MCQQ3 · page 533 of the book

Suppose we are transmitting frames between two
nodes
using
Stop-and-Wait
protocol.
The frame size is 3000 bits. The transmission rate of
the channel is 2000 bps (bits per second) and the
propagation delay between the two nodes is 100
milliseconds. Assume that the processing times at the
source and destination are negligible. Also, assume
that the size of the acknowledgment packet is
negligible. Which ONE of the following most
accurately gives the channel utilization for the above
scenario in percentage?

(a)88.23
(b)93.75
(c)85.44
(d)66.67

GATE 2023 · MCQ · 1 markQ5 · page 533 of the book

Suppose two hosts are connected by a point-to-point
link and they are configured to use Stop-and-Wait
protocol for reliable data transfer. Identify in which
one of the following scenarios, the utilization of the
link is the lowest.

(a)Longer link length and lower transmission rate
(b)Longer link length and higher transmission rate
(c)Shorter link length and lower transmission rate
(d)Shorter link length and higher transmission rate

GATE 2021 · NAT · 2 marksQ9 · page 534 of the book

Consider the sliding window flow-control protocol
operating between a sender and a receiver over a full-
duplex error-free link.

Assume the following:
 The time taken for processing the data frame by
the receiver is negligible.
 The
time
taken
for
processing
the
acknowledgement frame by the sender is
negligible.
 The sender has an infinite number of frames
available for transmission.
 The size of the data frame is 2000 bits, and the size
of the acknowledgement frame is 10 bits.
 The link data rate in each direction is 1 Mbps (=
106 bits per second).
 One-way propagation delay of the link is 100
milliseconds.

The minimum value of the sender's window size in
terms of the number of frames, (rounded to the
nearest integer) needed to achieve a link utilization of
50% is _______.

GATE 2017 · NATQ14 · page 535 of the book

The values of parameters for the Stop-and-Wait ARQ
protocol are as given below:
 Bit rate of the transmission channel = 1 Mbps.
 Propagation delay from sender to receiver = 0.75
ms.
 Time to process a frame = 0.25 ms.
 Number of bytes in the information frame = 1980.
 Number of bytes in the acknowledge frame = 20.
 Number of overhead bytes in the information
frame = 20.

Assume that there are no transmission errors. Then,
the transmission efficiency (expressed in percentage)
of the Stop-and-Wait ARQ protocol for the above
parameters is ______ (correct to 2 decimal places).

GATE 2016 · NATQ16 · page 535 of the book

Consider
a
128×103
bits/second
satellite
communication link with one-way propagation delay
of 150 milliseconds. Selective retransmission (repeat)
protocol is used on this link to send data with a frame
size of 1 kilobyte. Neglect the transmission time of
acknowledgment. The minimum number of bits
required for the sequence number field to achieve
100% utilization is ______.

COMPUTER NETWORK

GATE 2016 · NATQ17 · page 536 of the book

A sender uses the Stop-and-Wait ARQ protocol for
reliable transmission of frames. Frames are of size
1000 bytes and the transmission rate at the sender
is 80 Kbps (1 Kbps = 1000 bits/second). Size of an
acknowledgment is 100 bytes and the transmission
rate at the receiver is 8 Kbps. The one-way
propagation delay is 100 milliseconds. Assuming
no frame is lost, the sender throughput is
__________ bytes/second.

GATE 2015 · NATQ22 · page 536 of the book

A link has a transmission speed of 106 bits/sec. It uses
data packets of size 1000 bytes each. Assume that the
acknowledgment has negligible transmission delay,
and that its propagation delay is the same as the data
propagation delay. Also assume that the processing
delays at nodes are negligible. The efficiency of the
stop-and-wait protocol in this setup is exactly 25%.
The value of the one-way propagation delay (in
milliseconds) is:

year not read yetQ24 · page 537 of the book

Consider a network connecting two systems
located 8000 kilometers apart. The bandwidth of
the network is 500 × 106 bits per second. The
propagation speed of the media is

4 × 106 meters per second. It is needed to design a
Go-Back-N sliding window protocol for this
network. The average packet size is 107 bits. The
network is to be used to its full capacity. Assume
that processing delays at nodes are negligible.
Then, the minimum size in bits of the sequence
number field has to be

GATE 2015 · NATQ25 · page 537 of the book

Suppose that the stop-and-wait protocol is used on
a link with a bit rate of 64 kilobits per second and
20 milliseconds propagation delay. Assume that the
transmission time for the acknowledgment and the
processing time at nodes are negligible. Then the
minimum frame size in bytes to achieve a link
utilization of at least 50% is: __________

GATE 2014 · MCQQ26 · page 537 of the book

Consider a selective repeat sliding window
protocol that uses a frame size of 1 KB to send data
on a 1.5 Mbps link with a one-way latency of 50
msec . To achieve a link utilization of 60%, the
minimum number of bits required to represent the
sequence number field is ____ .

GATE 2009 · MCQ · 2 marksQ31 · page 538 of the book

Frames of 1000 bits are sent over a 106 bps duplex
link between two hosts. The propagation time is 25
ms. Frames are to be transmitted into this link to
maximally pack them in transit (within the link).

What is the minimum number of bits (l) required to
represent the sequence numbers distinctly? Assume
that no time gap needs to be given between
transmission of two frames.

(a)I = 2
(b)I = 3
(c)I = 4
(d)I = 5

GATE 2009 · MCQ · 2 marksQ32 · page 538 of the book

Suppose that the sliding window protocol is used
with the sender window size of 2l, where l is the
number of bits identified in the earlier part and
acknowledgements are always piggybacked. After
sending 2l frames, what is the minimum time the
sender will have to wait before starting
transmission of the next frame? (Ignore frame
processing time.)

(a)16 ms
(b)18 ms
(c)20 ms
(d)22 ms

GATE 2007 · MCQ · 2 marksQ34 · page 538 of the book

The distance between two stations M and N is L
kilometers. All frames are K bits long. The
propagation delay per kilometer is t seconds. Let R
bits/second be the channel capacity. Assuming that
processing delay is negligible, the minimum number
of bits for the sequence number field in a frame for
maximum utilization, when the sliding window
protocol is used, is:

(a)⌈log2 (2LtR+2K) K ⌉
(b)⌈log2 ( 2LtR K)⌉
(c)⌈log2(( 2LtR + K) K )⌉
(d)⌈log2( (2LtR + K) (2K) )⌉

GATE 2006 · MCQ · 2 marksQ38 · page 539 of the book

Station A uses 32 byte packets to transmit messages
to Station B using a sliding window protocol. The
round trip delay between A and B is 80
milliseconds and the bottleneck bandwidth on the
path between A and B is 128 kbps. What is the
optimal window size that A should use?

(a)20
(b)40
(c)160
(d)320

GATE 2006 · MCQ · 2 marksQ39 · page 539 of the book

Station A needs to send a message consisting of 9
packets of Station B using sliding window (window
size 3) and go-back-n error control strategy. All
packets are ready and immediately available for
transmission. If every 5th packet that A transmits
gets lost (but no ACKs from B ever get lost), then
what is the number of packets that A will transmit for
sending the message to B?

(a)12
(b)14
(c)16
(d)18

GATE 2005 · MCQ · 1 markQ42 · page 540 of the book

The maximum window size for data transmission
using the selective reject protocol with n-bit frame
sequence numbers is:

(a)2n
(b)2n-1
(c)2n -1
(d)2n-2

GATE 2026 · NATQ5 · page 547 of the book

It is necessary to design a link-layer protocol between
two hosts that are directly connected over a lossless
link of length 3000 km. The link bandwidth is 108 bits
per second, and the propagation delay is 5 ns per
meter. Every transmitted data byte is assigned a
unique sequence number.

Let N be the minimum number of bits needed for the
sequence number field such that:

i. the sequence numbers do not wrap around before
60 seconds, and
ii. the maximum utilization of the link is achieved.

Find N. (answer in integer)

GATE 2014 · MCQQ69 · page 559 of the book

Consider a selective repeat sliding window
protocol that uses a frame size of 1 KB to send data
on a 1.5 Mbps link with a one-way latency of 50
msec. To achieve a link utilization of 60%, the
minimum number of bits required to represent the
sequence number field is __________.

Self-check

Question 1

$a = 4$ . What window gives full utilisation, and what is the utilisation with $N = 3$ ?

Show answer

$1 + 2a = 9$ frames for full utilisation; with $N = 3$ : $3/9 = 33.3$ percent.

Question 2

Why can a Selective Repeat window not exceed half of the sequence numbers?

Show answer

Otherwise the receiver's new window overlaps the old one and a retransmitted old frame can be taken for a new frame.

Question 3

How many frames does Go-Back-N resend if the third frame of a window of $6$ is lost (the other five were already sent)?

Show answer

Frames $3$ to $6$ of the window: the lost one and all the following frames sent after it, $4$ frames.

Revision card

One-screen revision

$U = \min(1, N/(1 + 2a))$ ; fill the pipe with $N \ge 1 + 2a$ .
GBN: receiver window 1, resend from the lost frame, $N \le 2^k - 1$ . SR: resend only the lost, $N \le 2^{k-1}$ .
Cumulative acks (GBN), individual acks (SR).

References

·Kurose, Ross, Computer Networking: A Top-Down Approach (8th edition), Chapter 3, Section 3.4 (Principles of reliable data transfer)
·Tanenbaum, Wetherall, Computer Networks (5th edition), Chapter 3, Section 3.4 (Elementary data link protocols) and 3.4.3 (Sliding window protocols)

Verification

scripts/enum-checks/cn_tcp_check.py: the slotted simulator of scripts/cn_tcp.py (one frame per slot, one-way delay d slots, acknowledgements never lost, timeout = one round trip) gives, for 3000 frames, every protocol with windows 1 to 32 and delays 1 to 8 slots, a sender utilisation within 0.01 of min(1, N / (1 + 2a)) with the cycle 1 + 2a = 2d slots; under random loss (800 random cases with up to 6 lost first transmissions) Go-Back-N and stop-and-wait deliver all frames in order, Selective Repeat sends exactly n + (number of lost frames) frames, Go-Back-N sends at least that many and at most N more per loss; the sequence number limits come from a concrete model of the scenario in which all acknowledgements of a full window are lost (for k = 1 to 6 and every window size: Go-Back-N is ambiguous exactly when W is at least 2^k, Selective Repeat exactly when W exceeds 2^(k-1)). THE SIMULATION SHOWS THAT SELECTIVE REPEAT IS NOT ALWAYS FASTER than Go-Back-N in time on short examples with several losses (it sends fewer frames); the page claims only fewer transmissions. MODEL: acknowledgements are never lost and are not delayed; one fixed timeout; in Go-Back-N the receiver sends a (cumulative) acknowledgement for every arriving frame, repeating the last one for out-of-order frames; textbooks differ in details (negative acknowledgements, piggybacking, window numbering from 0 or 1). The formula for the expected number of transmissions with loss probability p (Selective Repeat 1/(1-p)) is the textbook value, not simulated here. Textbook chapter references are from memory. SECOND PASS (2026-11-02, done by the assistant, not a human check): every Self-check question was solved before the printed answer was read and all agreed; the definitions, worked examples, cheat box and traps were read claim by claim and the numbers re-derived by hand or by a small script (CRC remainders, binomial tail, checksums); long C programs were not re-read line by line (they are compiled and compared by npm run verify:c, and their printed outputs were checked against the prose). One confusing callout title fixed (it read '2^k, not 2^k - 1, for Selective Repeat's half' while the text states Go-Back-N 2^k - 1 and Selective Repeat 2^(k-1)). Status raised to self-checked; verified needs a textbook or human check.

last verified: never

My notes (saved in this browser)

TCP: segments, handshake and teardown

TCP flow control