Data Link Control and Framing

The Data Link Layer transforms raw physical-layer bitstreams into structured, reliable node-to-node communication links. This module explores framing mechanics, flow control, automatic repeat request (ARQ) strategies, and core standard implementations like HDLC and PPP.

1. Framing Techniques

To coordinate transmission, the data link layer must package raw bits into distinct, manageable data units called frames. This process, known as framing, enables the receiver to distinguish one packet of information from another, acting much like an envelope separating letters in a postal system.

text

Physical Layer:  ...011111101010010101111110... (Raw Bit Stream)
                 |                          |
Data Link Layer: [ FLAG ][  Header  ][ Payload ][ Trailer ][ FLAG ] (Discrete Frame)

There are two primary approaches to framing:

Fixed-Size Framing: Frames are of a uniform size defined by the protocol (e.g., ATM cells). This simplifies the receiver design as boundaries are predictable, but wastes bandwidth if payloads are small.
Variable-Size Framing: Frames have varying lengths. This requires dynamic delimiting techniques so the receiver knows where one frame ends and the next begins.

1.1 Character-Oriented (Byte-Oriented) Framing

In character-oriented framing, data to be sent is treated as a sequence of characters (typically 8-bit bytes). The frame begins with a special 1-byte flag and ends with the same flag.

If the payload itself contains a byte with the exact binary pattern of the flag (e.g., 0x7E), the receiver will mistakenly assume the frame has ended. To prevent this, byte stuffing (or character stuffing) is performed:

An escape character (ESC) (often 01111101 or 0x7D) is inserted immediately before any flag or escape character present in the user payload.
The receiver, upon seeing an ESC byte, discards the ESC byte and treats the subsequent byte as raw data rather than a control delimiter.

text

Original Payload:     [ DATA ] [ FLAG ] [ DATA ] [ ESC ] [ DATA ]
                                  |                 |
Stuffed Payload:      [ DATA ] [ ESC ][ FLAG ] [ DATA ] [ ESC ][ ESC ] [ DATA ]
                                  |                 |
Receiver Unstuffs:    [ DATA ] [ FLAG ] [ DATA ] [ ESC ] [ DATA ]

1.2 Bit-Oriented Framing

In bit-oriented framing, the frame payload is treated as a continuous stream of individual bits, independent of character boundaries. A unique bit sequence—typically the 8-bit flag 01111110 (hex 0x7E)—is used as the start and end delimiter.

To ensure this pattern does not naturally occur inside the payload, bit stuffing is used:

Sender Rule: The sender monitors the bit stream. Whenever it detects five consecutive 1s following a 0, it automatically inserts (stuffs) a 0 immediately after the fifth 1.
Receiver Rule: The receiver monitors the incoming bit stream. If it sees five consecutive 1s followed by a 0, it deletes (unstuffs) the 0. If it sees five consecutive 1s followed by a 1 and then a 0, it recognizes it as the frame flag sequence 01111110.

text

Input Bits:       0 1 1 1 1 1 1 0 0 1 0 1
                      ^ (Five consecutive 1s detected)
Stuffed Bits:     0 1 1 1 1 1 0 1 0 0 1 0 1  (Stuffed '0' inserted)
                              ^
Unstuffed Bits:   0 1 1 1 1 1 1 0 0 1 0 1    (Restored to original)

2. Flow and Error Control Foundations

The core algorithmic tasks of the data link layer are collectively known as Data Link Control (DLC).

Flow Control: A set of procedures designed to limit the amount of data a sender can transmit before waiting for an acknowledgment (ACK). This prevents a fast sender from overwhelming a slow receiver's processing and buffering capacity.
Error Control: Mechanisms that detect and correct transmission errors (lost or corrupted frames). In the data link layer, error control is based on Automatic Repeat Request (ARQ), which relies on the retransmission of data.

2.1 Performance Analysis: Link Utilization and the Bandwidth-Delay Product

To understand the necessity of advanced DLC protocols, we must analyze the theoretical performance of the physical link. Let:

$R$ = Bandwidth of the channel ( $\text{bps}$ )
$d$ = One-way propagation delay of the link ( $\text{seconds}$ )
$T_p$ = Propagation time ( $d$ )

