Error Control, Flow Control and Reliable Delivery

Introduction

Data transmitted across a network may be altered, lost, duplicated, delayed, or delivered out of order. Electrical interference, weak wireless signals, congestion, faulty hardware, buffer overflow, and software failures all contribute to these problems. Reliable communication therefore requires more than placing bits on a medium. A communication system must detect or correct errors, regulate the rate of transmission, and recover from loss or damage.

This chapter examines three closely related functions. Error control protects data integrity. Flow control prevents a fast sender from overwhelming a slower receiver. Reliable delivery combines detection, acknowledgements, sequencing, buffering, and retransmission to provide an acceptable service to applications. These functions appear at several layers: data-link protocols such as Ethernet and Wi-Fi, transport protocols such as TCP, and application-specific systems such as reliable file transfer.

Learning Objectives

By the end of this chapter, you should be able to:

• distinguish error detection from error correction;
• calculate and interpret parity, checksums, CRCs, and Hamming-code results;
• explain forward error correction and identify appropriate applications;
• describe acknowledgements, sequence numbers, timeouts, and retransmission;
• compare Stop-and-Wait, Go-Back-N, and Selective Repeat ARQ;
• explain buffering, sliding windows, and receiver-advertised flow control;
• analyse reliability mechanisms in a practical communication scenario.

1. Errors in Digital Communication

A transmitted frame normally contains a payload and additional control information. A bit error occurs when a 0 becomes 1 or a 1 becomes 0. A single-bit error affects one bit; a burst error affects a contiguous sequence of bits, although not every bit in that sequence must be changed.

A useful measure is the bit error rate (BER):

BER is dimensionless and is normally estimated over a sufficiently large observation interval. It describes the channel, not necessarily the application-level loss rate, because coding and retransmission can conceal many physical errors.

Error-control techniques have two broad purposes:

1. Error detection: add redundancy so that the receiver can determine that data is probably damaged.
2. Error correction: add enough structured redundancy for the receiver to determine the original data, either directly or through retransmission.

Detection codes generally require less overhead than correction codes. A system using Automatic Repeat reQuest (ARQ) detects errors and asks for a retransmission. A system using Forward Error Correction (FEC) sends correction information in advance, allowing the receiver to repair some errors without a return message.

2. Error-Detection Methods

2.1 Parity

The simplest parity method appends one bit to a data unit. With even parity, the total number of 1s, including the parity bit, must be even. With odd parity, the total must be odd.

For data 1011001, there are four 1s. The even-parity bit is 0, giving 10110010; the odd-parity bit is 1, giving 10110011. The receiver counts 1s and rejects a block whose parity rule is violated.

A single parity bit detects every odd number of bit reversals, but it fails to detect any error pattern involving an even number of changed bits. It also provides no indication of the error location. Two-dimensional parity, in which parity is calculated for rows and columns, can locate and correct many single-bit errors and detect several multiple-bit patterns.

2.2 Checksums

A checksum divides data into fixed-size words, adds them using one’s-complement arithmetic, and complements the result. The receiver adds the data words and checksum; a correct block produces an all-ones result under the usual one’s-complement convention.

In one’s-complement addition, any carry beyond the word size is wrapped around and added to the least significant bit. For example, using 8-bit words:

• 10110110 + 01101101 = 1 00100011;
• wrap the carry: 00100011 + 1 = 00100100;
• complement: checksum = 11011011.

The receiver adds 10110110, 01101101, and 11011011 using the same rules. The result is 11111111, indicating no detected error.

Checksums are inexpensive and widely used in network and transport protocols. However, different error patterns can produce the same sum, so a checksum is not a proof that data is correct. It is a probabilistic detector whose strength depends on word size and error pattern.

2.3 Cyclic Redundancy Check

A Cyclic Redundancy Check (CRC) treats a bit string as the coefficients of a polynomial over the binary field GF(2). Addition and subtraction are both exclusive OR (XOR); there are no carries. Let the generator polynomial be G(x), with degree r. The sender appends r zero bits to the data and divides the resulting polynomial by G(x) using modulo-2 division. The r-bit remainder is appended as the frame check sequence.

Here, M(x) is the message polynomial, r is the degree of G(x), R(x) is the remainder, and T(x) is the transmitted codeword. The remainder is selected so that T(x) is exactly divisible by G(x).

