Framing Byte Stuffing - Learning Module

Loading content...

0/240

PPP Example: Complete Real-World Implementation

Putting It All Together with PPP

Throughout this module, we've studied the individual components of byte-oriented framing: flag bytes for delimitation, escape sequences for transparency, byte stuffing as the complete algorithm, and the theoretical foundations that make it all work. Now it's time to see everything in action.

The Point-to-Point Protocol (PPP) is the definitive example of byte stuffing in practice. Defined in RFC 1661 (the protocol) and RFC 1662 (the framing), PPP has been the workhorse of serial data communication for decades. It's used in:

Dial-up modems (the original use case)
DSL connections (PPPoE - PPP over Ethernet)
Serial console connections (network equipment)
Cellular data (PPP over serial)
VPN tunnels (L2TP uses PPP frames)

In this page, we'll trace a real IP packet from application data, through PPP framing, transmission, reception, and back to the receiving application—examining every byte transformation along the way.

What You Will Master

By the end of this page, you will understand the complete PPP frame format and each field's purpose, be able to trace an IP packet through the full PPP transmit and receive path, see exactly how byte stuffing operates on real frame data, understand LCP negotiation and how it affects framing, and analyze real PPP frames from network captures.

PPP Protocol Overview

Before diving into the framing example, let's understand PPP's architecture and how framing fits into the bigger picture.

PPP Protocol Stack:

┌─────────────────────────────────────────────┐
│           Network Layer (IP, IPX)            │
├─────────────────────────────────────────────┤
│         Network Control Protocols            │
│        (IPCP, IPXCP - per protocol)         │
├─────────────────────────────────────────────┤
│       Link Control Protocol (LCP)            │
│    (Link setup, negotiation, teardown)       │
├─────────────────────────────────────────────┤
│         PPP Framing (RFC 1662)               │
│     (The subject of this module!)            │
├─────────────────────────────────────────────┤
│         Physical Layer (Serial)              │
│    (RS-232, Modem, Virtual serial)           │
└─────────────────────────────────────────────┘

PPP Session Lifecycle:

Physical connection established (modem connects, cable attached)
LCP negotiation (agree on MTU, ACCM, authentication, etc.)
Authentication (optional: PAP, CHAP)
NCP negotiation (e.g., IPCP assigns IP addresses)
Data transfer (IP packets flow in PPP frames)
Termination (LCP close, physical disconnection)

The PPP Frame Format:

Every PPP frame follows this structure (from RFC 1662):

+----------+----------+-----------+----------+-------------+----------+----------+
|  Flag    | Address  |  Control  | Protocol |   Payload   |   FCS    |  Flag    |
| (1 byte) | (1 byte) |  (1 byte) | (2 bytes)|  (variable) | (2 bytes)| (1 byte) |
|   0x7E   |   0xFF   |   0x03    |          |             |          |   0x7E   |
+----------+----------+-----------+----------+-------------+----------+----------+

Field Descriptions:

PPP Frame Fields
Field	Size	Value	Purpose
Flag	1 byte	0x7E	Frame delimiter; marks start and end
Address	1 byte	0xFF	Broadcast address (PPP is point-to-point, so always broadcast)
Control	1 byte	0x03	Unnumbered Information (UI) frame; no sequence numbers
Protocol	2 bytes	Variable	Identifies payload type (0x0021=IP, 0xC021=LCP, etc.)
Payload	0-1500 bytes	Variable	Upper layer data (IP packet, LCP message, etc.)
FCS	2 bytes	CRC-16	Frame Check Sequence for error detection

Field Compression

PPP can negotiate compression of the Address/Control fields (ACFC) and single-byte Protocol field (PFC) during LCP. With full compression, a frame might omit the Address and Control bytes entirely, and use a one-byte Protocol field for values ≤ 0x00FF. This reduces overhead for each frame.

The Complete Transmit Path

Let's trace an IP packet through the complete PPP transmission process, examining every byte transformation.

Scenario:

An application sends a small IP packet (an ICMP echo request - "ping") over a PPP link.

Step 1: IP Packet from Network Layer

The network layer presents this IP packet to PPP for transmission:

IP Packet (28 bytes):
45 00 00 1C    ; IP header: version, IHL, TOS, Total Length=28
00 01 00 00    ; Identification, Flags, Fragment Offset
40 01 B9 C4    ; TTL=64, Protocol=ICMP(1), Header Checksum
0A 00 00 01    ; Source IP: 10.0.0.1
0A 00 00 02    ; Destination IP: 10.0.0.2
08 00 F7 FF    ; ICMP: Type=8 (Echo), Code=0, Checksum
00 01 00 01    ; ICMP: Identifier=1, Sequence=1

Note: This IP packet contains 0x00 bytes (part of ACCM if enabled) but no 0x7E or 0x7D bytes.

Step 2: PPP Protocol Identification

PPP adds the protocol field to identify this as an IP packet:

Protocol: 0x0021 (Internet Protocol)

Step 3: Prepend Address and Control

Address: 0xFF (All-Stations Broadcast)
Control: 0x03 (Unnumbered Information)

Step 4: Construct Frame Content (Before FCS)

Frame content (32 bytes):
 FF 03          ; Address, Control
 00 21          ; Protocol (IP)
 45 00 00 1C    ; IP packet starts here
 00 01 00 00
 40 01 B9 C4
 0A 00 00 01
 0A 00 00 02
 08 00 F7 FF
 00 01 00 01

Step 5: Calculate FCS (CRC-16-CCITT)

The FCS is calculated over the Address, Control, Protocol, and Payload fields:

# FCS calculation (simplified)
fcs = crc16_ccitt(bytes.fromhex(
    'FF 03 00 21 45 00 00 1C 00 01 00 00 40 01 B9 C4 '
    '0A 00 00 01 0A 00 00 02 08 00 F7 FF 00 01 00 01'
))
# Result: FCS = 0x3B26 (hypothetical)

FCS is appended in little-endian order: 0x26 0x3B

Step 6: Complete Frame (Before Stuffing)

Unstuffed frame (34 bytes, excluding flags):
FF 03 00 21 45 00 00 1C 00 01 00 00 40 01 B9 C4
0A 00 00 01 0A 00 00 02 08 00 F7 FF 00 01 00 01
26 3B

Step 7: Byte Stuffing

Now we apply byte stuffing. This example uses minimal ACCM (only escape 0x7E and 0x7D):

Scanning the 34 bytes:

0xFF: Not reserved → pass through
0x03: Not reserved (minimal ACCM) → pass through
0x00: Not reserved (minimal ACCM) → pass through
... (no 0x7E or 0x7D in this frame)
All bytes pass through unchanged!

Stuffed frame (34 bytes, same as unstuffed):
FF 03 00 21 45 00 00 1C 00 01 00 00 40 01 B9 C4
0A 00 00 01 0A 00 00 02 08 00 F7 FF 00 01 00 01
26 3B

Step 8: Add Flags

Complete transmitted frame (36 bytes):
7E FF 03 00 21 45 00 00 1C 00 01 00 00 40 01 B9 C4
   0A 00 00 01 0A 00 00 02 08 00 F7 FF 00 01 00 01
   26 3B 7E

Minimal Overhead in This Case

This frame required no byte stuffing because the IP packet contained no reserved bytes. With minimal ACCM, most IP traffic has zero stuffing overhead. The only fixed overhead is the 2 flag bytes + 4 header bytes + 2 FCS bytes = 8 bytes total protocol overhead.

Example with Stuffing Required

Let's examine a more interesting case where byte stuffing is actually required. This happens when the payload contains reserved byte values.

Scenario:

A PPP frame carrying an LCP Configure-Request packet. LCP packets use protocol 0xC021 and often contain structured option data that might include reserved bytes.

LCP Packet:

