Computer Networks

Physical And Data Link Layers

Framing and Error Detection

Where does one message end and the next begin?

JrCodex·8 min read

Jr Codex Computer Networks Notes

Level: Beginner–Intermediate Prerequisites: Chapter 1: Signals, Media and Bandwidth Time to complete: ~20 minutes

Table of Contents

  1. Why Framing Is Needed
  2. Delimiting a Frame
  3. Parity — and Why It Is Insufficient
  4. Checksums
  5. Cyclic Redundancy Check
  6. Detection vs Correction
  7. Summary & Next Steps

1. Why Framing Is Needed

What the Physical Layer Delivers
─────────────────────────────────────────
  A continuous stream of bits:

    ...0110100101101110011001010111010...

  Where does one message end and the next begin?
  The physical layer has no idea — it moves bits,
  not meaning (Chapter 1).

  FRAMING is the data link layer's answer: mark
  the boundaries.
─────────────────────────────────────────

The Data Link Layer's Two Jobs
─────────────────────────────────────────
  1. FRAMING     turn a bit stream into discrete,
                 delimited units
  2. ERROR       detect frames corrupted in
     DETECTION   transit, and discard them

  Together they give the layer above something it
  can rely on: "whatever arrives, arrives intact
  and in identifiable units."

  Note it does not promise DELIVERY — only that
  what is delivered is correct.
─────────────────────────────────────────

2. Delimiting a Frame

Four Approaches
─────────────────────────────────────────
  LENGTH FIELD
    A header field says how many bytes follow.
    Simple. Fragile: corrupt the length and the
    receiver loses framing for every subsequent
    frame.

  FLAG BYTES with BYTE STUFFING
    A special byte marks boundaries — say 0x7E.
    But what if the DATA contains 0x7E?
    Escape it: insert an escape byte before it, and
    escape the escape byte too.
    Used by PPP.

  BIT STUFFING
    The flag is a bit pattern, say 01111110.
    After five consecutive 1s in the data, the
    sender INSERTS a 0. The receiver removes it.
    So the flag pattern can never occur in data.

  PHYSICAL LAYER CODING VIOLATIONS
    Use a signal pattern that is INVALID as data —
    impossible to confuse with content.
    Ethernet's preamble does this.
─────────────────────────────────────────

FLAG, ESC = 0x7E, 0x7D
 
def byte_stuff(payload: bytes) -> bytes:
    """Make the flag byte impossible inside the payload."""
    out = bytearray([FLAG])
    for b in payload:
        if b in (FLAG, ESC):
            out.append(ESC)
            out.append(b ^ 0x20)          # XOR so the escaped byte is not the flag either
        else:
            out.append(b)
    out.append(FLAG)
    return bytes(out)
 
def byte_unstuff(frame: bytes) -> bytes:
    body, out, esc = frame[1:-1], bytearray(), False
    for b in body:
        if esc:
            out.append(b ^ 0x20); esc = False
        elif b == ESC:
            esc = True
        else:
            out.append(b)
    return bytes(out)
 
data = bytes([0x01, 0x7E, 0x02, 0x7D])      # payload CONTAINS both special bytes
print(byte_stuff(data).hex())               # 7e 01 7d 5e 02 7d 5d 7e
print(byte_unstuff(byte_stuff(data)) == data)   # True
The Cost of Stuffing
─────────────────────────────────────────
  A payload full of flag bytes DOUBLES in size.

  This is why Ethernet does not use stuffing — it
  uses a fixed preamble and a length/type field
  instead, and relies on the physical layer's
  coding to mark the start.
─────────────────────────────────────────

3. Parity — and Why It Is Insufficient

The Simplest Scheme
─────────────────────────────────────────
  Append one bit making the total number of 1s
  even (even parity).

    1011001  ──► four 1s ──► parity 0 ──► 10110010
    1011000  ──► three 1s ──► parity 1 ──► 10110001

  Receiver counts the 1s. Odd count ──► error.
─────────────────────────────────────────

Why It Is Almost Useless on a Network
─────────────────────────────────────────
  It detects ANY ODD number of bit errors.
  It detects NO EVEN number of bit errors.

  Two bits flip ──► parity unchanged ──► the error
  passes silently.

  And network errors are usually BURSTS — a noise
  spike corrupts a run of adjacent bits, not one
  isolated bit. A burst has a roughly 50% chance of
  flipping an even number.

  So parity catches about half of real errors.
  That is not error detection; it is a coin flip.
─────────────────────────────────────────

4. Checksums

The Internet Checksum
─────────────────────────────────────────
  Used by IP, TCP and UDP.

  1. Treat the data as a sequence of 16-bit words
  2. Sum them with one's-complement arithmetic
     (carries wrap around and are added back)
  3. Take the one's complement of the result
  4. The receiver sums everything INCLUDING the
     checksum; the result should be all 1s
─────────────────────────────────────────

def internet_checksum(data: bytes) -> int:
    if len(data) % 2:
        data += b'\x00'
    total = 0
    for i in range(0, len(data), 2):
        total += (data[i] << 8) + data[i + 1]
        total = (total & 0xFFFF) + (total >> 16)      # END-AROUND CARRY
    return ~total & 0xFFFF
 