The round-trip capacity of the link is equivalent to the Bandwidth-Delay Product (BDP). The maximum utilization percentage ( $U$ ) of a link represents the fraction of time the link is actively carrying data frames:

$U = \frac{T_{fr}}{T_{fr} + 2 T_p}$

Example 2.1

Consider a $1\text{ Mbps}$ point-to-point satellite link where the round-trip propagation time ( $2 T_p$ ) is $20\text{ ms}$ . If the frame size is $1000\text{ bits}$ , let us calculate the link utilization under a basic Stop-and-Wait model.

Calculate the transmission delay ( $T_{fr}$ ): $T_{fr} = \frac{1000\text{ bits}}{1,000,000\text{ bps}} = 1\text{ ms}$

During the time it takes for a single frame to travel to the destination and its acknowledgment to return, the sender could have transmitted $20,000\text{ bits}$ ( $\text{BDP} = 10^6\text{ bps} \times 0.02\text{ s}$ ). Sending only $1000\text{ bits}$ wastes over $95\%$ of the link's capacity.

To solve this inefficiency, sliding window protocols are employed to pipeline multiple frames, keeping the communication channel filled.

3. Noiseless Channel Protocols

To analyze flow control algorithms in their purest form, we first assume an ideal, noiseless channel where no frames are lost, duplicated, or corrupted.

3.1 The Simplest Protocol

The Simplest Protocol has no flow or error control. The sender site continuously retrieves packets from its network layer, encapsulates them, and pushes them onto the physical line. The receiver site is assumed to have infinite buffer space and processing speed, instantly consuming incoming frames.

text

Sender Site                          Receiver Site
-----------                          -------------
Get packet from network layer        Receive frame from physical layer
Encapsulate into frame               Extract packet
Send frame                           Deliver packet to network layer

3.2 Stop-and-Wait Protocol

If the receiver's buffer space is finite, the sender must slow down. The Stop-and-Wait Protocol introduces basic flow control: the sender transmits one frame, stops, and waits for an explicit acknowledgment (ACK) from the receiver before sending the next frame.

text

Sender Site                          Receiver Site
-----------                          -------------
[Send Frame 0] ------------------->  [Receive Frame 0]
[Wait for ACK]                       [Process & Buffer Frame 0]
               <-------------------  [Send ACK]
[Receive ACK]
[Send Frame 1] ------------------->  [Receive Frame 1]

4. Noisy Channel Protocols (ARQ)

Real-world physical channels suffer from noise, attenuation, and interference. We now introduce three classic Automatic Repeat Request (ARQ) protocols to handle noisy links.

4.1 Stop-and-Wait ARQ

In Stop-and-Wait ARQ, the sender keeps a copy of the transmitted frame in memory and starts a retransmission timer.

Sequence Numbers: To resolve the ambiguity of lost or delayed frames/ACKs, frames and ACKs are numbered. Since only one frame can be outstanding at any time, sequence numbers are calculated using modulo-2 arithmetic (values alternate between $0$ and $1$ ).
ACK Numbers: The acknowledgment number always announces the sequence number of the next frame expected by the receiver.

Retransmission Scenarios

text

Scenario A: Frame is Lost
Sender (Seq 0) --------X (Lost in transit)
[Timer Expires]
Sender (Seq 0) --------------------------> Receiver (Expects 0)
                                           Receiver Sends ACK 1
               <-------------------------- (Expects Seq 1 next)
 
Scenario B: ACK is Lost
Sender (Seq 0) --------------------------> Receiver (Expects 0)
                                           Receiver Sends ACK 1
               X<------------------------- (ACK Lost)
[Timer Expires]
Sender (Seq 0) --------------------------> Receiver (Expects 1, gets duplicate 0)
                                           Receiver discards duplicate, resends ACK 1

4.2 Go-Back-N (GBN) ARQ

To improve link utilization, Go-Back-N ARQ allows the sender to transmit multiple frames before waiting for an ACK. This is achieved via a sliding window.

text

              |<----------- Send Window (Size = Ws) ----------->|
+-------------+-------------------------------------------------+-------------+
| Sent & ACKed|  Sf (Sent, Outstanding)  |  Sn (Ready to Send)  | Not Allowed |
+-------------+-------------------------------------------------+-------------+
              ^                          ^                      ^
              First Outstanding Frame    Next Frame to Send     End of Window