At the receiver, the received polynomial is divided by G(x). A nonzero remainder indicates a detected error. CRC performance depends on the generator. A well-chosen generator detects all single-bit errors, all burst errors of length ≤ r, and many longer error patterns. The exact guarantees depend on the polynomial’s factors and the assumed error model.

#### CRC worked example

Let the data be 1101 and the generator be 1011. The generator has four bits, so r = 3. Append three zeros:

Modulo-2 division gives a remainder of 001. Therefore, the transmitted codeword is:

Dividing 1101001 by 1011 gives a zero remainder. If one or more bits change in a pattern that the generator detects, the receiver obtains a nonzero remainder and discards the frame. CRC detects corruption; it does not identify the original bit pattern or repair the frame.

3. Error-Correction Techniques

3.1 Hamming distance

The Hamming distance between two equal-length bit strings is the number of positions in which they differ. The minimum distance of a code, dmin, is the smallest distance between any two valid codewords.

A code with minimum distance dmin can detect up to dmin − 1 errors and can correct up to:

where t is the guaranteed number of correctable errors and ⌊ ⌋ denotes the floor operation. These guarantees assume the received word is closest to the transmitted codeword and that the error pattern is within the code’s correction capability.

3.2 Hamming codes

A Hamming code places parity bits at positions that are powers of two: 1, 2, 4, 8, and so forth. If m data bits and r parity bits are used, the usual single-error-correcting condition is:

The right side represents all possible error locations, including no error. Each parity bit checks positions whose binary position number contains a particular 1 in its corresponding place. The receiver recomputes the parity checks. Their combined result is the syndrome, whose binary value identifies the erroneous position.

#### Hamming example

For four data bits, choose r = 3 because 2³ = 8 ≥ 4 + 3 + 1. The seven positions are:

Suppose the data is 1011, placed as d1 = 1, d2 = 0, d3 = 1, d4 = 1. Using even parity:

• p1 checks positions 1, 3, 5, 7, so p1 ⊕ 1 ⊕ 0 ⊕ 1 = 0; p1 = 0.
• p2 checks positions 2, 3, 6, 7, so p2 ⊕ 1 ⊕ 1 ⊕ 1 = 0; p2 = 1.
• p4 checks positions 4, 5, 6, 7, so p4 ⊕ 0 ⊕ 1 ⊕ 1 = 0; p4 = 0.

The codeword is 0110011. If position 6 changes, the parity checks associated with positions 2, 4, and 6 fail in a pattern 110₂ = 6. The receiver flips position 6 and recovers the original codeword. Basic Hamming code corrects one-bit errors, but it is not guaranteed to correct two-bit errors. An extended Hamming code adds an overall parity bit and can commonly correct one error while detecting two errors.

3.3 Forward Error Correction

FEC sends redundant information so that the receiver can correct errors without retransmission. Examples include Reed–Solomon codes in storage and optical systems, convolutional and turbo codes in communication systems, and LDPC and polar codes in modern wireless and broadband standards.

FEC is especially valuable when a return path is unavailable, propagation delay is large, retransmission is expensive, or errors occur in bursts. Its disadvantages are coding overhead, processing cost, and the possibility that correction fails when the error rate exceeds the code’s capability. Practical systems often combine FEC with ARQ, producing hybrid ARQ.

4. Reliable Delivery

A reliable protocol defines what the receiver and sender do when a frame is lost, duplicated, damaged, delayed, or delivered out of order. Its central mechanisms are:

• Sequence numbers, which identify frames and distinguish new data from duplicates;
• Acknowledgements (ACKs), which confirm successful receipt;
• Negative acknowledgements (NAKs), which explicitly report missing or damaged data;
• Timers, which cause recovery when an acknowledgement is not received;
• Retransmission, which sends the suspected missing data again;
• Checksums or CRCs, which prevent damaged data from being accepted;
• Buffering, which temporarily stores data awaiting processing or reordering.

An ACK is not necessarily proof that an application has permanently stored data. Its meaning is defined by the protocol: it may confirm receipt into a network buffer, delivery to a transport process, or successful durable storage. System designers must state this boundary clearly.

Stop-and-Wait ARQ

Stop-and-Wait sends one frame and waits for its ACK before sending the next. If the frame is damaged or the timer expires, the sender retransmits. Sequence numbers, often alternating 0 and 1, prevent a delayed duplicate from being mistaken for new data.

