Flow and Error Control Protocols

Reliable communication across physical channels requires robust management mechanisms to handle packet boundary identification, transmission rate mismatches, and physical signal degradation. This curriculum content details the theoretical and practical designs of framing, error control, and flow control protocols operating at the data link layer.

1. Framing Mechanics

The data link layer translates a raw stream of bits from the physical layer into distinct, logical units of data called frames. This process is known as framing. To prevent receiver ambiguity, the boundaries of each frame must be clearly delineated.

Character-Oriented (Byte-Oriented) Framing

In character-oriented protocols, data is packaged as a sequence of characters or bytes. Frame boundaries are established using unique control bytes called flags (often FLAG = 0x7E or similar).

If the payload payload contains the flag byte itself, the receiver might prematurely assume the frame has ended. To prevent this, byte stuffing (or character stuffing) is employed:

A special escape character (ESC = 0x1B) is inserted before any accidental flag or escape character present in the user payload.
The receiver detects the ESC byte, discards it, and treats the subsequent byte as raw data (unstuffing).

text

Sender Side:
[Original Data]  ---> FLAG ---> ESC FLAG ESC ESC ---> [Stuffed Data]
                    \              /
                  [ Stuffed Frame: FLAG | ESC FLAG | ESC ESC | FLAG ]
 
Receiver Side:
[Stuffed Frame]  ---> Drops ESC before FLAG/ESC ---> [Original Data]

Bit-Oriented Framing

Modern protocols operate on bit streams, where frames can contain an arbitrary number of bits. A unique bit pattern, typically 01111110 ( $6$ consecutive ones), serves as the start and end flag.

To prevent the payload from accidentally containing this flag sequence, bit stuffing is used:

Transmitter Rule: Whenever the sender encounters five consecutive ones (11111) in the data stream, it automatically inserts (stuffs) a 0 bit immediately after the fifth 1.
Receiver Rule: When the receiver observes five consecutive ones:
- If the next bit is 0, it is recognized as a stuffed bit. The receiver removes (unstuffs) it.
- If the next bit is 1, the receiver checks the following bit:
  - If it is 0, it detects the flag pattern 01111110 (frame boundary).
  - If it is 1, the frame is discarded as corrupted (error state).

text

Input Payload:      0 1 1 1 1 1 1 0 1
                     ^ ^ ^ ^ ^
                  (Five consecutive 1s)
 
Stuffed Bit Stream: 0 1 1 1 1 1 0 1 0 1
                                ^
                           (Stuffed 0)

2. Mathematical Foundations of Error Control

Physical channels introduce noise, thermal interference, and signal attenuation, leading to single-bit or burst errors.

Block Coding

In block coding, we partition the original message into $k$ -bit blocks called datawords. We append $r$ redundant bits to each dataword, producing an $n$ -bit block called a codeword, where:

$n = k + r$

The coding scheme restricts the valid codewords to $2^k$ patterns out of the $2^n$ possible $n$ -bit combinations. If a received codeword is not in the set of $2^k$ valid codewords, an error is declared.

Hamming Distance

The Hamming distance $d(x, y)$ between two binary words $x$ and $y$ of equal length is the number of bit positions in which they differ. It is calculated by finding the Hamming weight (number of ones) of the exclusive-OR (XOR) operation between $x$ and $y$ :

$d(x, y) = \text{weight}(x \oplus y)$

The minimum Hamming distance $d_{min}$ of a coding scheme is the smallest Hamming distance between any pair of valid codewords in the code set $C$ :

$d_{min} = \min \{ d(x, y) \mid x, y \in C, x \neq y \}$

Error Detection Capability

To guarantee the detection of up to $s$ arbitrary bit errors, the minimum Hamming distance must satisfy:

$d_{min} \ge s + 1$

text

Valid Codeword 1 (radius s)
      *-----------------------------> [Boundary of Detection]
                                       If error falls inside, it's detected.
                                       If s+1 errors occur, it may land on
                                       another valid codeword (undetected).