LCP Configure-Request (with ACCM option):
Code:        0x01 (Configure-Request)
Identifier:  0x01
Length:      0x000A (10 bytes)
Options:
  Option Type: 0x02 (ACCM)
  Option Length: 0x06
  ACCM Value: 0x00 0x00 0x7E 0x00  ← Contains FLAG byte!

This LCP packet requests an ACCM that would allow literal 0x7E in data—but first, we must transmit this request, and the ACCM value itself contains 0x7E!

Frame Construction:

Unstuffed frame content:
FF 03           ; Address, Control
C0 21           ; Protocol (LCP)
01 01 00 0A     ; LCP: Code=1, ID=1, Length=10
02 06           ; Option: ACCM, length=6
00 00 7E 00     ; ACCM value (contains 0x7E!)
[FCS bytes]     ; Calculated CRC

Byte Stuffing Process:

Processing each byte:
FF → FF          (not reserved)
03 → 03          (not reserved)
C0 → C0          (not reserved)
21 → 21          (not reserved)
01 → 01          (not reserved)
01 → 01          (not reserved)
00 → 00          (not reserved with minimal ACCM)
0A → 0A          (not reserved)
02 → 02          (not reserved)
06 → 06          (not reserved)
00 → 00          (not reserved)
00 → 00          (not reserved)
7E → 7D 5E       ← ESCAPE REQUIRED! (Flag byte in data)
00 → 00          (not reserved)
[FCS byte 1] → possibly escaped
[FCS byte 2] → possibly escaped

Stuffed Frame:

The single 0x7E in the ACCM value becomes 0x7D 0x5E, adding one byte:

Stuffed frame content (one byte longer):
FF 03 C0 21 01 01 00 0A 02 06 00 00 7D 5E 00 [FCS]
                                    ↑↑↑↑
                               Escape sequence!

Complete Transmitted Frame:

7E FF 03 C0 21 01 01 00 0A 02 06 00 00 7D 5E 00 [stuffed FCS] 7E
↑                                      ↑↑↑↑                   ↑
Start flag                      Escaped 0x7E               End flag

Why This Works:

The receiver processes this frame:

Sees opening flag 0x7E → begin receiving frame
Receives FF 03 C0 21 01 01 00 0A 02 06 00 00 → accumulates normally
Receives 0x7D → enters escape state
Receives 0x5E → XOR 0x20 = 0x7E, outputs 0x7E, returns to normal state
Receives 00 → accumulates normally
Processes FCS bytes (with unstuffing if needed)
Sees closing flag 0x7E → frame complete
Verifies FCS → delivers LCP packet with ACCM value 0x0000007E000

The Crucial Point:

The 0x7E that appears between the flags as part of the escape sequence (0x7D 0x5E) is never mistaken for a frame boundary because:

It appears as 0x5E, not 0x7E
The invariant is maintained: no literal 0x7E appears in stuffed content

FCS Must Also Be Stuffed

The FCS bytes are computed on the unstuffed data, but the FCS itself may contain 0x7E or 0x7D and must be escaped when transmitted. This is a common implementation bug: forgetting to stuff the FCS bytes. Always apply stuffing to the entire frame content, including the FCS.

The Complete Receive Path

Now let's trace the receive path in detail, showing how the receiver reconstructs the original data from the transmitted frame.

Received Byte Stream:

The receiver sees this stream of bytes from the serial port:

7E FF 03 00 21 45 00 00 1C 00 01 00 00 40 01 B9 C4
   0A 00 00 01 0A 00 00 02 08 00 F7 FF 00 01 00 01
   26 3B 7E

State Machine Processing:

Let's trace through the receiver state machine byte-by-byte:

State: HUNT (initial)

Byte 0x7E received:
  → Flag detected!
  → Clear buffer
  → State: NORMAL

Byte 0xFF received:
  → Not flag, not escape
  → Append to buffer: [FF]
  → State: NORMAL

Byte 0x03 received:
  → Append to buffer: [FF, 03]
  
Byte 0x00 received:
  → Append to buffer: [FF, 03, 00]

... (continues for each data byte)

Byte 0x26 received:
  → Append to buffer: [..., 26]
  
Byte 0x3B received:
  → Append to buffer: [..., 26, 3B]

Byte 0x7E received:
  → Flag detected!
  → Frame complete
  → State: NORMAL (ready for next frame)

After Unstuffing:

Since this frame had no escape sequences, the unstuffed content equals the received content:

Unstuffed frame (34 bytes):
FF 03 00 21 45 00 00 1C 00 01 00 00 40 01 B9 C4
0A 00 00 01 0A 00 00 02 08 00 F7 FF 00 01 00 01
26 3B

FCS Verification:

The receiver calculates CRC-16 over the entire unstuffed content (including the FCS bytes):

crc = crc16_ccitt(unstuffed_frame)
# If frame is valid, CRC produces "magic" value 0xF0B8

If the CRC matches, the frame is valid.

Frame Decomposition:

Address:  0xFF (verified: all-stations)
Control:  0x03 (verified: UI frame)
Protocol: 0x0021 (IP)
Payload:  45 00 00 1C 00 01 00 00 40 01 B9 C4
          0A 00 00 01 0A 00 00 02 08 00 F7 FF
          00 01 00 01
          (28 bytes)
FCS:      26 3B (verified)

Delivery to Network Layer:

The 28-byte IP packet is delivered to the network layer for routing/forwarding:

IP Packet delivered:
45 00 00 1C 00 01 00 00 40 01 B9 C4
0A 00 00 01 0A 00 00 02 08 00 F7 FF
00 01 00 01

This is exactly the original IP packet—transparency achieved!

Perfect Reconstruction

The receive path perfectly reconstructs the original 28-byte IP packet from the 36-byte transmitted frame. The 8 bytes of PPP overhead (flags + header + FCS) protected the data with error detection and provided clean framing—all while maintaining complete transparency.

LCP Negotiation and ACCM

One of PPP's powerful features is the ability to negotiate link parameters through the Link Control Protocol (LCP). The ACCM is one such negotiable parameter, and understanding this negotiation illuminates real-world byte stuffing optimization.

LCP Negotiation Phase:

┌─────────────┐                           ┌─────────────┐
│   Peer A    │                           │   Peer B    │
└──────┬──────┘                           └──────┬──────┘
       │                                          │
       │─── Configure-Request (ACCM=0x00000000) ─→│
       │                                          │
       │←── Configure-Request (ACCM=0x000A0000) ──│
       │                                          │
       │←── Configure-Ack ────────────────────────│
       │                                          │
       │─── Configure-Ack ───────────────────────→│
       │                                          │
       │        Link Opened (parameters agreed)   │
       │                                          │

ACCM Option Format:

Option-Type:   0x02 (ACCM)
Option-Length: 0x06 (always 6 bytes)
ACCM:          4 bytes (32-bit bitmap)

Interpreting the ACCM:

The 32-bit ACCM indicates which control characters (0x00-0x1F) must be escaped:

ACCM = 0xFFFFFFFF (default):
  Bits 0-31 are set → Escape all control characters (0x00-0x1F)
  
ACCM = 0x00000000 (minimal):
  No bits set → Only escape 0x7E and 0x7D
  (Control characters pass through literally)
  
ACCM = 0x000A0000:
  Bits 17 and 19 set → Escape XON (0x11) and XOFF (0x13)
  (For links using software flow control)

Real-World Negotiation Trace:

Here's what an actual LCP negotiation might look like:

=== PPP LCP Negotiation Trace ===

→ LCP Configure-Request [ID=01, Length=18]
    MRU: 1500
    ACCM: 0x00000000
    Magic Number: 0x6B8A3C1D
    Protocol Field Compression
    Address/Control Field Compression

