Framing: Byte Stuffing

In the context of data communication, transparency refers to the ability of a communication channel to transmit arbitrary data without the data being misinterpreted as control information. A transparent channel is one where any sequence of data bits or bytes can pass through unchanged, with no special patterns causing unintended behavior.

This concept is fundamental to protocol design. Without transparency, protocols would be limited to transmitting only "safe" data—data that doesn't contain reserved patterns. This would make binary data transmission impossible, severely limiting the utility of the communication system.

Byte stuffing (and its cousin, bit stuffing) exists precisely to create transparent channels from non-transparent ones. By encoding reserved patterns so they cannot appear literally in the data stream, stuffing transforms a channel with reserved patterns into one that can carry arbitrary content.

Let's establish a precise, mathematical definition of transparency that we can reason about formally.

Definition (Transparent Channel):

A communication channel C is transparent if and only if:

1. For any arbitrary input data D from the data domain 𝔻, the channel can transmit D without error
2. The received data equals the transmitted data: receive(transmit(D)) = D
3. No input data D causes the channel to malfunction or misinterpret the data as control information

More formally, let:

• 𝔻 = {0, 1}* be the set of all possible binary strings (the data domain)
• T: 𝔻 → 𝕊 be the transmit function (encoding)
• R: 𝕊 → 𝔻 be the receive function (decoding)
• 𝕊 be the set of valid signal sequences on the channel

The channel is transparent if:

∀D ∈ 𝔻: R(T(D)) = D

This states that encoding followed by decoding returns the original data for all possible inputs.

Definition (Non-Transparent Channel):

A channel is non-transparent if there exists at least one data value D such that transmission fails or corrupts the data:

∃D ∈ 𝔻: R(T(D)) ≠ D  or  T(D) is undefined

Example: Raw Flag-Delimited Channel (Non-Transparent)

Consider a channel that uses 0x7E as a frame delimiter without stuffing:

Transmit: T(D) = [0x7E] + D + [0x7E]
Receive:  R(S) = extract bytes between flags

This channel is non-transparent because:

• If D = [0x01, 0x7E, 0x02], then T(D) = [0x7E, 0x01, 0x7E, 0x02, 0x7E]
• The receiver sees: [0x7E] [0x01] [0x7E] [0x02] [0x7E]
• R(T(D)) = [0x01] (receiver stops at first interior 0x7E)
• R(T(D)) ≠ D, so transparency is violated

Example: Flag-Delimited Channel with Stuffing (Transparent)

With byte stuffing added:

Transmit: T(D) = [0x7E] + stuff(D) + [0x7E]
Receive:  R(S) = unstuff(extract bytes between flags)

Now:

• If D = [0x01, 0x7E, 0x02], then stuff(D) = [0x01, 0x7D, 0x5E, 0x02]
• T(D) = [0x7E, 0x01, 0x7D, 0x5E, 0x02, 0x7E]
• Receiver extracts: [0x01, 0x7D, 0x5E, 0x02]
• R(T(D)) = unstuff([0x01, 0x7D, 0x5E, 0x02]) = [0x01, 0x7E, 0x02] = D ✓

We will now formally prove that byte stuffing achieves transparency. This proof demonstrates why the seemingly simple stuffing mechanism actually works for all possible inputs.

Theorem: The byte stuffing encoding scheme as defined in PPP (RFC 1662) is transparent.

Proof Strategy: We will show that:

1. The stuffing function is well-defined for all inputs
2. The unstuffing function inverts stuffing exactly
3. No flags appear in stuffed data

Definitions:

Let:

• F = 0x7E (flag byte)
• E = 0x7D (escape byte)
• M = 0x20 (XOR mask)
• S = {F, E} ∪ ACCM (set of bytes requiring escaping)

The stuffing function stuff: Byte* → Byte* is:

stuff([]) = []
stuff([b] + rest) = 
  if b ∈ S: [E, b ⊕ M] + stuff(rest)
  else:      [b] + stuff(rest)

The unstuffing function unstuff: Byte* → Byte* is:

unstuff([]) = []
unstuff([E, x] + rest) = [x ⊕ M] + unstuff(rest)
unstuff([b] + rest) = [b] + unstuff(rest)  if b ≠ E

Lemma 1: Stuffing is total (well-defined for all inputs)