Error Correction Capability

To guarantee the correction of up to $t$ arbitrary bit errors, the minimum Hamming distance must satisfy:

$d_{min} \ge 2t + 1$

This ensures that a corrupted codeword with $t$ errors remains closer to its original codeword than to any other valid codeword in the vector space.

text

        Codeword A                                     Codeword B
          ( O ) <---------- t --------->*<--------- t ---------> ( O )
            \___________________________|___________________________/
                                     d_min >= 2t + 1

3. Cyclic Codes and Checksums

Cyclic Redundancy Check (CRC)

Cyclic codes are a category of linear block codes where a cyclic shift of any valid codeword results in another valid codeword. The most common implementation is the Cyclic Redundancy Check (CRC), which can be easily implemented in hardware using shift registers.

In CRC, binary words are represented as polynomials with coefficients in Galois Field $GF(2)$ (where addition and subtraction are equivalent to bitwise XOR):

$a_{n-1}x^{n-1} + a_{n-2}x^{n-2} + \dots + a_1x + a_0$

For example, the binary sequence 10111 corresponds to the polynomial:

$f(x) = x^4 + x^2 + x^1 + x^0 = x^4 + x^2 + x + 1$

Division Mechanics

Let $d(x)$ be the dataword of degree $k-1$ , and $g(x)$ be the generator polynomial of degree $r$ .

Multiply $d(x)$ by $x^r$ (this appends $r$ zeros to the right of the dataword binary representation).
Divide $x^r \cdot d(x)$ by using modulo-2 polynomial division:

$\frac{x^r \cdot d(x)}{g(x)} = q(x) + \frac{s(x)}{g(x)}$

where $q(x)$ is the quotient and $s(x)$ is the remainder (syndrome) of degree $< r$ . 3. The transmitted codeword $c(x)$ is constructed by subtracting (XORing) the remainder $s(x)$ from the appended dataword:

$c(x) = x^r \cdot d(x) \oplus s(x)$

Since $c(x)$ is perfectly divisible by $g(x)$ , any error-free codeword received will yield a remainder of zero when divided by $g(x)$ .

Properties of the Generator Polynomial $g(x)$

The error detection properties of a cyclic code depend entirely on the choice of $g(x)$ :

Single-Bit Errors: If $g(x)$ has more than one term and the coefficient of $x^0$ is $1$ , all single-bit errors are detected.
Double-Bit Errors: If $g(x)$ does not divide $x^t + 1$ for any up to the frame length, all isolated double-bit errors are detected.

4. Flow Control and Noiseless Channels

Flow control refers to the set of procedures used to restrict the amount of data a sender can transmit before waiting for an acknowledgment (ACK).

The Simplest Protocol

This ideal, hypothetical protocol assumes a completely noiseless channel with infinite receiver buffer capacity. The sender transmits frames continuously without performing any flow or error control.

Stop-and-Wait Protocol

If the receiver has a finite buffer but the channel is still assumed to be noiseless, the Stop-and-Wait protocol prevents receiver buffer overflow.

The sender transmits one frame.
The sender stops and waits for an explicit acknowledgment (ACK) from the receiver.
Once the ACK is received, the sender transmits the next frame.

text

Sender                               Receiver
  |                                     |
  |------ Frame 0 --------------------->|
  |                                     | (Process & Buffer)
  |<----- ACK --------------------------|
  |                                     |
  |------ Frame 1 --------------------->|
  |                                     |

5. Sliding Window ARQ Protocols (Noisy Channels)

Real-world channels are noisy. Automatic Repeat Request (ARQ) adds error control (sequence numbers, timers, and retransmissions) to flow control protocols.

Stop-and-Wait ARQ

To handle lost or corrupted frames and acknowledgments, Stop-and-Wait ARQ introduces:

