Acknowledgments

Part of Networking

Confirming receipt — how acknowledgment systems ensure that every transmitted packet actually arrives and how to recover when it does not.

Why This Matters

Sending data over a network is like sending a letter by post: you have no guarantee of delivery. The wire may have been cut, the receiving computer may have crashed, a buffer may have overflowed, noise may have corrupted the packet beyond repair. Without some form of acknowledgment, the sender has no way to know whether the data arrived.

Acknowledgment systems are the foundation of reliable communication protocols. They transform unreliable packet delivery (best-effort) into reliable message delivery (guaranteed). TCP, the protocol underlying virtually all internet applications, is built on acknowledgments. But the principle is simple enough to implement over any bidirectional link — even a pair of radios, a telephone line, or a long wire between buildings.

In a rebuilt network where hardware is heterogeneous and link quality is unpredictable, explicit acknowledgment protocols are more important than in a well-maintained commercial network. Dropped packets on a noisy radio link without acknowledgment go unnoticed; with acknowledgment, they are detected and retransmitted automatically.

What an Acknowledgment Is

An acknowledgment (ACK) is a short message sent by the receiver back to the sender, saying “I received your message and it was correct.” The absence of an ACK within a timeout period tells the sender to retransmit.

The simplest possible acknowledgment protocol:

1. Sender sends a packet
2. Sender starts a timer
3. Receiver receives packet, checks for errors (via checksum), sends ACK back to sender
4. If sender receives ACK before timer expires: success, send next packet
5. If timer expires before ACK received: retransmit the packet and restart the timer

This is called Stop-and-Wait ARQ (Automatic Repeat reQuest). It is reliable: if the ACK arrives, the packet was received correctly; if not, the packet is retransmitted until it is received correctly or a maximum retry count is exhausted.

Stop-and-Wait: Detail and Limitations

Packet sequence numbers: Consider what happens if the ACK is lost (not the packet, but the acknowledgment). The sender does not receive the ACK, retransmits the packet, and the receiver receives a duplicate. Without sequence numbers, the receiver cannot distinguish a new packet from a retransmission of the previous one.

Solution: Assign a sequence number to each packet. For stop-and-wait, a 1-bit sequence number suffices: packets alternate between 0 and 1. The receiver accepts a packet only if its sequence number matches what is expected next. If it is a duplicate (same number as previous packet), send ACK but discard the data.

Efficiency: Stop-and-wait sends one packet at a time — the second packet cannot be sent until the first ACK arrives. If the propagation delay is long (e.g., a satellite link or a slow radio link), the sender spends most of its time waiting. Efficiency = packet transmission time / (packet transmission time + round-trip propagation delay).

For a local network where propagation delay is microseconds and packet transmission takes milliseconds, stop-and-wait is 99%+ efficient. For a satellite link where round-trip delay is 500 milliseconds, stop-and-wait with 1 KB packets at 1 Mbps achieves only ~2% efficiency. This is the motivation for sliding window protocols.

Sliding Window: Pipelining ACKs

A sliding window protocol allows the sender to have multiple unacknowledged packets in flight simultaneously. The “window” is the maximum number of unacknowledged packets allowed at once.

Go-Back-N ARQ:

• Sender numbers packets with n-bit sequence numbers (window size up to 2^n - 1)
• Sender may have up to W packets outstanding without receiving ACKs
• Receiver accepts only in-order packets; if packet K is received but packet K-1 hasn’t been received, receiver discards K and sends ACK for K-1 (the last correctly received in-order packet)
• On timeout or negative acknowledgment (NAK), sender retransmits from the last unacknowledged packet onward (“goes back N”)
• Receiver buffer needed: 1 packet only (discards out-of-order arrivals)

Selective Repeat ARQ:

• Same window structure as Go-Back-N
• Receiver accepts and buffers out-of-order packets; sends ACK for each correctly received packet individually
• Sender retransmits only specifically unacknowledged packets (not all subsequent ones)
• More efficient than Go-Back-N when individual packets are lost (common on noisy links)
• Receiver buffer needed: up to W packets

