Go-Back-N Automatic Repeat reQuest

In our exploration of reliable data transfer, we've seen that Stop-and-Wait ARQ provides correctness but sacrifices efficiency. When a sender transmits a single frame and waits for its acknowledgment before sending the next, the communication channel sits idle during the entire round-trip propagation time. For high bandwidth-delay product links—satellite connections, transcontinental fiber, or high-speed networks—this idle time represents an enormous waste of capacity.

Go-Back-N ARQ revolutionizes this approach by introducing pipelining: the sender maintains multiple outstanding (unacknowledged) frames simultaneously, keeping the channel continuously utilized. This conceptually simple yet operationally sophisticated protocol forms the backbone of reliable data transfer in protocols like HDLC, and its principles underpin TCP's reliability mechanisms.

But pipelining introduces complexity. When frames can be in flight simultaneously, how do we handle losses? How do we prevent buffer overflow at the receiver? How do we ensure frames are delivered in order? Go-Back-N answers these questions with an elegant design that prioritizes simplicity at the receiver while accepting strategic trade-offs at the sender.

At its core, Go-Back-N ARQ allows the sender to transmit up to N frames before receiving any acknowledgment, where N is the window size. This window of outstanding frames slides forward as acknowledgments arrive, hence the broader category name: sliding window protocols.

The defining characteristics of Go-Back-N:

1. Sender maintains a window: The sender can have up to N unacknowledged frames outstanding at any time
2. In-order delivery guarantee: The receiver delivers frames to the upper layer strictly in sequence
3. Cumulative acknowledgments: An ACK for frame n implicitly acknowledges all frames up to and including n
4. Complete retransmission on error: When a frame is lost or corrupted, the sender retransmits that frame AND all subsequent frames already sent

The name "Go-Back-N" derives from this retransmission behavior: upon detecting an error, the sender "goes back" N frames (or to the last unacknowledged frame) and retransmits from that point, even if subsequent frames were received correctly.

The Go-Back-N sender is more sophisticated than its Stop-and-Wait counterpart, maintaining several critical state variables:

Sender State Variables:

• send_base: The sequence number of the oldest unacknowledged frame (left edge of the window)
• nextseqnum: The sequence number to be assigned to the next frame to be sent
• N: The window size (maximum number of outstanding frames)
• buffer[0..N-1]: Storage for frames that may need retransmission

The Sender Window:

Conceptually, the sequence number space is divided into four regions:

1. [0, send_base): Frames sent and acknowledged; no longer of concern
2. [send_base, nextseqnum): Frames sent but not yet acknowledged (outstanding/in-flight)
3. [nextseqnum, send_base + N): Frames that can be sent immediately if data is available
4. [send_base + N, ∞): Frames that cannot be sent until the window advances

The usable window consists of regions 2 and 3: frames already in flight plus frames available for immediate transmission. The invariant maintained is:

send_base <= nextseqnum <= send_base + N

This ensures no more than N frames are ever outstanding.

Sender Events and Actions:

Event 1: Data from Upper Layer

When the upper layer (e.g., network layer) has data to send:

if (nextseqnum < send_base + N) {
    // Window has room
    buffer[nextseqnum mod N] = make_frame(data, nextseqnum);
    send(buffer[nextseqnum mod N]);
    if (send_base == nextseqnum) {
        start_timer();  // Start timer for oldest outstanding frame
    }
    nextseqnum++;
} else {
    // Window full - refuse data or buffer at application level
    refuse_data(data);
}

Event 2: ACK Received

When an acknowledgment for frame with sequence number ack_num arrives:

if (ack_num >= send_base) {
    // Cumulative ACK: all frames up to ack_num are now acknowledged
    send_base = ack_num + 1;
    if (send_base == nextseqnum) {
        stop_timer();  // All frames acknowledged
    } else {
        restart_timer();  // Reset timer for new oldest outstanding frame
    }
}
// If ack_num < send_base, this is a duplicate ACK (ignore or handle specially)

Event 3: Timeout

When the timer expires (no ACK received within timeout period):

start_timer();
for (i = send_base; i < nextseqnum; i++) {
    // Retransmit ALL outstanding frames
    send(buffer[i mod N]);
}

This is the "Go-Back-N" behavior: the sender retransmits every frame from send_base to nextseqnum - 1, regardless of which frame actually caused the timeout.

The Go-Back-N receiver is deliberately simple, maintaining only a single state variable:

Receiver State Variable:

• expectedseqnum: The sequence number of the next frame expected (the only frame that will be accepted)

Receiver Behavior:

The receiver enforces strict in-order delivery with the following logic:

receive(frame):
    if (frame.seqnum == expectedseqnum && !corrupted(frame)) {
        // Frame is exactly what we expect
        deliver_data(frame.data);
        send(ACK, expectedseqnum);
        expectedseqnum++;
    } else {
        // Frame is out of order, corrupted, or duplicate
        // Discard the frame
        // Send ACK for last correctly received in-order frame
        send(ACK, expectedseqnum - 1);
    }

