101
0/240
Loading content...
The name Go-Back-N reveals the protocol's defining characteristic: when error recovery is needed, the sender doesn't simply retransmit the lost frame—it "goes back" to that frame and retransmits all subsequent frames as well, even if those frames were already received correctly by the receiver.
This behavior, at first glance, appears wasteful. Why retransmit correctly received frames? The answer lies in a deliberate design trade-off: simplicity at the receiver outweighs efficiency in retransmission. By keeping the receiver stateless (no buffering of out-of-order frames), the protocol sacrifices bandwidth during error recovery but gains implementation simplicity and guaranteed in-order delivery.
This page dissects the retransmission mechanism in detail: what triggers retransmission, exactly which frames are resent, how the receiver handles the arriving duplicates, and the bandwidth cost of this approach compared to selective retransmission.
By the end of this page, you will understand the precise mechanics of Go-Back-N retransmission, be able to trace through complex retransmission scenarios, quantify the bandwidth overhead compared to Selective Repeat, and appreciate when this overhead is acceptable and when it motivates more sophisticated protocols.
In the standard Go-Back-N protocol, there is one primary trigger for retransmission: timeout expiration. The sender maintains a single timer associated with the oldest unacknowledged frame. When this timer expires without receiving an acknowledgment that advances the window, retransmission begins.
Timer Semantics:
send_base == nextseqnum transitions to send_base < nextseqnum)send_base advances (new oldest outstanding frame)send_base == nextseqnum)What Timeout Indicates:
A timeout can result from several underlying causes:
From the sender's perspective, all these cases are indistinguishable—the expected ACK simply didn't arrive in time.
If timeout is set too short, the sender retransmits unnecessarily (the ACK was just delayed). If set too long, the sender waits excessively when the frame was actually lost. Optimal timeout balances these concerns, typically set slightly above the observed round-trip time.
Enhanced Trigger: Duplicate ACKs (Optional)
Some implementations extend GBN with a fast retransmit mechanism inspired by TCP:
if (3 consecutive duplicate ACKs received for ack_num == send_base - 1):
// Don't wait for timeout; retransmit immediately
retransmit_from(send_base)
The rationale: receiving multiple duplicate ACKs indicates that subsequent frames are arriving at the receiver, but the expected frame is missing. This strongly suggests frame loss rather than delay.
Standard GBN vs. Enhanced GBN:
| Trigger | Standard GBN | Enhanced GBN | TCP Comparison |
|---|---|---|---|
| Timeout expiration | Yes | Yes | Yes |
| Duplicate ACKs (×3) | No | Yes | Yes (fast retransmit) |
| NACK (negative ACK) | No | Some variants | Not in TCP (uses SACK) |
| Proactive sensing | No | Rare | RACK algorithm |
When retransmission is triggered, the sender executes the defining behavior of Go-Back-N:
Retransmission Algorithm:
procedure retransmit_all_outstanding():
restart_timer()
for i = send_base to nextseqnum - 1:
send(buffer[i mod N])
What Gets Retransmitted:
Every frame with sequence number in the range [send_base, nextseqnum - 1] is resent. This includes:
Example:
Window size N = 5, sender has transmitted frames 3, 4, 5, 6, 7 (send_base = 3, nextseqnum = 8).
Frame 4 was lost. The receiver accepted frame 3, then saw frames 5, 6, 7 arrive out of order and discarded them.
Timeout occurs (no ACK for frame 4). Sender retransmits:
Four frames are retransmitted, but only one (frame 4) was actually lost. The other three were correctly received on the first transmission!
The receiver discarded frames 5, 6, 7 because it operates in strict in-order mode with no buffer for out-of-order frames. Even if only frame 4 were retransmitted, the receiver couldn't process frames 5, 6, 7 because they were already discarded. The sender MUST resend them.
When retransmitted frames arrive at the receiver, their handling depends on the receiver's current state:
Case 1: Retransmitted Frame Matches Expected
If the retransmitted frame's sequence number equals expectedseqnum, the frame is accepted:
Receive Frame 4 (retransmission):
expectedseqnum == 4? Yes!
Accept frame, deliver data
Send ACK(4)
expectedseqnum = 5
This is normal operation—the retransmission successfully recovered the lost frame.
Case 2: Retransmitted Frame Is Behind Expected
If the receiver has already moved past this sequence number (perhaps due to delayed original transmission), the frame is a duplicate:
Receive Frame 3 (retransmission due to lost ACK):
expectedseqnum == 5? No, 3 < 5
Recognize as duplicate/old frame
Discard frame
Send ACK(4) — highest received in-order
Case 3: First-Time Frame After Successful Recovery
After the lost frame is successfully retransmitted, subsequent retransmissions (frames 5, 6, 7 in our example) arrive as expected:
Receive Frame 5 (retransmission):
expectedseqnum == 5? Yes!
Accept frame, deliver data
Send ACK(5)
expectedseqnum = 6
Even though frame 5 was received correctly the first time (and discarded), this retransmission is now accepted because expectedseqnum has advanced.
| Frame Seq# | Expected Seq# | Relation | Action | ACK Sent |
|---|---|---|---|---|
| 4 | 4 | Match | Accept & deliver | ACK(4) |
| 5 | 5 | Match | Accept & deliver | ACK(5) |
| 3 | 5 | Behind (duplicate) | Discard | ACK(4) |
| 6 | 5 | Ahead (out-of-order) | Discard | ACK(4) |
The receiver maintains only expectedseqnum—no buffer, no bitmap of received frames, no history. This extreme simplicity is GBN's defining characteristic. Every arriving frame is either exactly expected (accept) or not (discard). No decisions require remembering past frames.
The "go back" retransmission behavior wastes bandwidth by resending correctly received frames. Let's quantify this cost.
Worst-Case Scenario:
With window size N, if the first frame in the window is lost while all subsequent N-1 frames are received correctly:
The redundancy ratio in worst case:
Redundancy = (frames retransmitted) / (frames actually lost)
= N / 1 = N
With N = 127 (extended HDLC), the worst case retransmits 127 frames to recover 1!
Average Case Analysis:
Assuming uniform random frame loss at position k within the window (k = 0, 1, ..., N-1):
Average wasted frames per loss = (1/N) × Σ(k=0 to N-1) k = (N - 1) / 2
Average wasted retransmissions = (N - 1) / 2. With N = 127, each loss wastes on average 63 frames. On lossy channels, this becomes significant. A 1% frame loss rate means roughly 0.63% additional redundant traffic—not catastrophic, but not negligible either.
Comparison with Selective Repeat:
In Selective Repeat ARQ, the receiver buffers out-of-order frames, and the sender retransmits only the specific lost frame. This drastically reduces retransmission overhead:
| Metric | Go-Back-N | Selective Repeat |
|---|---|---|
| Frames lost per 1000 | 10 | 10 |
| Frames retransmitted per loss (worst) | 10 | 1 |
| Frames retransmitted per loss (avg) | 5.5 | 1 |
| Total retransmissions per 1000 frames | ~55 | ~10 |
| Effective overhead | 5.5% | 1% |
When GBN's Cost Is Acceptable:
Despite the overhead, Go-Back-N remains appropriate when:
When to Choose Selective Repeat:
When multiple frames within a single window are lost, Go-Back-N's behavior depends on which frames are lost and their relative positions.
Scenario 1: Consecutive Losses
Frames 4 and 5 are both lost (sender transmitted 3, 4, 5, 6, 7).
Recovery is straightforward—one retransmission round handles both losses.
Scenario 2: Non-Consecutive Losses
Frames 4 and 6 are lost (sender transmitted 3, 4, 5, 6, 7).
First retransmission cycle:
Problematic Pattern: Loss During Retransmission
If frame 6 is lost again during retransmission:
On a very lossy channel, Go-Back-N can enter a pathological state where retransmissions themselves are lost, triggering more retransmissions. Throughput collapses toward zero. This is why GBN is unsuitable for high-error-rate environments.
Mathematical Model: Retransmissions Under Random Loss
Let p = probability of frame loss. Let N = window size.
Expected number of transmission attempts for a single frame to succeed:
E[attempts] = 1 / (1 - p)
But in GBN, when a frame is lost, we retransmit N frames. If any of those N frames is lost again, we retransmit all N again.
Probability that all N frames in a retransmission succeed:
P(all succeed) = (1 - p)^N
Expected retransmission rounds:
E[rounds] = 1 / (1 - p)^N...approximately.
For p = 0.1 (10% loss) and N = 10:
P(all succeed) = (0.9)^10 ≈ 0.349
E[rounds] ≈ 1 / 0.349 ≈ 2.9 rounds on average!
This means even moderate loss rates with large windows cause significant retransmission cycles.
An often-overlooked aspect of Go-Back-N retransmission is its interaction with flow control—particularly when the receiver's processing capacity is limited.
The Problem:
When the sender retransmits a burst of N frames, the receiver must:
If the receiver's upper layer is slow (e.g., application can't consume data fast enough), accepted frames might cause buffer overflow at the receiver—even though Go-Back-N's receiver itself doesn't buffer.
Wait—Doesn't GBN Receiver Not Buffer?
The GBN receiver doesn't buffer out-of-order frames. But it still needs to pass accepted in-order frames to the upper layer. If the upper layer's buffer is full:
This is the domain of flow control, overlapping with but distinct from error control.
Flow Control Mechanisms in GBN:
Window-based flow control: Receiver advertises available buffer space; sender window is the minimum of sender's N and receiver's advertised window
Explicit feedback: Receiver sends a "pause" or "RNR" (Receive Not Ready) signal when overwhelmed
Implicit signaling: Receiver simply doesn't send ACKs; sender times out but this wastes bandwidth
HDLC (using GBN) provides explicit flow control through supervisory frames:
• RR (Receive Ready): Normal ACK, ready for more frames • RNR (Receive Not Ready): Acknowledged frames up to N, but don't send more yet • REJ (Reject): Explicit negative acknowledgment, request retransmission
These provide finer control than pure timeout-based retransmission.
Retransmission While Flow-Controlled:
A subtle issue arises when flow control limits the window during retransmission:
Resolution:
In practice, implementations often retransmit all outstanding frames in one burst and let the receiver's flow control feedback throttle subsequent new transmissions.
The retransmission mechanism is the heart of Go-Back-N, defining its character and trade-offs. Let's consolidate the essential insights:
What's Next:
With the complete operational picture—from fundamental concepts through window limits and retransmission behavior—we're ready for the capstone: efficiency analysis. The next page derives the mathematical model for GBN throughput, comparing it with Stop-and-Wait and Selective Repeat to answer the quantitative question: how much does pipelining help, and when is Go-Back-N the right choice?
You now understand Go-Back-N's distinctive retransmission mechanism: timeout-triggered full retransmission of outstanding frames, receiver handling of retransmissions, bandwidth cost quantification, and interaction with flow control. This completes the behavioral foundation for the efficiency analysis that follows.