TCP’s approach: TCP uses cumulative ACKs (ACK N means “I have received everything through byte N”) plus selective acknowledgment (SACK) options for specific missing segments. This is an advanced version of selective repeat.

Negative Acknowledgments (NAK)

Instead of waiting for a timeout, a receiver can explicitly signal the sender that a packet was received with an error (wrong checksum) or out of order. This negative acknowledgment (NAK or NACK) triggers immediate retransmission without waiting for the timeout.

NAK advantages: Faster recovery from errors on noisy links; the sender does not have to wait the full timeout period.

NAK disadvantages: Requires bidirectional communication even for one-way data transfers; NAK itself might be lost; more complex implementation.

Many simple point-to-point protocols use NAK in addition to ACK timeouts: normal reception sends no response (ACK silence = success), corrupted reception sends NAK immediately, missing reception (sequence gap) triggers NAK.

Implementing a Simple ACK Protocol

For a minimal reliable data transfer between two computers over a serial link (RS-232 or UART), here is a complete protocol:

Packet format (total: 6 + data_length bytes):

Byte 0:   STX (0x02) — start of packet marker
Byte 1:   SEQ — 1-bit sequence number (0 or 1) in bit 0; remaining bits 0
Byte 2–3: LEN — data length in bytes (16-bit big-endian)
Byte 4 to 4+LEN-1: DATA
Byte 4+LEN: Checksum low byte (16-bit additive)
Byte 5+LEN: Checksum high byte
Byte 6+LEN: ETX (0x03) — end of packet marker

ACK format (3 bytes):

Byte 0: ACK (0x06) — acknowledged
Byte 1: SEQ — sequence number being acknowledged
Byte 2: Checksum — XOR of bytes 0 and 1

NAK format (3 bytes):

Byte 0: NAK (0x15) — not acknowledged
Byte 1: SEQ — sequence number being rejected
Byte 2: Checksum

Sender algorithm:

seq = 0
for each block to send:
    retries = 0
    while retries < MAX_RETRIES:
        send packet(seq, data_block)
        start_timer(TIMEOUT_MS)
        response = wait_for_response()
        if response is ACK with seq == current_seq:
            seq ^= 1  # flip between 0 and 1
            break
        elif timeout or NAK:
            retries++
    if retries == MAX_RETRIES:
        report_error("Link failure")

Receiver algorithm:

expected_seq = 0
loop:
    packet = receive_next_packet()
    if checksum_valid(packet) and packet.seq == expected_seq:
        process(packet.data)
        send ACK(expected_seq)
        expected_seq ^= 1
    elif checksum_valid(packet) and packet.seq != expected_seq:
        # duplicate from retransmission
        send ACK(packet.seq)  # resend ACK for this (old) packet
    else:
        # checksum error
        send NAK(packet.seq)

This protocol handles: lost packets (timeout retransmit), corrupted packets (checksum failure + NAK), lost ACKs (timeout retransmit + duplicate detection), and duplicate packets (sequence number check).

Choosing Timeout Values

The timeout period must be long enough that the ACK has time to return before the timer expires, but short enough that failed transmissions are detected quickly.

Minimum timeout: Round-trip propagation delay + processing time at receiver + transmission time of ACK.

• For a local serial link at 9600 baud: ACK transmission takes ~3 ms, processing ~5 ms, propagation ~negligible → minimum timeout ~10 ms
• For a radio link with 100 ms range: ~250 ms minimum
• For a long telephone line: variable, set to 1–3 seconds

Adaptive timeout (TCP RTT estimation): TCP measures actual round-trip times and adjusts the timeout dynamically. A simplified version: after each successful exchange, update estimated RTT = 0.875 × old_RTT + 0.125 × measured_RTT. Set timeout = 2 × estimated_RTT. Start with a large conservative estimate (e.g., 1 second) and let it converge.

For simple systems, a fixed timeout of 2–5× the expected round-trip time is sufficient. Include a maximum retry count (typically 3–5 retries) and report link failure if exceeded — this distinguishes a slow link from a dead link.