Skip to content
Tutorials Center
My learning

Topics

Lesson 11 of 79 ยท Data Link Layer

Framing and Error Detection

Learn how the data link layer marks frame boundaries with byte and bit stuffing and detects corruption with parity, checksums and CRC, with live Python.

The physical layer delivers a stream of bits and nothing else. It does not say where one message ends and the next begins, and it does not promise that every bit arrived the way it left. Wires pick up noise, radio links fade, and a single flipped bit can turn "pay 100" into "pay 900". The data link layer fixes both problems with two jobs: framing (cutting the bit stream into frames) and error detection (noticing when a frame was damaged).

This lesson covers both. You will build byte stuffing and bit stuffing, then work through parity, the Internet checksum and the cyclic redundancy check (CRC) that almost every real link layer uses. Detection only tells the receiver that something is wrong. Fixing it is the job of error correction or of retransmission, which comes in flow control and ARQ. The signals underneath were described in Line Coding and Modulation.

Framing: where does a frame start and end?

If a sender simply pushed bytes onto the wire, the receiver could not tell where a frame begins. There are four common ways to mark boundaries:

  • Character count. The header holds the length. Simple, but one corrupted length field makes the receiver lose its place for good.
  • Flag bytes with byte stuffing. A special byte marks both ends of a frame.
  • Flag bits with bit stuffing. A special bit pattern marks the ends (used by HDLC).
  • Physical-layer violations. Use a signal pattern that cannot occur in data, such as the illegal symbols in the line codes from the previous chapter.

The flag approach has an obvious problem: what if the payload itself contains the flag? The answer is stuffing: the sender changes the payload so the flag can never appear inside it, and the receiver undoes the change.

flowchart LR
    A["Network layer packet"] --> B["Add header<br/>and trailer"]
    B --> C["Stuff the payload"]
    C --> D["Flag | frame | Flag"]
    D --> E["Bit stream on the wire"]

A frame is the unit the link layer sends: a payload wrapped in a header, a trailer with an error check, and boundary markers.

Byte stuffing

In PPP the flag byte is 0x7E. To protect it, PPP uses an escape byte 0x7D. When the payload contains 0x7E or 0x7D, the sender writes 0x7D followed by the original byte XOR 0x20. The receiver reverses this: after a 0x7D, it XORs the next byte with 0x20. So 0x7E travels as 7D 5E, and 0x7D as 7D 5D.

Bit stuffing

HDLC uses the flag 01111110 (six ones between zeros). To keep six ones from appearing in the data, the sender inserts a 0 after every five consecutive ones, whatever comes next. The receiver deletes a 0 that follows five ones. Bit stuffing works on any number of bits, not only whole bytes, and its cost depends on the data: random data costs about 1 extra bit per 62.

Python Byte stuffing and bit stuffing

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Look at the output: the payload bytes 7e and 7d become 7d 5e and 7d 5d, so the only 7e bytes in the frame are the two flags. In the bit version, the long run of ones in the payload received three extra zeros, and the framed result never contains six ones in a row except in the flags.

Error detection: the idea of redundancy

Every detection method adds redundant bits that are computed from the data. The receiver recomputes them and compares. If they differ, the frame is damaged. The more redundancy, the more errors you catch, so the design question is how to get a lot of protection from a few bits.

A useful measure is the Hamming distance between two bit strings: the number of positions where they differ. 10110 and 10011 differ in two places, so the distance is 2. If the legal codewords of a scheme are all at least distance d apart:

  • it can detect up to d - 1 bit errors, because that many flips can never turn one legal word into another;
  • it can correct up to โŒŠ(d - 1) / 2โŒ‹ errors by choosing the nearest legal word.

A single parity bit gives distance 2: it detects one flipped bit and corrects none. The next lesson uses larger distances to correct errors.

Parity

Even parity appends one bit so the total number of ones is even. The receiver counts ones and complains if the count is odd. It is cheap and catches every odd number of flipped bits. It misses every even number: flip two bits and the parity looks perfect again. Real noise often arrives in bursts that damage several adjacent bits, which is why parity alone is weak. Two-dimensional parity (a parity bit for each row and each column of a block of bytes) catches more, and can even locate and fix a single flipped bit.