Sequence Numbers: Applied to frames and ACKs. Since only one frame is outstanding at any time, a 1-bit sequence number ( $0$ or $1$ ) using modulo-2 arithmetic is sufficient.
Timer: The sender starts a timer upon transmission. If no ACK arrives before the timer expires (Timeout), the sender retransmits its cached copy of the frame.
ACK Numbering: An $ACK_n$ always announces the sequence number $n$ of the next expected frame.

text

Sender                               Receiver
  |                                     |
  |------ Frame 0 --------------------->| (Receives 0, expects 1)
  |<----- ACK 1 ------------------------|
  |                                     |
  |------ Frame 1 --------------------->| (Lost in transit!)
  |      X                              |
  |      (Timer Expires)                |
  |------ Frame 1 (Retransmit) -------->| (Receives 1, expects 0)
  |<----- ACK 0 ------------------------|

Go-Back-N ARQ

To improve utilization, Go-Back-N (GBN) allows the sender to transmit multiple frames before waiting for an acknowledgment.

text

Send Window Concept (m-bit sequence number):
      [ S_f   ...   S_n - 1 ]   S_n  ...
        |             |          |
   First Outstanding  |       Next to Send
                      |
              Outstanding Frames
              (Max size = 2^m - 1)

Key Characteristics

Sequence Numbers: Ranging from $0$ to $2^m - 1$ , where $m$ is the bit-width of the sequence field.
Sender Window ( $S_{size}$ ): The maximum number of outstanding, unacknowledged frames the sender can transmit. To prevent sequence ambiguity:

$S_{size} \le 2^m - 1$

Receiver Window ( $R_{size}$ ): Always exactly $1$ . The receiver only accepts frames in strict sequential order.
Cumulative Acknowledgments: An $ACK_n$ acknowledges the receipt of all frames up to , and indicates that the receiver expects frame next.

text

Sender                               Receiver
  |------ Frame 0 --------------------->|
  |------ Frame 1 --------------------->| (Lost!)
  |------ Frame 2 --------------------->| (Discarded: Out-of-order)
  |------ Frame 3 --------------------->| (Discarded: Out-of-order)
  |                                     |
  |      (Timeout Frame 1)              |
  |------ Frame 1 --------------------->| (Now accepted!)
  |------ Frame 2 --------------------->|
  |------ Frame 3 --------------------->|

Selective Repeat ARQ

To avoid the inefficient retransmission of correctly received out-of-order frames in GBN, Selective Repeat (SR) buffers out-of-order frames and retransmits only the specific frames that were lost or corrupted.

Key Characteristics

Sender and Receiver Window Sizes: Both windows are larger than $1$ . To prevent overlapping window ambiguity:

$S_{size} = R_{size} \le 2^{m-1}$

Independent Timers: The sender maintains an individual timer for each transmitted frame.
Negative Acknowledgments (NAK): The receiver can send a $NAK_n$ to explicitly request the immediate retransmission of frame $n$ before a timeout occurs.
Receiver Buffering: The receiver accepts and buffers out-of-order frames that fall within its current receiver window, waiting for the missing frame(s) to arrive before delivering them sequentially to the network layer.

text

Sender                               Receiver (Window Size = 2)
  |------ Frame 0 --------------------->| (Accepted, expected: 1)
  |------ Frame 1 --------------------->| (Lost!)
  |------ Frame 2 --------------------->| (Buffered out-of-order, sends NAK 1)
  |<----- NAK 1 ------------------------|
  |                                     |
  |------ Frame 1 (Retransmit) -------->| (Receives 1, delivers 1 & 2)
  |<----- ACK 3 ------------------------|

6. Performance Analysis & Link Utilization

The efficiency of a data link protocol is measured by its channel utilization ( $\eta$ ), defined as the fraction of time the channel is actively conveying payload data.

Let:

$L$ = Frame size (bits)
$B$ = Channel bandwidth (bps)
$T_p$ = One-way propagation delay (seconds)
$T_{fr}$ = Frame transmission delay (seconds), where:

$T_{fr} = \frac{L}{B}$

Stop-and-Wait Efficiency

