Framing Byte Stuffing - Learning Module

Loading content...

0/240

Flag Bytes: Foundational Frame Delimiters

The Frame Boundary Problem

In the realm of data communication, the Data Link Layer faces a fundamental challenge that might seem deceptively simple: How does a receiver know where one frame ends and another begins?

Unlike reading a book where chapters have visible headings and pages have clear boundaries, a continuous stream of bits arriving at a network interface provides no inherent structure. Without explicit delimitation mechanisms, the receiver would face an insurmountable parsing problem—unable to distinguish the end of one message from the beginning of the next, unable to identify headers from payloads, and ultimately unable to deliver coherent data to higher layers.

This is the frame boundary problem, and its elegant solution—the flag byte—represents one of the most important design patterns in data link layer engineering.

What You Will Master

By the end of this page, you will understand the theoretical foundations of flag bytes, their precise role in byte-oriented framing, the design decisions that led to specific flag byte values, implementation considerations at both hardware and software levels, and the challenges that flag bytes create—setting the stage for escape sequences and byte stuffing in subsequent pages.

Understanding Byte-Oriented Protocols

Before diving into flag bytes specifically, we must understand the broader context of byte-oriented protocols (also called character-oriented protocols). These protocols represent a fundamental design philosophy where the basic unit of transmission is the byte (or character) rather than individual bits.

Historical Context:

Byte-oriented protocols emerged from the early days of computing when data communication was primarily concerned with transmitting text between terminals and mainframes. Characters from established character sets (ASCII, EBCDIC) formed natural boundaries, and hardware was optimized for processing data in byte-aligned chunks.

Key Characteristics of Byte-Oriented Protocols:

Defining Characteristics

•Byte Boundaries: Data is processed and transmitted as sequences of bytes (8 bits), with all control information aligned to byte boundaries
•Character Set Foundation: Originally designed around text character sets, leveraging control characters for signaling
•Hardware Alignment: Early UART (Universal Asynchronous Receiver/Transmitter) chips and communication hardware operated naturally on byte boundaries
•Variable-Length Frames: Frame lengths are typically specified in bytes, not bits, simplifying implementation and debugging
•Software-Friendly: Byte alignment makes protocol processing easier in software, since most programming languages handle bytes naturally

Comparison with Bit-Oriented Protocols:

While byte-oriented protocols process data in 8-bit units, bit-oriented protocols (like HDLC and its derivatives) treat the data stream as a sequence of individual bits. Bit-oriented protocols offer advantages in flexibility and efficiency but require more sophisticated hardware for bit-level manipulation. The choice between these approaches represents a classic engineering tradeoff between implementation simplicity and operational efficiency.

Why Byte Orientation Persists:

Despite the rise of bit-oriented protocols, byte-oriented approaches remain prevalent for several reasons:

Simplicity: Byte-aligned processing is straightforward to implement in both hardware and software
Debugging: Byte-oriented frames are easier to inspect with standard debugging tools
Integration: Modern systems process data in bytes (or larger units), making byte-oriented protocols a natural fit
Legacy Compatibility: Extensive infrastructure exists for byte-oriented protocols like PPP

Modern Relevance

The Point-to-Point Protocol (PPP), still used in many serial connections and DSL implementations, is a prime example of a byte-oriented protocol. Understanding byte-oriented framing is essential for anyone working with embedded systems, modems, serial communications, or analyzing network captures at the data link layer.

The Concept of Flag Bytes

A flag byte (also known as a frame delimiter or sync character) is a special byte pattern that marks the beginning and/or end of a data frame. The concept is elegantly simple: reserve a specific byte value that cannot appear in user data, and use it exclusively to signal frame boundaries.

The Fundamental Principle:

When a receiver detects a flag byte, it knows with certainty that it has reached a frame boundary. Everything between two consecutive flags constitutes a complete frame. This creates an unambiguous parsing structure that enables reliable frame extraction from a continuous byte stream.

Mathematical Definition:

