Retransmission Behavior

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.

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:

• Timer starts when the first frame enters an empty window (send_base == nextseqnum transitions to send_base < nextseqnum)
• Timer restarts when send_base advances (new oldest outstanding frame)
• Timer stops when all frames are acknowledged (send_base == nextseqnum)
• Timer expires after a protocol-specific duration (timeout value)

What Timeout Indicates:

A timeout can result from several underlying causes:

1. Frame loss: The data frame was lost in transit (never reached the receiver)
2. Frame corruption: The frame arrived but failed error checking (discarded)
3. ACK loss: The frame arrived correctly, but the ACK was lost
4. ACK delay: Network congestion delayed the ACK beyond the timeout

From the sender's perspective, all these cases are indistinguishable—the expected ACK simply didn't arrive in 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:

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:

• The frame that presumably triggered the timeout (might be lost)
• All frames sent after it (might have been received correctly)

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:

• Frame 3? No—if ACK(3) arrived, send_base = 4
• Frame 4: Yes (the lost frame)
• Frame 5: Yes (correctly received but discarded)
• Frame 6: Yes (correctly received but discarded)
• Frame 7: Yes (correctly received but discarded)

Four frames are retransmitted, but only one (frame 4) was actually lost. The other three were correctly received on the first transmission!

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.

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:

• Frames lost by channel: 1
• Frames retransmitted by sender: N
• Redundant retransmissions: N - 1

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):

• If position 0 (first) is lost: retransmit N frames, waste N - 1
• If position 1 (second) is lost: retransmit N - 1 frames, waste N - 2
• ...
• If position N-1 (last) is lost: retransmit 1 frame, waste 0

Average wasted frames per loss = (1/N) × Σ(k=0 to N-1) k = (N - 1) / 2

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:

When GBN's Cost Is Acceptable:

Despite the overhead, Go-Back-N remains appropriate when:

1. Low error rate: If P(loss) is very small (< 0.1%), redundant retransmissions are rare
2. Small window: With small N, the waste per error is bounded
3. Simple receiver required: Embedded systems, sensors, low-power devices benefit from receiver simplicity
4. In-order delivery critical: Applications requiring strict ordering without buffering
5. Implementation resource constraints: Memory for buffering is expensive or unavailable

When to Choose Selective Repeat:

1. High error rate: Lossy channels (wireless, congested networks) amplify GBN's waste
2. Large window: High bandwidth-delay products require large N; waste grows proportionally
3. Receiver resources available: Modern systems can afford buffering
4. Throughput is paramount: When every bit of bandwidth matters

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).

• Timeout triggers retransmission from frame 4
• Retransmit 4, 5, 6, 7
• Frame 4 arrives → ACK(4), expectedseqnum = 5
• Frame 5 arrives → ACK(5), expectedseqnum = 6
• Frame 6 arrives → ACK(6), expectedseqnum = 7
• Frame 7 arrives → ACK(7), expectedseqnum = 8

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:

• Timeout triggers retransmission from frame 4
• Retransmit 4, 5, 6, 7
• Frame 4 arrives → ACK(4)
• Frame 5 arrives → ACK(5)
• Frame 6 LOST AGAIN? If channel is persistently lossy...

Problematic Pattern: Loss During Retransmission

If frame 6 is lost again during retransmission:

• Receiver gets 4, 5, then expects 6
• Frame 7 arrives out of order → discarded
• Timeout triggers ANOTHER retransmission from frame 6
• This can cascade if channel remains lossy

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:

1. Process each frame as it arrives (error check, sequence number check)
2. Decide to accept or reject
3. Send ACK
4. If accepted, deliver to upper layer

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:

• Receiver cannot accept the frame (would cause overflow)
• Receiver must signal sender to slow down

This is the domain of flow control, overlapping with but distinct from error control.

Flow Control Mechanisms in GBN:

1. Window-based flow control: Receiver advertises available buffer space; sender window is the minimum of sender's N and receiver's advertised window

2. Explicit feedback: Receiver sends a "pause" or "RNR" (Receive Not Ready) signal when overwhelmed

3. Implicit signaling: Receiver simply doesn't send ACKs; sender times out but this wastes bandwidth

Retransmission While Flow-Controlled:

A subtle issue arises when flow control limits the window during retransmission:

1. Sender has 10 frames outstanding (send_base = 0, nextseqnum = 10)
2. Frame 3 is lost; frames 4-9 are discarded by receiver
3. Receiver sends ACK(2) with window = 5 (flow control)
4. Timeout triggers retransmission
5. Sender should retransmit frames 3-9 (7 frames)
6. But receiver only has space for 5 frames!

Resolution:

• Sender retransmits min(outstanding, receiver_window) frames
• Or sender retransmits all outstanding but receiver applies flow control by delaying ACKs or sending RNR
• Protocol design must specify exact behavior

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?