Why Character Stuffing is Used?

Character stuffing, also known as byte stuffing, is used to ensure that special control characters, particularly frame delimiters (like start and end flags), within a data frame are not mistaken for actual frame boundaries by the receiver.

The Challenge of Data Framing

In data communication, data is often sent in discrete blocks called frames. To identify where one frame ends and the next begins, special bit patterns or characters, known as flag bytes or delimiters, are used at the start and end of each frame.

For example, a common flag byte might be 01111110.

The Problem: Flags in the Data

A problem arises if the data being transmitted itself contains the same bit pattern as the flag byte. If the receiver is simply scanning the incoming bit stream for the flag pattern to determine frame boundaries, it might incorrectly interpret an occurrence of the flag pattern within the data as the end of the frame. This leads to:

• Premature frame termination.
• Incorrect data extraction.
• Loss of synchronization between the sender and receiver regarding frame boundaries.

The Solution: Character Stuffing

Character stuffing is a technique employed at the sender side to prevent this confusion. When the sender's data link layer encounters the flag byte pattern within the data portion of the frame, it inserts a special escape character (often 01111101, but can vary) before that data byte.

Additionally, if the escape character itself appears within the data, the sender also inserts another escape character before it. This ensures that the receiver knows the following character is part of the data, not a control character.

Here's a simplified illustration:

• Flag Byte: F
• Escape Byte: E
• Original Data: A B F C E D F

The sender scans the data:

1. Encounters F: Inserts E before it. Data becomes A B E F C E D F.
2. Encounters E: Inserts E before it. Data becomes A B E F C E E D F.
3. Encounters F: Inserts E before it. Data becomes A B E F C E E D E F.

The frame sent would look like: F A B E F C E E D E F F (where the first and last F are the actual frame flags).

Receiver's Role

Upon receiving the frame, the receiver's data link layer performs the reverse process:

1. It identifies the start flag F.
2. It reads subsequent bytes.
3. When it encounters the escape character E, it removes the E and treats the next character literally as data, even if it's an F or another E.
4. It continues this process until it reaches the actual end flag F (which is not preceded by an E).

Following the example:

• Received Data (between flags): A B E F C E E D E F
• Receiver scans:
  • A (Data)
  • B (Data)
  • E: Remove E, next byte F is data. Data is now A B F.
  • C (Data). Data is now A B F C.
  • E: Remove E, next byte E is data. Data is now A B F C E.
  • E: Remove E, next byte F is data. Data is now A B F C E F.

The original data A B F C E D F is incorrectly reconstructed in this manual walk-through example due to a typo in the original data string. Let's correct and retry.

• Original Data: A B F C E D F
• Sender scans the data:
  1. A, B (No change)
  2. F: Insert E. Data is now A B E F.
  3. C (No change). Data is now A B E F C.
  4. E: Insert E. Data is now A B E F C E E.
  5. D (No change). Data is now A B E F C E E D.
  6. F: Insert E. Data is now A B E F C E E D E F.
• Frame Sent (between flags): A B E F C E E D E F
• Receiver scans:
  • A (Data) -> A
  • B (Data) -> A B
  • E: Remove E, next byte F is data -> A B F
  • C (Data) -> A B F C
  • E: Remove E, next byte E is data -> A B F C E
  • D (Data) -> A B F C E D
  • E: Remove E, next byte F is data -> A B F C E D F

The original data A B F C E D F is correctly recovered.

Addressing Resynchronization After Errors

As highlighted by the reference:

The character stuffing method gets around the problem of re synchronization after an error by having each frame start and end with special bytes.

By using character stuffing, the unique flag byte pattern is guaranteed to appear only at the actual start and end of the frame (when not preceded by an escape character). If an error causes the receiver to lose track of the current position within a frame, it can resynchronize by simply scanning the incoming bit stream for the unique, unstuffed flag byte pattern. Once found, it knows that's either the start or end of a frame, allowing it to re-establish frame boundaries. Without stuffing, a flag pattern appearing inside the data could cause false resynchronization points.

In summary, character stuffing is essential for reliable data transmission using flag bytes as frame delimiters because it prevents data content from being misinterpreted as control information, thereby maintaining proper frame boundaries and enabling effective resynchronization after transmission errors.