In the Data Link Layer, Automatic Repeat reQuest (ARQ) protocols improve reliability by combining sequence numbers with acknowledgements and timers. The central idea behind modern reliable link control is the sliding window mechanism, which enables pipelining so the sender does not remain idle while waiting for one acknowledgement at a time.2

Without pipelining, stop-and-wait wastes capacity when the round-trip time is large compared with frame transmission time. Sliding windows solve this by allowing several outstanding frames, ideally enough to fill the bandwidth-delay product of the link.2 In network theory, this matters especially in the Data Link Layer and Medium Access context because link efficiency depends not just on correctness, but on keeping the medium busy with useful data.

At a high level, both Go-Back-N and Selective Repeat maintain sender and receiver windows, but they differ sharply in what the receiver accepts, how acknowledgements are interpreted, how timers are managed, and how retransmissions are triggered.2

5

Footnotes

1. Flow Control + ARQ Lecture Notes, University of Michigan - Detailed lecture notes covering sliding windows, Go-Back-N, Selective Repeat, timers, ACK behavior, and receiver buffering. ↩ ↩² ↩³

2. Data Link Control PDF - Teaching material discussing sender/receiver windows, Go-Back-N limits, Selective Repeat, and piggybacking. ↩ ↩²

3. ECE 333 Lecture 9, Northwestern University - Explains pipelining, filling the pipe, ARQ evolution, and sequence-space constraints. ↩ ↩² ↩³

4. Sliding Window Protocol - GeeksforGeeks - Summarizes stop-and-wait efficiency, pipelining motivation, and bandwidth-delay product intuition. ↩ ↩²

5. Selective Repeat ARQ - Wikipedia - Concise reference for Selective Repeat behavior, window equality, buffering, and half-sequence-space rule. ↩ ↩²

A sender window and a receiver window define which sequence numbers are currently valid. The sender window contains frames that may be transmitted or have been transmitted but not yet acknowledged; the receiver window contains frames that may be accepted next.2 As ACKs arrive, the window “slides” forward.

If frame transmission time is $T_t$ and one-way propagation delay is $T_p$, then stop-and-wait efficiency in the idealized case is

$$\eta_{SW} = \frac{T_t}{T_t + 2T_p} = \frac{1}{1+2a}$$

where $a = \frac{T_p}{T_t}$.2

With a window of size $W$, a pipeline can keep up to $W$ frames outstanding. In the idealized no-error case, larger $W$ increases link utilization until the pipe is full, meaning the sender can keep transmitting continuously.2

A useful engineering rule is:

$$W \approx 1 + 2a$$

to keep the link busy in ideal conditions.2

This is why sliding window ARQ is essential on long-delay links: the channel may hold many frames “in flight,” so reliability must be coordinated over a sequence space rather than one frame at a time.

Footnotes

1. Flow Control + ARQ Lecture Notes, University of Michigan - Detailed lecture notes covering sliding windows, Go-Back-N, Selective Repeat, timers, ACK behavior, and receiver buffering. ↩

2. Selective Repeat ARQ - Wikipedia - Concise reference for Selective Repeat behavior, window equality, buffering, and half-sequence-space rule. ↩

3. ECE 333 Lecture 9, Northwestern University - Explains pipelining, filling the pipe, ARQ evolution, and sequence-space constraints. ↩ ↩² ↩³ ↩⁴

4. Sliding Window Protocol - GeeksforGeeks - Summarizes stop-and-wait efficiency, pipelining motivation, and bandwidth-delay product intuition. ↩ ↩² ↩³

Go-Back-N ARQ

Go-Back-N is the simpler sliding window protocol. The sender may have up to $N$ outstanding frames, but the receiver window is effectively 1: it accepts only the next expected frame and discards out-of-order arrivals.2 This makes receiver logic lightweight, since the receiver needs only to remember the next expected sequence number rather than sort or buffer a range of future frames.2

ACKs in Go-Back-N are cumulative ACKs. If the receiver sends ACK for frame $k$, it means all frames up to that point have been received in order.2 If a later frame arrives while an earlier one is missing, the receiver discards it and typically repeats the last cumulative ACK.2

The sender typically maintains only one active retransmission timer, associated with the oldest unacknowledged frame. If that timer expires, the sender retransmits that frame and every later frame still in the sender window. This “go back” behavior is what gives the protocol its name.2