Its simplicity is attractive, but link utilisation can be poor on long-delay links. If frame transmission time is Tt and round-trip propagation plus processing and acknowledgement delay is approximately RTT, the ideal utilisation without additional pipelining is approximately:

This approximation assumes no losses, negligible ACK transmission time, and one outstanding frame. With a 1 ms frame transmission time and a 20 ms RTT, U ≈ 1 ÷ 21 ≈ 4.8%.

Go-Back-N ARQ

Go-Back-N permits several unacknowledged frames. The receiver generally accepts only the next frame in sequence and discards later out-of-order frames. A cumulative ACK confirms receipt of all frames up to a stated sequence number. If frame k is lost, the sender retransmits frame k and all subsequent outstanding frames.

Go-Back-N is simple and requires limited receiver buffering, but one loss can cause unnecessary retransmission of correctly received frames.

Selective Repeat ARQ

Selective Repeat allows the receiver to buffer out-of-order frames and acknowledge them individually or selectively. The sender retransmits only frames believed to be missing. It improves efficiency on high-delay or error-prone links but requires more memory, timers, sequence-number management, and careful duplicate handling.

For a sequence-number space of size S, a Selective Repeat window is normally constrained to at most S ÷ 2, so that old and new frames cannot be confused after sequence numbers wrap around. Exact protocol rules may impose additional constraints.

5. Flow Control and Sliding Windows

Error control asks, “Was the data received correctly?” Flow control asks, “Can the receiver accept data at this rate?” Without flow control, a fast sender can fill the receiver’s buffer, causing loss even when the physical link is error-free.

A receiver may advertise a receive window, commonly denoted rwnd, indicating how much additional data it can accept. The sender limits the amount of unacknowledged data accordingly. In a byte-oriented protocol, a simplified usable sending limit is:

The congestion window protects the network; the receive window protects the receiver. This distinction is important in protocols such as TCP. In a pure data-link sliding-window protocol, the window may primarily represent sequence-number and buffer constraints.

A sliding window contains frames or bytes that have been sent but not yet cumulatively acknowledged. When an ACK advances the lower edge, new data can enter at the upper edge. The sender therefore maintains a pipeline rather than stopping after every frame.

If the window size is W frames and the sender can keep the link busy, the approximate maximum number of outstanding frames is W. A practical window must account for sequence-number space, receiver memory, retransmission strategy, and delay-bandwidth product. The bandwidth-delay product is:

If bandwidth is measured in bits per second and RTT in seconds, BDP is in bits. A sender needs approximately this much in-flight data to fully utilise a path, subject to protocol and receiver limits.

Other flow-control mechanisms

• Stop-and-wait flow control: the sender transmits only after permission or acknowledgement.
• Credit-based flow control: the receiver grants a number of frames or bytes that may be sent.
• Sliding-window flow control: permission is represented by a moving range of sequence numbers.
• Rate-based flow control: the sender is instructed to transmit at a specified rate.
• Backpressure: downstream congestion signals upstream components to slow or stop.
• Buffer thresholds: high- and low-water marks trigger pause and resume actions.

Flow control must avoid deadlock. For example, if a receiver advertises zero capacity, the sender needs a mechanism for probing later so that a lost window-update message does not stop communication permanently.

6. Buffering, Ordering and Timers

Buffers absorb short-term differences between arrival and processing rates. A receiver may maintain separate buffers for accepted data, out-of-order data, and data awaiting application consumption. Excessive buffering increases delay and may create bufferbloat; insufficient buffering causes drops and retransmissions.

A reliable receiver should define whether it delivers data strictly in order or permits out-of-order delivery. In-order delivery simplifies applications but may cause head-of-line blocking: one missing segment delays later segments that have already arrived.

Timeout selection is a design compromise. A timeout that is too short causes premature retransmissions and duplicate traffic; one that is too long delays recovery. Adaptive protocols estimate round-trip time and variation rather than using one fixed value. The timer should also allow for processing and queuing delays, not only propagation.

7. Worked Application: Reliable Telemetry over a Wireless Link

Background

Consider an illustrative environmental-monitoring system. Battery-powered sensors transmit 64-byte measurements to a gateway over a radio link. Interference from machinery produces occasional burst errors, and the gateway may temporarily be busy writing data to storage.

Problem

The design must protect measurement integrity, prevent a sensor from overrunning the gateway, and conserve battery power. A lost packet should not cause indefinite waiting, but unnecessary retransmissions should be limited.

Analysis