Send Window Size ( $W_s$ ): Let $m$ be the size of the sequence number field in bits. The maximum send window size is: $W_s = 2^m - 1$

Why $W_s$ must be less than $2^m$ in Go-Back-N

Consider a $2$ -bit sequence space ( $m=2$ ), giving $2^2 = 4$ sequence numbers: $\{0, 1, 2, 3\}$ .

Suppose we set $W_s = 2^2 = 4$ (violating the rule $W_s \le 2^m - 1$ ):

The sender transmits frames $0, 1, 2,$ and $3$ .
The receiver receives all four frames, slides its receive window, and expects frame $0$ again. The receiver sends ACK 0 (acknowledging all frames and expecting $0$ next).
The ACK 0 is lost in transit.
The sender's timer expires. It retransmits the entire window: frames $0, 1, 2, 3$ .

By restricting $W_s = 2^m - 1 = 3$ , at least one sequence number remains vacant, eliminating sequence overlap ambiguity.

4.3 Selective Repeat (SR) ARQ

While Go-Back-N uses bandwidth efficiently under low-error conditions, a single packet loss causes the retransmission of the entire window ("going back N"). Selective Repeat ARQ optimizes this by retransmitting only the specific lost or corrupted frame.

text

Sender Window (Ws):                        Receiver Window (Wr):
+---+---+---+---+                          +---+---+---+---+
| 0 | 1 | 2 | 3 |  (Ws = 4)                | 0 | 1 | 2 | 3 |  (Wr = 4)
+---+---+---+---+                          +---+---+---+---+
      ^                                          ^
   Lost Frame                                 Buffer Out-of-Order

Window Symmetry: To guarantee correct operation, the send and receive windows must be equal in size, and their maximum capacity is restricted to: $W_s = W_r = 2^{m-1}$
Negative Acknowledgments (NAK): The receiver sends a NAK frame when it detects a gap in the received sequence numbers. This triggers the sender to immediately retransmit the missing frame without waiting for its timer to expire.

5. High-Level Data Link Control (HDLC)

High-Level Data Link Control (HDLC) is a highly structured, bit-oriented protocol standardized by the ISO. It operates over both point-to-point and multipoint communication configurations.

5.1 Transfer Modes

HDLC supports two primary link configurations:

Normal Response Mode (NRM): An asymmetric configuration containing one Primary Station and one or more Secondary Stations. Secondary stations can only transmit in response to an explicit poll command from the primary station.
Asynchronous Balanced Mode (ABM): A symmetric configuration where each station acts as a "Combined Station". Both nodes can initiate transmissions on the point-to-point link without waiting for permission.

text

Normal Response Mode (NRM)            Asynchronous Balanced Mode (ABM)
+------------+                        +------------+      +------------+
|  Primary   |                        |  Combined  |      |  Combined  |
+------------+                        |  Station A |<====>|  Station B |
   |      ^                           +------------+      +------------+
   v      |
+------------+
| Secondary  |
+------------+

5.2 HDLC Frame Structure

HDLC frames are bit-oriented and framed using the standard flag 01111110.

text

+----------+-----------+-----------+-------------+----------+----------+
|   Flag   |  Address  |  Control  | Information |   FCS    |   Flag   |
|  8 bits  | 8/16 bits | 8/16 bits |  Variable   | 16/32 bit|  8 bits  |
+----------+-----------+-----------+-------------+----------+----------+

Flag: 01111110 delimits frame boundaries.
Address: Contains the address of the secondary station. If sent by the primary, it represents the destination. If sent by the secondary, it represents the source.
Control: A 1- or 2-byte field defining the frame type and sequencing/flow parameters.
Information: Contains the user data payload (only present in specific frame types).
Frame Check Sequence (FCS): A 16- or 32-bit CRC code used for error detection.

5.3 Frame Types and the Control Field

HDLC classifies frames into three distinct types based on the structure of their control fields:

text

                  Control Field Bit Formats
                 +---+---+---+---+---+---+---+---+
I-Frame (Info)   | 0 |    N(S)   |P/F|    N(R)   |
                 +---+---+---+---+---+---+---+---+