The Internet checksum

IP, ICMP, UDP and TCP use a simple sum. Treat the data as a sequence of 16-bit words, add them with end-around carry (any carry out of bit 16 is added back into the low bits), and send the ones' complement of the sum. The receiver adds everything including the checksum and expects all ones. The method is easy to do in software, and it appears in the IPv4 header. Its weakness is that addition does not care about order: swapping two words leaves the sum unchanged, so a reordering error goes unnoticed. For the link layer, where bursts and hardware are the norm, CRC is the better tool.

CRC: polynomial division

A cyclic redundancy check treats a bit string as the coefficients of a polynomial over arithmetic modulo 2. The bits 10011 mean xโด + x + 1. Sender and receiver agree on a generator polynomial G of degree r. The sender:

  1. appends r zero bits to the message;
  2. divides the result by G using modulo-2 long division, where subtraction is XOR with no borrow;
  3. replaces the appended zeros with the remainder.

The transmitted codeword is now exactly divisible by G. The receiver divides what it got by G; a remainder of zero means "no error detected". Hardware does this division with a small shift register and a few XOR gates, which is why CRC is so fast.

A well-chosen generator of degree r detects:

  • all single-bit errors;
  • all double-bit errors (for a suitable G and a limited frame length);
  • any odd number of errors, if G has the factor x + 1;
  • every burst of length up to r bits;
  • most longer bursts, missing only about 1 in 2r of them.

Ethernet uses the 32-bit CRC-32 polynomial; a long burst slips through with probability about 1 in 4 billion.

Python CRC by long division, plus parity and the Internet checksum

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The CRC of 1101011011 with generator 10011 is 1110, giving the codeword 11010110111110. Every single flip and the four-bit burst are detected, because the burst is no longer than the 4-bit CRC. The parity example shows the weakness: after two flips the word still has an even number of ones, so parity says "fine". The two checksums are identical (0x6e10) even though the words were swapped, which is the Internet checksum's blind spot. The last line uses Python's built-in CRC-32, the same polynomial as Ethernet.

CRC detects accidental errors, not tampering. Anyone who changes a frame on purpose can simply recompute the CRC. For protection against attackers you need a cryptographic MAC, covered in Cryptography for Networking.

Where each method lives

Method Typical place Strength
Parity Serial lines, memory Cheap, catches odd numbers of errors
Internet checksum IP, TCP, UDP, ICMP Easy in software, weak on reordering
CRC-16 / CRC-32 Ethernet, Wi-Fi, PPP, storage Strong against bursts, easy in hardware

Layers duplicate checks on purpose: the link layer checks each hop, while the transport layer checks end to end, because a faulty router can corrupt a packet after the link CRC has passed.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In HDLC bit stuffing, when does the sender insert a 0?

    The flag is 01111110, so the sender breaks up any run of five ones by inserting a 0. The receiver removes the 0 that follows five ones.
  2. 2. A scheme's valid codewords are all at least Hamming distance 4 apart. How many bit errors can it always detect?

    It detects up to d - 1 errors, so 3. With fewer than 4 flips a valid word can never turn into another valid word.
  3. 3. Why can a single even-parity bit miss an error?

    Parity catches every odd number of flips but no even number. Burst errors often flip several bits.
  4. 4. What does a remainder of zero tell a CRC receiver?

    A zero remainder means the received word is divisible by the generator. Some rare error patterns are also divisible, and CRC gives no protection against deliberate changes.

Summary

  • Framing marks where frames start and end; stuffing keeps the flag out of the payload (byte stuffing with an escape byte, bit stuffing after five ones).
  • Error detection adds redundancy computed from the data; the receiver recomputes and compares.
  • Hamming distance d detects d - 1 errors and corrects โŒŠ(d - 1) / 2โŒ‹.
  • Parity is cheap but misses even numbers of flips; the Internet checksum is simple but order-blind.
  • CRC divides the message by a generator polynomial modulo 2, catches all bursts up to its length, and is used by Ethernet and Wi-Fi.

Next: Error Correction and Hamming Codes