HDLC and Point-to-Point Protocol

Modern data link control protocols provide the logical administrative framework required to reliably move raw binary streams over physical channels. Without these mechanisms, receiver hardware cannot distinguish where one packet ends and another begins, nor can it manage transmission rates to prevent resource starvation.

1. Framing in the Data Link Layer

Before transmission, the data link layer packs bits into independent chunks called frames. This process is analogous to placing physical letters into envelopes to serve as delimiters.

Fixed-Size vs. Variable-Size Framing

Fixed-size framing: The size of the frame is pre-configured and constant across all transmissions (e.g., ATM cells). No boundary delimiters are required; the receiver counts incoming bits to segment frames.
Variable-size framing: Frame boundaries must be explicitly defined using delimiters. This is used in most local and wide area networks. There are two primary techniques used to resolve data transparency: character-oriented (byte-oriented) and bit-oriented framing.

Character-Oriented Framing and Byte Stuffing

In character-oriented protocols, the frame is composed of an integer number of bytes. The start and end of a frame are marked by a dedicated control character called a flag (often denoted as FLAG or 0x7E).

If the actual binary payload contains a byte identical to the control FLAG, the receiver will prematurely conclude that the frame has ended. To prevent this, byte stuffing is used. Whenever a FLAG or an escape character (ESC, often 0x7D) appears in the payload, an extra ESC byte is inserted directly ahead of it.

text

Original Payload:     [ Data ] ---> [ FLAG ] ---> [ Data ]
Stuffed Frame:    FLAG [ Data ] [ ESC ] [ FLAG ] [ Data ] FLAG

When the receiver detects an ESC character, it discards it and processes the subsequent byte as literal data.

Bit-Oriented Framing and Bit Stuffing

Bit-oriented protocols view the frame as a continuous sequence of individual bits. Frame boundaries are delimited by a unique bit pattern, typically 01111110 ( $0\text{x}7\text{E}$ ).

To ensure this pattern does not naturally occur in the user data, bit stuffing is executed at the transmitter. The rule is simple: whenever five consecutive $1$ s are encountered in the payload, a $0$ is automatically inserted immediately after them, regardless of the value of the next bit.

text

Sender Side:
Data to send:         0 1 1 1 1 1 1 0 1 1 0 1 1 1 1 1 0 0
Stuffed bitstream:    0 1 1 1 1 1 0 1 0 1 1 0 1 1 1 1 1 0 0 0
                                  ^                   ^
                               (Stuffed)           (Stuffed)
 
Receiver Side:
Received bitstream:   0 1 1 1 1 1 0 1 0 1 1 0 1 1 1 1 1 0 0 0
Unstuffed data:       0 1 1 1 1 1   1 0 1 1 0 1 1 1 1 1   0 0
                                  ^                   ^
                             (0 discarded)       (0 discarded)

At the receiving node, if five consecutive $1$ s are detected followed by a $0$ , the $0$ bit is discarded. If five consecutive $1$ s are followed by a $1$ and then a $0$ (i.e., 01111110), it is processed as the frame boundary flag.

2. High-Level Data Link Control (HDLC)

High-Level Data Link Control (HDLC) is a bit-oriented, synchronous protocol developed by the ISO to provide reliable node-to-node communication over point-to-point and multipoint links.

Configurations and Transfer Modes

HDLC supports two primary station configurations:

Unbalanced Configuration: Consists of one primary station and one or more secondary stations. The primary station is responsible for link management, issuing commands, and controlling frame flow.
Balanced Configuration: Consists of two peer stations. Both stations can act as primary or secondary, initiating command and response frames independently.

These configurations operate under two fundamental transfer modes:

1. Normal Response Mode (NRM)

Under NRM, the station configuration is unbalanced. A secondary station cannot initiate transmissions on its own; it must wait for a explicit poll command from the primary station.

text

  Primary Station                            Secondary Station
         |                                           |
         |---- Command (Poll: P=1) ----------------->|
         |                                           | (Granted permission)
         |<--- Response (I-Frame: F=1) --------------|

2. Asynchronous Balanced Mode (ABM)

Under ABM, the configuration is balanced. Either peer station can initiate transmission at any time without waiting for permission from the other. This is the dominant mode used on point-to-point physical links.

text

    Node A                                      Node B
      |                                           |
      |---- I-Frame (Initiates Send) ------------>|
      |<--- I-Frame (Simultaneous Send) ----------|

HDLC Frame Format

An HDLC frame contains up to six fields: Flag, Address, Control, Information, Frame Check Sequence (FCS), and a closing Flag.

