Data Link Layer: Framing Methods, Bit/Byte Stuffing, and Error Detection (CRC)
The Data Link Layer (Layer 2) takes an unstructured stream of raw bits from the Physical Layer and packages them into discrete manageable units called Frames.
1. What is Framing?
Framing is the method of marking the beginning and the end of a packet of data so the receiver knows where one frame starts and where it stops.
The 4 Standard Framing Methods:
Four Standard Framing Techniques
1. Character Count
A number in the header specifies the total characters in the frame
2. Byte Stuffing
Uses special Flag bytes (`FLAG`); escapes internal flag bytes with `ESC`
3. Bit Stuffing
Inserts a 0 after five consecutive 1s to avoid confusing flag `01111110`
4. Physical Layer Coding Violations
Uses illegal signal states (e.g., High-High in Manchester encoding)
Understanding Bit Stuffing (The HDLC Method):
- In bit-oriented protocols, every frame starts and ends with a special 8-bit flag byte:
01111110(a zero, six ones, and a zero). - The Problem: What if the user’s actual image or file contains the pattern
01111110? The receiver will mistakenly think the frame has ended! - The Solution (Bit Stuffing):
- Sender: Whenever the sender sees five consecutive 1s (
11111) in the data stream, it automatically inserts an extra 0 right after it (111110). - Receiver: Whenever the receiver sees five consecutive 1s followed by a 0, it automatically destuffs (deletes) that 0 to restore the original data!
- Sender: Whenever the sender sees five consecutive 1s (
2. Error Detection Techniques
During transmission, electrical noise can flip bits (turning 0 into 1). The Data Link Layer detects these errors:
1. Parity Check (Simple Parity & 2D Parity)
- Adds 1 extra parity bit to make the total number of 1s even (Even Parity) or odd (Odd Parity).
- Limitation: Can only detect single-bit errors. If 2 bits flip simultaneously, parity check fails to detect the error.
2. Checksum (Used in TCP and IP)
- Data is split into 16-bit integers, added together using 1’s complement arithmetic, and inverted. The receiver adds all segments; if the sum is all 1s, data is error-free.
3. CRC (Cyclic Redundancy Check - Polynomial Code)
- The most powerful and widely used error detection method in modern networking (Ethernet, Wi-Fi, 4G/5G).
- How it Works (Modulo-2 Binary Division):
- Both sender and receiver agree on a Generator Polynomial G(x) of degree r (e.g., x^3 + x + 1 represented as binary
1011). - The sender appends r zeros to the end of the data frame.
- The sender divides this extended data by the generator binary using Modulo-2 XOR division.
- The remainder of this division (the CRC checksum) replaces the r zeros at the end of the frame.
- The receiver divides the entire received frame by the same generator. If the remainder is ZERO (000), there is NO error!
- Both sender and receiver agree on a Generator Polynomial G(x) of degree r (e.g., x^3 + x + 1 represented as binary
💡 DAVV Exam Tip
Question (10 Marks): “Explain Bit Stuffing and Byte Stuffing with examples. How does CRC detect errors? Solve a numerical example.”
- Give the Bit Stuffing rule: Insert a 0 after five consecutive 1s (
11111).- Explain CRC modulo-2 division (XOR subtraction where 1 ⊕ 1 = 0 and 1 ⊕ 0 = 1).
- Show that a remainder of 0 indicates valid error-free transmission.