Critical Insight: Out-of-Order Frames Are Discarded

This is the most distinctive aspect of Go-Back-N receiver behavior. If the receiver expects frame 5 but receives frame 6 (because frame 5 was lost), it discards frame 6 and sends an ACK for frame 4 (the last in-order frame received). This happens even though frame 6 is a perfectly valid frame!

Why discard correct frames?

1. No buffering required: The receiver doesn't need to buffer out-of-order frames
2. Guaranteed in-order delivery: Frames are always delivered to the upper layer in sequence
3. Simple implementation: Receiver logic is minimal and stateless (beyond one counter)
4. Triggers retransmission: Duplicate ACKs signal to the sender that something went wrong

ACK Semantics in Go-Back-N:

The ACK sent by the receiver carries the sequence number of the last correctly received in-order frame. When the receiver sends ACK n, it means:

"I have correctly received all frames with sequence numbers ≤ n. I am now expecting frame n+1."

This cumulative semantics has important implications:

• If ACK 7 arrives, the sender knows frames 0-7 are all received
• Even if ACK 5 was lost, receiving ACK 7 retroactively acknowledges frames 5, 6, and 7
• The sender can advance send_base based on a single ACK

Let's trace through a complete Go-Back-N scenario to solidify understanding. Consider a sender with window size N = 4 and data frames 0, 1, 2, 3, 4, 5 to transmit. We'll examine both normal operation and error recovery.

Scenario Setup:

• Sender window size: N = 4
• Initial state: send_base = 0, nextseqnum = 0, expectedseqnum = 0
• Frame 2 will be lost during transmission

Understanding the Go-Back Behavior:

When the timeout occurred at T10, the sender's state showed send_base = 2 (oldest unacknowledged frame) and nextseqnum = 5 (next frame to send would be 5). The go-back behavior retransmitted frames 2, 3, and 4—everything from send_base to nextseqnum - 1.

The sender effectively "goes back" to the point of the error and retransmits from there. This is simpler than selectively retransmitting only Frame 2, but wastes bandwidth resending Frames 3 and 4.

Duplicate ACKs as Error Signals:

Notice that the receiver sent ACK 1 multiple times (at T6, T7, T9). These duplicate ACKs signal that the receiver keeps getting frames after frame 1 but is still waiting for frame 2. Some implementations use duplicate ACKs to trigger fast retransmission before timeout expires—a technique later refined in TCP's Fast Retransmit mechanism.

Timer management in Go-Back-N is crucial for correct operation and efficiency. Unlike Selective Repeat (which maintains a timer per outstanding frame), Go-Back-N uses a single timer associated with the oldest unacknowledged frame.

Timer Lifecycle:

1. Start timer when the first frame is transmitted (when window goes from empty to non-empty)
2. Stop timer when all frames are acknowledged (send_base == nextseqnum)
3. Restart timer when a new frame becomes the oldest unacknowledged (when send_base advances but window is not empty)
4. On timeout restart timer and retransmit all outstanding frames

Why a Single Timer?

When the timer for the oldest outstanding frame expires, we know that at least one frame was lost (or its ACK was lost). Due to cumulative acknowledgments and the receiver's in-order delivery requirement, if frame k is lost, all frames k+1, k+2, ... must be retransmitted anyway. Therefore, a single timer suffices—timeout always triggers retransmission of all outstanding frames.

Timer Implementation Strategies:

Strategy 1: Hardware Timer

- Single countdown timer
- On expiry: Interrupt CPU, trigger retransmission
- On ACK: Reset timer to initial value
- Simple but requires hardware support

Strategy 2: Software Timer with Timestamps

- Record transmission time of oldest outstanding frame
- Periodically check: if (current_time - oldest_tx_time > timeout)
     trigger retransmission
- More flexible, works without dedicated timer hardware

Strategy 3: Piggyback on Event Loop

- Use select() / poll() with timeout parameter
- Timeout = min(remaining_timeout, ...) 
- Integrate with network I/O multiplexing
- Common in modern implementations

Timeout and RTT Estimation:

In real implementations, the timeout value adapts to network conditions:

Estimated_RTT = (1 - α) × Estimated_RTT + α × Sample_RTT
Timeout = β × Estimated_RTT

Where:

• Sample_RTT = measured round-trip time for a recent frame
• α = smoothing factor (typically 0.125 or 1/8)
• β = safety margin multiplier (typically 2-4)

For complete clarity and implementation guidance, here is the formal specification of Go-Back-N ARQ as finite state machines.

GBN Sender FSM:

GBN Receiver FSM:

We've now established a complete understanding of Go-Back-N ARQ operation. Let's consolidate the essential knowledge:

What's Next:

With the operational mechanics established, the next page dives deep into cumulative acknowledgments—exploring their semantics, advantages, implications for lost ACKs, and how they enable the window to slide efficiently. Understanding cumulative ACKs is essential for grasping GBN's efficiency characteristics and its relationship to TCP's acknowledgment scheme.