DLL services → framing (byte / bit stuffing) → error types → detection: parity, 2D parity, CRC, checksum → correction.

Tutorial 4 = calculations on parity, CRC and checksum. Practise each by hand.

This part is 3.1 introduction and 3.2 data link control (framing, error control). Part 2 is 3.3 media access control.

Seen again Ch 1 Part 2, slide 28: Data link layer overview

Framing = packing bits into frames so the receiver knows where each one starts and ends (like envelopes).

The destination address says where it goes; the sender address lets the receiver acknowledge it.

Trap Flow control protects the RECEIVER from being flooded; congestion control (Ch 9) protects the NETWORK.

Seen again Ch 3 Part 2, slide 2: Media access control

Seen again Ch 9, slide 6: Flow and error control at the transport layer

Character (byte) oriented: frame length is a whole number of bytes. Bit oriented: any number of bits.

A flag byte marks the start and end of every frame.

Problem: the flag pattern can appear inside the data.

Trap ESC itself must also be escaped, or the receiver would drop a real ESC byte from the data.

After five 1s in a row, the sender always inserts a 0, even if the next bit is already 0. So 01111110 can never appear in the data.

Memory trick Count to five 1s, then add a 0. Restart the count after the stuffed 0.

Burst: TWO or more bits changed (not necessarily next to each other).

Burst length = from the first corrupted bit to the last, counting the good bits in between.

The faster the link, the more bits a burst of noise hits.

Trap A burst of length 5 may corrupt only 3 bits: the length counts from first to last bad bit.

Same 2 ms of noise: 2 bits on a slow link, 2 million on a fast one. That is why burst errors are worse at high rates.

Every detection method sends EXTRA (redundant) bits along with the data.

Parity check · CRC · checksum.

Sender: a generator adds redundant bits. Receiver: a checker recomputes them and accepts or discards.

Memory trick Even parity bit = 1 if the data has an ODD number of 1s (so the total becomes even).

Each 7-bit ASCII character gets one even-parity bit: count the 1s and add 0 or 1 to make the count even.

Trap Two flipped bits keep the parity the same, so simple parity misses every even number of errors.

2D parity: arrange the data in rows; add a parity bit to each row AND a parity row for the columns.

Row parities catch which row; column parities catch which column. One bad bit = the crossing point, so it can be corrected.

It misses 4 errors that sit at the corners of a rectangle: every row and column still has even parity.

Sender: append n zeros (n = divisor length - 1), divide, the remainder is the CRC. Send data + CRC.

Receiver: divide data + CRC by the same divisor. Remainder 0 → accept; otherwise reject.

Each 1 bit is a power of x: 1000011 = x⁶ + x + 1.

Division uses XOR, with no carries.

Memory trick Polynomial → bits: write a 1 for every power present, from the highest down to x⁰. x³ + x + 1 = 1011.

Dataword 1001 + 000 ÷ 1011 → remainder 110 → codeword 1001110.

When the leftmost bit of the current remainder is 0, divide by 0000 instead (just bring the next bit down).

Remainder (syndrome) 000 → accept. Anything else → discard.

A zero remainder means no error detected.

Trap Generator 1011 has 4 bits → append 3 zeros and the CRC is 3 bits.

CRC-32 is the one used in LANs (Ethernet’s FCS).

Seen again Ch 4, slide 4: The Ethernet frame’s CRC field

CRC catches single, double, odd-count and burst errors, and is fast in hardware.

Length r + 1 slips by with probability 1/2^(r-1); longer ones with 1/2^r.

Memory trick Degree = highest power. x⁶ + 1 → 6 → all bursts up to 6 bits.

Higher degree → longer bursts caught → that’s why LANs use CRC-32.

Checksum: add all words (one’s complement), complement the sum, send it. The receiver adds everything; complemented result 0 = OK.

Seen again Ch 9, slide 20: The UDP and TCP checksum

Steps: split into 16-bit words, checksum field = 0, add with one’s complement, complement → checksum.

Memory trick One’s complement addition: any carry out of the top bit wraps around and is added back at the bottom.

Receiver: add all words INCLUDING the checksum, complement. 0 → accept, anything else → reject.

Complement = flip every bit.

Nonzero after complementing → corrupted.

Two ways to fix errors: send it again, or send enough redundancy to fix it on arrival (FEC).

Retransmission is bad for wireless (high bit error rate → too many resends) and for real-time multimedia (waiting = delay).

FEC fixes errors at the receiver with no resend.

XOR trick: send R = XOR of all blocks; any ONE lost block = XOR of R with the rest.

Interleave: spread each packet’s chunks across several transmitted packets. Losing one packet then costs each original packet only one chunk, which multimedia can tolerate.

The lost packet (orange) removes one chunk from each of the five packets instead of a whole packet.