This design is efficient when errors are rare, because cumulative ACK processing and a single timer make implementation simple. However, on noisy links, one lost frame may cause many correctly received later frames to be retransmitted unnecessarily.2

Footnotes

1. Data Link Control PDF - Teaching material discussing sender/receiver windows, Go-Back-N limits, Selective Repeat, and piggybacking. ↩

2. Go-Back-N ARQ - Wikipedia - Reference on Go-Back-N receive window size, cumulative ACK behavior, and retransmission semantics. ↩ ↩² ↩³ ↩⁴ ↩⁵

3. Flow Control + ARQ Lecture Notes, University of Michigan - Detailed lecture notes covering sliding windows, Go-Back-N, Selective Repeat, timers, ACK behavior, and receiver buffering. ↩ ↩² ↩³ ↩⁴ ↩⁵

4. Selective Repeat ARQ - Wikipedia - Concise reference for Selective Repeat behavior, window equality, buffering, and half-sequence-space rule. ↩

5. Chapter 5: Peer-to-Peer Protocols and Data Link Layer PDF, SFU - Discusses Go-Back-N inefficiency under errors and the performance advantages of Selective Repeat. ↩

Window Size Constraint in Go-Back-N

If the sequence number field has $m$ bits, the sequence space contains $2^m$ values. In Go-Back-N, the maximum sender window size is

$$W_s \le 2^m - 1$$

while the receiver window remains

$$W_r = 1$$

.3

The reason is ambiguity avoidance. If the sender were allowed to use all $2^m$ sequence numbers in its window, then after wraparound, an old ACK or a delayed duplicate frame could be confused with a new one from the next cycle through sequence numbers.2 By leaving one sequence number unused from the full space, the protocol prevents this overlap between “old outstanding” and “newly sent” interpretations.

Footnotes

1. Data Link Control PDF - Teaching material discussing sender/receiver windows, Go-Back-N limits, Selective Repeat, and piggybacking. ↩ ↩² ↩³

2. Lecture 9 - Data Link Layer V, Northwestern University - Provides examples showing why Go-Back-N uses $2^m-1$ and Selective Repeat uses at most $2^{m-1}$. ↩ ↩²

3. Go-Back-N ARQ - Wikipedia - Reference on Go-Back-N receive window size, cumulative ACK behavior, and retransmission semantics. ↩

Selective Repeat ARQ

Selective Repeat is a more sophisticated protocol in which the receiver may accept frames out of order, buffer them, and acknowledge them individually.2 The sender therefore maintains more detailed state: each outstanding frame has its own acknowledgement status and typically its own timer.2

This changes the recovery logic fundamentally. If frame $i$ is lost but frames $i+1$, $i+2$, and $i+3$ arrive correctly, the receiver stores them instead of discarding them. It sends individual ACKs for those correctly received frames, while still waiting for the missing one before delivering the buffered sequence upward in order.3

As a result, when frame $i$ times out, only frame $i$ is retransmitted. Once it arrives, the receiver can reorder and release the entire contiguous block.2 This is why Selective Repeat is far more efficient than Go-Back-N over noisy links: retransmission cost is targeted rather than cascading across the rest of the pipeline.

Footnotes

1. Flow Control + ARQ Lecture Notes, University of Michigan - Detailed lecture notes covering sliding windows, Go-Back-N, Selective Repeat, timers, ACK behavior, and receiver buffering. ↩ ↩² ↩³

2. Selective Repeat ARQ - Wikipedia - Concise reference for Selective Repeat behavior, window equality, buffering, and half-sequence-space rule. ↩ ↩² ↩³ ↩⁴

3. Chapter 5: Peer-to-Peer Protocols and Data Link Layer PDF, SFU - Discusses Go-Back-N inefficiency under errors and the performance advantages of Selective Repeat. ↩ ↩² ↩³

Window Size Constraint in Selective Repeat

Selective Repeat requires stricter window sizing than Go-Back-N. If sequence numbers use $m$ bits, then the sequence space has size $2^m$, and the sender and receiver windows must satisfy

$$W_s = W_r \le 2^{m-1}$$

.3

The reason is sequence-number ambiguity after wraparound. Because the receiver accepts out-of-order frames and buffers them, a sequence number reused too early could be mistaken for an older delayed duplicate rather than a new frame.2 Restricting each window to at most half the sequence space ensures that the set of valid “new” sequence numbers cannot overlap with still-relevant “old” ones.3

This is the key contrast often emphasized in exams and protocol design:

6

Footnotes