For any finite byte sequence D, stuff(D) is defined and finite.

Proof: The stuffing function processes one byte at a time, either outputting one byte (pass-through) or two bytes (escape sequence). Since D is finite, stuff(D) terminates after |D| iterations with output length between |D| and 2|D|. □

Lemma 2: Stuffed data contains no literal flags

For any input D: F ∉ stuff(D) (as a literal byte)

Proof: By case analysis on the stuffing function:

• If byte b = F, then b ∈ S, so output is [E, F ⊕ M] = [0x7D, 0x5E]. Neither is F.

• If byte b ≠ F and b ∈ S, output is [E, b ⊕ M]. E = 0x7D ≠ F. And b ⊕ M ≠ F because b ≠ F implies b ⊕ M ≠ F ⊕ M ⊕ M = F (since M ≠ 0x5E would make this equal F).

  Wait, we need to verify: if b ⊕ M = F, then b = F ⊕ M = 0x5E. But 0x5E ∉ S (not a control char, not F or E), so this case doesn't apply.

• If byte b ∉ S, output is [b]. Since F ∈ S, b ≠ F.

Thus no byte in stuff(D) equals F. □

Lemma 3: Unstuffing inverts stuffing

For any input D: unstuff(stuff(D)) = D

Proof by induction:

Base case: D = []. stuff([]) = []. unstuff([]) = []. ✓

Inductive case: Assume unstuff(stuff(rest)) = rest for |rest| < n.

For D = [b] + rest where |D| = n:

Case 1: b ∈ S

• stuff(D) = [E, b ⊕ M] + stuff(rest)
• unstuff([E, b ⊕ M] + stuff(rest)) = [b ⊕ M ⊕ M] + unstuff(stuff(rest))
• = [b] + rest = D ✓ (by induction hypothesis)

Case 2: b ∉ S

• stuff(D) = [b] + stuff(rest)
• Since b ∉ S, b ≠ E (because E ∈ S)
• unstuff([b] + stuff(rest)) = [b] + unstuff(stuff(rest))
• = [b] + rest = D ✓ (by induction hypothesis)

By induction, the property holds for all D. □

Main Theorem: Byte stuffing achieves transparency

Combining the lemmas:

• By Lemma 1, stuffing is defined for all inputs
• By Lemma 2, frame delimiters work correctly (no ambiguity)
• By Lemma 3, original data is perfectly recovered

Therefore, ∀D ∈ Byte*: R(T(D)) = D, proving transparency. □

The proof depends on maintaining a crucial invariant—a property that remains true throughout the stuffing process. Understanding this invariant provides deep insight into why byte stuffing works.

The Core Invariant:

After byte stuffing, the only occurrence of the byte value 0x7E (FLAG) in the complete frame is at the actual frame boundaries (start and end). All other occurrences have been escaped.

This invariant is what makes the receiver's job unambiguous: scan for 0x7E → that IS a frame boundary, guaranteed.

Invariant in Action:

Consider the frame construction process:

1. Original data: [any bytes, including 0x7E, 0x7D, etc.]

2. After stuffing: [bytes where 0x7E → 7D 5E, 0x7D → 7D 5D]
   Invariant: No 0x7E in stuffed content ✓

3. Add FCS (may contain 0x7E, 0x7D)
   After stuffing FCS: No 0x7E in stuffed FCS ✓

4. Complete frame: [0x7E] [stuffed content] [stuffed FCS] [0x7E]
   Invariant: Only boundary 0x7E bytes exist ✓

Why the Invariant Matters:

Without this invariant, the receiver faces an impossible parsing problem:

With invariant:     7E xx xx xx 7E → Exactly one frame
Without invariant:  7E xx 7E xx 7E → One frame or two frames??

The invariant transforms an ambiguous grammar into an unambiguous one.

Preserving the Invariant:

Several conditions must hold to maintain the invariant:

1. All flag bytes in data are escaped: The stuffing function must process every byte, not skipping any.

2. The escape sequence doesn't introduce flags: The escaped form [0x7D, 0x5E] contains no 0x7E.

3. Headers and FCS are also stuffed: Any part of the frame that could contain reserved bytes must be processed.

4. The escape byte itself is escaped: Otherwise, data containing [0x7D, 0x5E] would be misinterpreted.

