Go-Back-N Automatic Repeat reQuest

In reliable data transfer protocols, acknowledgments serve as the fundamental feedback mechanism confirming successful frame reception. However, not all acknowledgment schemes are created equal. While individual (selective) acknowledgments explicitly confirm each frame independently, Go-Back-N employs cumulative acknowledgments—a semantically richer approach where a single ACK carries information about multiple frames.

Cumulative acknowledgments are not merely an implementation choice; they represent a profound design decision with far-reaching implications for protocol efficiency, robustness to ACK loss, and implementation complexity. Understanding cumulative ACK semantics is essential for mastering Go-Back-N and provides insight into TCP's acknowledgment mechanisms, which share the same fundamental principle.

This page dissects cumulative acknowledgments from first principles: their precise semantics, mathematical properties, practical advantages, edge cases, and the subtle ways they interact with the sliding window mechanism.

Definition:

In Go-Back-N, when the receiver sends ACK(n), it asserts:

"I have correctly received all frames with sequence numbers 0, 1, 2, ..., n in order, and I have delivered them to my upper layer. I am now expecting frame n+1."

This single acknowledgment carries information equivalent to n+1 individual acknowledgments. It is cumulative because it implicitly acknowledges all frames up to and including the specified sequence number.

Formal Properties:

Let ACK(n) denote an acknowledgment for sequence number n. The cumulative semantics imply:

1. Monotonicity: If ACK(n) has been sent, then for all k ≤ n, frame k has been received correctly
2. Subsumption: ACK(n) subsumes ACK(k) for all k < n (i.e., ACK(n) provides strictly more information)
3. Ordering: ACKs are logically monotonically increasing; once ACK(n) is valid, ACK(k) for k < n is redundant
4. Atomicity: There is no partial acknowledgment; either all frames ≤ n are acknowledged, or ACK(n) is not valid

Mathematical Representation:

Let R(t) denote the set of sequence numbers correctly received by time t. In Go-Back-N with cumulative ACKs:

• At any time t, R(t) = {0, 1, 2, ..., k} for some k ≥ -1 (where k = -1 means no frames received)
• The receiver sends ACK(k) where k = max(R(t))
• R(t) is always a contiguous prefix of the natural numbers

This contiguity property is enforced by the receiver discarding out-of-order frames. If the receiver accepted out-of-order frames, R(t) could have gaps, and cumulative ACKs would be insufficient to report the reception status accurately.

One of the most powerful properties of cumulative acknowledgments is their natural tolerance to ACK loss. This robustness arises directly from the subsumption property: if ACK(n) is received, all information from ACK(0) through ACK(n-1) is recovered.

Scenario: Lost ACKs in Go-Back-N

Consider the sender transmits frames 0, 1, 2, 3, 4 with window size N = 5. The receiver correctly receives all frames and sends ACK(0), ACK(1), ACK(2), ACK(3), ACK(4). However, ACK(0), ACK(1), and ACK(2) are lost in transit. Only ACK(3) and ACK(4) arrive at the sender.

Contrast with Selective ACKs:

If the protocol used selective (individual) acknowledgments, losing ACK(0), ACK(1), ACK(2) would be catastrophic. The sender would have no confirmation for frames 0, 1, 2 and would eventually time out and retransmit them—even though they were correctly received. This wastes bandwidth and increases latency.

Formal Analysis:

Let p be the probability of ACK loss. In a system with selective ACKs, a frame requires retransmission if its ACK is lost. Expected transmissions per frame = 1/(1-p).

With cumulative ACKs, a frame requires retransmission only if ALL subsequent ACKs are lost (i.e., no later ACK arrives before timeout). If we send k frames after frame n, frame n needs retransmission only if ACK(n), ACK(n+1), ..., ACK(n+k) are all lost. Probability = p^(k+1).

For even moderate k (say, k = 5 frames before timeout), and p = 0.1:

• Selective: 10% of frames need retransmission
• Cumulative: 0.000001% of frames need retransmission

This dramatic difference demonstrates why cumulative ACKs provide superior ACK loss tolerance.

Cumulative acknowledgments directly drive the sliding window mechanism. When an ACK arrives, the sender's window advances proportionally, potentially opening space for multiple new frames to be transmitted.

Window Update Algorithm:

on_receive_ack(ack_num):
    if ack_num >= send_base:        // Valid cumulative ACK
        frames_acked = ack_num - send_base + 1
        send_base = ack_num + 1     // Advance window left edge
        
        // Now we can send 'frames_acked' new frames
        // (assuming upper layer has data to send)
        for i in range(frames_acked):
            if upper_layer_has_data():
                transmit_next_frame()

Example: Window Dynamics

Consider window size N = 4, initial send_base = 0, and frames 0-7 to send.

Interaction with Delayed ACKs:

In practice, receivers often delay ACKs to reduce the number of acknowledgment packets. Instead of sending ACK(n) immediately upon receiving frame n, the receiver might:

1. Wait for additional frames — If frame n+1 arrives shortly, send ACK(n+1) instead
2. Piggyback on data — If receiver has data to send, include ACK in the data frame
3. Use a delayed ACK timer — Send ACK after a short delay (e.g., 200ms) or after every 2nd frame

Cumulative ACKs work seamlessly with delayed acknowledgments. If the receiver delays ACK(n) and frame n+1 arrives, it can send only ACK(n+1), effectively combining two acknowledgments into one. The sender receives full information despite fewer ACK packets.

This is particularly valuable for asymmetric channels where the reverse path (receiver → sender) has limited bandwidth. Reducing ACK traffic improves overall channel efficiency.

