Data link layer: error detection, medium access control, Ethernet

Link-layer service

Definition. The data-link layer transfers frames across one link between directly connected nodes. It may provide framing, local addressing, medium access, and error detection; reliability and flow control are optional design choices. End-to-end delivery across multiple links is handled by higher layers. Example. A router receives one Ethernet frame and creates a new frame for its next link. Exam point. Link-layer delivery is hop-by-hop, not host-to-host across the full Internet path.

Framing

Definition. Framing marks where one link-layer unit begins and ends in a stream of bits. Methods include length fields, byte/bit delimiters with escaping, and fixed-size frames. The receiver must distinguish payload bits from control delimiters. Example. A delimiter byte occurring inside payload can be escaped before transmission and unescaped at the receiver. Exam point. Framing overhead and error detection are related but distinct functions.

Error detection and correction

Definition. Error detection adds redundant bits so a receiver can detect some corruptions. Error correction adds enough structure to infer and repair certain errors. Detection probability depends on the error pattern and code; a checksum does not guarantee detection of every possible corruption. Example. A parity bit detects every odd number of flipped bits in its protected block but misses any even number of flips. Exam point. Do not claim that a detected-error code corrects the error unless a correction method is specified.

Parity check

Definition. Even parity chooses the parity bit so the total number of 1s is even; odd parity makes that total odd. A single parity bit detects all odd-weight error patterns and misses all even-weight patterns. Two-dimensional parity can detect and locate many single-bit errors. Example. Data 1011001 has four ones, so even-parity bit is 0 and odd-parity bit is 1. Exam point. Parity is a weak error detector for bursts or even-count bit flips.

Internet checksum concept

Definition. A one’s-complement checksum adds fixed-width words using end-around carry, then complements the sum. The receiver adds all words including the checksum; a valid result is all ones in the one’s-complement representation, subject to the protocol’s exact convention. It detects many errors but is not a polynomial code. Example. For 4-bit words 0101 and 1010, their sum is 1111; complement is 0000. Exam point. Fold carry back into the low-order end before complementing.

CRC polynomial representation

Definition. A cyclic redundancy check treats a bit string as a polynomial over GF(2), where addition and subtraction are XOR. For generator G(x) of degree r, append r zero bits to data, divide by G using XOR long division, and append the r-bit remainder. A received codeword is valid when its remainder is zero under the same generator. Example. Generator 1011 represents $x^3+x+1$ and produces a 3-bit remainder. Exam point. The generator’s degree, not its bit length, determines the CRC remainder width.

CRC worked division

Definition. CRC division uses XOR instead of ordinary subtraction and never carries or borrows. At each step align the generator’s leading 1 with the current leading 1; XOR it, then bring down the next dividend bit. The last r bits are the remainder. Example. Data 1101 with generator 1011. Exam point. Append three zeroes before dividing because the generator degree is three.

Step-by-step:

1. Data is 1101. Append 000: dividend 1101000.
2. Align 1011 under the first four bits: 1101 XOR 1011 = 0110; retain remainder stream 0110 and bring down next bit to form 1100.
3. 1100 XOR 1011 = 0111; bring down next bit to form 1110.
4. 1110 XOR 1011 = 0101; bring down last bit to form 1010.
5. 1010 XOR 1011 = 0001. The final 3-bit remainder is 001.
6. Transmitted codeword is 1101 001.

Check: divide 1101001 by 1011; the remainder is 000. CRC calculation should be checked by re-dividing the codeword.

CRC error-detection properties

Definition. A generator with a nonzero constant term detects every single-bit error and every burst error of length at most r, where r is the generator degree. It detects all odd-numbered bit errors if $(x+1)$ is a factor. Some longer bursts can be undetected when their error polynomial is divisible by G(x). Example. A degree-4 generator detects every burst of length at most 4 bits. Exam point. State the exact generator condition and burst bound; avoid saying CRC catches all errors.

Stop-and-wait protocol

Definition. Stop-and-wait sends one frame and waits for its acknowledgment before sending the next. Sequence numbers distinguish a retransmission from a new frame. With negligible ACK transmission and no errors, utilization is approximately $T_{frame}/(RTT+T_{frame})$ for a single link and a transmission time measured at the sender. Example. If frame transmission is 1 ms and round-trip propagation/ACK time is 19 ms, utilization is about 1/20=5%. Exam point. Include the ACK path and distinguish one-way propagation from RTT.

Sliding-window protocols

Definition. A sliding-window sender may transmit multiple unacknowledged frames, up to its window size W. The window advances when acknowledgments confirm received data. Pipelining can keep a long-delay link busy, but sequence-number space constrains the valid window size. Example. If the bandwidth-delay product equals 8 frames, a sender window of at least 8 can keep the link busy under ideal ACK assumptions. Exam point. Calculate BDP in frames, not bytes, when the window is counted in frames.