Data link layer — framing, error detection (CRC computation), MAC

1. Framing

WHY: The receiver gets a continuous stream ...10110101.... Without markers it can't tell one frame from the next. We need delimiters — but delimiters can also accidentally appear inside the data, so we need an escaping trick.

Methods

(a) Byte/character count — first field says "next $N$ bytes are my payload."

• Problem: if the count field itself is corrupted, the receiver loses sync forever.

(b) Byte stuffing (flag bytes) — put a special FLAG byte at start & end (e.g. 0x7E). If FLAG or the escape byte ESC appears in data, prefix it with ESC.

(c) Bit stuffing — frame is delimited by the flag pattern 01111110. To avoid this pattern in data, the sender inserts a 0 after every 5 consecutive 1s in the data.

2. Error Detection — CRC

WHAT is GF(2) arithmetic? Coefficients are bits. Addition = subtraction = XOR (no carries!). $1+1=0$. So polynomial long division uses XOR instead of subtraction.

Derivation from scratch — WHY the remainder makes it divisible

Let:

• $M(x)$ = message polynomial, degree $m-1$ (message has $m$ bits).
• $G(x)$ = generator, degree $r$ (so $r+1$ bits).

Step 1 — make room. Multiply message by $x^r$, i.e. append $r$ zeros: $M(x)\cdot x^r$ Why? This shifts the message left, reserving $r$ low-order slots for the check bits.

Step 2 — divide. Over GF(2): $M(x)\cdot x^r = Q(x)\,G(x) + R(x), \qquad \deg R < r$ $R(x)$ is the CRC remainder ($r$ bits, the FCS = Frame Check Sequence).

Step 3 — transmit. Send: $T(x) = M(x)\cdot x^r + R(x)$ Why is this divisible? Because over GF(2) addition = subtraction: $T(x) = Q(x)G(x) + R(x) + R(x) = Q(x)G(x) + 0$ since $R(x)+R(x)=0$ (XOR). So $T(x)$ is an exact multiple of $G(x)$.

Worked example (full long division)

Message $M = 1101$, generator $G = 1011$ (so $r=3$).

Why append 3 zeros? $\deg G=3 \Rightarrow$ 3 check bits → dividend = 1101000.

1101000 ÷ 1011   (XOR division)

1101000
1011
----
0110000
 1011
 ----
 01110 0
  1011
  ----
  01010
   1011
   ----
   0001   → remainder R = 001

Step-by-step (Why each step?): we XOR $G$ whenever the leading bit is 1, shift, repeat until we run out of bits. Leading 0 ⇒ bring next bit down (XOR with 000).

Transmit $T = 1101\,\underline{001} = 1101001$.

Receiver check: divide 1101001 by 1011 → remainder 000 ⇒ accept. If any bit flips, remainder ≠ 0 (for errors $G$ can catch).

What errors does CRC catch? (WHY choose good $G$)

An error pattern is $E(x)$; received = $T(x)+E(x)$. Error is undetected iff $E(x)$ is divisible by $G(x)$. So we pick $G$ to make that rare:

• All single-bit errors ($E=x^i$): caught if $G$ has $\ge 2$ terms.
• All odd numbers of bit errors: caught if $G$ has factor $(x+1)$.
• All burst errors of length $\le r$: caught (a burst is $x^i\cdot B(x)$ with $\deg B<r$; $G\nmid x^i$ and $\deg B<\deg G$).

3. MAC — Medium Access Control

Two flavours:

(a) CSMA/CD (wired Ethernet): Carrier Sense (listen before talking), Multiple Access, Collision Detection (keep listening while sending; if you hear garble ≠ your bits → collision). On collision: jam + binary exponential backoff (wait random time in $[0, 2^k-1]$ slots after the $k$-th collision).

(b) CSMA/CA (Wi-Fi): can't reliably detect collisions on radio, so avoid them — wait random backoff before sending, use ACKs, optional RTS/CTS.

Active Recall

Connections

• Physical Layer — provides the raw bit pipe framing sits on.
• Polynomials over GF(2) — math foundation of CRC.
• Hamming Code — error correction vs CRC's detection.
• Ethernet — uses CSMA/CD, 64-byte min frame, MAC addresses.
• Network Layer (IP) — hierarchical addressing contrasted with flat MAC.
• Stop-and-Wait & Sliding Window — reliability built atop framing + error detection.

Concept Map

Hinglish (regional understanding)