← LCP Configure-Request [ID=01, Length=14]
    MRU: 1500
    ACCM: 0x000A0000
    Magic Number: 0x45C2D8F3

← LCP Configure-Ack [ID=01]
    (Accepts our parameters)

→ LCP Configure-Nak [ID=01, Length=10]
    ACCM: 0x000A0000
    (We can accept their ACCM, countering with same value)

← LCP Configure-Request [ID=02, Length=14]
    (Peer resends with accepted ACCM)

→ LCP Configure-Ack [ID=02]
    (We accept)

=== Link Open ===
Agreed parameters:
  MRU: 1500 bytes (both directions)
  TX ACCM: 0x000A0000 (escape XON/XOFF when sending)
  RX ACCM: 0x00000000 (no control char escaping needed when receiving)
  Compression: PFC and ACFC enabled

ACCM Asymmetry:

Note that ACCM can be different in each direction:

When I send TO the peer, I use the ACCM they specified (protecting their system)
When I receive FROM the peer, they use the ACCM I specified (protecting my system)

This allows each endpoint to request protection against its own system's vulnerabilities without imposing overhead on the other direction.

Common ACCM Configurations
ACCM Value	Binary (bits 0-31)	Characters Escaped	Use Case
0xFFFFFFFF	All bits set	All 0x00-0x1F, plus 0x7D/0x7E	Maximum compatibility (default)
0x000A0000	Bits 17, 19 set	XON, XOFF, plus 0x7D/0x7E	Software flow control links
0x00000000	No bits set	Only 0x7D/0x7E	8-bit clean links (modems)

Optimization Impact

With full ACCM (default), approximately 13% of bytes in random data require escaping. With minimal ACCM, only 0.8% require escaping. For a 1500-byte frame, this difference is approximately 180 bytes—significant for low-bandwidth links! Always negotiate minimal ACCM when the underlying transport supports it.

Analyzing Real PPP Frames

Let's look at real PPP frames as they would appear in a network capture or serial monitor. Being able to read and analyze these frames is an essential debugging skill.

Reading a Raw Frame Capture:

Captured frame (hex dump):
0000: 7E FF 03 C0 21 01 01 00 12 01 04 05 DC 02 06 00
0010: 00 00 00 05 06 3B 2C 7D 5E 93 E2 7E

Step-by-Step Analysis:

Position | Bytes      | Interpretation
---------+------------+--------------------------------
0000     | 7E         | Opening flag
0001     | FF         | Address (All-Stations)
0002     | 03         | Control (UI frame)
0003-04  | C0 21      | Protocol: 0xC021 (LCP)
0005     | 01         | LCP Code: Configure-Request
0006     | 01         | LCP Identifier: 1
0007-08  | 00 12      | LCP Length: 18 bytes
0009-0C  | 01 04 05 DC| Option: MRU = 1500 (0x05DC)
000D-12  | 02 06 00 00 00 00 | Option: ACCM = 0x00000000
0013-18  | 05 06 3B 2C 7D 5E | Option: Magic = 0x3B2C???? + escape!!
0019-1A  | 93 E2      | FCS
001B     | 7E         | Closing flag

Wait—There's an Escape Sequence!

Look at bytes 0017-0018: 7D 5E. This is the escape sequence for 0x7E!

The Magic Number option contained 0x7E as one of its bytes:

Unstuffed magic number: 0x3B2C7E??
The 0x7E was escaped as 0x7D 0x5E

analyze_ppp_frame.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
"""
PPP Frame Analyzer
 
A tool for parsing and analyzing PPP frames from hex dumps.
Useful for debugging and learning.
"""
 
from dataclasses import dataclass
from typing import List, Optional, Dict
 
@dataclass
class PPPFrame:
    """Parsed PPP frame."""
    raw_bytes: bytes
    address: int
    control: int
    protocol: int
    payload: bytes
    fcs: int
    fcs_valid: bool
    escape_count: int  # Number of escape sequences found
 