1. Selective Repeat ARQ - Wikipedia - Concise reference for Selective Repeat behavior, window equality, buffering, and half-sequence-space rule. ↩ ↩² ↩³ ↩⁴

2. Lecture 9 - Data Link Layer V, Northwestern University - Provides examples showing why Go-Back-N uses $2^m-1$ and Selective Repeat uses at most $2^{m-1}$. ↩ ↩² ↩³ ↩⁴

3. Chapter 5: Peer-to-Peer Protocols and Data Link Layer PDF, SFU - Discusses Go-Back-N inefficiency under errors and the performance advantages of Selective Repeat. ↩ ↩² ↩³

4. Flow Control + ARQ Lecture Notes, University of Michigan - Detailed lecture notes covering sliding windows, Go-Back-N, Selective Repeat, timers, ACK behavior, and receiver buffering. ↩

5. Data Link Control PDF - Teaching material discussing sender/receiver windows, Go-Back-N limits, Selective Repeat, and piggybacking. ↩

6. Go-Back-N ARQ - Wikipedia - Reference on Go-Back-N receive window size, cumulative ACK behavior, and retransmission semantics. ↩

Piggybacking on Duplex Links

Piggybacking is an efficiency technique used when communication is bidirectional over a duplex link. Instead of sending a standalone ACK immediately, a station may wait briefly and attach the ACK to its next outgoing data frame. This reduces control-frame overhead because one transmission carries both data and acknowledgement information.

Piggybacking is especially useful in sliding window protocols, since both endpoints may simultaneously have data to send and ACKs to return.2 Over a full-duplex line, this can significantly reduce the number of separate frames transmitted.

However, piggybacking cannot delay ACKs indefinitely. If the receiver waits too long for outbound data to attach the ACK to, the sender may time out and retransmit unnecessarily. Therefore implementations often use an auxiliary ACK timer: if no outbound data appears soon enough, a standalone ACK is sent.

Footnotes

1. Piggybacking in Computer Networks - GeeksforGeeks - Explains piggybacking, duplex efficiency gains, and ACK-delay trade-offs. ↩ ↩² ↩³ ↩⁴ ↩⁵

2. Data Link Control PDF - Teaching material discussing sender/receiver windows, Go-Back-N limits, Selective Repeat, and piggybacking. ↩

Comparative Evaluation for Network Theory

From a systems perspective, Go-Back-N and Selective Repeat represent a classic trade-off between implementation complexity and channel efficiency.

Go-Back-N is easier to implement because:

• the receiver window is fixed at 1,
• acknowledgements are cumulative,2
• no receiver-side sorting of future frames is required,
• timer management is simpler, often with only the oldest outstanding frame timed.

Selective Repeat is more complex because:

• the receiver window spans multiple sequence numbers,
• out-of-order frames must be buffered and sorted,2
• acknowledgements are tracked per frame,
• the sender manages independent timers and per-frame state.2

Yet Selective Repeat is substantially more efficient over noisy links because it avoids redundant retransmission of frames already received correctly. In a high-error environment, the waste in Go-Back-N grows with window size: a single loss can force replay of many later frames, consuming bandwidth and increasing delay. Selective Repeat confines recovery to the actual missing data, making it a better choice when link errors are nontrivial and buffering complexity is acceptable.2

A useful conceptual summary is:

$$\text{GBN: simplicity} \;>\; \text{efficiency under errors}$$ $$\text{SR: efficiency under errors} \;>\; \text{implementation simplicity}$$

For the Data Link Layer, the protocol choice depends on the expected error rate, memory available for buffering, timer sophistication, and the performance requirement of the link.3

Footnotes

1. Go-Back-N ARQ - Wikipedia - Reference on Go-Back-N receive window size, cumulative ACK behavior, and retransmission semantics. ↩ ↩² ↩³

2. Flow Control + ARQ Lecture Notes, University of Michigan - Detailed lecture notes covering sliding windows, Go-Back-N, Selective Repeat, timers, ACK behavior, and receiver buffering. ↩ ↩² ↩³ ↩⁴

3. Selective Repeat ARQ - Wikipedia - Concise reference for Selective Repeat behavior, window equality, buffering, and half-sequence-space rule. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶

4. Chapter 5: Peer-to-Peer Protocols and Data Link Layer PDF, SFU - Discusses Go-Back-N inefficiency under errors and the performance advantages of Selective Repeat. ↩ ↩² ↩³ ↩⁴ ↩⁵