text

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

Flag: The byte 01111110 ( $0\text{x}7\text{E}$ ) which synchronizes the receiver and identifies the starting and ending boundaries of the frame.
Address: Identifies the secondary station that created or is intended to receive the frame. In balanced configurations, it identifies the target node.
Control: A $1$ or $2$ -byte field containing sequence numbers, acknowledgments, and control flags.
Information (Payload): Contains the network-layer data. This field is absent in certain control frames.
FCS: Frame Check Sequence used for error detection. It contains a $16$ -bit or $32$ -bit Cyclic Redundancy Check (CRC) value. The standard generator polynomial used for -bit CRC is:

$G(x) = x^{16} + x^{12} + x^5 + 1$

3. HDLC Control Fields and Frame Types

The Control field defines the primary function of an HDLC frame. Based on this field, frames are categorized into three types:

text

I-Frame (Information):
+---+---+---+---+---+---+---+---+
| 0 |    N(S)   |P/F|    N(R)   |
+---+---+---+---+---+---+---+---+
 
S-Frame (Supervisory):
+---+---+---+---+---+---+---+---+
| 1 | 0 |   S   |P/F|    N(R)   |
+---+---+---+---+---+---+---+---+
 
U-Frame (Unnumbered):
+---+---+---+---+---+---+---+---+
| 1 | 1 |   M   |P/F|     M     |
+---+---+---+---+---+---+---+---+

1. Information Frames (I-Frames)

I-frames carry user data from the network layer. They also implement flow and error control via piggybacking.

$N(S)$ : The sequence number of the current frame, using modulo- $8$ or modulo- $128$ arithmetic.
$N(R)$ : The acknowledgment number. It represents the sequence number of the next frame the station expects to receive, implying cumulative acknowledgment of all frames up to $N(R) - 1$ .

2. Supervisory Frames (S-Frames)

S-frames handle flow and error control when piggybacking is not possible (e.g., when a node has no outgoing data frames). They do not contain an Information field. The $2$ -bit S field determines the command type:

00 (Receive Ready - RR): Indicates the station is ready to receive and acknowledges frames up to $N(R) - 1$ .
10 (Receive Not Ready - RNR): Acknowledges frames up to $N(R) - 1$ but signals that the receiver is temporarily busy and cannot accept more frames.
01 (Reject - REJ): Sent in Go-Back-N ARQ to request the immediate retransmission of all outstanding frames starting from $N(R)$ .

3. Unnumbered Frames (U-Frames)

U-frames manage the link itself. They do not have sequence numbers ( $N(S)$ or $N(R)$ ) and are used for session initialization, mode selection, and connection teardown. The $5$ modifier bits ( $M$ ) define several control commands and responses:

Connection Establishment and Release Sequence

Establishing and tearing down a connection in HDLC requires a handshake of U-frames:

text

Node A                                                     Node B
  |                                                          |
  |--- SABM (Set Asynchronous Balanced Mode) --------------->|
  |<-- UA (Unnumbered Acknowledgment) -----------------------| (Link Established)
  |                                                          |
  |================= DATA TRANSFER PHASE ====================|
  |                                                          |
  |--- DISC (Disconnect Command) ----------------------------|
  |<-- UA (Unnumbered Acknowledgment) -----------------------| (Link Released)

4. HDLC Flow and Error Control Scenarios

HDLC implements Automatic Repeat Request (ARQ) schemes to guarantee reliable, error-free delivery over noisy physical lines.

Piggybacking without Errors

The following sequence demonstrates error-free communication between Node A and Node B using piggybacking:

text