payload = b"Hello, network!"
ck = internet_checksum(payload)
print(f"checksum: 0x{ck:04x}")
 
# The receiver's check: summing data + checksum gives zero.
print(internet_checksum(payload + ck.to_bytes(2, 'big')) == 0)     # True
Its Weakness
─────────────────────────────────────────
  Addition is COMMUTATIVE, so reordering the words
  does not change the sum.

  Swap two 16-bit words in the payload and the
  checksum is identical. It also misses some
  patterns of compensating errors.

  It is cheap to compute in software, which is why
  the transport layer uses it — and it is why the
  LINK layer uses something stronger.
─────────────────────────────────────────

5. Cyclic Redundancy Check

The Idea
─────────────────────────────────────────
  Treat the message as a large binary POLYNOMIAL.
  Divide it by a fixed GENERATOR polynomial. Send
  the REMAINDER as the CRC.

  The receiver divides the whole received frame
  (data + CRC) by the same generator. A remainder
  of ZERO means no detected error.

  It is polynomial long division in GF(2), where
  addition and subtraction are both XOR — which
  makes it trivial in hardware.
─────────────────────────────────────────

def crc32_bitwise(data: bytes) -> int:
    """CRC-32, as used by Ethernet. Shown bitwise to make the mechanism visible."""
    crc = 0xFFFFFFFF
    for byte in data:
        crc ^= byte
        for _ in range(8):
            crc = (crc >> 1) ^ (0xEDB88320 if crc & 1 else 0)   # the generator
    return crc ^ 0xFFFFFFFF
 
frame = b"payload data here"
print(f"CRC-32: 0x{crc32_bitwise(frame):08x}")
 
# One flipped bit changes the CRC completely:
corrupted = bytearray(frame); corrupted[3] ^= 0x01
print(f"corrupt: 0x{crc32_bitwise(bytes(corrupted)):08x}")
WHAT CRC-32 GUARANTEES
─────────────────────────────────────────
  With a well-chosen 32-bit generator, it detects:

    ✓ ALL single-bit errors
    ✓ ALL double-bit errors
    ✓ ALL errors with an ODD number of bits
    ✓ ALL burst errors up to 32 bits long
    ✓ 99.99999998% of longer bursts

  Compare parity's ~50%.

  These are PROVABLE properties of the polynomial,
  not statistical hopes — which is why CRC is the
  standard for link-layer error detection
  everywhere.
─────────────────────────────────────────

Why Bursts Specifically
─────────────────────────────────────────
  Real errors on a physical medium are bursty: an
  electrical spike, a moment of radio interference,
  a scratch on a disk.

  CRC generators are chosen precisely to catch
  bursts up to the CRC's own length. That match
  between the error model and the code is what
  makes it so effective.
─────────────────────────────────────────

6. Detection vs Correction

Two Strategies
─────────────────────────────────────────
  ERROR DETECTION + RETRANSMISSION (ARQ)
    Detect it, discard the frame, ask again.
    + low overhead — just the CRC
    - needs a return path and costs a round trip
    Used by: Ethernet (discard; TCP retransmits),
    wifi (link-level retry)

  FORWARD ERROR CORRECTION (FEC)
    Send enough redundancy to RECONSTRUCT the
    original without asking.
    + no round trip; works with no return path
    - significant overhead, always paid
    Used by: satellite, deep space, optical
    storage, mobile radio
─────────────────────────────────────────

Choosing Between Them
─────────────────────────────────────────
  Use ARQ when a round trip is CHEAP.
    A LAN's RTT is under a millisecond.
    Retransmitting costs almost nothing.

  Use FEC when a round trip is EXPENSIVE or
  IMPOSSIBLE.
    Earth to Mars is 4-24 minutes ONE WAY. Asking
    for a retransmission is not a strategy.
    Live streaming to thousands cannot retransmit
    per viewer.
─────────────────────────────────────────

Where This Reappears
─────────────────────────────────────────
  Ethernet DETECTS and DISCARDS. It never
  retransmits — that is deliberately left to TCP
  (Module 4).

  This is Module 1, Chapter 1's END-TO-END
  PRINCIPLE: the link layer does the cheap local
  check, and the reliability that actually matters
  is implemented once, end to end, where it can be
  guaranteed.
─────────────────────────────────────────

7. Summary & Next Steps

Key Takeaways

  • The data link layer's two jobs are framing a bit stream into delimited units and detecting corruption — it guarantees correctness of what arrives, not delivery.
  • Parity detects only an odd number of flipped bits, so it catches roughly half of real errors, which are typically bursts.
  • CRC-32 provably detects all single, double and odd-bit errors and all bursts up to 32 bits, because the generator is chosen to match the physical error model.
  • Detection plus retransmission suits cheap round trips; forward error correction suits links where asking again is expensive or impossible.

Concept Check

  1. Why is parity nearly useless against real network errors specifically?
  2. What property of addition makes the internet checksum blind to reordered words?
  3. Why does Ethernet detect errors but never retransmit, and which principle is that?

Next Chapter

→ Chapter 3: MAC Addressing and Ethernet

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index | Back to Computer Networks Index