While cumulative ACKs cannot directly report reception gaps (unlike SACKs), they provide an indirect mechanism for error detection: duplicate acknowledgments.

Definition:

A duplicate ACK is an acknowledgment with the same sequence number as a previously received ACK (where the receiver has already advanced past that point but continues to receive out-of-order frames).

How Duplicate ACKs Arise:

When the receiver expects frame n but receives frame n+1 (because frame n was lost or delayed):

1. Receiver discards frame n+1 (Go-Back-N receiver behavior)
2. Receiver sends ACK(n-1) — acknowledging up to the last in-order frame
3. If frame n+2 arrives (still expecting n), receiver again sends ACK(n-1)
4. Each out-of-order arrival generates another ACK(n-1)

The sender receives multiple ACK(n-1) packets— these are duplicate ACKs.

Interpreting Duplicate ACKs:

Duplicate ACKs signal a potential problem:

• 1-2 duplicates: Could be reordering in the network; not necessarily a loss
• 3+ duplicates: Strong indication that a frame was lost and subsequent frames are arriving

This interpretation inspired TCP Fast Retransmit: upon receiving 3 duplicate ACKs, TCP retransmits the presumed lost segment without waiting for timeout.

Example: Duplicate ACK Generation

Sender transmits frames 0, 1, 2, 3, 4 (window N = 5). Frame 2 is lost.

The sender receives: ACK(0), ACK(1), ACK(1), ACK(1).

Three ACK(1)s confirm that:

• Frames 0 and 1 were received
• Frame 2 (or later) is missing
• Frames after 2 are arriving (hence the duplicate ACKs)

Using Duplicate ACKs for Fast Retransmit (Enhancement):

on_receive_ack(ack_num):
    if ack_num == last_ack_received:
        dup_ack_count++
        if dup_ack_count >= 3:
            // Fast retransmit: don't wait for timeout
            retransmit_from(ack_num + 1)
            dup_ack_count = 0
    else:
        last_ack_received = ack_num
        dup_ack_count = 0
        advance_window(ack_num)

This enhancement is not part of classic GBN but demonstrates how cumulative ACKs can be leveraged for faster error recovery.

Cumulative acknowledgments, while elegant, introduce subtle edge cases that implementations must handle correctly.

Edge Case 1: Out-of-Order ACK Arrival

ACKs can arrive out of order due to network path variations. If the sender receives ACK(5) then ACK(3):

• ACK(5) advances send_base to 6
• ACK(3) arrives, but 3 < 6, so it's stale
• Sender must recognize ACK(3) as redundant and ignore it

Implementation:

if (ack_num >= send_base):
    // Valid, advance window
else:
    // Stale ACK, ignore

Edge Case 2: ACK for Unsent Frame

Due to corruption or bugs, an ACK might arrive for a sequence number not yet sent:

if (ack_num >= nextseqnum):
    // Impossible! ACK for unsent frame
    // Likely corruption or protocol violation
    // Ignore or log anomaly

Edge Case 3: ACK During Retransmission

If a timeout occurs and the sender is retransmitting frames, an ACK might arrive mid-retransmission. Should the sender:

a) Complete retransmission of all outstanding frames? b) Stop retransmission and process the ACK?

Option (b) is more efficient—if ACK(k) arrives during retransmission, frames ≤ k are confirmed received; only frames > k need retransmission.

Edge Case 4: Wraparound Near Window Boundary

With finite sequence number space (say, 0 to 7 with 3-bit sequence numbers), ACK values wrap around. An ACK(1) could mean:

• Frame 1 in the current cycle, OR
• Frame 1 from a previous cycle (stale)

The protocol must use the window position to disambiguate:

if (ack_num is within the range [send_base, send_base + N) modulo sequence_space):
    // Valid ACK for current window
else:
    // Likely stale or corrupted

This check relies on having a sequence number space larger than the window size—a constraint we'll explore in the window sizing page.

Edge Case 5: ACK for Exactly send_base - 1

If ACK(send_base - 1) arrives:

• This acknowledges up to the frame before the current window
• But frames before send_base are already acknowledged
• This is a duplicate/stale ACK and should be ignored

Notably, the receiver might send this ACK if it receives a duplicate of a frame it already processed. The cumulative semantics don't advance the sender's window.

TCP, the workhorse of Internet transport, uses cumulative acknowledgments in its core design, directly inheriting from Go-Back-N principles. Understanding GBN cumulative ACKs provides direct insight into TCP behavior.

TCP's Acknowledgment Field:

The TCP header contains a 32-bit Acknowledgment Number field. When the ACK flag is set:

"The acknowledgment number contains the next sequence number the sender of the ACK is expecting to receive, acknowledging receipt of all bytes up to but not including this number."

This is cumulative semantics using byte sequence numbers rather than frame numbers.

TCP Enhancement: SACK

While TCP's base mechanisms use cumulative ACKs, the Selective Acknowledgment (SACK) option (RFC 2018) adds the ability to report non-contiguous blocks. This combines GBN's cumulative robustness with SR's gap reporting.

TCP SACK example:
ACK = 1000          (cumulative: bytes 0-999 received)
SACK block 1: 1500-2000
SACK block 2: 2500-3000

Meaning: Received 0-999, 1500-1999, 2500-2999
         Missing: 1000-1499, 2000-2499

Cumulative acknowledgments are a cornerstone of Go-Back-N's elegance and efficiency. Let's consolidate the essential insights:

What's Next:

With cumulative acknowledgments understood, we're ready to explore a critical protocol constraint: window size limits. Why can't we simply set N to infinity for maximum efficiency? The next page reveals how sequence number space, receiver buffer, and error recovery interact to impose strict bounds on the window size—and how violating these bounds leads to protocol failure.