In Stop-and-Wait, the total cycle time to send a single frame and receive its ACK (ignoring ACK transmission time and processing delays) is:

$T_{total} = T_{fr} + 2 \cdot T_p$

The utilization $\eta_{SW}$ is:

$\eta_{SW} = \frac{T_{fr}}{T_{fr} + 2 \cdot T_p} = \frac{1}{1 + 2 \cdot a}$

where $a$ is the ratio of propagation delay to transmission delay:

$a = \frac{T_p}{T_{fr}}$

The term $2 \cdot T_p \cdot B$ is the Bandwidth-Delay Product (BDP), representing the number of bits that can fill the transmission link in both directions. If the BDP is high (e.g., in long-distance fiber or satellite links), $a \gg 1$ , making Stop-and-Wait highly inefficient ( $\eta \to 0$ ).

Sliding Window Efficiency

With a sender window size of $W$ , the sender can transmit up to $W$ frames consecutively. If $W \cdot T_{fr} \ge T_{fr} + 2 \cdot T_p$ , the sender can transmit continuously without waiting. The utilization is:

$\eta = \min \left( 1, \frac{W \cdot T_{fr}}{T_{fr} + 2 \cdot T_p} \right) = \min \left( 1, \frac{W}{1 + 2a} \right)$

To achieve $100\%$ theoretical efficiency on an error-free channel, we must choose:

$W \ge 1 + 2a$

HDLC Frame Structure:
[ Flag: 8 bits ] [ Address: 8+ bits ] [ Control: 8/16 bits ] [ Information: Var ] [ FCS: 16/32 bits ] [ Flag: 8 bits ]

Information Frames (I-frames): Used to transport user payload data. They include send sequence numbers $N(S)$ and receive sequence numbers $N(R)$ to support piggybacked acknowledgments.
Supervisory Frames (S-frames): Used for flow and error control when piggybacking is not possible. They include:
- Receive Ready (RR): Positive acknowledgment, ready to receive.
- Receive Not Ready (RNR): Positive acknowledgment, but temporarily busy.
- Reject (REJ): Requests Go-Back-N retransmission starting from $N(R)$ .
- Selective Reject (SREJ): Requests Selective Repeat retransmission of a specific frame.
Unnumbered Frames (U-frames): Used for link initialization, mode setting, and disconnection (e.g., SABM - Set Asynchronous Balanced Mode, - Disconnect, - Unnumbered Acknowledgment).

Point-to-Point Protocol (PPP)

PPP is a widely used, byte-oriented protocol designed to establish direct connections over point-to-point links (such as dial-up or fiber broadband lines).

text

PPP Frame Structure:
[ Flag: 0x7E ] [ Address: 0xFF ] [ Control: 0x03 ] [ Protocol: 16 bits ] [ Payload: Var ] [ FCS: 16/32 bits ] [ Flag: 0x7E ]

Protocol Components

Framing: Uses byte stuffing with the escape byte 0x7D.
Link Control Protocol (LCP): Establishes, configures, and tests the physical link. It negotiates operational parameters like maximum frame size, compression options, and authentication protocols.
Authentication Protocols:
- PAP (Password Authentication Protocol): A simple two-way handshake where credentials are sent in cleartext.
- CHAP (Challenge Handshake Authentication Protocol): A secure three-way handshake that uses cryptography to prevent credential theft.
Network Control Protocols (NCP): A family of protocols used to establish and configure network-layer connections (e.g., IPCP for configuring IP addresses).

Summary

Framing partitions raw physical bits into structured frames using either byte stuffing (inserting escape characters) or bit stuffing (inserting zeros after five consecutive ones).
Error detection relies on block coding properties. To detect $s$ errors, the minimum Hamming distance $d_{min} \ge s+1$ ; to correct $t$ errors, $d_{min} \ge 2t+1$ .

Assessed progress

Flow and Error Control Protocols

Key Concepts

Framing

Flow Control

Error Control

Go-Back-N ARQ

Selective Repeat ARQ

Quick Check

Computer Networks

Computer Networks