A parity bit is inadequate because a burst may change an even number of bits. A CRC is appropriate for detecting burst corruption. Because the radio link has a return path and measurements are not extremely delay-sensitive, ARQ is practical. The gateway needs a receive buffer and should advertise available capacity. Stop-and-Wait would be simple but would waste energy and link capacity when propagation and processing delays are significant.

Approach and solution

Each data frame contains a sensor identifier, sequence number, measurement payload, CRC, and a battery-status field. The gateway:

1. verifies the CRC;
2. discards damaged frames without delivering them to storage;
3. sends a cumulative ACK for correctly received in-order frames;
4. buffers limited out-of-order frames;
5. advertises remaining receive credits;
6. sends a NAK or relies on timeout when a gap is detected.

A small Selective Repeat window is suitable because it avoids retransmitting correctly received measurements. The sensor starts a retransmission timer after sending a frame. If an ACK arrives, the frame buffer is released. If the timer expires, the frame is retransmitted with a bounded retry count. After repeated failure, the sensor records an exception and reports it when connectivity improves.

Outcome

The CRC rejects corrupted measurements, sequence numbers prevent duplicates, selective retransmission reduces radio activity, and credits protect the gateway buffer. The retry limit prevents a permanently unreachable gateway from exhausting the battery. If the channel becomes extremely noisy, adding FEC or changing the transmission rate may be more efficient than repeated ARQ.

Learning points

Reliability is a system property, not merely a checksum feature. Detection, recovery, flow control, energy policy, buffering, and application semantics must be designed together. The meaning of “delivered” must also be specified: received by the gateway, accepted by its software, or durably stored.

8. Limitations, Security and Professional Practice

No error-control method guarantees that data is correct. A corrupted frame may occasionally produce a valid checksum or CRC. Moreover, integrity checks designed for accidental errors are not cryptographic authentication mechanisms. An attacker who can modify data may also recompute an ordinary CRC. Security-sensitive systems require message authentication codes, authenticated encryption, secure key management, and replay protection.

Reliability can also amplify congestion. If many senders retransmit after a common outage, a retransmission storm may occur. Randomised backoff, bounded retries, rate limiting, and congestion control reduce this risk. Protocol designers should monitor loss rate, retransmission rate, RTT, window occupancy, buffer utilisation, and application delivery latency.

Contemporary systems increasingly combine FEC, ARQ, congestion control, and programmable network devices. Machine-learning methods may help predict channel quality or tune coding rates, but they do not remove the need for verifiable protocol rules. Safety-critical and regulated systems require documented assumptions, traceable test cases, fault injection, and evidence that failure modes are handled safely.

Best practices include:

• choose detection strength according to the error model and consequences of failure;
• use sequence numbers and unambiguous duplicate rules;
• define ACK meaning and timer behaviour precisely;
• size windows using delay, bandwidth, sequence space, and buffer capacity;
• avoid treating CRCs as security controls;
• test loss, duplication, reordering, corruption, delay, and receiver overload;
• measure performance under realistic worst-case conditions;
• make retry limits and failure reporting explicit.

Chapter Summary

Error control adds redundancy to detect or correct transmission errors. Parity is simple but limited; checksums provide inexpensive arithmetic detection; CRCs offer strong detection of many random and burst errors; and Hamming codes use structured parity to locate and correct single-bit errors. The minimum Hamming distance determines guaranteed detection and correction capability.

Reliable delivery combines error detection with sequence numbers, acknowledgements, timers, retransmission, and buffering. Stop-and-Wait is simple but inefficient on long-delay paths. Go-Back-N pipelines frames but may repeat correctly received data. Selective Repeat is more efficient but requires greater receiver memory and protocol complexity.

Flow control prevents sender overload by limiting outstanding data through credits or sliding windows. Receive capacity must be distinguished from network capacity, and buffers must be managed to avoid both overflow and excessive delay. In professional systems, reliability, performance, security, energy use, and application semantics must be considered together.

Key Terms

Parity: A redundant bit used to enforce an odd or even count of 1s.

Checksum: An error-detection value calculated from data words.

CRC: A polynomial-based error-detection code using modulo-2 division.

Generator polynomial: The polynomial used to calculate a CRC remainder.

Burst error: An error affecting a span of transmitted bits.

Hamming distance: The number of differing positions between two equal-length codewords.

Minimum distance: The smallest Hamming distance among valid codewords.

Syndrome: A parity-check result used to identify an error position.