class PPPFrameAnalyzer:
    """Analyzes and decodes PPP frames."""
    
    FLAG = 0x7E
    ESCAPE = 0x7D
    XOR_MASK = 0x20
    
    # Protocol ID lookup
    PROTOCOLS = {
        0x0021: "IP",
        0x002B: "IPX",
        0x002D: "Van Jacobson Compressed TCP/IP",
        0x002F: "Van Jacobson Uncompressed TCP/IP",
        0x8021: "IPCP (IP Control Protocol)",
        0x8029: "AppleTalk Control Protocol",
        0xC021: "LCP (Link Control Protocol)",
        0xC023: "PAP (Password Authentication Protocol)",
        0xC223: "CHAP (Challenge Handshake Auth Protocol)",
    }
    
    # LCP Code lookup
    LCP_CODES = {
        1: "Configure-Request",
        2: "Configure-Ack",
        3: "Configure-Nak",
        4: "Configure-Reject",
        5: "Terminate-Request",
        6: "Terminate-Ack",
        7: "Code-Reject",
        8: "Protocol-Reject",
        9: "Echo-Request",
        10: "Echo-Reply",
        11: "Discard-Request",
    }
    
    def unstuff(self, data: bytes) -> tuple[bytes, int]:
        """
        Unstuff escaped bytes that appear between the "flag" characters.
        Returns (unstuffed_data, escape_count).
        """
        result = []
        escape_count = 0
        i = 0
        
        while i < len(data):
            if data[i] == self.ESCAPE:
                if i + 1 < len(data):
                    result.append(data[i + 1] ^ self.XOR_MASK)
                    escape_count += 1
                    i += 2
                else:
                    # Incomplete escape at end
                    break
            else:
                result.append(data[i])
                i += 1
        
        return bytes(result), escape_count
    
    def parse_frame(self, hex_string: str) -> Optional[PPPFrame]:
        """
        Parse a PPP frame from a hex string.
        
        Args:
            hex_string: Space-separated or continuous hex bytes
        
        Returns:
            Parsed PPPFrame or None if invalid
        """
        # Clean and convert hex string
        hex_clean = hex_string.replace(" ", "").replace("
", "")
        try:
            raw_bytes = bytes.fromhex(hex_clean)
        except ValueError:
            return None
        
        # Check for flags
        if len(raw_bytes) < 2:
            return None
        if raw_bytes[0] != self.FLAG or raw_bytes[-1] != self.FLAG:
            print("Warning: Missing frame flags")
        
        # Extract content between flags
        content = raw_bytes
        if content[0] == self.FLAG:
            content = content[1:]
        if content[-1] == self.FLAG:
            content = content[:-1]
        
        # Unstuff
        unstuffed, escape_count = self.unstuff(content)
        
        if len(unstuffed) < 6:  # Minimum frame size
            return None
        
        # Parse fields
        address = unstuffed[0]
        control = unstuffed[1]
        protocol = (unstuffed[2] << 8) | unstuffed[3]
        payload = unstuffed[4:-2]
        fcs = (unstuffed[-1] << 8) | unstuffed[-2]  # Little-endian
        
        # Verify FCS (would need CRC implementation)
        fcs_valid = True  # Placeholder
        
        return PPPFrame(
            raw_bytes=raw_bytes,
            address=address,
            control=control,
            protocol=protocol,
            payload=payload,
            fcs=fcs,
            fcs_valid=fcs_valid,
            escape_count=escape_count,
        )
    
    def analyze_frame(self, frame: PPPFrame) -> str:
        """Generate human-readable analysis of a frame."""
        lines = []
        lines.append("=" * 60)
        lines.append("PPP FRAME ANALYSIS")
        lines.append("=" * 60)
        
        lines.append(f"
Raw frame ({len(frame.raw_bytes)} bytes):")
        lines.append(f"  {frame.raw_bytes.hex(' ')}")
        
        lines.append(f"
Frame Fields:")
        lines.append(f"  Address:  0x{frame.address:02X}")
        lines.append(f"  Control:  0x{frame.control:02X}")
        
        proto_name = self.PROTOCOLS.get(frame.protocol, "Unknown")
        lines.append(f"  Protocol: 0x{frame.protocol:04X} ({proto_name})")
        
        lines.append(f"  Payload:  {len(frame.payload)} bytes")
        if len(frame.payload) <= 32:
            lines.append(f"            {frame.payload.hex(' ')}")
        else:
            lines.append(f"            {frame.payload[:32].hex(' ')}...")
        
        lines.append(f"  FCS:      0x{frame.fcs:04X}")
        lines.append(f"  FCS OK:   {frame.fcs_valid}")
        lines.append(f"  Escapes:  {frame.escape_count}")
        
        # Protocol-specific analysis
        if frame.protocol == 0xC021:  # LCP
            lines.append(self._analyze_lcp(frame.payload))
        elif frame.protocol == 0x0021:  # IP
            lines.append(self._analyze_ip(frame.payload))
        
        return "
".join(lines)
    
    def _analyze_lcp(self, payload: bytes) -> str:
        """Analyze LCP payload."""
        if len(payload) < 4:
            return "
  LCP: (too short)"
        
        code = payload[0]
        identifier = payload[1]
        length = (payload[2] << 8) | payload[3]
        
        code_name = self.LCP_CODES.get(code, f"Unknown({code})")
        
        lines = [f"
  LCP {code_name}:"]
        lines.append(f"    Identifier: {identifier}")
        lines.append(f"    Length: {length}")
        
        # Parse options
        if code in [1, 2, 3, 4]:  # Configure messages
            lines.append("    Options:")
            pos = 4
            while pos + 2 <= len(payload):
                opt_type = payload[pos]
                opt_len = payload[pos + 1]
                opt_data = payload[pos + 2:pos + opt_len]
                
                opt_name = {
                    1: "MRU",
                    2: "ACCM",
                    3: "Auth-Protocol",
                    5: "Magic-Number",
                    7: "PFC",
                    8: "ACFC",
                }.get(opt_type, f"Unknown({opt_type})")
                
                lines.append(f"      {opt_name}: {opt_data.hex(' ')}")
                pos += opt_len
        
        return "
".join(lines)
    
    def _analyze_ip(self, payload: bytes) -> str:
        """Analyze IP payload."""
        if len(payload) < 20:
            return "
  IP: (too short)"
        
        version = (payload[0] >> 4) & 0x0F
        ihl = payload[0] & 0x0F
        total_length = (payload[2] << 8) | payload[3]
        protocol = payload[9]
        src_ip = ".".join(str(b) for b in payload[12:16])
        dst_ip = ".".join(str(b) for b in payload[16:20])
        
        proto_name = {1: "ICMP", 6: "TCP", 17: "UDP"}.get(protocol, str(protocol))
        
        return f"""
  IP Packet:
    Version: {version}
    IHL: {ihl} ({ihl * 4} bytes)
    Total Length: {total_length}
    Protocol: {proto_name}
    Source: {src_ip}
    Destination: {dst_ip}"""
 
 
# Demonstration
if __name__ == "__main__":
    analyzer = PPPFrameAnalyzer()
    
    # Example LCP frame with escape sequence
    hex_dump = """
    7E FF 03 C0 21 01 01 00 12 01 04 05 DC 02 06 00
    00 00 00 05 06 3B 2C 7D 5E 93 E2 7E
    """
    
    frame = analyzer.parse_frame(hex_dump)
    if frame:
        print(analyzer.analyze_frame(frame))

Debugging Tip

When debugging PPP links, always capture at the serial level to see the actual transmitted bytes including escape sequences. Higher-level captures (like Wireshark PPP dissector) often show unstuffed frames, hiding the escape sequences from view.

Common Implementation Pitfalls

Understanding common implementation mistakes helps you avoid them in your own code and recognize them when debugging others' implementations.

Pitfall 1: Forgetting to Stuff the FCS

# WRONG:
def transmit_frame(payload):
    content = header + payload
    fcs = calculate_fcs(content)
    stuffed = stuff(content)  # FCS not included!
    return FLAG + stuffed + fcs + FLAG  # FCS sent unstuffed!

# CORRECT:
def transmit_frame(payload):
    content = header + payload
    fcs = calculate_fcs(content)
    stuffed = stuff(content + fcs)  # Stuff ENTIRE frame including FCS
    return FLAG + stuffed + FLAG

If FCS happens to contain 0x7E, the receiver will see a premature frame boundary.

Pitfall 2: Off-by-One in Buffer Processing

# WRONG:
for i in range(len(data)):
    if data[i] == ESCAPE:
        output[j] = data[i+1] ^ 0x20  # May read past buffer!
        i += 1  # Doesn't work as expected in Python!
        
# CORRECT:
i = 0
while i < len(data):
    if data[i] == ESCAPE and i + 1 < len(data):
        output.append(data[i + 1] ^ 0x20)
        i += 2
    else:
        output.append(data[i])
        i += 1

Pitfall 3: Not Handling Multiple Consecutive Flags

# WRONG: Treats consecutive flags as empty frames
def receive():
    if byte == FLAG:
        if len(buffer) > 0:
            process_frame(buffer)  # Processes "empty" frames!
        buffer.clear()

# CORRECT: Consecutive flags are inter-frame fill
def receive():
    if byte == FLAG:
        if len(buffer) > 0:
            process_frame(buffer)
        buffer.clear()  # Buffer cleared but no frame processed for empty

More Common Pitfalls

•Wrong ACCM direction: Using peer's ACCM when should use own, or vice versa
•Not updating ACCM: Using default ACCM after negotiation completes
•CRC on stuffed data: Calculating FCS on already-stuffed bytes (should be on original)
•FCS byte order: Using big-endian when PPP uses little-endian
•Buffer too small: Not allocating for worst-case 2x expansion
•Escape at frame end: Not handling lone escape byte before closing flag
•State leak: Not resetting receiver state between frames

Pitfall 4: Efficiency Mistakes

# INEFFICIENT: Checking each byte with function call
def must_escape(byte, accm):
    if byte == 0x7E: return True
    if byte == 0x7D: return True
    if byte < 32 and (accm & (1 << byte)): return True
    return False

for byte in data:
    if must_escape(byte, accm):  # Function call per byte!
        ...

# EFFICIENT: Pre-computed lookup table
escape_table = [False] * 256
escape_table[0x7E] = True
escape_table[0x7D] = True
for i in range(32):
    if accm & (1 << i):
        escape_table[i] = True

for byte in data:
    if escape_table[byte]:  # Simple array lookup
        ...

Pitfall 5: Forgetting Protocol Field Escaping

The protocol field comes before the payload but after the header. With certain protocols (unlikely but possible), the protocol field might contain escapable bytes:

Protocol 0x7E21 → Must be escaped as: 7D 5E 21

Though standard protocols are designed to avoid this, a robust implementation stuffs the entire frame content uniformly.

Test-Driven Development

Write tests that exercise all these edge cases before implementing. Create test frames with: 0x7E in every field position, 0x7D in every field position, consecutive flags, empty frames, maximum-length frames, and the patterns [0x7D 0x5E] and [0x7D 0x5D] in data.

Summary: Byte Stuffing in Action

We have now seen byte stuffing in complete action through the lens of PPP—one of the most successful and long-lived data link layer protocols. Let's consolidate everything we've learned in this module:

Module Summary

•Flag Bytes (Page 1): Reserved byte value (0x7E) marks frame boundaries; receiver can always identify where frames start and end
•Escape Sequences (Page 2): Two-byte sequences represent reserved bytes in payload; enables arbitrary data transmission
•Byte Stuffing (Page 3): Complete algorithm combining flags and escaping; transmitter stuffs, receiver unstuffs
•Transparency (Page 4): Mathematical guarantee that any data survives round-trip unchanged; formal proofs ensure correctness
•PPP Example (This Page): Real-world protocol demonstrating all concepts working together

What You Can Now Do:

✓ Explain byte-oriented framing from first principles
✓ Implement correct byte stuffing and unstuffing algorithms
✓ Analyze PPP frames in network captures
✓ Prove that an encoding scheme achieves transparency
✓ Debug common implementation errors
✓ Optimize stuffing implementations for performance
✓ Understand LCP negotiation and ACCM configuration

The Bigger Picture:

Byte stuffing is just one framing mechanism in the data link layer toolkit. The next modules in this chapter will explore:

Bit Stuffing: The bit-oriented alternative (HDLC)
Flow Control: Managing sender/receiver speed mismatch
Error Control: Handling transmission errors

Each builds on the foundation we've established here: reliable, transparent, delimited frames that can carry any data the network layer wishes to transmit.

PPP's Enduring Legacy:

Though dial-up modems are rare today, PPP lives on:

PPPoE carries DSL and fiber internet to homes
L2TP tunnels encapsulate PPP for VPNs
Serial console connections use PPP for network access
Embedded systems use PPP over UART for IoT connectivity

The principles you've learned apply wherever byte-oriented framing is needed.

Module Complete

Congratulations! You have completed Module 3: Framing - Byte Stuffing. You now possess deep understanding of how byte-oriented protocols achieve reliable, transparent frame delimitation. This knowledge is foundational for understanding the data link layer and will serve you well when studying higher-layer protocols that rely on this infrastructure.

PPP Example: Complete Real-World Implementation

Putting It All Together with PPP

Dial-up modems (the original use case)
DSL connections (PPPoE - PPP over Ethernet)
Serial console connections (network equipment)
Cellular data (PPP over serial)
VPN tunnels (L2TP uses PPP frames)

What You Will Master

PPP Protocol Overview

Before diving into the framing example, let's understand PPP's architecture and how framing fits into the bigger picture.

PPP Protocol Stack:

┌─────────────────────────────────────────────┐
│           Network Layer (IP, IPX)            │
├─────────────────────────────────────────────┤
│         Network Control Protocols            │
│        (IPCP, IPXCP - per protocol)         │
├─────────────────────────────────────────────┤
│       Link Control Protocol (LCP)            │
│    (Link setup, negotiation, teardown)       │
├─────────────────────────────────────────────┤
│         PPP Framing (RFC 1662)               │
│     (The subject of this module!)            │
├─────────────────────────────────────────────┤
│         Physical Layer (Serial)              │
│    (RS-232, Modem, Virtual serial)           │
└─────────────────────────────────────────────┘

PPP Session Lifecycle:

Physical connection established (modem connects, cable attached)
LCP negotiation (agree on MTU, ACCM, authentication, etc.)
Authentication (optional: PAP, CHAP)
NCP negotiation (e.g., IPCP assigns IP addresses)
Data transfer (IP packets flow in PPP frames)
Termination (LCP close, physical disconnection)

The PPP Frame Format:

Every PPP frame follows this structure (from RFC 1662):

+----------+----------+-----------+----------+-------------+----------+----------+
|  Flag    | Address  |  Control  | Protocol |   Payload   |   FCS    |  Flag    |
| (1 byte) | (1 byte) |  (1 byte) | (2 bytes)|  (variable) | (2 bytes)| (1 byte) |
|   0x7E   |   0xFF   |   0x03    |          |             |          |   0x7E   |
+----------+----------+-----------+----------+-------------+----------+----------+

Field Descriptions:

PPP Frame Fields
Field	Size	Value	Purpose
Flag	1 byte	0x7E	Frame delimiter; marks start and end
Address	1 byte	0xFF	Broadcast address (PPP is point-to-point, so always broadcast)
Control	1 byte	0x03	Unnumbered Information (UI) frame; no sequence numbers
Protocol	2 bytes	Variable	Identifies payload type (0x0021=IP, 0xC021=LCP, etc.)
Payload	0-1500 bytes	Variable	Upper layer data (IP packet, LCP message, etc.)
FCS	2 bytes	CRC-16	Frame Check Sequence for error detection

Field Compression

The Complete Transmit Path

Let's trace an IP packet through the complete PPP transmission process, examining every byte transformation.

Scenario:

An application sends a small IP packet (an ICMP echo request - "ping") over a PPP link.

Step 1: IP Packet from Network Layer

The network layer presents this IP packet to PPP for transmission:

IP Packet (28 bytes):
45 00 00 1C    ; IP header: version, IHL, TOS, Total Length=28
00 01 00 00    ; Identification, Flags, Fragment Offset
40 01 B9 C4    ; TTL=64, Protocol=ICMP(1), Header Checksum
0A 00 00 01    ; Source IP: 10.0.0.1
0A 00 00 02    ; Destination IP: 10.0.0.2
08 00 F7 FF    ; ICMP: Type=8 (Echo), Code=0, Checksum
00 01 00 01    ; ICMP: Identifier=1, Sequence=1

Note: This IP packet contains 0x00 bytes (part of ACCM if enabled) but no 0x7E or 0x7D bytes.

Step 2: PPP Protocol Identification

PPP adds the protocol field to identify this as an IP packet:

Protocol: 0x0021 (Internet Protocol)

Step 3: Prepend Address and Control

Address: 0xFF (All-Stations Broadcast)
Control: 0x03 (Unnumbered Information)

Step 4: Construct Frame Content (Before FCS)

Frame content (32 bytes):
 FF 03          ; Address, Control
 00 21          ; Protocol (IP)
 45 00 00 1C    ; IP packet starts here
 00 01 00 00
 40 01 B9 C4
 0A 00 00 01
 0A 00 00 02
 08 00 F7 FF
 00 01 00 01

Step 5: Calculate FCS (CRC-16-CCITT)

The FCS is calculated over the Address, Control, Protocol, and Payload fields:

# FCS calculation (simplified)
fcs = crc16_ccitt(bytes.fromhex(
    'FF 03 00 21 45 00 00 1C 00 01 00 00 40 01 B9 C4 '
    '0A 00 00 01 0A 00 00 02 08 00 F7 FF 00 01 00 01'
))
# Result: FCS = 0x3B26 (hypothetical)

FCS is appended in little-endian order: 0x26 0x3B

Step 6: Complete Frame (Before Stuffing)

Unstuffed frame (34 bytes, excluding flags):
FF 03 00 21 45 00 00 1C 00 01 00 00 40 01 B9 C4
0A 00 00 01 0A 00 00 02 08 00 F7 FF 00 01 00 01
26 3B

Step 7: Byte Stuffing

Now we apply byte stuffing. This example uses minimal ACCM (only escape 0x7E and 0x7D):

Scanning the 34 bytes:

0xFF: Not reserved → pass through
0x03: Not reserved (minimal ACCM) → pass through
0x00: Not reserved (minimal ACCM) → pass through
... (no 0x7E or 0x7D in this frame)
All bytes pass through unchanged!

Stuffed frame (34 bytes, same as unstuffed):
FF 03 00 21 45 00 00 1C 00 01 00 00 40 01 B9 C4
0A 00 00 01 0A 00 00 02 08 00 F7 FF 00 01 00 01
26 3B

Step 8: Add Flags

Complete transmitted frame (36 bytes):
7E FF 03 00 21 45 00 00 1C 00 01 00 00 40 01 B9 C4
   0A 00 00 01 0A 00 00 02 08 00 F7 FF 00 01 00 01
   26 3B 7E

Minimal Overhead in This Case

Example with Stuffing Required

Let's examine a more interesting case where byte stuffing is actually required. This happens when the payload contains reserved byte values.

Scenario:

A PPP frame carrying an LCP Configure-Request packet. LCP packets use protocol 0xC021 and often contain structured option data that might include reserved bytes.

LCP Packet:

LCP Configure-Request (with ACCM option):
Code:        0x01 (Configure-Request)
Identifier:  0x01
Length:      0x000A (10 bytes)
Options:
  Option Type: 0x02 (ACCM)
  Option Length: 0x06
  ACCM Value: 0x00 0x00 0x7E 0x00  ← Contains FLAG byte!

This LCP packet requests an ACCM that would allow literal 0x7E in data—but first, we must transmit this request, and the ACCM value itself contains 0x7E!

Frame Construction:

Unstuffed frame content:
FF 03           ; Address, Control
C0 21           ; Protocol (LCP)
01 01 00 0A     ; LCP: Code=1, ID=1, Length=10
02 06           ; Option: ACCM, length=6
00 00 7E 00     ; ACCM value (contains 0x7E!)
[FCS bytes]     ; Calculated CRC

Byte Stuffing Process:

Processing each byte:
FF → FF          (not reserved)
03 → 03          (not reserved)
C0 → C0          (not reserved)
21 → 21          (not reserved)
01 → 01          (not reserved)
01 → 01          (not reserved)
00 → 00          (not reserved with minimal ACCM)
0A → 0A          (not reserved)
02 → 02          (not reserved)
06 → 06          (not reserved)
00 → 00          (not reserved)
00 → 00          (not reserved)
7E → 7D 5E       ← ESCAPE REQUIRED! (Flag byte in data)
00 → 00          (not reserved)
[FCS byte 1] → possibly escaped
[FCS byte 2] → possibly escaped

Stuffed Frame:

The single 0x7E in the ACCM value becomes 0x7D 0x5E, adding one byte:

Stuffed frame content (one byte longer):
FF 03 C0 21 01 01 00 0A 02 06 00 00 7D 5E 00 [FCS]
                                    ↑↑↑↑
                               Escape sequence!

Complete Transmitted Frame:

7E FF 03 C0 21 01 01 00 0A 02 06 00 00 7D 5E 00 [stuffed FCS] 7E
↑                                      ↑↑↑↑                   ↑
Start flag                      Escaped 0x7E               End flag

Why This Works:

The receiver processes this frame:

Sees opening flag 0x7E → begin receiving frame
Receives FF 03 C0 21 01 01 00 0A 02 06 00 00 → accumulates normally
Receives 0x7D → enters escape state
Receives 0x5E → XOR 0x20 = 0x7E, outputs 0x7E, returns to normal state
Receives 00 → accumulates normally
Processes FCS bytes (with unstuffing if needed)
Sees closing flag 0x7E → frame complete
Verifies FCS → delivers LCP packet with ACCM value 0x0000007E000

The Crucial Point:

The 0x7E that appears between the flags as part of the escape sequence (0x7D 0x5E) is never mistaken for a frame boundary because:

It appears as 0x5E, not 0x7E
The invariant is maintained: no literal 0x7E appears in stuffed content

FCS Must Also Be Stuffed

The Complete Receive Path

Now let's trace the receive path in detail, showing how the receiver reconstructs the original data from the transmitted frame.

Received Byte Stream:

The receiver sees this stream of bytes from the serial port:

7E FF 03 00 21 45 00 00 1C 00 01 00 00 40 01 B9 C4
   0A 00 00 01 0A 00 00 02 08 00 F7 FF 00 01 00 01
   26 3B 7E

State Machine Processing:

Let's trace through the receiver state machine byte-by-byte:

State: HUNT (initial)

Byte 0x7E received:
  → Flag detected!
  → Clear buffer
  → State: NORMAL

Byte 0xFF received:
  → Not flag, not escape
  → Append to buffer: [FF]
  → State: NORMAL

Byte 0x03 received:
  → Append to buffer: [FF, 03]
  
Byte 0x00 received:
  → Append to buffer: [FF, 03, 00]

... (continues for each data byte)

Byte 0x26 received:
  → Append to buffer: [..., 26]
  
Byte 0x3B received:
  → Append to buffer: [..., 26, 3B]

Byte 0x7E received:
  → Flag detected!
  → Frame complete
  → State: NORMAL (ready for next frame)

After Unstuffing:

Since this frame had no escape sequences, the unstuffed content equals the received content:

Unstuffed frame (34 bytes):
FF 03 00 21 45 00 00 1C 00 01 00 00 40 01 B9 C4
0A 00 00 01 0A 00 00 02 08 00 F7 FF 00 01 00 01
26 3B

FCS Verification:

The receiver calculates CRC-16 over the entire unstuffed content (including the FCS bytes):

crc = crc16_ccitt(unstuffed_frame)
# If frame is valid, CRC produces "magic" value 0xF0B8

If the CRC matches, the frame is valid.

Frame Decomposition:

Address:  0xFF (verified: all-stations)
Control:  0x03 (verified: UI frame)
Protocol: 0x0021 (IP)
Payload:  45 00 00 1C 00 01 00 00 40 01 B9 C4
          0A 00 00 01 0A 00 00 02 08 00 F7 FF
          00 01 00 01
          (28 bytes)
FCS:      26 3B (verified)

Delivery to Network Layer:

The 28-byte IP packet is delivered to the network layer for routing/forwarding:

IP Packet delivered:
45 00 00 1C 00 01 00 00 40 01 B9 C4
0A 00 00 01 0A 00 00 02 08 00 F7 FF
00 01 00 01

This is exactly the original IP packet—transparency achieved!

Perfect Reconstruction

LCP Negotiation and ACCM

LCP Negotiation Phase:

┌─────────────┐                           ┌─────────────┐
│   Peer A    │                           │   Peer B    │
└──────┬──────┘                           └──────┬──────┘
       │                                          │
       │─── Configure-Request (ACCM=0x00000000) ─→│
       │                                          │
       │←── Configure-Request (ACCM=0x000A0000) ──│
       │                                          │
       │←── Configure-Ack ────────────────────────│
       │                                          │
       │─── Configure-Ack ───────────────────────→│
       │                                          │
       │        Link Opened (parameters agreed)   │
       │                                          │

ACCM Option Format:

Option-Type:   0x02 (ACCM)
Option-Length: 0x06 (always 6 bytes)
ACCM:          4 bytes (32-bit bitmap)

Interpreting the ACCM:

The 32-bit ACCM indicates which control characters (0x00-0x1F) must be escaped:

ACCM = 0xFFFFFFFF (default):
  Bits 0-31 are set → Escape all control characters (0x00-0x1F)
  
ACCM = 0x00000000 (minimal):
  No bits set → Only escape 0x7E and 0x7D
  (Control characters pass through literally)
  
ACCM = 0x000A0000:
  Bits 17 and 19 set → Escape XON (0x11) and XOFF (0x13)
  (For links using software flow control)

Real-World Negotiation Trace:

Here's what an actual LCP negotiation might look like:

=== PPP LCP Negotiation Trace ===

→ LCP Configure-Request [ID=01, Length=18]
    MRU: 1500
    ACCM: 0x00000000
    Magic Number: 0x6B8A3C1D
    Protocol Field Compression
    Address/Control Field Compression

← LCP Configure-Request [ID=01, Length=14]
    MRU: 1500
    ACCM: 0x000A0000
    Magic Number: 0x45C2D8F3

← LCP Configure-Ack [ID=01]
    (Accepts our parameters)

→ LCP Configure-Nak [ID=01, Length=10]
    ACCM: 0x000A0000
    (We can accept their ACCM, countering with same value)

← LCP Configure-Request [ID=02, Length=14]
    (Peer resends with accepted ACCM)

→ LCP Configure-Ack [ID=02]
    (We accept)

=== Link Open ===
Agreed parameters:
  MRU: 1500 bytes (both directions)
  TX ACCM: 0x000A0000 (escape XON/XOFF when sending)
  RX ACCM: 0x00000000 (no control char escaping needed when receiving)
  Compression: PFC and ACFC enabled

ACCM Asymmetry:

Note that ACCM can be different in each direction:

When I send TO the peer, I use the ACCM they specified (protecting their system)
When I receive FROM the peer, they use the ACCM I specified (protecting my system)

This allows each endpoint to request protection against its own system's vulnerabilities without imposing overhead on the other direction.

Common ACCM Configurations
ACCM Value	Binary (bits 0-31)	Characters Escaped	Use Case
0xFFFFFFFF	All bits set	All 0x00-0x1F, plus 0x7D/0x7E	Maximum compatibility (default)
0x000A0000	Bits 17, 19 set	XON, XOFF, plus 0x7D/0x7E	Software flow control links
0x00000000	No bits set	Only 0x7D/0x7E	8-bit clean links (modems)

Optimization Impact

Analyzing Real PPP Frames

Let's look at real PPP frames as they would appear in a network capture or serial monitor. Being able to read and analyze these frames is an essential debugging skill.

Reading a Raw Frame Capture:

Captured frame (hex dump):
0000: 7E FF 03 C0 21 01 01 00 12 01 04 05 DC 02 06 00
0010: 00 00 00 05 06 3B 2C 7D 5E 93 E2 7E

Step-by-Step Analysis:

Position | Bytes      | Interpretation
---------+------------+--------------------------------
0000     | 7E         | Opening flag
0001     | FF         | Address (All-Stations)
0002     | 03         | Control (UI frame)
0003-04  | C0 21      | Protocol: 0xC021 (LCP)
0005     | 01         | LCP Code: Configure-Request
0006     | 01         | LCP Identifier: 1
0007-08  | 00 12      | LCP Length: 18 bytes
0009-0C  | 01 04 05 DC| Option: MRU = 1500 (0x05DC)
000D-12  | 02 06 00 00 00 00 | Option: ACCM = 0x00000000
0013-18  | 05 06 3B 2C 7D 5E | Option: Magic = 0x3B2C???? + escape!!
0019-1A  | 93 E2      | FCS
001B     | 7E         | Closing flag

Wait—There's an Escape Sequence!

Look at bytes 0017-0018: 7D 5E. This is the escape sequence for 0x7E!

The Magic Number option contained 0x7E as one of its bytes:

Unstuffed magic number: 0x3B2C7E??
The 0x7E was escaped as 0x7D 0x5E

analyze_ppp_frame.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
"""
PPP Frame Analyzer
 
A tool for parsing and analyzing PPP frames from hex dumps.
Useful for debugging and learning.
"""
 
from dataclasses import dataclass
from typing import List, Optional, Dict
 
@dataclass
class PPPFrame:
    """Parsed PPP frame."""
    raw_bytes: bytes
    address: int
    control: int
    protocol: int
    payload: bytes
    fcs: int
    fcs_valid: bool
    escape_count: int  # Number of escape sequences found
 
class PPPFrameAnalyzer:
    """Analyzes and decodes PPP frames."""
    
    FLAG = 0x7E
    ESCAPE = 0x7D
    XOR_MASK = 0x20
    
    # Protocol ID lookup
    PROTOCOLS = {
        0x0021: "IP",
        0x002B: "IPX",
        0x002D: "Van Jacobson Compressed TCP/IP",
        0x002F: "Van Jacobson Uncompressed TCP/IP",
        0x8021: "IPCP (IP Control Protocol)",
        0x8029: "AppleTalk Control Protocol",
        0xC021: "LCP (Link Control Protocol)",
        0xC023: "PAP (Password Authentication Protocol)",
        0xC223: "CHAP (Challenge Handshake Auth Protocol)",
    }
    
    # LCP Code lookup
    LCP_CODES = {
        1: "Configure-Request",
        2: "Configure-Ack",
        3: "Configure-Nak",
        4: "Configure-Reject",
        5: "Terminate-Request",
        6: "Terminate-Ack",
        7: "Code-Reject",
        8: "Protocol-Reject",
        9: "Echo-Request",
        10: "Echo-Reply",
        11: "Discard-Request",
    }
    
    def unstuff(self, data: bytes) -> tuple[bytes, int]:
        """
        Unstuff escaped bytes that appear between the "flag" characters.
        Returns (unstuffed_data, escape_count).
        """
        result = []
        escape_count = 0
        i = 0
        
        while i < len(data):
            if data[i] == self.ESCAPE:
                if i + 1 < len(data):
                    result.append(data[i + 1] ^ self.XOR_MASK)
                    escape_count += 1
                    i += 2
                else:
                    # Incomplete escape at end
                    break
            else:
                result.append(data[i])
                i += 1
        
        return bytes(result), escape_count
    
    def parse_frame(self, hex_string: str) -> Optional[PPPFrame]:
        """
        Parse a PPP frame from a hex string.
        
        Args:
            hex_string: Space-separated or continuous hex bytes
        
        Returns:
            Parsed PPPFrame or None if invalid
        """
        # Clean and convert hex string
        hex_clean = hex_string.replace(" ", "").replace("
", "")
        try:
            raw_bytes = bytes.fromhex(hex_clean)
        except ValueError:
            return None
        
        # Check for flags
        if len(raw_bytes) < 2:
            return None
        if raw_bytes[0] != self.FLAG or raw_bytes[-1] != self.FLAG:
            print("Warning: Missing frame flags")
        
        # Extract content between flags
        content = raw_bytes
        if content[0] == self.FLAG:
            content = content[1:]
        if content[-1] == self.FLAG:
            content = content[:-1]
        
        # Unstuff
        unstuffed, escape_count = self.unstuff(content)
        
        if len(unstuffed) < 6:  # Minimum frame size
            return None
        
        # Parse fields
        address = unstuffed[0]
        control = unstuffed[1]
        protocol = (unstuffed[2] << 8) | unstuffed[3]
        payload = unstuffed[4:-2]
        fcs = (unstuffed[-1] << 8) | unstuffed[-2]  # Little-endian
        
        # Verify FCS (would need CRC implementation)
        fcs_valid = True  # Placeholder
        
        return PPPFrame(
            raw_bytes=raw_bytes,
            address=address,
            control=control,
            protocol=protocol,
            payload=payload,
            fcs=fcs,
            fcs_valid=fcs_valid,
            escape_count=escape_count,
        )
    
    def analyze_frame(self, frame: PPPFrame) -> str:
        """Generate human-readable analysis of a frame."""
        lines = []
        lines.append("=" * 60)
        lines.append("PPP FRAME ANALYSIS")
        lines.append("=" * 60)
        
        lines.append(f"
Raw frame ({len(frame.raw_bytes)} bytes):")
        lines.append(f"  {frame.raw_bytes.hex(' ')}")
        
        lines.append(f"
Frame Fields:")
        lines.append(f"  Address:  0x{frame.address:02X}")
        lines.append(f"  Control:  0x{frame.control:02X}")
        
        proto_name = self.PROTOCOLS.get(frame.protocol, "Unknown")
        lines.append(f"  Protocol: 0x{frame.protocol:04X} ({proto_name})")
        
        lines.append(f"  Payload:  {len(frame.payload)} bytes")
        if len(frame.payload) <= 32:
            lines.append(f"            {frame.payload.hex(' ')}")
        else:
            lines.append(f"            {frame.payload[:32].hex(' ')}...")
        
        lines.append(f"  FCS:      0x{frame.fcs:04X}")
        lines.append(f"  FCS OK:   {frame.fcs_valid}")
        lines.append(f"  Escapes:  {frame.escape_count}")
        
        # Protocol-specific analysis
        if frame.protocol == 0xC021:  # LCP
            lines.append(self._analyze_lcp(frame.payload))
        elif frame.protocol == 0x0021:  # IP
            lines.append(self._analyze_ip(frame.payload))
        
        return "
".join(lines)
    
    def _analyze_lcp(self, payload: bytes) -> str:
        """Analyze LCP payload."""
        if len(payload) < 4:
            return "
  LCP: (too short)"
        
        code = payload[0]
        identifier = payload[1]
        length = (payload[2] << 8) | payload[3]
        
        code_name = self.LCP_CODES.get(code, f"Unknown({code})")
        
        lines = [f"
  LCP {code_name}:"]
        lines.append(f"    Identifier: {identifier}")
        lines.append(f"    Length: {length}")
        
        # Parse options
        if code in [1, 2, 3, 4]:  # Configure messages
            lines.append("    Options:")
            pos = 4
            while pos + 2 <= len(payload):
                opt_type = payload[pos]
                opt_len = payload[pos + 1]
                opt_data = payload[pos + 2:pos + opt_len]
                
                opt_name = {
                    1: "MRU",
                    2: "ACCM",
                    3: "Auth-Protocol",
                    5: "Magic-Number",
                    7: "PFC",
                    8: "ACFC",
                }.get(opt_type, f"Unknown({opt_type})")
                
                lines.append(f"      {opt_name}: {opt_data.hex(' ')}")
                pos += opt_len
        
        return "
".join(lines)
    
    def _analyze_ip(self, payload: bytes) -> str:
        """Analyze IP payload."""
        if len(payload) < 20:
            return "
  IP: (too short)"
        
        version = (payload[0] >> 4) & 0x0F
        ihl = payload[0] & 0x0F
        total_length = (payload[2] << 8) | payload[3]
        protocol = payload[9]
        src_ip = ".".join(str(b) for b in payload[12:16])
        dst_ip = ".".join(str(b) for b in payload[16:20])
        
        proto_name = {1: "ICMP", 6: "TCP", 17: "UDP"}.get(protocol, str(protocol))
        
        return f"""
  IP Packet:
    Version: {version}
    IHL: {ihl} ({ihl * 4} bytes)
    Total Length: {total_length}
    Protocol: {proto_name}
    Source: {src_ip}
    Destination: {dst_ip}"""
 
 
# Demonstration
if __name__ == "__main__":
    analyzer = PPPFrameAnalyzer()
    
    # Example LCP frame with escape sequence
    hex_dump = """
    7E FF 03 C0 21 01 01 00 12 01 04 05 DC 02 06 00
    00 00 00 05 06 3B 2C 7D 5E 93 E2 7E
    """
    
    frame = analyzer.parse_frame(hex_dump)
    if frame:
        print(analyzer.analyze_frame(frame))

Debugging Tip

Common Implementation Pitfalls

Understanding common implementation mistakes helps you avoid them in your own code and recognize them when debugging others' implementations.

Pitfall 1: Forgetting to Stuff the FCS

# WRONG:
def transmit_frame(payload):
    content = header + payload
    fcs = calculate_fcs(content)
    stuffed = stuff(content)  # FCS not included!
    return FLAG + stuffed + fcs + FLAG  # FCS sent unstuffed!

# CORRECT:
def transmit_frame(payload):
    content = header + payload
    fcs = calculate_fcs(content)
    stuffed = stuff(content + fcs)  # Stuff ENTIRE frame including FCS
    return FLAG + stuffed + FLAG

If FCS happens to contain 0x7E, the receiver will see a premature frame boundary.

Pitfall 2: Off-by-One in Buffer Processing

# WRONG:
for i in range(len(data)):
    if data[i] == ESCAPE:
        output[j] = data[i+1] ^ 0x20  # May read past buffer!
        i += 1  # Doesn't work as expected in Python!
        
# CORRECT:
i = 0
while i < len(data):
    if data[i] == ESCAPE and i + 1 < len(data):
        output.append(data[i + 1] ^ 0x20)
        i += 2
    else:
        output.append(data[i])
        i += 1

Pitfall 3: Not Handling Multiple Consecutive Flags

# WRONG: Treats consecutive flags as empty frames
def receive():
    if byte == FLAG:
        if len(buffer) > 0:
            process_frame(buffer)  # Processes "empty" frames!
        buffer.clear()

# CORRECT: Consecutive flags are inter-frame fill
def receive():
    if byte == FLAG:
        if len(buffer) > 0:
            process_frame(buffer)
        buffer.clear()  # Buffer cleared but no frame processed for empty

More Common Pitfalls

•Wrong ACCM direction: Using peer's ACCM when should use own, or vice versa
•Not updating ACCM: Using default ACCM after negotiation completes
•CRC on stuffed data: Calculating FCS on already-stuffed bytes (should be on original)
•FCS byte order: Using big-endian when PPP uses little-endian
•Buffer too small: Not allocating for worst-case 2x expansion
•Escape at frame end: Not handling lone escape byte before closing flag
•State leak: Not resetting receiver state between frames

Pitfall 4: Efficiency Mistakes

# INEFFICIENT: Checking each byte with function call
def must_escape(byte, accm):
    if byte == 0x7E: return True
    if byte == 0x7D: return True
    if byte < 32 and (accm & (1 << byte)): return True
    return False

for byte in data:
    if must_escape(byte, accm):  # Function call per byte!
        ...

# EFFICIENT: Pre-computed lookup table
escape_table = [False] * 256
escape_table[0x7E] = True
escape_table[0x7D] = True
for i in range(32):
    if accm & (1 << i):
        escape_table[i] = True

for byte in data:
    if escape_table[byte]:  # Simple array lookup
        ...

Pitfall 5: Forgetting Protocol Field Escaping

The protocol field comes before the payload but after the header. With certain protocols (unlikely but possible), the protocol field might contain escapable bytes:

Protocol 0x7E21 → Must be escaped as: 7D 5E 21

Though standard protocols are designed to avoid this, a robust implementation stuffs the entire frame content uniformly.

Test-Driven Development

Summary: Byte Stuffing in Action

Module Summary

•Flag Bytes (Page 1): Reserved byte value (0x7E) marks frame boundaries; receiver can always identify where frames start and end
•Escape Sequences (Page 2): Two-byte sequences represent reserved bytes in payload; enables arbitrary data transmission
•Byte Stuffing (Page 3): Complete algorithm combining flags and escaping; transmitter stuffs, receiver unstuffs
•Transparency (Page 4): Mathematical guarantee that any data survives round-trip unchanged; formal proofs ensure correctness
•PPP Example (This Page): Real-world protocol demonstrating all concepts working together

What You Can Now Do:

✓ Explain byte-oriented framing from first principles
✓ Implement correct byte stuffing and unstuffing algorithms
✓ Analyze PPP frames in network captures
✓ Prove that an encoding scheme achieves transparency
✓ Debug common implementation errors
✓ Optimize stuffing implementations for performance
✓ Understand LCP negotiation and ACCM configuration

The Bigger Picture:

Byte stuffing is just one framing mechanism in the data link layer toolkit. The next modules in this chapter will explore:

Bit Stuffing: The bit-oriented alternative (HDLC)
Flow Control: Managing sender/receiver speed mismatch
Error Control: Handling transmission errors

Each builds on the foundation we've established here: reliable, transparent, delimited frames that can carry any data the network layer wishes to transmit.

PPP's Enduring Legacy:

Though dial-up modems are rare today, PPP lives on:

PPPoE carries DSL and fiber internet to homes
L2TP tunnels encapsulate PPP for VPNs
Serial console connections use PPP for network access
Embedded systems use PPP over UART for IoT connectivity

The principles you've learned apply wherever byte-oriented framing is needed.

Module Complete