Invariant Violation = Protocol Failure:

If any code path allows a literal 0x7E into the stuffed data:

def BAD_stuff(data):
    result = []
    for i, byte in enumerate(data):
        if byte == 0x7E and i % 2 == 0:  # BUG: only escape even positions!
            result.extend([0x7D, 0x5E])
        else:
            result.append(byte)
    return result

# Data: [0x7E, 0x7E] (two flags)
# BAD_stuff: [0x7D, 0x5E, 0x7E]  ← INVARIANT VIOLATED: literal 0x7E at position 2!
# Receiver: sees 7E at position 2 → FRAME BOUNDARY?!

This illustrates why complete, unconditional escaping is critical.

Transparency is closely related to the fundamental protocol design principle of data-control separation: the ability to distinguish between user data and protocol control information.

The Separation Problem:

Every communication protocol must solve this problem:

Incoming bit stream: 01001110 01111110 10110010 ...
                             ↑
                     Is this data or control?

Without a mechanism to separate data from control, the protocol cannot function. Different approaches exist:

Approach 1: Reserved Patterns (Without Stuffing)

• Reserve certain byte/bit patterns for control functions
• Data cannot contain these patterns
• Pro: Simple implementation
• Con: Not transparent (limits what data can be sent)

Approach 2: Reserved Patterns with Stuffing

• Reserve patterns for control
• Escape/stuff data to avoid contamination
• Pro: Fully transparent
• Con: Variable-length encoding, processing overhead

Approach 3: Out-of-Band Signaling

• Use separate channel for control vs. data
• Pro: Clean separation, no stuffing needed
• Con: Requires additional channel infrastructure

Approach 4: Length-Based Framing

• Include explicit length field in header
• Data is exactly that many bytes, regardless of content
• Pro: No stuffing overhead, fully transparent
• Con: Length field corruption is unrecoverable

Why Stuffing Excels at Error Recovery:

Length-based framing has a critical weakness: if the length field is corrupted, the receiver loses synchronization with no way to recover until some higher-layer mechanism intervenes.

Corrupted length field:
[Length: 1000] [100 bytes of data] [next frame start...]
                ↑
        Receiver expects 1000 bytes, reads into next frame!
        Synchronization completely lost.

With stuffing-based framing:

Corrupted data (any amount):
[FLAG] [corrupted bytes...] [FLAG] [next frame start...]
         ↑                    ↑
     Receiver may see garbage, but...
     ...FLAG always marks frame boundary!
     CRC catches corruption, frame discarded, resync automatic.

This self-synchronizing property is why stuffing remains popular for serial links where errors are common.

Transparency isn't just a data link layer concern—it appears throughout the protocol stack. Understanding how different layers achieve transparency illuminates the general principle.

Physical Layer Transparency:

The physical layer must transmit any bit pattern. Challenges:

• Clock recovery: Long runs of identical bits can cause timing drift
• DC balance: Some media require equal numbers of 0s and 1s
• Signal levels: Certain patterns may violate electrical specifications

Solutions:

• Line coding (Manchester, 4B/5B, 8B/10B): Ensure transitions and balance
• Scrambling: Randomize bit patterns
• These are physical-layer "stuffing" equivalents

Data Link Layer Transparency:

This is what we've been studying:

• Frame delimitation without content restrictions
• Byte stuffing, bit stuffing
• Escape sequences

Network Layer Transparency:

IP packets can contain any payload. Transparency concerns:

• IP-in-IP: Encapsulated packets must not confuse routers
• Fragmentation: Arbitrary split points must work
• Options: Variable-length headers must not confuse parsing

IP achieves transparency through length fields and protocol numbers, not stuffing.

Transport Layer Transparency:

TCP/UDP carry arbitrary data:

• Length field indicates exact payload size
• No reserved byte patterns in payload
• Fully transparent by design

Application Layer Transparency:

Many application protocols face transparency challenges:

• HTTP/1.x: Content-Length header or chunked encoding
• SMTP: Lines starting with "." are escaped (dot stuffing)
• Quoted-Printable: Encode non-printable characters
• Base64: Encode binary as ASCII text

The Layering Principle:

Each layer provides transparency to the layer above:

[Application data]
         ↓ (transparent to application)
[Transport segment]
         ↓ (transparent to transport)