Let F represent the flag byte value. In a byte stream B = b₁, b₂, b₃, ..., bₙ, frame boundaries occur at positions where bᵢ = F. If we observe the pattern:

... F | b₁ b₂ b₃ ... bₘ | F ...

Then the sequence b₁ b₂ b₃ ... bₘ constitutes a single complete frame (assuming bⱼ ≠ F for all 1 ≤ j ≤ m).

Common Flag Byte Values in Historical and Modern Protocols
Protocol	Flag Byte (Hex)	Flag Byte (Binary)	Flag Byte (Decimal)
BISYNC (SOH)	0x01	00000001	1
BISYNC (STX)	0x02	00000010	2
BISYNC (ETX)	0x03	00000011	3
HDLC/PPP	0x7E	01111110	126
SLIP (END)	0xC0	11000000	192
SLIP (ESC)	0xDB	11011011	219

Why 0x7E for HDLC and PPP?

The choice of 0x7E (01111110 in binary) as the flag byte for HDLC-based protocols is not arbitrary. This pattern was selected for several important reasons:

Transition Density: The pattern 01111110 contains multiple transitions between 0 and 1, aiding clock synchronization in synchronous systems
Uniqueness: The sequence contains exactly six consecutive 1s between two 0s, which forms the basis for bit stuffing in HDLC (a topic we'll explore when comparing byte and bit stuffing)
Detectability: The distinctive pattern is unlikely to occur naturally in random data and is easy for hardware to detect
Historical Standardization: Once standardized in HDLC (ISO 3309), the value was adopted by subsequent protocols for consistency

Design Insight

The selection of a flag byte value involves balancing multiple factors: clock synchronization properties, distinguishability from normal data, hardware detection efficiency, and compatibility with existing systems. The longevity of 0x7E across multiple protocols demonstrates that good design choices compound over time.

Flag Byte Placement Strategies

Different protocols employ different strategies for placing flag bytes around frame data. Understanding these strategies is crucial for implementing and debugging byte-oriented protocols.

Strategy 1: Start and End Flags (Symmetric Framing)

The most common approach places a flag byte at both the beginning and end of each frame:

[FLAG] [Header] [Payload] [Trailer] [FLAG]

In this model:

The opening flag signals "a new frame is beginning"
The closing flag signals "this frame is complete"
Consecutive frames share flags: the ending flag of one frame serves as the starting flag of the next

Strategy 2: Start Flag Only (Implicit End)

Some protocols use only a starting flag, with the frame length encoded in the header:

[FLAG] [Header with Length] [Payload]

The receiver reads the length field after detecting the flag and knows exactly how many subsequent bytes belong to this frame. This approach saves one byte per frame but requires careful error handling.

Strategy 3: End Flag Only (Start-on-Any)

Rarely used, this approach delimits only frame endings, with receivers accumulating data until an end flag appears.

Symmetric Framing Advantages

•Easy Synchronization: Receiver can detect frame start at any point in the stream
•Error Recovery: If synchronization is lost, the next flag provides a recovery point
•Simple Implementation: State machine has clear entry and exit conditions
•Self-Delimiting: No need for external length information to determine frame boundaries
•Robust: Works even if clock synchronization is temporarily lost

Symmetric Framing Challenges

•Overhead: One or two extra bytes per frame (flags)
•Data Transparency Problem: What if payload contains flag byte? (solved by stuffing)
•Synchronization Latency: Must wait for flag to confirm frame boundary
•Processing Complexity: Requires escape sequence handling (covered later)
•Variable Overhead: Stuffing can increase frame size unpredictably

Inter-Frame Gap and Flag Filling:

When there is no data to transmit, a station may send continuous flag bytes to maintain synchronization. This practice, called flag filling or inter-frame time fill, serves several purposes:

Clock Recovery: Continuous transmission helps the receiver maintain bit-level synchronization
Link Monitoring: Active flag transmission indicates the link is operational
Quick Resynchronization: If frames are waiting, the receiver is already synchronized and can immediately process them

Flag Filling Example:

... 7E 7E 7E 7E [Frame 1] 7E 7E 7E [Frame 2] 7E 7E ...
                ^                  ^
                |                  |
    Multiple flags between frames are redundant but harmless

Receivers must handle multiple consecutive flags gracefully, treating them as inter-frame fill rather than empty frames.

Frame Structure Anatomy

To fully appreciate the role of flag bytes, we must understand the complete structure of a byte-oriented frame. Let's examine the anatomy of a PPP frame as a concrete example:

PPP Frame Format:

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

Field-by-Field Analysis:

PPP Frame Fields Explained
Field	Size	Value/Purpose	Significance
Opening Flag	1 byte	0x7E	Signals frame start; receiver synchronizes here
Address	1 byte	0xFF (broadcast)	Vestigial from HDLC; always broadcast in PPP
Control	1 byte	0x03 (UI frame)	Unnumbered Information; indicates no sequence numbers
Protocol	2 bytes	Variable (e.g., 0x0021 for IP)	Identifies encapsulated protocol (LCP, NCP, IP, etc.)
Data/Payload	0-1500 bytes	Variable	Actual user data; may contain any byte values
FCS	2-4 bytes	CRC checksum	Frame Check Sequence for error detection
Closing Flag	1 byte	0x7E	Signals frame end; may be shared with next frame

The Critical Role of Flags:

Examining this structure reveals why flag bytes are essential:

Boundary Identification: Without flags, where does one frame end and another begin? The receiver has no other indication.
Error Recovery: If bits are corrupted, the receiver can scan for the next flag to re-establish synchronization.
Variable Length Handling: PPP data fields can be 0-1500+ bytes. Flags handle any length transparently.
Continuous Operation: After the closing flag, the receiver immediately knows whether more data follows (another frame) or if the line is idle (continuous flags).

Minimum and Maximum Frame Sizes:

PPP with protocol field compression and ACFC (Address/Control Field Compression):

Minimum frame: 7 bytes (Flag + Protocol[1] + FCS[2] + Flag = minimum viable frame with no data)
Maximum frame: Typically 1500 bytes payload + overhead (MTU negotiated during LCP)

These bounds affect buffer allocation, timeout calculations, and flow control strategies—all topics where understanding the frame structure is foundational.

The Transparency Problem

Here's the critical question that leads to our next topics: What happens if the DATA field contains the byte 0x7E? The receiver would misinterpret it as a frame boundary, causing catastrophic parsing errors. This is the 'transparency problem,' and its solution—escape sequences and byte stuffing—is the subject of the next two pages.

Receiver State Machine

Implementing a byte-oriented frame receiver requires a carefully designed finite state machine (FSM). This state machine must correctly identify frame boundaries, accumulate payload bytes, and handle error conditions.

Basic Receiver States:

A minimal receiver FSM for flag-delimited frames has three core states:

HUNT State (Idle/Synchronizing)
- Waiting for a flag byte
- Discards all non-flag bytes
- Transitions to FRAME state upon receiving flag
FRAME State (Receiving)
- Accumulating payload bytes into a buffer
- Transitions to HUNT state upon receiving flag (frame complete)
- Must handle escape sequences (covered in later pages)
ERROR State (Recovery)
- Entered when buffer overflows or invalid sequences detected
- Discards current frame
- Transitions to HUNT to resynchronize

State Transition Diagram:

                 ┌──────────────────────────────┐
                 │         Non-Flag Byte        │
                 │   (Discard, stay in HUNT)    │
                 ▼                              │
            ┌─────────┐                    ┌────┴────┐
  Start ───►│  HUNT   │◄────── Error ──────│  ERROR  │
            │ (Idle)  │                    │(Recovery)│
            └────┬────┘                    └────▲────┘
                 │                              │
                 │ Flag Byte                    │ Buffer Overflow
                 │ (Begin Frame)                │ or Invalid Sequence
                 ▼                              │
            ┌─────────┐                         │
            │  FRAME  │─────────────────────────┘
            │(Receive)│
            └────┬────┘
                 │
                 │ Flag Byte (Frame Complete)
                 │
                 ▼
          [Deliver Frame to Upper Layer]
                 │
                 └──────► Back to HUNT

flag_receiver.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
# Simplified Flag Byte Receiver State Machine
# (Escape sequence handling omitted for clarity - covered in next page)
 
from enum import Enum, auto
from typing import Optional, List
 
class ReceiverState(Enum):
    HUNT = auto()    # Waiting for flag byte
    FRAME = auto()   # Receiving frame data
    ERROR = auto()   # Recovery mode
 
class FlagByteReceiver:
    """
    A basic byte-oriented frame receiver using flag byte delimitation.
    
    This implementation demonstrates the core state machine logic
    for frame extraction. Production implementations would add:
    - Escape sequence handling (byte stuffing)
    - CRC verification
    - Timeout handling
    - Statistics collection
    """
    
    FLAG_BYTE = 0x7E
    MAX_FRAME_SIZE = 2048  # Buffer limit
    
    def __init__(self):
        self.state = ReceiverState.HUNT
        self.buffer: List[int] = []
        self.frames_received = 0
        self.frames_dropped = 0
    
    def receive_byte(self, byte: int) -> Optional[bytes]:
        """
        Process a single received byte.
        Returns a complete frame (as bytes) when one is ready, None otherwise.
        """
        if self.state == ReceiverState.HUNT:
            return self._handle_hunt_state(byte)
        elif self.state == ReceiverState.FRAME:
            return self._handle_frame_state(byte)
        else:  # ERROR state
            return self._handle_error_state(byte)
    
    def _handle_hunt_state(self, byte: int) -> Optional[bytes]:
        """
        In HUNT state: wait for flag byte, discard everything else.
        """
        if byte == self.FLAG_BYTE:
            # Flag detected - transition to FRAME state
            self.buffer.clear()
            self.state = ReceiverState.FRAME
        # Non-flag bytes are silently discarded (inter-frame garbage)
        return None
    
    def _handle_frame_state(self, byte: int) -> Optional[bytes]:
        """
        In FRAME state: accumulate data bytes, detect frame end.
        """
        if byte == self.FLAG_BYTE:
            # End of frame detected
            if len(self.buffer) > 0:
                # Valid frame - deliver to upper layer
                frame = bytes(self.buffer)
                self.buffer.clear()
                self.frames_received += 1
                # Stay in FRAME state (this flag is also start of next frame)
                return frame
            # Empty frame (consecutive flags) - stay in FRAME state
            return None
        
        # Regular data byte - add to buffer
        if len(self.buffer) < self.MAX_FRAME_SIZE:
            self.buffer.append(byte)
            return None
        else:
            # Buffer overflow - enter ERROR state
            self.state = ReceiverState.ERROR
            self.frames_dropped += 1
            return None
    
    def _handle_error_state(self, byte: int) -> Optional[bytes]:
        """
        In ERROR state: wait for flag to resynchronize.
        """
        if byte == self.FLAG_BYTE:
            # Resynchronized - return to FRAME state
            self.buffer.clear()
            self.state = ReceiverState.FRAME
        return None
 
 
# Demonstration of receiver operation
def demonstrate_receiver():
    """
    Demonstrates flag byte receiver processing a stream of bytes.
    """
    receiver = FlagByteReceiver()
    
    # Simulated byte stream with two frames
    # Frame 1: [0x01, 0x02, 0x03]
    # Frame 2: [0x04, 0x05]
    byte_stream = [
        0x7E,                     # Start flag
        0x01, 0x02, 0x03,        # Frame 1 data
        0x7E,                     # End flag / Start flag (shared)
        0x04, 0x05,              # Frame 2 data
        0x7E,                     # End flag
        0x7E, 0x7E,              # Inter-frame fill (ignored)
    ]
    
    print("Processing byte stream...")
    for byte in byte_stream:
        frame = receiver.receive_byte(byte)
        if frame:
            print(f"  Frame received: {frame.hex()}")
    
    print(f"
Total frames received: {receiver.frames_received}")
    print(f"Frames dropped: {receiver.frames_dropped}")
 
 
if __name__ == "__main__":
    demonstrate_receiver()

Implementation Note

This simplified example omits escape sequence handling, which would add additional states and transitions. The complete state machine for PPP reception, which we'll develop in subsequent pages, includes escape byte detection and transparent data reconstruction.

Hardware vs. Software Implementation

The detection and processing of flag bytes can be implemented at different levels of the system stack. The choice between hardware and software implementation involves tradeoffs in performance, flexibility, and complexity.

Hardware Implementation:

Dedicated hardware (in NICs, communication chips, or FPGAs) can detect flag bytes at wire speed without CPU intervention:

Pattern Matching Circuits: Simple combinational logic can match the 8-bit flag pattern (0x7E) in a single clock cycle
Synchronization: Hardware can maintain bit-level timing while simultaneously detecting byte-level patterns
DMA Transfer: Once a frame is delimited, the complete frame can be transferred to memory via DMA
Interrupt Generation: CPU is only interrupted when complete frames are available, reducing overhead

Advantages of Hardware Detection:

Zero CPU overhead during frame reception
Predictable, deterministic timing
Can operate at the highest line speeds
Power efficient for embedded applications

Software Implementation:

In many applications, flag byte detection occurs entirely in software:

UART Reception: Hardware delivers individual bytes; software assembles frames
USB Serial: Similar to UART, with USB abstracting the physical layer
Virtual Interfaces: Software-only implementations for tunneling and testing

Advantages of Software Detection:

Maximum flexibility for protocol changes
Easier debugging and logging
No special hardware required
Can operate on any byte stream (files, sockets, etc.)

Hardware vs. Software Flag Detection Comparison
Aspect	Hardware Implementation	Software Implementation
Speed	Wire speed (Gbps+)	Limited by CPU (Mbps-Gbps depending on optimization)
CPU Overhead	Near zero	Proportional to data rate
Flexibility	Fixed protocol (may require firmware update)	Highly flexible, runtime configurable
Development Cost	Higher (ASIC/FPGA design)	Lower (standard programming)
Power Consumption	Lower per-byte cost	Higher for equivalent throughput
Debugging	Requires specialized tools	Standard debugging tools apply
Error Handling	May require software fallback	Fully programmable

Hybrid Approaches:

Modern systems often combine hardware and software processing:

Hardware Offload with Software Fallback:
- NIC detects flags and frames in hardware
- Complex or error cases escalate to software
- Example: Many Ethernet NICs detect framing errors, triggering software recovery
Hardware Assist with Software Processing:
- Hardware delivers flag-synchronized byte streams
- Software performs stuffing/unstuffing and higher-layer processing
- Example: Serial port hardware provides byte reception; PPP framing in driver
Full Software with DMA:
- Hardware does DMA transfers of raw bytes
- Software processes the complete buffer for flags
- Example: High-performance software routers with generic NICs

Performance Considerations:

For software implementation, the tight inner loop of flag detection must be optimized:

# Naive (slow) - function call overhead per byte
for byte in stream:
    if is_flag_byte(byte):
        process_frame_boundary()

# Optimized - inline comparison, minimal branching
FLAG = 0x7E
for byte in stream:
    if byte == FLAG:
        process_frame_boundary()

Additional optimizations include:

SIMD processing (checking multiple bytes simultaneously)
Branch prediction hints
Buffer pre-fetching
Lock-free frame queues for multi-core systems

Synchronization and Error Recovery

One of the most valuable properties of flag byte delimitation is its inherent ability to support automatic synchronization and error recovery. This capability is critical for robust communication over unreliable physical media.

Initial Synchronization:

When a receiver first connects to a byte stream, it has no knowledge of frame boundaries. The receiver enters HUNT mode and scans for a flag byte. This process is called hunting or flag hunting:

Receiver starts: Stream position unknown
   ↓
Enter HUNT mode: Scan for 0x7E
   ↓
Flag detected: Now synchronized at frame boundary
   ↓
Enter FRAME mode: Begin accumulating data

Key Property: The receiver can achieve synchronization starting from any point in the byte stream. There is no need for special initialization sequences or prior knowledge of frame timing.

Error-Induced Desynchronization:

Various error conditions can cause the receiver to lose synchronization:

Bit Errors: A flag byte could be corrupted to look like data, or vice versa
Byte Loss: Missing bytes can shift the receiver's interpretation of frame boundaries
Byte Insertion: Extra bytes (from noise) can similarly corrupt frame parsing
Buffer Overflows: If the receiver's buffer fills before a frame ends, the current frame must be abandoned

Error Recovery Mechanisms

•Automatic Resync: Upon detecting any error condition, the receiver returns to HUNT mode and waits for the next flag byte. This simple mechanism guarantees eventual recovery.
•CRC Verification: Even if framing is correct, CRC errors indicate data corruption. Corrupted frames are discarded and the receiver resynchronizes.
•Timeout Handling: If no flag is received within a maximum expected time, the receiver can assume loss of signal and reset.
•Maximum Frame Size: Enforcing a maximum frame size prevents runaway buffering if closing flag is never detected.
•Inter-Frame Gap Detection: Extended periods without received flags may indicate link failure.

Recovery Time Analysis:

How long does recovery take after an error? In the worst case:

The receiver must discard all bytes until the next valid flag
Maximum bytes discarded = Maximum frame size
At typical line rates, recovery is nearly instantaneous

Example:

Maximum frame size: 1500 bytes
Line rate: 10 Mbps
Maximum recovery time: 1500 × 8 bits ÷ 10 Mbps = 1.2 ms

This rapid recovery is one reason flag byte delimitation remains popular. Errors are isolated to single frames, and recovery is automatic.

Robustness Property

Flag-delimited framing is inherently self-synchronizing. No matter how badly the receiver loses sync—whether from noise, disconnection, or startup conditions—it can always recover by hunting for the next flag. This property makes flag-based protocols remarkably robust in practice.

Summary: Flag Bytes as Frame Delimiters

We have now established a thorough understanding of flag bytes as the foundational mechanism for frame delimitation in byte-oriented protocols. Let's consolidate the key concepts:

Key Takeaways

•Byte-oriented protocols process data in 8-bit units, aligning with hardware capabilities and simplifying implementation
•Flag bytes are reserved byte values (commonly 0x7E) that mark frame boundaries unambiguously
•Symmetric framing (flags at both ends) provides robust synchronization and error recovery
•Receiver state machines (HUNT, FRAME, ERROR) implement reliable flag detection
•Hardware and software implementations offer different tradeoffs in speed, flexibility, and complexity
•Self-synchronization ensures receivers can recover from any error by hunting for the next flag

The Transparency Problem:

We've carefully avoided one critical question: What happens when the payload data itself contains the flag byte value (0x7E)?

If user data can contain any arbitrary byte value—which is essential for transmitting binary files, compressed data, or encrypted content—then we will inevitably encounter 0x7E within payloads. Without special handling, the receiver would misinterpret these data bytes as frame boundaries, causing:

Premature frame termination
Payload corruption
Mis-synchronization
Complete communication failure

This is the data transparency problem, and its elegant solution involves escape sequences—the subject of our next page.

What's Next:

The next page explores how escape sequences solve the transparency problem by providing a mechanism to represent the flag byte within payload data. We'll examine the design principles, implementation details, and subtle complexities that arise when any byte sequence must be transmittable through a flag-delimited channel.

Page Complete

You now understand flag bytes as frame delimiters—their purpose, implementation, and role in creating reliable byte-oriented communication channels. The foundation is set for exploring escape sequences and byte stuffing, the mechanisms that complete the picture of transparent data transmission.