S-Frame (Super)  | 1 | 0 |  Type |P/F|    N(R)   |
                 +---+---+---+---+---+---+---+---+
U-Frame (Unnum)  | 1 | 1 |  Type |P/F|   Type    |
                 +---+---+---+---+---+---+---+---+

Information Frames (I-Frames): Used to transport user payload data and control information.
- N(S): Sequence number of the current frame.
- N(R): Piggybacked acknowledgment number, declaring the sequence number of the next frame expected.
- P/F: Poll/Final bit. When set to 1 by a primary, it polls the secondary; when set to 1 by a secondary, it indicates the final frame in response.
Supervisory Frames (S-Frames): Used to carry flow and error control commands when active user data transmission (and thus piggybacking) is not occurring.
- Receive Ready (RR): Code 00. Acknowledges frames up to $N(R) - 1$ and indicates readiness to receive.
- Receive Not Ready (RNR): Code 10. Acknowledges frames but halts further transmission from the sender due to temporary buffer congestion.
- Reject (REJ): Code 01. Negative acknowledgment used in Go-Back-N to request immediate retransmission starting from .

6. Point-to-Point Protocol (PPP)

While HDLC is a powerful bit-oriented protocol, the Point-to-Point Protocol (PPP) is the standard, byte-oriented protocol used to encapsulate IP datagrams over physical point-to-point links (such as dial-up connections, DSL, and fiber links).

6.1 PPP Frame Format

The PPP frame is modeled closely on HDLC, but operates on character-aligned byte boundaries and incorporates byte stuffing using the escape byte 01111101 (0x7D).

text

+--------+--------+--------+----------+----------+---------+--------+
|  Flag  |Address |Control | Protocol | Payload  |   FCS   |  Flag  |
|  0x7E  |  0xFF  |  0x03  | 1-2 bytes| Variable | 2-4 byte|  0x7E  |
+--------+--------+--------+----------+----------+---------+--------+

Address: Set to the broadcast address 11111111 (0xFF), as point-to-point links do not require individual node addressing.
Control: Set to the fixed value 00000011 (0x03), indicating unnumbered information.
Protocol: Declares what network-layer or control-layer packet is encapsulated inside the payload field (e.g., 0x0021 for Internet Protocol version 4, or 0xC021 for Link Control Protocol).

6.2 Multiplexing in PPP

PPP provides a highly flexible multi-protocol architecture using sub-protocols to manage link parameters:

text

               +--------------------------------------+
               |          IP / IPv6 / IPX             |  (Network Layer)
               +--------------------------------------+
               |    IPCP  /  IPV6CP  /  IPXCP (NCPs)   |  (Network Control)
               +-------------------+------------------+
               |    PAP / CHAP     |   LCP Packets    |  (Auth & Link Control)
               +-------------------+------------------+
               |             PPP Frame                |  (Data Link Layer)
               +--------------------------------------+

Link Control Protocol (LCP): Responsible for establishing, configuring, testing, and terminating the data link connection. LCP negotiates optional parameters such as maximum receive unit (MRU) sizes and compression options.
Authentication Protocols:
- Password Authentication Protocol (PAP): A simple two-way handshake where the client sends user credentials in plain text.
- Challenge Handshake Authentication Protocol (CHAP): A secure three-way handshake using a shared secret and MD5 hashing, preventing credential theft over the wire.
Network Control Protocols (NCP): A family of protocols used to configure network-layer settings for specific protocols. The most common is the Internet Protocol Control Protocol (IPCP), which dynamically assigns and configures IP addresses for the client node.

6.3 Transition Phases of a PPP Link

A PPP link transitions through distinct phases from physical initialization to complete closure:

text

   +--------+      Link      +-----------+
   |  DEAD  |--------------->| ESTABLISH | (LCP Negotiation)
   +--------+                +-----------+
       ^                           |
       |                           v
       |  Auth Fail          +-----------+
       +---------------------| AUTHENTY  | (PAP / CHAP)
       |                     +-----------+
       |                           | Auth Success
       |                           v
       |  NCP Fail           +-----------+
       +---------------------|  NETWORK  | (NCP IPCP Setup)
       |                     +-----------+
       |                           | Net Success
       |                           v
       |                     +-----------+
       |                     |   OPEN    | (Data Transfer)
       |                     +-----------+
       |                           |
       |  Terminate                |
       +---------------------------+