Node A                                                          Node B
  |                                                               |
  |--- I-frame [N(S)=0, N(R)=0] --------------------------------->| (Recv 0, expect 1)
  |                                                               |
  |--- I-frame [N(S)=1, N(R)=0] --------------------------------->| (Recv 1, expect 2)
  |                                                               |
  |<-- I-frame [N(S)=0, N(R)=2] ----------------------------------| (Ack A's 0 & 1; expect 2)
  |                                                               | (Recv B's 0, expect 1)
  |                                                               |
  |<-- I-frame [N(S)=1, N(R)=2] ----------------------------------| (Recv B's 1, expect 2)
  |                                                               |
  |--- S-frame: RR [N(R)=2] ------------------------------------->| (Ack B's 0 & 1; expect 2)

Recovery from Lost Frames (Go-Back-N Mode)

If a frame is lost or corrupted during transit, HDLC uses S-frames to initiate recovery. This example shows Go-Back-N recovery after a frame is lost:

text

Node A                                                          Node B
  |                                                               |
  |--- I-frame [N(S)=0, N(R)=0] --------------------------------->|
  |                                                               |
  |--- I-frame [N(S)=1, N(R)=0] --XXXX (LOST)                     |
  |                                                               |
  |--- I-frame [N(S)=2, N(R)=0] --------------------------------->| (Out of order; discarded)
  |                                                               |
  |<-- S-frame: REJ [N(R)=1] -------------------------------------| (Requests retransmission from 1)
  |                                                               |
  |--- I-frame [N(S)=1, N(R)=0] --------------------------------->| (Retransmitting 1)
  |                                                               |
  |--- I-frame [N(S)=2, N(R)=0] --------------------------------->| (Retransmitting 2)

5. Point-to-Point Protocol (PPP)

While HDLC is a powerful protocol for point-to-point and multipoint configurations, it is primarily hardware-driven. For software-managed, dial-up, and broadband internet connections, the industry uses the Point-to-Point Protocol (PPP).

PPP is a byte-oriented protocol designed to run over IP networks, serial lines, and physical fiber links. Unlike HDLC, it supports multiple network-layer protocols simultaneously and provides built-in user authentication.

PPP Frame Format

The PPP frame closely mirrors HDLC, but introduces crucial structural differences:

text

+----------+----------+----------+----------+------------------+----------+----------+
|   Flag   | Address  | Control  | Protocol |   Information    |   FCS    |   Flag   |
|  1 byte  |  1 byte  |  1 byte  | 1/2 bytes|  Variable Length | 2/4 bytes|  1 byte  |
|  (0x7E)  |  (0xFF)  |  (0x03)  |          |                  |          |  (0x7E)  |
+----------+----------+----------+----------+------------------+----------+----------+

Flag: $1$ byte containing the value 01111110 ( $0\text{x}7\text{E}$ ).
Address: Set to 11111111 ( $0\text{x}FF$ ), representing the broadcast address. Point-to-point topologies do not require individual node addresses.
Control: Set to the constant value 00000011 ( $0\text{x}03$ ), mimicking HDLC's Unnumbered Information frame format.
Protocol: A or -byte field that identifies the specific protocol encapsulated in the payload (e.g., for IPv4, for LCP, for PAP).

PPP Byte Stuffing Algorithm

Because PPP is character-oriented, it uses byte stuffing with an escape character of 0x7D ( $01111101$ ). The stuffing mechanism operates as follows:

$\text{If } \text{byte} = 0\text{x}7\text{E} \text{ or } 0\text{x}7\text{D} \implies \text{Insert } 0\text{x}7\text{D}, \text{ then transmit } (\text{byte} \oplus 0\text{x}20)$

For example, a payload byte of 0x7E is transmitted as the two-byte sequence 0x7D 0x5E.

PPP Protocol Multiplexing

PPP functions as a container for several internal protocols. Rather than using a single monolithic design, it decouples link configuration from network-layer coordination.

text

       +--------------------------------------------------------+
       |                  Network Layer (IP, IPv6)              |
       +--------------------------------------------------------+
       |   IPCP (IP Control Protocol)   | IPv6CP | ...          | <--- NCPs
       +--------------------------------------------------------+
       |   PAP / CHAP (Authentication Protocols)                |
       +--------------------------------------------------------+
       |   LCP (Link Control Protocol)                          | <--- LCP
       +--------------------------------------------------------+
       |                  Physical Link                         |
       +--------------------------------------------------------+

Link Control Protocol (LCP): Responsible for establishing, configuring, testing, and terminating the physical link. LCP negotiates options such as the maximum receive unit (MRU) and compression choices.
Authentication Protocols:
- PAP (Password Authentication Protocol): A simple, two-way handshake where the user sends their credentials in plain text.
- CHAP (Challenge Handshake Authentication Protocol): A secure, three-way handshake that uses a shared secret and a MD5 hash to prevent credentials from being sent in plain text over the wire.
Network Control Protocols (NCP): A suite of protocols used to configure network-layer settings for each supported network protocol. For IP networks, PPP uses the Internet Protocol Control Protocol (IPCP) to negotiate settings like IP addresses.

6. PPP State Transition Lifecycle

A PPP connection transitions through a well-defined sequence of states as it moves from physical silence to data transfer and back.

text

            +-----------+
            |   DEAD    |  <---------------------------------+
            +-----------+                                    |
                  |                                          |
                  | Physical line detected                   | Link failed /
                  v                                          | termination complete
            +-----------+                                    |
            | ESTABLISH |  <------------+                    |
            +-----------+               | Option negotiation |
                  |                     | failed             |
                  | LCP closed          |                    |
                  v                     |                    |
            +-----------+               |                    |
            | AUTHENT-  | --------------+                    |
            |  ICATE    |                                    |
            +-----------+                                    |
                  |                                          |
                  | Auth succeeded                           |
                  v                                          |
            +-----------+                                    |
            |  NETWORK  |                                    |
            +-----------+                                    |
                  |                                          |
                  | NCP closed                               |
                  v                                          |
            +-----------+                                    |
            | TERMINATE | -----------------------------------+
            +-----------+

Detailed Phase Transitions:

Dead: The physical link is inactive. Once a carrier signal is detected, the protocol transitions to the Establish phase.
Establish: LCP packets are exchanged to negotiate link configuration options (such as maximum frame sizes and authentication protocols).
Authenticate: If authentication was negotiated during the Establish phase, the connection transitions here. PAP or CHAP packets are exchanged to verify the client's identity. If authentication fails, the link transitions directly to the Terminate phase.
Network: Once authenticated, the corresponding NCPs (such as IPCP) are initialized to configure the network layer (e.g., assigning IP addresses).
Open: With both the link and network layers configured, data transfer begins. User IP packets are encapsulated inside PPP frames and transmitted across the link.
Terminate: When the session ends, LCP disconnect packets are exchanged, closing the logical connection and bringing the physical line back down to the Dead state.

7. Software Implementation of Bit Stuffing

This Python script implements the bit-stuffing and un-stuffing algorithms used by bit-oriented protocols like HDLC to ensure data transparency.

python

def hdlc_bit_stuff(data_bits: str) -> str:
    """
    Stuffs a zero bit after every sequence of five consecutive ones.
    """
    consecutive_ones = 0
    stuffed_bits = []
    
    for bit in data_bits:
        if bit == '1':
            consecutive_ones += 1
            stuffed_bits.append(bit)
            if consecutive_ones == 5:
                stuffed_bits.append('0')  # Stuff the 0 bit
                consecutive_ones = 0
        elif bit == '0':
            consecutive_ones = 0
            stuffed_bits.append(bit)
        else:
            raise ValueError

Summary

Framing is a fundamental responsibility of the data link layer. Character-oriented systems use byte stuffing to escape control characters in the payload, while bit-oriented systems use bit stuffing to prevent user data from being mistaken for frame flags.
HDLC is a bit-oriented protocol that supports both balanced and unbalanced configurations. It implements flow and error control using Information, Supervisory, and Unnumbered frames.
HDLC Frame Types are determined by the starting bits of the control field: I-frames (starting with 0), S-frames (starting with 10), and U-frames (starting with 11).
PPP is a byte-oriented protocol commonly used for internet access. It uses byte stuffing with 0x7D as its escape character.
PPP Decouples Link Management from Network Setup: It uses the Link Control Protocol (LCP) to manage the physical link, PAP or CHAP for user authentication, and Network Control Protocols (NCPs) like IPCP to negotiate network-layer settings.

Assessed progress

HDLC and Point-to-Point Protocol

HDLC and Point-to-Point Protocol

1. Framing in the Data Link Layer

Fixed-Size vs. Variable-Size Framing

Character-Oriented Framing and Byte Stuffing

Bit-Oriented Framing and Bit Stuffing

2. High-Level Data Link Control (HDLC)

Configurations and Transfer Modes

1. Normal Response Mode (NRM)

2. Asynchronous Balanced Mode (ABM)

HDLC Frame Format

3. HDLC Control Fields and Frame Types

1. Information Frames (I-Frames)

2. Supervisory Frames (S-Frames)

3. Unnumbered Frames (U-Frames)

Connection Establishment and Release Sequence

4. HDLC Flow and Error Control Scenarios

Piggybacking without Errors

Recovery from Lost Frames (Go-Back-N Mode)

5. Point-to-Point Protocol (PPP)

PPP Frame Format

PPP Byte Stuffing Algorithm

PPP Protocol Multiplexing

6. PPP State Transition Lifecycle

Detailed Phase Transitions:

7. Software Implementation of Bit Stuffing

Summary

Key Concepts

Bit Stuffing

Byte Stuffing

Asynchronous Balanced Mode (ABM)

PPP Protocol Suite Multiplexing

Piggybacking

Quick Check

Computer Networks

Computer Networks