[Network packet]
         ↓ (transparent to network)
[Data link frame] ← Byte stuffing here!
         ↓ (transparent to data link)
[Physical signal]

Each layer can send arbitrary data because the layer below provides transparency. This is the essence of protocol layering.

From an information-theoretic perspective, transparency relates to the concepts of encoding efficiency and channel capacity. Let's explore this connection.

Source Coding vs. Channel Coding:

• Source coding: Represents data as compactly as possible (compression)
• Channel coding: Represents data to survive channel errors and constraints

Byte stuffing is a form of channel coding—it encodes data to avoid reserved patterns, at the cost of some expansion.

Encoding Efficiency:

The efficiency of an encoding is the ratio of input size to output size:

Efficiency = |input| / |output|

For byte stuffing:

• Best case: Efficiency = 1.0 (no escaping needed)
• Average case (minimal ACCM, random data): Efficiency ≈ 0.992 (99.2%)
• Worst case: Efficiency = 0.5 (every byte escaped, 50%)

Suffix-Free Property:

An important property of good transparent encodings is being suffix-free (or prefix-free for decoding):

No valid encoded sequence is a suffix/prefix of another valid encoded sequence.

For byte stuffing:

• [0x7D, 0x5E] (escaped flag) is not a suffix of any non-escape sequence
• This ensures unambiguous decoding

Fixed-to-Variable Length Encoding:

Byte stuffing is a fixed-to-variable encoding:

• Input: Fixed meaning per byte
• Output: Variable length (1 or 2 bytes per input byte)

This contrasts with fixed-length encodings like 8B/10B where every 8 bits become exactly 10 bits.

8B/10B:        Always 8 → 10 bits,    Efficiency = 80%
Byte stuffing: Usually 8 → 8 bits,    Efficiency ≈ 99.2%
                Sometimes 8 → 16 bits

Byte stuffing is more efficient on average but has more variable output length.

Entropy Considerations:

The overhead of stuffing depends on the entropy (randomness) of the data:

• High-entropy data (random, compressed, encrypted): Uniform byte distribution → ~0.8% overhead
• Low-entropy data (text, structured): Few reserved bytes → ~0% overhead
• Adversarial data (all flag bytes): Maximally bad → 100% overhead

This means stuffing is adaptive: it adds overhead only where needed.

Information-Theoretic Lower Bound:

Is there a fundamental limit to how efficient a transparent encoding can be?

For an alphabet of 256 symbols with 2 reserved:

• 254 symbols can be encoded directly
• 2 symbols require escape sequences

Minimum average overhead for random data:

Overhead = 2/256 × 1 extra byte = 0.78%

Byte stuffing achieves this lower bound! It is optimal in the sense that no simpler scheme can achieve both transparency and lower average overhead for random data.

Comparison with Other Encodings:

Base64:      33% overhead, always (4 bytes per 3 input bytes)
Quoted-Print: ~0-200% overhead, variable
Byte stuffing: ~0-100% overhead, variable
8B/10B:      25% overhead, always
Bit stuffing: ~0-20% overhead, variable

Byte stuffing offers an excellent balance: very low average overhead with reasonable worst-case bounds.

How do we verify that an implementation correctly achieves transparency? Formal proofs give us confidence in the algorithm, but implementation bugs can still violate transparency. Let's develop a testing strategy.

Test Categories:

1. Boundary Cases: Test with data containing reserved bytes
2. Exhaustive Values: Test all possible single-byte values
3. Sequence Patterns: Test patterns that resemble escape sequences
4. Random Testing: Fuzz test with random data of various lengths
5. Worst-Case Testing: All reserved bytes, maximum overhead

Essential Test Cases:

We have explored transparency both theoretically and practically, establishing it as a fundamental property of well-designed communication systems. Let's consolidate our understanding:

The Module So Far:

1. Flag Bytes (Page 1): Frame boundary markers
2. Escape Sequences (Page 2): Reserved byte representation
3. Byte Stuffing (Page 3): Complete algorithm combining both
4. Transparency (This Page): Theoretical foundations and proofs

What's Next:

The final page of this module brings everything together with a complete PPP example. We'll trace a real IP packet through the entire PPP framing process, from application data to transmitted bits and back, seeing every concept from this module in action.