7. Error Detection and Coding Principles

To make ARQ systems work, errors must first be detected. In this section, we cover the underlying mathematics of block coding, parity checks, and cyclic redundancy checks.

7.1 Block Coding

In block coding, we divide our message into blocks of $k$ bits, called datawords. We add $r$ redundant bits to each block to make the length $n = k + r$ . The resulting $n$ -bit blocks are called codewords.

text

                  +-------------------------+
Dataword (k bits) |     Encoder Block       |
                  +------------+------------+
                               |
                               v
Codeword (n bits) | Data (k)   | Redundancy (r) |

Hamming Distance

The Hamming distance $d(x, y)$ between two binary words of equal length is the number of differences between their corresponding bits. It can be found by performing an Exclusive-OR (XOR) operation on the two words and counting the number of $1$ s in the result.

$\text{If } x = 10101, y = 11110 \implies x \oplus y = 01011 \implies d(x, y) = 3$

The minimum Hamming distance ( $d_{\min}$ ) of a coding scheme is the smallest Hamming distance between all possible pairs of valid codewords in the codebook.

Detection and Correction Limits

To guarantee the detection of up to $s$ errors: $d_{\min} \ge s + 1$
To guarantee the correction of up to $t$ errors: $d_{\min} \ge 2t + 1$

Example 7.1

A coding scheme has a minimum Hamming distance $d_{\min} = 5$ . Let us find its error detection and correction capabilities.

For detection: $s = d_{\min} - 1 = 5 - 1 = 4$ errors.
For correction: $2t + 1 \le 5 \implies 2t \le 4 \implies t = 2$ errors.

7.2 Cyclic Redundancy Check (CRC)

Cyclic codes are special linear block codes where cyclically shifting (rotating) any valid codeword results in another valid codeword. The most widely used cyclic code is the Cyclic Redundancy Check (CRC).

A CRC system represents binary words as polynomials with coefficients in $\{0, 1\}$ . For example, the binary word $10011$ is written as: $1x^4 + 0x^3 + 0x^2 + 1x^1 + 1x^0 = x^4 + x + 1$

The divisor in a cyclic code is called the generator polynomial, denoted as $g(x)$ .

Hardware Implementation of CRC Division

CRC computation is implemented in hardware using linear feedback shift registers (LFSR) and XOR gates. This allows the incoming bitstream to be processed bit-by-bit in real-time, requiring minimal silicon area.

text

Incoming Bits ------> (XOR) ------> [Reg 2] ------> [Reg 1] ------> [Reg 0]
                       ^                             ^
                       |_____________________________| (Feedback taps based on g(x))

Error Analysis of CRC

A CRC code is highly robust and catches a wide variety of transmission errors:

Single-bit errors: If $g(x)$ has at least two terms 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 between and , all isolated double-bit errors are detected.

Standard generator polynomials like CRC-16 ( $x^{16} + x^{15} + x^2 + 1$ ) and CRC-32 ( $x^{32} + x^{26} + x^{23} + x^{22} + x^{16} + x^{12} + x^{}$ ) are universally used in Ethernet, Wi-Fi, and HDLC due to these robust mathematical guarantees.

8. Summary

Framing establishes frame boundaries using byte stuffing (with escape characters) or bit stuffing (injecting a 0 after five consecutive 1s).
Flow control prevents the sender from overwhelming the receiver, while error control employs Automatic Repeat Request (ARQ) systems to ensure reliable deliveries.
Stop-and-Wait ARQ uses a sequence number space of $2$ (modulo-2) to handle single outstanding frames.
Go-Back-N (GBN) ARQ uses a send window size of $W_s = 2^m - 1$ and a receive window of . It relies on cumulative ACKs, but forces the retransmission of all outstanding frames if one is lost.

Assessed progress

Data Link Control and Framing

Key Concepts

Framing

Flow and Error Control

Go-Back-N ARQ

Selective Repeat ARQ

HDLC and PPP

Quick Check

Computer Networks

Computer Networks