FEC: Forward Error Correction, which repairs some errors without retransmission.

ARQ: Automatic Repeat reQuest, in which detected failures trigger retransmission.

ACK: Acknowledgement confirming protocol-defined successful receipt.

NAK: Negative acknowledgement indicating missing or damaged data.

Sequence number: An identifier used to order data and detect duplicates.

Timeout: A limit after which missing feedback triggers recovery.

Buffer: Temporary storage used to absorb rate differences or reorder data.

Flow control: Regulation that prevents a sender from overwhelming a receiver.

Sliding window: A moving range of permitted outstanding frames or bytes.

Receive window: The amount of data a receiver can currently accept.

Head-of-line blocking: Delay of later data because an earlier item is missing.

Bandwidth-delay product: The amount of data needed in transit to fill a path.

Review Questions

Short Answer Questions

1. Distinguish error detection from error correction.
2. Why can a single parity bit fail to detect two bit errors?
3. What role does a sequence number play in reliable delivery?
4. State one major difference between Go-Back-N and Selective Repeat.
5. Why is flow control necessary even when a link has no bit errors?

Long Answer Questions

1. Explain parity, checksum, CRC, and Hamming codes, including their strengths and limitations.
2. Describe the operation of Stop-and-Wait ARQ, including duplicate prevention and timeout recovery.
3. Compare Go-Back-N and Selective Repeat in terms of receiver buffering, retransmission, and efficiency.
4. Explain how sliding windows provide both pipelining and flow control.
5. Discuss why CRC-based integrity checking is not a substitute for cryptographic authentication.

Analytical / Application Questions

1. A code has minimum Hamming distance 5. How many errors can it guarantee to detect and how many can it guarantee to correct? Explain your reasoning.
2. Design a reliable protocol for a long-delay satellite telemetry link. Justify your choices of FEC, ARQ, windowing, buffering, and timeout policy.
3. A gateway frequently advertises zero receive capacity while the sender continues retransmitting. Analyse possible causes and propose protocol and operational remedies.

Multiple Choice Questions with Answers

Question 1

Which technique is primarily designed to detect burst errors using polynomial division?

A. Single parity

B. Checksum

C. CRC

D. Stop-and-Wait

Correct Answer: C. CRC

Question 2

For a code with minimum Hamming distance 5, what is the guaranteed correction capability?

A. 1 error

B. 2 errors

C. 3 errors

D. 4 errors

Correct Answer: B. 2 errors

Question 3

In a Hamming code, the syndrome is used mainly to identify what?

A. The transmission speed

B. The location of a correctable error

C. The receiver buffer size

D. The checksum word size

Correct Answer: B. The location of a correctable error

Question 4

What does Go-Back-N normally do after losing frame k?

A. Retransmits only the acknowledgement

B. Discards the entire connection

C. Retransmits frame k and subsequent outstanding frames

D. Accepts all later frames as complete

Correct Answer: C. Retransmits frame k and subsequent outstanding frames

Question 5

Which protocol generally buffers out-of-order frames and retransmits only missing frames?

A. Stop-and-Wait

B. Go-Back-N

C. Selective Repeat

D. Parity checking

Correct Answer: C. Selective Repeat

Question 6

What is the primary purpose of a receive window?

A. To encrypt the payload

B. To indicate how much data the receiver can accept

C. To calculate the CRC polynomial

D. To eliminate sequence numbers

Correct Answer: B. To indicate how much data the receiver can accept

Question 7

Using even parity, what parity bit should be appended to 1011001?

A. 0

B. 1

C. Either bit always works

D. No parity bit is needed

Correct Answer: A. 0

Question 8

Why are sequence numbers necessary in ARQ protocols?

A. They increase the electrical signal strength

B. They identify order and help detect duplicates

C. They replace all error detection

D. They guarantee zero congestion

Correct Answer: B. They identify order and help detect duplicates

Question 9

If a frame takes 1 ms to transmit and the RTT is 20 ms, the ideal Stop-and-Wait utilisation under the stated approximation is closest to:

A. 4.8%

B. 20%

C. 50%

D. 95%

Correct Answer: A. 4.8%

Question 10

Why is an ordinary CRC unsuitable as a security authentication mechanism?

A. It cannot detect any errors

B. It is too long for networks

C. An attacker can modify the data and recompute the CRC

D. It requires a public-key certificate

Correct Answer: C. An attacker can modify the data and recompute the CRC